06661nam 22007695 450 991014362700332120251116234158.03-540-44670-210.1007/3-540-44670-2(CKB)1000000000211554(SSID)ssj0000322401(PQKBManifestationID)11233025(PQKBTitleCode)TC0000322401(PQKBWorkID)10301294(PQKB)11154685(DE-He213)978-3-540-44670-5(MiAaPQ)EBC3073239(PPN)155205927(BIP)7336020(EXLCZ)99100000000021155420121227d2001 u| 0engurnn|008mamaatxtccrCryptography and Lattices International Conference, CaLC 2001, Providence, RI, USA, March 29-30, 2001. Revised Papers /edited by Joseph H. Silverman1st ed. 2001.Berlin, Heidelberg :Springer Berlin Heidelberg :Imprint: Springer,2001.1 online resource (VIII, 224 p.) Lecture Notes in Computer Science,0302-9743 ;2146Bibliographic Level Mode of Issuance: Monograph3-540-42488-1 Includes bibliographical references at the end of each chapters and index.An Overview of the Sieve Algorithm for the Shortest Lattice Vector Problem -- Low Secret Exponent RSA Revisited -- Finding Small Solutions to Small Degree Polynomials -- Fast Reduction of Ternary Quadratic Forms -- Factoring Polynomials and 0—1 Vectors -- Approximate Integer Common Divisors -- Segment LLL-Reduction of Lattice Bases -- Segment LLL-Reduction with Floating Point Orthogonalization -- The Insecurity of Nyberg-Rueppel and Other DSA-Like Signature Schemes with Partially Known Nonces -- Dimension Reduction Methods for Convolution Modular Lattices -- Improving Lattice Based Cryptosystems Using the Hermite Normal Form -- The Two Faces of Lattices in Cryptology -- A 3-Dimensional Lattice Reduction Algorithm -- The Shortest Vector Problem in Lattices with Many Cycles -- Multisequence Synthesis over an Integral Domain.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.Lecture Notes in Computer Science,0302-9743 ;2146Data encryption (Computer science)ComputersAlgorithmsComputer science—MathematicsCryptologyhttps://scigraph.springernature.com/ontologies/product-market-codes/I28020Computation by Abstract Deviceshttps://scigraph.springernature.com/ontologies/product-market-codes/I16013Algorithm Analysis and Problem Complexityhttps://scigraph.springernature.com/ontologies/product-market-codes/I16021Discrete Mathematics in Computer Sciencehttps://scigraph.springernature.com/ontologies/product-market-codes/I17028Symbolic and Algebraic Manipulationhttps://scigraph.springernature.com/ontologies/product-market-codes/I17052Algorithmshttps://scigraph.springernature.com/ontologies/product-market-codes/M14018Data encryption (Computer science)Computers.Algorithms.Computer science—Mathematics.Cryptology.Computation by Abstract Devices.Algorithm Analysis and Problem Complexity.Discrete Mathematics in Computer Science.Symbolic and Algebraic Manipulation.Algorithms.005.8/2Silverman Joseph Hedthttp://id.loc.gov/vocabulary/relators/edtCaLC 2001MiAaPQMiAaPQMiAaPQBOOK9910143627003321Cryptography and Lattices2018022UNINA