Association for Women in Mathematics Series Everett W. Howe Kristin E. Lauter Judy L. Walker Editors Algebraic Geometry for Coding Theory and Cryptography IPAM, Los Angeles, CA, February 2016 Association for Women in Mathematics Series Volume 9 SeriesEditor KristinLauter MicrosoftResearch Redmond,Washington,USA Association for Women in Mathematics Series Focusingonthegroundbreakingworkofwomeninmathematicspast,present,and future,Springer’sAssociationforWomeninMathematicsSeriespresentsthelatest research and proceedings of conferences worldwide organized by the Association forWomeninMathematics(AWM).Allworksarepeer-reviewedtomeetthehighest standardsofscientificliterature,whilepresentingtopicsatthecuttingedgeofpure andappliedmathematics.Sinceitsinceptionin1971,TheAssociationforWomenin Mathematicshasbeenanon-profitorganizationdesignedtohelpencouragewomen and girls to study and pursue active careers in mathematics and the mathematical sciencesandtopromoteequalopportunityandequaltreatmentofwomenandgirls inthemathematicalsciences.Currently,theorganizationrepresentsmorethan3000 members and 200 institutions constituting a broad spectrum of the mathematical community,intheUnitedStatesandaroundtheworld. Moreinformationaboutthisseriesathttp://www.springer.com/series/13764 Everett W. Howe • Kristin E. Lauter Judy L. Walker Editors Algebraic Geometry for Coding Theory and Cryptography IPAM, Los Angeles, CA, February 2016 123 Editors EverettW.Howe KristinE.Lauter CenterforCommunicationsResearch MicrosoftResearch SanDiego,CA,USA OneMicrosoftWay Redmond,WA,USA JudyL.Walker DepartmentofMathematics UniversityofNebraska-Lincoln Lincoln,NE,USA This book was advertised with a copyright holder in the name of the publisher in error, whereas the author(s) and the Association for Women in Mathematics are holding the copyright. ISSN2364-5733 ISSN2364-5741 (electronic) AssociationforWomeninMathematicsSeries ISBN978-3-319-63930-7 ISBN978-3-319-63931-4 (eBook) DOI10.1007/978-3-319-63931-4 LibraryofCongressControlNumber:2017954504 ©TheAuthor(s)andtheAssociationforWomeninMathematics2017 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade.Thepublisherremainsneutralwithregardtojurisdictional claimsinpublishedmapsandinstitutionalaffiliations. Gratefulacknowledgmentismadeforpermissiontoquotefromthelyricsto“LayMyLove,” writtenbyBrianEnoandJohnCale,publishedbyBucksMusicGroupLimitedo/b/oOpal LimitedandJohnCaleMusic.Allrightsreserved.Usedbypermission. Printedonacid-freepaper ThisSpringerimprintispublishedbySpringerNature TheregisteredcompanyisSpringerInternationalPublishingAG Theregisteredcompanyaddressis:Gewerbestrasse11,6330Cham,Switzerland Iamtheseaofpermutation Ilivebeyondinterpretation Iscrambleallthenamesandthecombinations Ipenetratethewallsofexplanation —BrianEnoandJohnCale,LayMyLove Preface In February 2016, we held a conference on Algebraic Geometry for Coding The- ory and Cryptography at the Institute for Pure and Applied Mathematics (IPAM) on the campus of the University of California, Los Angeles. The conference was run in cooperation with the Association for Women in Mathematics (AWM) and was designed in the research collaboration format that underlies many of the con- ferences whose proceedings appear in the AWM Springer Series. We are pleased to add this volume to the series. The goal of the conference was to bring together researchers working in Algebraic Geometry, Coding Theory, and Cryptography to cross-fertilizetheideasandproblems fromtheseareas.Bringingresearchcommu- nitiestogethertodocross-disciplinaryworkinthemathematicalsciencesisacore partofthemissionofIPAM.Toencourage theinterdisciplinarywork,wedecided to use the collaboration format from the Research Collaboration Conferences for Women based on the Women in Numbers model. This model has been successful forresearchconferencesforwomen,andwewereeagertoseehowitwouldwork inaconference withallgenders. For our conference, with43% women, wefound thatitworkedextremelywell!Feedbackfromtheparticipantswasoverwhelmingly enthusiasticabouttheformat,theexchangeofknowledge,andtheresearchresults achieved. Sixgroupsofbetweenfiveandsevenpeopleeachwereformedaheadofthecon- ferencetoworkoninterdisciplinaryresearchproblems.Groupleaderswereselected whowerewillingtodesignandleadprojects,andtherestoftheslotswereleftopen so that graduate students, postdoctoral researchers, and junior faculty could apply. There were close to 60 applications for only 24 open spots. Participants were as- signedtotheirgroupsaheadoftheconferenceandthegroupleaderscommunicated the research problems and some background reading to them. During the confer- ence,averysmallnumberoftalksinthemorningsgaveoverviewsoftheresearch problems,whilethemajorityofeachdaywasspentingroupworktomakeprogress ontheproblems,withsnackandlunchbreakstoencouragediscussion.Attheendof thedaytherewerebriefprogressreports.Agraduatestudentfromeachgroupwas appointed to give a presentation on the group’s results on the last day of the con- vii viii Preface ference.Groupswereencouraged tocontinuetheirresearchtogetherafterthecon- ference to produce a research article representing their results. In December 2016 fiveofthesixgroupssubmittedpapersforpeerreview,andthisvolumeconsistsof revisedversionsofthesefivepapers. Codingtheoryandcryptographyareimportantineverydaylife,becausetheyare building blocks for e-commerce. Error correction via coding theory protects infor- mationasitisstoredorsent,andefficienterrorcorrectionmayprovidesignificant benefits and cost-savings for enterprises. Cryptographic systems are necessary to secureinformationinstorage,transmission,andinteraction,andprovidebothconfi- dentialityandauthenticityguarantees.Whiletherehasalwaysbeensignificantand fruitfulinteractionbetweenalgebraicgeometryandbothcodingtheoryandcryptog- raphy,newdirectionsincodingtheory—suchaslocallydecodablecodes,codesfor distributedstoragesystems,andnetworkcoding—suggestedthepossibilityofnew connections with algebraic geometry. We set out to encourage cross-disciplinary workinthesethreeareas,andweareverypleasedthateveryoneofthefivepapers inthisvolumeachievesthegoalofusingalgebraicgeometrytoaddressaproblem ineithercodingtheoryorcryptography. Chapter 1 brings algebraic techniques to bear on the multicast network cod- ing problem. Chapter 2 focuses on error-correcting codes from hypersurfaces in weighted projective space. Chapter 3 uses modular polynomials to improve point- countingalgorithmsforJacobiansofgenus-2curves,whichareimportantforcurve selectionincryptography.Chapter4presentsseveralconstructionsoflocallyrecov- erablecodesfromalgebraiccurvesandsurfaces.Chapter5proposesvariantsofthe McEliececryptosystembasedonseveraldifferentconstructionsofcodes. WewouldliketothankIPAMforsuggestingandsupportingthisworkshopand for providing the great collaboration space to work in. As conference organizers, we each agreed to co-lead a group in order to help groups adjust to the research collaborationformat.Luckily,wewereabletofullyenjoythechancetocollaborate withourgroupsandco-leadersthankstotheexcellentsupportfromtheIPAMstaff and Directors, which left us free to concentrate on research during the workshop. Thanks are due especially to Jorge Balbas, Associate Director of IPAM, who was theWorkshopCoordinator,andtoStacyOrozco,whosupportedusonsite(andtook the pictures). Finally, we would like to thank all of the researchers who attended theconferencefortheirhardworkandtheirenthusiasticparticipation;wehopethat theyenjoyedtheexperienceasmuchaswedid. SanDiego,CA,USA EverettW.Howe Redmond,WA,USA KristinE.Lauter Lincoln,NE,USA JudyL.Walker May2017 Contents 1 RepresentationsoftheMulticastNetworkProblem ............... 1 SarahE.Anderson,WaelHalbawi,NathanKaplan,HiramH.López, FeliceManganiello,EminaSoljanin,andJudyL.Walker 2 HypersurfacesinWeightedProjectiveSpacesOverFiniteFields withApplicationstoCodingTheory ............................ 25 YvesAubry,WouterCastryck,SudhirR.Ghorpade,GillesLachaud, MichaelE.O’Sullivan,andSamrithRam 3 IsogeniesforPointCountingonGenusTwoHyperellipticCurves withMaximalRealMultiplication ............................. 63 Sean Ballentine, Aurore Guillevic, Elisa Lorenzo García, ChloeMartindale,MaikeMassierer,BenjaminSmith,andJaapTop 4 LocallyRecoverableCodesfromAlgebraicCurvesandSurfaces.... 95 Alexander Barg, Kathryn Haymaker, Everett W. Howe, GretchenL.Matthews,andAnthonyVárilly-Alvarado 5 VariationsoftheMcElieceCryptosystem........................ 129 Jessalyn Bolkema, Heide Gluesing-Luerssen, Christine A. Kelley, KristinE.Lauter,BethMalmskog,andJoachimRosenthal xi