On the hardness of the NTRU problem
PELLET-MARY, Alice
Centre National de la Recherche Scientifique [CNRS]
Lithe and fast algorithmic number theory [LFANT]
Centre National de la Recherche Scientifique [CNRS]
Lithe and fast algorithmic number theory [LFANT]
PELLET-MARY, Alice
Centre National de la Recherche Scientifique [CNRS]
Lithe and fast algorithmic number theory [LFANT]
< Leer menos
Centre National de la Recherche Scientifique [CNRS]
Lithe and fast algorithmic number theory [LFANT]
Idioma
en
Communication dans un congrès
Este ítem está publicado en
Asiacrypt 2021 - 27th Annual International Conference on the Theory and Applications of Cryptology and Information Security, 2021-12-05, Singapore. 2021-12-01
Resumen en inglés
The 25 year-old NTRU problem is an important computational assumption in public-key cryptography. However, from a reduction perspective, its relative hardness compared to other problems on Euclidean lattices is not ...Leer más >
The 25 year-old NTRU problem is an important computational assumption in public-key cryptography. However, from a reduction perspective, its relative hardness compared to other problems on Euclidean lattices is not well-understood. Its decision version reduces to the search Ring-LWE problem, but this only provides a hardness upper bound.We provide two answers to the long-standing open problem of providing reduction-based evidence of the hardness of the NTRU problem. First, we reduce the worst-case approximate Shortest Vector Problem over ideal lattices to an average-case search variant of the NTRU problem. Second, we reduce another average-case search variant of the NTRU problem to the decision NTRU problem.< Leer menos
Proyecto europeo
PRivacy preserving pOst-quantuM systEms from advanced crypTograpHic mEchanisms Using latticeS
Orígen
Importado de HalCentros de investigación