Cryptography and Lattices: International Conference, CaLC 2001, Providence, RI, USA, March 29-30, 2001. Revised Papers (Lecture Notes in Computer Science, 2146)

This book constitutes the thoroughly refereed post-proceedings of the International Conference on Cryptography and Lattices, CaLC 2001, held in Providence, RI, USA in March 2001. The 14 revised full papers presented together with an overview paper were carefully reviewed and selected for inclusion in the book. All current aspects of lattices and lattice reduction in cryptography, both for cryptographic construction and cryptographic analysis, are addressed. Thesearetheproceedingsofcalc2001,the?rstconferencedevotedtocr- Tographyandlattices. Wehavelongbelievedthattheimportanceoflattices Andlatticereductionincryptography,bothforcryptographicconstructionand Cryptographicanalysis,meritsagatheringdevotedtothistopic. Theenthusiastic Responsethatwereceivedfromtheprogramcommittee,theinvitedspeakers,the Manypeoplewhosubmittedpapers,andthe90registeredparticipantsamply Con?rmedthewidespreadinterestinlatticesandtheircryptographicappli- Tions. Wethankeveryonewhoseinvolvementmadecalcsuchasuccessfulevent; Inparticularwethanknataliejohnson,larrylarrivee,doreenpappas,andthe Brownuniversitymathematicsdepartmentfortheirassistanceandsupport. March2001 Je?reyho?stein,jillpipher,josephsilverman Vi Preface Organization Calc2001wasorganizedbythedepartmentofmathematicsatbrownuniv- Sity. Theprogramchairsexpresstheirthankstotheprogramcommiteeandthe Additionalexternalrefereesfortheirhelpinselectingthepapersforcalc2001.^ Theprogramchairswouldalsoliketothankntrucryptosystemsforproviding ?nancialsupportfortheconference. Program Commitee Doncoppersmith Ibmresearch Je?reyho?stein(co-chair), Brownuniversityandntrucryptosystems Arjenlenstra Citibank,usa Phongnguyen Ens Andrewodlyzko At&tlabsresearch Josephh. Silverman(co-chair), Brownuniversityandntrucryptosystems External Referees Aliakhavi,glenndurfee,nickhowgrave-graham,danielemicciancio Sponsoring Institutions Ntrucryptosystems,inc.^ ,burlington,ma Table Of Contents An Overveiw Of The Sieve Algorithm Forthe Shortest Lattice Vector Problem 1 Miklos Ajtai, Ravi Kumar,^ And Dandapani Sivakumar Low Secret Exponent Rsa Revisited ::::::::::::::::::::::::::::::::: 4 Johannes Bl ̈ Omer And Alexander May Finding Small Solutions To Small Degree Polynomials::::::::::::::::::: 20 Don Coppersmith Fast Reduction Of Ternary Quadratic Forms::::::::::::::::::::::::::: 32 Friedrich Eisenbrand And Gunt ̈ Er Rote Factoring Polynomialsand 0-1 Vectors:::::::::::::::::::::::::::::::: 45 Mark Van Hoeij Approximate Integer Common Divisors::::::::::::::::::::::::::::::: 51 Nick Howgrave-graham Segment Lll-reduction Of Lattice Bases ::::::::::::::::::::::::::::: 67 Henrik Koy And Claus Peter Schnorr Segment Lll-reduction With Floating Point Orthogonalization:::::::::: 81 Henrik Koy And Claus Peter Schnorr Theinsecurity Ofnyberg-rueppel Andother Dsa-likesignatureschemes With Partially Known Nonces:::::::::::::::::::::::::::::::::::::::: 97 Edwin El Mahassni, Phong Q. Nguyen, And Igor E.^ Shparlinski Dimension Reduction Methods For Convolution Modular Lattices :::::::: 110 Alexander May And Joseph H. Silverman Improving Lattice Based Cryptosystems Using The Hermite Normal Form : 126 Daniele Micciancio The Two Faces Of Lattices In Cryptology:::::::::::::::::::::::::::::: 146 Phong Q. An Overview Of The Sieve Algorithm For The Shortest Lattice Vector Problem / Miklos Ajtai, Ravi Kumar And Dandapani Sivakumar -- Low Secret Exponent Rsa Revisited / Johannes Blomer And Alexander May -- Finding Small Solutions To Small Degree Polynomials / Don Coppersmith -- Fast Reduction Of Ternary Quadratic Forms / Friedrich Eisenbrand And Gunter Rote -- Factoring Polynomials And 0-1 Vectors / Mark Van Hoeij -- Approximate Integer Common Divisors / Nick Howgrave-graham -- Segment Lll-reduction Of Lattice Bases / Henrik Koy And Claus Peter Schnorr -- Segment Lll-reduction With Floating Point Orthogonalization / Henrik Koy And Claus Peter Schnorr. Joseph H. Silverman (ed.). Includes Bibliographical References And Index. An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem....Pages 1-3 Low Secret Exponent RSA Revisited....Pages 4-19 Finding Small Solutions to Small Degree Polynomials....Pages 20-31 Fast Reduction of Ternary Quadratic Forms....Pages 32-44 Factoring Polynomials and 0—1 Vectors....Pages 45-50 Approximate Integer Common Divisors....Pages 51-66 Segment LLL-Reduction of Lattice Bases....Pages 67-80 Segment LLL-Reduction with Floating Point Orthogonalization....Pages 81-96 The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces....Pages 97-109 Dimension Reduction Methods for Convolution Modular Lattices....Pages 110-125 Improving Lattice Based Cryptosystems Using the Hermite Normal Form....Pages 126-145 The Two Faces of Lattices in Cryptology....Pages 146-180 A 3-Dimensional Lattice Reduction Algorithm....Pages 181-193 The Shortest Vector Problem in Lattices with Many Cycles....Pages 194-205 Multisequence Synthesis over an Integral Domain....Pages 206-217