Lecture Notes in Computer Science 7369 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 Ferruh Özbudak Francisco Rodríguez-Henríquez (Eds.) Arithmetic of Finite Fields 4th International Workshop, WAIFI 2012 Bochum, Germany, July 16-19, 2012 Proceedings 1 3 VolumeEditors FerruhÖzbudak MiddleEastTechnicalUniversity InstituteofAppliedMathematics Ankara,Turkey E-mail:[email protected] FranciscoRodríguez-Henríquez CentrodeInvestigaciónydeEstudios AvanzadosdelInstitutoPolitécnicoNacional(CINVESTAV-IPN) DepartamentodeComputación Av.IPNNo.2508,Col.SanPedroZacatenco,Mexico,D.F.07360,Mexico E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-642-31661-6 e-ISBN978-3-642-31662-3 DOI10.1007/978-3-642-31662-3 SpringerHeidelbergDordrechtLondonNewYork LibraryofCongressControlNumber:2012940985 CRSubjectClassification(1998):I.1,G.2,E.3,K.6.5,D.4.6,F.2.1 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©Springer-VerlagBerlinHeidelberg2012 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 These are the proceedings of WAIFI 2012, the 4th International Workshop on the Arithmetic of Finite Fields, held in Bochum, Germany, during July 16–19, 2012. The three previous editions of this workshop were held in Madrid, Spain (WAIFI 2007),Siena, Italy (WAIFI 2008),and Istanbul, Turkey (WAIFI 2010). Since 2008, WAIFI has been held every even year, bringing together mathe- maticians, computer scientists, engineers and physicists who conduct research in different areas of finite field arithmetic. WAIFI 2012 was organized by the Ruhr-Universita¨t Bochum, Germany, in cooperation with the International As- sociationforCryptologicResearch(IACR).TheGeneralChairoftheconference was Christopher Wolf. The program consisted of four invited talks and 13 contributed papers. The invited speakers were Shay Gueron (University of Hafia, Israel), Florian Hess (Universita¨t Oldenburg, Germany), Alexander Pott (Universita¨t Magdeburg, Germany),and Emmanuel Thome (INRIA, France).The papers supporting the four invited talks were also included in the proceedings. The contributed talks were selected from 29 submissions each of which was assigned to at least three committee members. Additionally, the Program Committee had a significant online discussion phase for several days. We are very grateful to the Program Committee members and to the exter- nal reviewers for their dedication and profesionalism. Special thanks go out to Christopher Wolf, the General Chair, for his hard work in leading the overall organizationand dealing with various local arrangements with meticulous care. We wouldalsoliketo thankJean-JacquesQuisquaterandC¸etinKayaKoc¸,who helped us to negotiate the publication of WAIFI 2012 proceedings as a volume of Lecture Notes in Computer Science. We are also very grateful to Jos´e Luis Iman˜a for dilingently maintaining the workshop website. We heartily thank the members of the Steering Committee of the workshop series for their constant support and encouragement. The submission and selection of papers were done using the EasyChair con- ference management system. Hence, thank you EasyChair! Finally, but most importantly,we deeply thank all the authors who submitted their papers to the workshop and the participants all over the world who chose to honor us with their attendance. July 2012 Ferruh O¨zbudak Francisco Rodr´ıguez-Henr´ıquez WAIFI 2012 International Workshop on the Arithmetic of Finite Fields Bochum, Germany July 16–19, 2012 Organized by Ruhr-Universita¨t Bochum In cooperation with The International Association for Cryptologic Research (IACR) Steering Committee Claude Carlet University of Paris 8, France Jean-Pierre Deschamps University Rovira i Virgili, Spain Jos´e Luis Iman˜a Complutense University of Madrid, Spain C¸etin Kaya Koc¸ University of California Santa Barbara, USA Christof Paar Ruhr-Universita¨t Bochum, Germany Jean-Jacques Quisquater Universit´e Catholique de Louvain, Belgium Berk Sunar Worcester Polytechnic Institute, USA Gustavo Sutter Autonomous University of Madrid, Spain General Chair Christopher Wolf Ruhr-Universita¨t Bochum, Germany Program Chairs Ferruh O¨zbudak Middle East Technical University, Turkey Francisco Rodr´ıguez-Henr´ıquez CINVESTAV-IPN, M´exico Local Organizing Committee Marina Efimenko Ruhr-Universita¨t Bochum, Germany Sebastian Uellenbeck Ruhr-Universita¨t Bochum, Germany Christian Walter Ruhr-Universita¨t Bochum, Germany VIII WAIFI 2012 Program Committee Jean-Claude Bajard LIP6 CNRS/Universit´e Pierre et Marie Curie, France Stephane Ballet Institut de Math´ematiques de Luminy, France Jean-Luc Beuchat University of Tsukuba, Japan Luca Breveglieri Politecnico di Milano, Italy Debrup Chakraborty CINVESTAV-IPN, Mexico Ricardo Dahab University of Campinas, Brazil J´er´emie Detrey INRIA, France Haining Fan Tsinghua University, China Olav Geil Aalborg University, Denmark Guang Gong University of Waterloo, Canada Jorge Guajardo Robert Bosch LLC, USA Anwar Hasan University of Waterloo, Canada Tor Helleseth University of Bergen, Norway Jos´e L. Iman˜a Complutense University of Madrid, Spain Koray Karabina University of Waterloo, Canada Alexander Kholosha University of Bergen, Norway Tanja Lange Technical University of Eindhoven, The Netherlands Ivan Landjev Bulgarian Academy of Sciences, Bulgaria Julio Lo´pez University of Campinas, Brazil Edgar Mart´ınez-Moro University of Valladollid, Spain Gary Mullen Pennsylvania State University, USA Harald Niederreiter Austrian Academy of Sciences, Austria Arash Reyhani-Masoleh University of Western Ontario, Canada Erkay Sava¸s Sabanci University, Turkey Peter Schwabe Academia Sinica, Taiwan Igor Semaev University of Bergen, Norway Patrick Sol´e T´el´ecomParisTech,France and AbdelAziz University, Saudi Arabia Arne Winterhof Austrian Academy of Sciences, Austria External Reviewers Diego Aranha St´ephane Louboutin Jean-Philippe Aumasson Cuauhtemoc Mancillas-L´opez Selc¸uk Baktır Marc Mouffron Razvan Barbulescu Mehran Mozaffari-Kermani Daniel Bernstein Christophe Negre Alessandro Barenghi Matthew Parker Qi Chai Gerardo Pelosi Fernando Hernando Christiane Peters Hans Hu¨ttel Thomas Plantard WAIFI 2012 IX Damien Robert Reza Sohizadeh Robert Rolland Zilong Wang Sumanta Sarkar Yang Yang Sponsoring Institutions Ruhr-Universita¨t Bochum, Germany Mercator Foundation, Essen, Germany Table of Contents Invited Talk 1 Generalised Jacobians in Cryptography and Coding Theory ........... 1 Florian Hess Coding Theory and Code-Based Cryptography The Weight Distribution of a Family of Reducible Cyclic Codes........ 16 Gerardo Vega and Carlos A. Va´zquez A New Method for Constructing Small-Bias Spaces from Hermitian Codes .......................................................... 29 Olav Geil, Stefano Martin, and Ryutaroh Matsumoto An Improved Threshold Ring Signature Scheme Based on Error Correcting Codes ................................................ 45 Pierre-Louis Cayrel, Sidi Mohamed El Yousfi Alaoui, Gerhrad Hoffmann, and Pascal V´eron Invited Talk 2 Sequences and Functions Derived from Projective Planes and Their Difference Sets................................................... 64 Alexander Pott, Qi Wang, and Yue Zhou Boolean Functions On Formally Self-dual Boolean Functions in 2, 4 and 6 Variables....... 81 Lin Sok and Patrick Sol´e On the Algebraic Normal Form and Walsh Spectrum of Symmetric Functions over Finite Rings ....................................... 92 Boris Batteux Verification of Restricted EA-Equivalence for Vectorial Boolean Functions ....................................................... 108 Lilya Budaghyan and Oleksandr Kazymyrov XII Table of Contents Invited Talk 3 Software Implementation of Modular Exponentiation, Using Advanced Vector Instructions Architectures .................................. 119 Shay Gueron and Vlad Krasnov Finite Field Arithmetic Efficient Multiplication over Extension Fields........................ 136 Nadia El Mrabet and Nicolas Gama GF(2m) Finite-Field Multipliers with Reduced Activity Variations ..... 152 Danuta Pamula and Arnaud Tisserand Finding Optimal Formulae for Bilinear Maps ........................ 168 Razvan Barbulescu, J´er´emie Detrey, Nicolas Estibals, and Paul Zimmermann Equations and Functions Solving Binary Linear Equation Systems over the Rationals and Binaries ........................................................ 187 Benedikt Driessen and Christof Paar Hashing with Elliptic Curve L-Functions............................ 196 Sami Omar, Raouf Ouni, and Saber Bouanani Invited Talk 4 Square Root Algorithms for the Number Field Sieve.................. 208 Emmanuel Thom´e Polynomial Factorization and Permutation Polynomial Improving the Berlekamp Algorithm for Binomials xn−a............. 225 Ryuichi Harasawa, Yutaka Sueyoshi, and Aichi Kudo On Some Permutation Binomials of the Form x2nk−1+1+ax over F2n : Existence and Count ............................................. 236 Sumanta Sarkar, Srimanta Bhattacharya, and Ay¸ca C¸e¸smelio˘glu Author Index.................................................. 247