Philippe Gaborit (Ed.) 2 Post-Quantum 3 9 7 S Cryptography C N L 5th International Workshop, PQCrypto 2013 Limoges, France, June 2013 Proceedings 123 Lecture Notes in Computer Science 7932 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany MadhuSudan MicrosoftResearch,Cambridge,MA,USA DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum MaxPlanckInstituteforInformatics,Saarbruecken,Germany Philippe Gaborit (Ed.) Post-Quantum Cryptography 5th International Workshop, PQCrypto 2013 Limoges, France, June 4-7, 2013 Proceedings 1 3 VolumeEditor PhilippeGaborit UniversityofLimoges XLIMLaboratory,DepartmentDMI 123,AvenueAlbertThomas,87000Limoges,France E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-642-38615-2 e-ISBN978-3-642-38616-9 DOI10.1007/978-3-642-38616-9 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2013938951 CRSubjectClassification(1998):E.3,K.6.5,D.4.6,F.2,G.2.1,E.4,C.2.0 LNCSSublibrary:SL4–SecurityandCryptology ©Springer-VerlagBerlinHeidelberg2013 Thisworkissubjecttocopyright.Allrightsarereserved,whetherthewholeorpartofthematerialis concerned,specificallytherightsoftranslation,reprinting,re-useofillustrations,recitation,broadcasting, reproductiononmicrofilmsorinanyotherway,andstorageindatabanks.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheGermanCopyrightLawofSeptember9,1965, initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Violationsareliable toprosecutionundertheGermanCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,etc.inthispublicationdoesnotimply, evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevantprotectivelaws andregulationsandthereforefreeforgeneraluse. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface PQCrypto 2013, the 5th International Workshop on Post-Quantum Cryptogra- phy was held in Limoges, France, during June 4–7, 2013. The workshopattracted24 submissions,of which the ProgramCommmittee selected 17 for publication in the workshop proceedings. The accepted papers dealt with the topics of code-based cryptography, lattice-based cryptography, multivariate-cryptography,and cryptanalysisor implementations. The Program Committee included 23 subject-matter experts from 11 countries. The workshop included two invited talks by Fr´ed´eric Magniez and Michael Naehrig and a recent results session chaired by Carlos Aguilar Melchor. I would like to thank all the ProgramCommittee members, who made great effortcontributingtheirtime,knowledge,andexpertise.Ialsothanktheexternal reviewers who assisted in the process. I wish to thank the generous sponsors of PQCRypto 2013: the Region Limousin, the Limoges University, the Mathematics and Computer Science De- partementoftheXLIMlaboratoryandtheXLIMlaboratory.Specialthanksare also due to Thierry Berger for his organizationaleffort as General Chair and to Odile Duval and Jean-Christophe Deneuville for their everyday help. April 2013 Philippe Gaborit Organization General Chair Thierry Berger Limoges University, France Program Chair Philippe Gaborit Limoges University, France Steering Committee Daniel J. Bernstein University of Illinois at Chicago, USA Johannes Buchmann Technische Universit¨at Darmstadt, Germany Claude Cr´epeau McGill University, Canada Jintai Ding University of Cincinnati, USA Philippe Gaborit University of Limoges, France Tanja Lange Technische Universiteit Eindhoven, The Netherlands Daniele Micciancio University of California, San Diego, USA Werner Schindler BSI, Germany Nicolas Sendrier INRIA, France Shigeo Tsujii Chuo University, Japan Bo-Yin Yang Academia Sinica, Taiwan Program Committee Carlos Aguilar Melchor University of Limoges, France Paulo Barreto University of Sao Paulo, Brazil Daniel J. Bernstein University of Illinois at Chicago, USA Xavier Boyen QUT, Australia Johannes Buchmann TU Darmstadt, Germany Stanislav Bulygin TU Darmstadt, Germany Claude Cr´epeau McGill University, Canada Jintai Ding University of Cincinnati, USA Pierre-AlainFouque University of Rennes I, France Tim Guneysu Rhur University Bochum, Germany Sean Hallgren University of Pennsylvania,USA Kazukuni Kobara AIST, Japan Tanja Lange TU Eindhoven, The Netherlands Gregor Leander Danmarks TU, Denmark VIII Organization Michele Mosca University of Waterloo, Canada Bart Preneel KU Leuven, Belgium Michael Schneider TU Darmstadt, Germany Nicolas Sendrier INRIA, France Damien Stehl´e ENS Lyon, France Jean-PierreTillich INRIA, France Bo-Yin Yang Academia Sinica, Taiwan External Reviewers Francois Arnault Ryo Nojima (cid:2) Rafael Baiao Ayoub Otmani Daniel Cabarcas Christiane Peters Jie Chen Albrecht Petzold Ming-Shing Chen Thomas P¨oppelmann Adama Diene Koichi Sakumoto Vivien Dubois John Schanck Nicolas Gama Dimitris E. Simos Val´erie Gauthier Uman˜a Yasuda Takanori Stefan Heyse Chendong Tao Jeffrey Hoffstein Enrico Thomae (special thanks) Lei Hu Joop van de Pol Andreas Hu¨lsing Ingo von Maurich Rafael Misoczki Patrick Weiden Kirill Morozov Christopher Wolf Khoa Nguyen (special thanks) C.-H. Yu Table of Contents Using LDGM Codes and Sparse Syndromes to Achieve Digital Signatures ...................................................... 1 Marco Baldi, Marco Bianchi, Franco Chiaraluce, Joachim Rosenthal, and Davide Schipani Quantum Algorithms for the Subset-Sum Problem ................... 16 Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer Improved Lattice-Based Threshold Ring Signature Scheme ............ 34 Slim Bettaieb and Julien Schrek Degree of Regularity for HFEv and HFEv- .......................... 52 Jintai Ding and Bo-Yin Yang Software Speed Records for Lattice-Based Signatures ................. 67 Tim Gu¨neysu, Tobias Oder, Thomas P¨oppelmann, and Peter Schwabe Solving the Shortest Vector Problemin Lattices Faster Using Quantum Search.......................................................... 83 Thijs Laarhoven, Michele Mosca, and Joop van de Pol An Efficient Attack of a McEliece Cryptosystem Variant Based on ConvolutionalCodes ............................................. 102 Gr´egory Landais and Jean-Pierre Tillich Extended Algorithm for Solving Underdefined Multivariate Quadratic Equations....................................................... 118 Hiroyuki Miura, Yasufumi Hashimoto, and Tsuyoshi Takagi Quantum Key Distribution in the Classical Authenticated Key Exchange Framework............................................. 136 Michele Mosca, Douglas Stebila, and Berkant Ustao˘glu Cryptanalysis of Hash-Based Tamed Transformation and Minus Signature Scheme ................................................ 155 Xuyun Nie, Zhaohu Xu, and Johannes Buchmann AClassificationofDifferentialInvariantsforMultivariatePost-quantum Cryptosystems................................................... 165 Ray Perlner and Daniel Smith-Tone X Table of Contents Secure and Anonymous Hybrid Encryption from Coding Theory ....... 174 Edoardo Persichetti Fast Verification for Improved Versions of the UOV and Rainbow Signature Schemes ............................................... 188 Albrecht Petzoldt, Stanislav Bulygin, and Johannes Buchmann The Hardness of Code Equivalence over Fq and Its Application to Code-Based Cryptography ........................................ 203 Nicolas Sendrier and Dimitris E. Simos Timing Attacks against the Syndrome Inversion in Code-Based Cryptosystems................................................... 217 Falko Strenzke Simple Matrix Scheme for Encryption .............................. 231 Chengdong Tao, Adama Diene, Shaohua Tang, and Jintai Ding Multivariate Signature Scheme Using Quadratic Forms ............... 243 Takanori Yasuda, Tsuyoshi Takagi, and Kouichi Sakurai Author Index.................................................. 259 Using LDGM Codes and Sparse Syndromes (cid:2) to Achieve Digital Signatures Marco Baldi1, Marco Bianchi1, Franco Chiaraluce1, Joachim Rosenthal2, and Davide Schipani3 1 Universit`aPolitecnica delle Marche, Ancona, Italy {m.baldi,m.bianchi,f.chiaraluce}@univpm.it 2 Universityof Zurich, Zurich,Switzerland [email protected] 3 Nottingham Trent University,Nottingham, UK [email protected] Abstract. In this paper, we address the problem of achieving efficient code-based digital signatures with small public keys. The solution we propose exploits sparse syndromes and randomly designed low-density generatormatrixcodes.Basedonourevaluations,theproposedschemeis abletooutperformexistingsolutions,permittingtoachieveconsiderable security levels with verysmall public keys. Keywords: Code-based digital signatures, LDGM codes, sparse syn- dromes. 1 Introduction The problem of replacing current cryptographic primitives which will be sub- ject to quantum computer attacks with alternative post-quantum solutions is fostering research on code-based systems, which are among the most promising options for this replacement. Concerningasymmetriccryptography,theMcEliececryptosystem[21]andits recentimprovements[9] alreadyrepresentefficientsolutions to replacequantum vulnerablesystems,likeRSA.ThemaindrawbackoftheMcEliececryptosystem compared to RSA is the large size of its public keys. However, great steps have been done towards the reduction of the McEliece public key size. A possible solution consists in replacing the Goppa codes used in the original system with other families of codes. Among these, low-density parity-check (LDPC) codes have been considered since several years [1–3, 24], and most recent proposals based on them have been able to achieve significant reductions in the key size [6, 7, 23]. For what concerns digital signatures, the widespread DSA and RSA signa- ture schemes will be endangered by quantum computers as well, and only a few (cid:2) This work was supported in part by the MIUR project “ESCAPADE” (Grant RBFR105NLC) under the “FIRB - Futuro in Ricerca 2010” funding program, and in part by theSwiss National Science Foundation undergrant No. 132256. P.Gaborit(Ed.):PQCrypto2013,LNCS7932,pp.1–15,2013. (cid:2)c Springer-VerlagBerlinHeidelberg2013