Making NTRU as Secure as Worst-Case Problems over Ideal Lattices
Identifieur interne : 002973 ( Istex/Curation ); précédent : 002972; suivant : 002974Making NTRU as Secure as Worst-Case Problems over Ideal Lattices
Auteurs : Damien Stehlé [France] ; Ron Steinfeld [Australie]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.
Descripteurs français
- Wicri :
- topic : Cryptographie.
English descriptors
- KwdEn :
- Algorithm, Chinese remainder theorem, Cryptographic, Cryptography, Cyclic lattices, Cyclotomic, Decryption, Decryption algorithm, Discrete gaussian, Discrete gaussian distribution, Discrete gaussians, Dz2n, Encryption, Encryption scheme, Encryption schemes, Errors problem, Factors modulo, Future work, Gaussian, Generation algorithm, Hardness, Heidelberg, Ideal lattice, Ideal lattices, Invertible, Lattice, Lattice problems, Linear factors modulo, Lncs, Lyubashevsky, Matrix, Micciancio, Modulo, Ntru, Ntruencrypt, Outputs samples, Peikert, Quantum hardness, Regev, Regularity, Regularity result, Resp, Rntru, Springer, Standard deviation, Standard model, Standard problems, Statistical distance, Stehl, Steinfeld, Success probability, Whole ring.
- Teeft :
- Algorithm, Chinese remainder theorem, Cryptographic, Cryptography, Cyclic lattices, Cyclotomic, Decryption, Decryption algorithm, Discrete gaussian, Discrete gaussian distribution, Discrete gaussians, Dz2n, Encryption, Encryption scheme, Encryption schemes, Errors problem, Factors modulo, Future work, Gaussian, Generation algorithm, Hardness, Heidelberg, Ideal lattice, Ideal lattices, Invertible, Lattice, Lattice problems, Linear factors modulo, Lncs, Lyubashevsky, Matrix, Micciancio, Modulo, Ntru, Ntruencrypt, Outputs samples, Peikert, Quantum hardness, Regev, Regularity, Regularity result, Resp, Rntru, Springer, Standard deviation, Standard model, Standard problems, Statistical distance, Stehl, Steinfeld, Success probability, Whole ring.
Abstract
Abstract: NTRUEncrypt, proposed in 1996 by Hoffstein, Pipher and Silverman, is the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum computers could make it a desirable alternative to factorisation and discrete-log based encryption schemes. However, since its introduction, doubts have regularly arisen on its security. In the present work, we show how to modify NTRUEncrypt to make it provably secure in the standard model, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. Our main contribution is to show that if the secret key polynomials are selected by rejection from discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its domain. The security then follows from the already proven hardness of the the R-LWE problem.
Url:
DOI: 10.1007/978-3-642-20465-4_4
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :002973
Links to Exploration step
ISTEX:DEFBDD833F40D0195BBA2AE1DFC9280EA211AB88Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Making NTRU as Secure as Worst-Case Problems over Ideal Lattices</title>
<author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
<affiliation wicri:level="1"><mods:affiliation>CNRS, Laboratoire LIP (U. Lyon, CNRS, ENS Lyon, INRIA, UCBL), 46 Allée d’Italie, 69364, Lyon Cedex 07, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>CNRS, Laboratoire LIP (U. Lyon, CNRS, ENS Lyon, INRIA, UCBL), 46 Allée d’Italie, 69364, Lyon Cedex 07</wicri:regionArea>
</affiliation>
<affiliation><mods:affiliation>E-mail: damien.stehle@gmail.com</mods:affiliation>
<wicri:noCountry code="no comma">E-mail: damien.stehle@gmail.com</wicri:noCountry>
</affiliation>
</author>
<author><name sortKey="Steinfeld, Ron" sort="Steinfeld, Ron" uniqKey="Steinfeld R" first="Ron" last="Steinfeld">Ron Steinfeld</name>
<affiliation wicri:level="1"><mods:affiliation>Centre for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, 2109, NSW, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>Centre for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, 2109, NSW</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: ron.steinfeld@mq.edu.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:DEFBDD833F40D0195BBA2AE1DFC9280EA211AB88</idno>
<date when="2011" year="2011">2011</date>
<idno type="doi">10.1007/978-3-642-20465-4_4</idno>
<idno type="url">https://api.istex.fr/document/DEFBDD833F40D0195BBA2AE1DFC9280EA211AB88/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002973</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002973</idno>
<idno type="wicri:Area/Istex/Curation">002973</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Making NTRU as Secure as Worst-Case Problems over Ideal Lattices</title>
<author><name sortKey="Stehle, Damien" sort="Stehle, Damien" uniqKey="Stehle D" first="Damien" last="Stehlé">Damien Stehlé</name>
<affiliation wicri:level="1"><mods:affiliation>CNRS, Laboratoire LIP (U. Lyon, CNRS, ENS Lyon, INRIA, UCBL), 46 Allée d’Italie, 69364, Lyon Cedex 07, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>CNRS, Laboratoire LIP (U. Lyon, CNRS, ENS Lyon, INRIA, UCBL), 46 Allée d’Italie, 69364, Lyon Cedex 07</wicri:regionArea>
</affiliation>
<affiliation><mods:affiliation>E-mail: damien.stehle@gmail.com</mods:affiliation>
</affiliation>
</author>
<author><name sortKey="Steinfeld, Ron" sort="Steinfeld, Ron" uniqKey="Steinfeld R" first="Ron" last="Steinfeld">Ron Steinfeld</name>
<affiliation wicri:level="1"><mods:affiliation>Centre for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, 2109, NSW, Australia</mods:affiliation>
<country xml:lang="fr">Australie</country>
<wicri:regionArea>Centre for Advanced Computing - Algorithms and Cryptography, Department of Computing, Macquarie University, 2109, NSW</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: ron.steinfeld@mq.edu.au</mods:affiliation>
<country wicri:rule="url">Australie</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2011</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Chinese remainder theorem</term>
<term>Cryptographic</term>
<term>Cryptography</term>
<term>Cyclic lattices</term>
<term>Cyclotomic</term>
<term>Decryption</term>
<term>Decryption algorithm</term>
<term>Discrete gaussian</term>
<term>Discrete gaussian distribution</term>
<term>Discrete gaussians</term>
<term>Dz2n</term>
<term>Encryption</term>
<term>Encryption scheme</term>
<term>Encryption schemes</term>
<term>Errors problem</term>
<term>Factors modulo</term>
<term>Future work</term>
<term>Gaussian</term>
<term>Generation algorithm</term>
<term>Hardness</term>
<term>Heidelberg</term>
<term>Ideal lattice</term>
<term>Ideal lattices</term>
<term>Invertible</term>
<term>Lattice</term>
<term>Lattice problems</term>
<term>Linear factors modulo</term>
<term>Lncs</term>
<term>Lyubashevsky</term>
<term>Matrix</term>
<term>Micciancio</term>
<term>Modulo</term>
<term>Ntru</term>
<term>Ntruencrypt</term>
<term>Outputs samples</term>
<term>Peikert</term>
<term>Quantum hardness</term>
<term>Regev</term>
<term>Regularity</term>
<term>Regularity result</term>
<term>Resp</term>
<term>Rntru</term>
<term>Springer</term>
<term>Standard deviation</term>
<term>Standard model</term>
<term>Standard problems</term>
<term>Statistical distance</term>
<term>Stehl</term>
<term>Steinfeld</term>
<term>Success probability</term>
<term>Whole ring</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term>
<term>Chinese remainder theorem</term>
<term>Cryptographic</term>
<term>Cryptography</term>
<term>Cyclic lattices</term>
<term>Cyclotomic</term>
<term>Decryption</term>
<term>Decryption algorithm</term>
<term>Discrete gaussian</term>
<term>Discrete gaussian distribution</term>
<term>Discrete gaussians</term>
<term>Dz2n</term>
<term>Encryption</term>
<term>Encryption scheme</term>
<term>Encryption schemes</term>
<term>Errors problem</term>
<term>Factors modulo</term>
<term>Future work</term>
<term>Gaussian</term>
<term>Generation algorithm</term>
<term>Hardness</term>
<term>Heidelberg</term>
<term>Ideal lattice</term>
<term>Ideal lattices</term>
<term>Invertible</term>
<term>Lattice</term>
<term>Lattice problems</term>
<term>Linear factors modulo</term>
<term>Lncs</term>
<term>Lyubashevsky</term>
<term>Matrix</term>
<term>Micciancio</term>
<term>Modulo</term>
<term>Ntru</term>
<term>Ntruencrypt</term>
<term>Outputs samples</term>
<term>Peikert</term>
<term>Quantum hardness</term>
<term>Regev</term>
<term>Regularity</term>
<term>Regularity result</term>
<term>Resp</term>
<term>Rntru</term>
<term>Springer</term>
<term>Standard deviation</term>
<term>Standard model</term>
<term>Standard problems</term>
<term>Statistical distance</term>
<term>Stehl</term>
<term>Steinfeld</term>
<term>Success probability</term>
<term>Whole ring</term>
</keywords>
<keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Cryptographie</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: NTRUEncrypt, proposed in 1996 by Hoffstein, Pipher and Silverman, is the fastest known lattice-based encryption scheme. Its moderate key-sizes, excellent asymptotic performance and conjectured resistance to quantum computers could make it a desirable alternative to factorisation and discrete-log based encryption schemes. However, since its introduction, doubts have regularly arisen on its security. In the present work, we show how to modify NTRUEncrypt to make it provably secure in the standard model, under the assumed quantum hardness of standard worst-case lattice problems, restricted to a family of lattices related to some cyclotomic fields. Our main contribution is to show that if the secret key polynomials are selected by rejection from discrete Gaussians, then the public key, which is their ratio, is statistically indistinguishable from uniform over its domain. The security then follows from the already proven hardness of the the R-LWE problem.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002973 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 002973 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Asie |area= AustralieFrV1 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:DEFBDD833F40D0195BBA2AE1DFC9280EA211AB88 |texte= Making NTRU as Secure as Worst-Case Problems over Ideal Lattices }}
![]() | This area was generated with Dilib version V0.6.33. | ![]() |