Towards efficient lattice-based cryptography [Elektronische Ressource] / von Richard Lindner

Richard Lindner

Description

Towards E cient Lattice-BasedCryptographyVom Fachbereich Informatik derTechnischen Universit at Darmstadt genehmigteDissertationzur Erlangung des GradesDoctor rerum naturalium (Dr. rer. nat.)vonDipl.-Math. Richard Lindnergeboren in Dresden.Referenten: Prof. Dr. Johannes BuchmannProf. Dr. Christopher PeikertTag der Einreichung: 8. November 2010Tag der mundlic hen Prufung: 20. Dezember 2010Hochschulkennzi er: D 17Darmstadt 2011Wissenschaftlicher WerdegangSeptember 2006 { heuteWissenschaftlicher Mitarbeiter und Promotionsstudent in der Arbeitsgruppe vonProf. Johannes Buchmann, Fachgebiet Informatik, an der Technischen UniversitatDarmstadtOktober 2001 { July 2006Studium von Mathematics with Computer Science\ an der Technischen Universitat"DarmstadtSeptember 2003 { Juni 2004Auslandsstudium in England an der University of BirminghamiiiList of Publications[BDL08] J. Buchmann, M. D oring, and R. Lindner. E ciency improvement for NTRU.In A. Alkassar and J. H. Siekmann, editors, Sicherheit 2008: Sicherheit,Schutz und Zuverlassigkeit. Konferenzband der 4. Jahrestagung des Fachbere-ichs Sicherheit der Gesellschaft fur Informatik e.V. (GI), 2.-4. April 2008 imSaarbrucker Schloss, volume 128 of LNI, pages 163{178. GI, 2008. Cited onpage 23.[BL09a] J. Buchmann and R. Lindner. Density of ideal lattices. In WEWoRC, toappear. Springer, 2009. Cited on page 11.[BL09b] J. Buchmann and R. Lindner. Secure parameters for SWIFFT. In B. Royand S.

Sujets

• Informatik
• Mathematics

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2011
• Nombre de lectures: 31

Extrait

Towards

Efficient Lattice-Based Cryptography

Vom Fachbereich Informatik der TechnischenUniversit¨atDarmstadtgenehmigte

Dissertation

zur Erlangung des Grades Doctor rerum naturalium (Dr. rer. von

Dipl.-Math.

Referenten:

nat.)

Richard Lindner

geboren in Dresden.

Tag der Einreichung: Tagdermu¨ndlichenPru¨fung: Hochschulkennziffer:

Prof. Dr. Johannes Buchmann Prof. Dr. Christopher Peikert 8. November 2010 20. Dezember 2010 D 17

Darmstadt 2011

September 2006 – heute

Wissenschaftlicher

Werdegang

Wissenschaftlicher Mitarbeiter und Promotionsstudent in der Arbeitsgruppe von Prof.JohannesBuchmann,FachgebietInformatik,anderTechnischenUniversita ¨ t Darmstadt

Oktober 2001 – July 2006

Studiumvon ” MathematicswithComputerScience“anderTechnischenUniversita ¨ t Darmstadt

September 2003 – Juni 2004

Auslandsstudium in England an der University of Birmingham

iii

[BDL08]

[BL09a]

[BL09b]

[BLR08]

[BLRS09]

[BLS09]

[CLRS10a]

[CLRS10b]

List

of

Publications

J.Buchmann,M.Do¨ring,andR.Lindner.EfficiencyimprovementforNTRU. In A. Alkassar and J. H. Siekmann, editors,Sicherheit 2008: Sicherheit, SchutzundZuverl¨assigkeit.Konferenzbandder4.JahrestagungdesFachbere- ichsSicherheitderGesellschaftfu¨rInformatike.V.(GI),2.-4.April2008im Saarbr¨uckerSchloss, volume 128 ofLNI on Cited, pages 163–178. GI, 2008. page 23.

J. Buchmann and R. Lindner. Density of ideal lattices. InWEWoRC, to appear on page 11. Cited. Springer, 2009.

J. Buchmann and R. Lindner. Secure parameters for SWIFFT. In B. Roy and S. Nicolas, editors,Progress in Cryptology - INDOCRYPT 2009, 10th International Conference on Cryptology in India, New Delhi, India, December 13-16, 2009. Proceedings, volume 5922 ofLNCS, pages 1–17. Springer, 2009. Cited on page 17.

J.Buchmann,R.Lindner,andM.Ru¨ckert.Explicithardinstancesofthe shortest vector problem. In J. Buchmann and J. Ding, editors,Post-Quantum Cryptography, Second International Workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17-19, 2008, Proceedings, volume 5299 ofLNCS, pages 79–94. Springer, 2008. Cited on page 8.

J.Buchmann,R.Lindner,M.Ru¨ckert,andM.Schneider.Post-quantum cryptography: Lattice signatures.Computing on Cited, 85:105–125, 2009. page 5.

J. Buchmann, R. Lindner, and M. Schneider. Probabilistic analysis of LLL reduced bases. InWEWoRC, to appear. Springer, 2009.

P.-L.Cayrel,R.Lindner,M.R¨uckert,andR.Silva.Improvedzero-knowledge identification with lattices. In S.-H. Heng and K. Kurosawa, editors,Provable Security, 4th International Conference, ProvSec 2010, Malacca, Malaysia, Oc- tober 2010. Proceedings, volume 6402 ofLNCS, pages 1–17. Springer, 2010. Cited on page 31.

P.-L.Cayrel,R.Lindner,M.Ru¨ckert,andR.Silva.Alattice-basedthreshold ring signature scheme. In M. Abdalla and P. S. L. M. Barreto, editors,LATIN- CRYPT, volume 6212 ofLecture Notes in Computer Science, pages 255–272. Springer, 2010. Cited on page 39.

v

List of Publications

[DL07]

[LP11]

vi

J. Ding and R. Lindner. Identifying ideal lattices. Technical Report 2007/322, Cryptology ePrint Archive, 2007.aircni.te/rppt/:ht/rg.o. Cited on page 12.

R. Lindner and C. Peikert. Better key sizes (and attacks) for LWE-based encryption. InCT-RSA 2011, to appear. Springer, 2011. on page 45. Cited

Acknowledgments

I would like to thank many people for their help, support, and encouragement on my long journey of writing this thesis. First and foremost, I thank Johannes Buchmann for his ideas and supervision, and for giving me the opportunity to travel the world to present my results. I am also extraordinary thankful to Chris Peikert for wanting to work with me, which was so much fun and productive, and for agreeing to be my co-referee. For interesting and beneficial collaborations, I thank Paulo Barreto, Pierre-Louis Cayrel, JintaiDing,MartinDo¨ring,RafaelMisoczki,MarkusR¨uckert,MichaelSchneider,and RosembergAndre´daSilva. For supporting my research with remarks, questions, and answers, I thank all of my col- leagues, as well as Indranil Banerjee, Marc Fischlin, Vadim Lyubashevsky, Oded Regev, and Alon Rosen. For advice in the fascinating field of number theory, I thank Jan Hendrik Bruinier, Michael Pohst, and Jonathan Sands. For advice in the field of lattice reduc- tionthatisessentialformywork,IthankBartolFilipovi´c,HenrikKoy,andChristoph Ludwig.Furthermore,IthankPaulBaecher,ErikDahmen,RoswithaJa¨ger-Beck,Lucie Langer,AnjaLehmann,AxelSchmidt,MichaelSchneider,andMaritaSkrobic´forcreating a pleasant office atmosphere. Next, I thank my parents Bernd and Eva Lindner for their mixture of unfaltering en- couragement and nagging questions, which instilled in me the drive necessary to finish this undertaking. I thank all of my friends both old and new for the net of support they wove for me. My special thanks go to Pierre-Louis Cayrel for our restaurant tours and the poolholiday,BenCohenforbeingmyeditorinchief,Rafa¨elDahmenfortheeverfruitful tomato wheat sessions, Frank Karinda for showing that it can be done, Anja Lehmann for engaging discussions in the park, and Michael Schneider for being funny sometimes.

Richard Lindner Darmstadt, 2010

vii