22ndWorkshoponEllipticCurveCryptography,
ECC2018,OsakaUniversity,November20,2018

HistoryofPublicͲKeyCryptography
Rabi Model(1944)
1980
㽢䡘
哎
哎

RecentDevelopmentsinPostͲQuantumCryptography

Shor
Algorithm
1990䡘 㽢

IBM’s NMR
Quantum Computer
2000
2010
䡘㽢䡘 㽢

Haroche-Wineland’s
Quantum Experiments
2020
2030
䡘
|RSA (integer factorization problem)
widelyused

Elliptic Curve Cryptography (discrete logarithm problem)

Tsuyoshi Takagi
Thesecryptosystemsarenolongersecureintheeraofquantumcomputer.

DepartmentofMathematicalEngineering
UniversityofTokyo,Japan

Post-quantum cryptography (PQC)(coding, multivariate polynomial, lattice, isogeny, etc)
researchphase

RecentDevelopmentsinPostͲQuantumCryptography

01/38

RecentDevelopmentsinPostͲQuantumCryptography

02/38

TrendinPostͲQuantumCryptography

QuantumCloudͲ IBMQ• NationalSecurityAgency(NSA)announcedpreliminaryplansfor
transitioningtoquantumresistantalgorithms inAugust2015.
https://www.nsa.gov/ia/programs/suiteb_cryptography/• SomeWorkshopsin2015Ͳ2016
January2015,DIMACSWorkshoponTheMathematicsofPostͲQuantumCryptography
http://dimacs.rutgers.edu/Workshops/PostͲQuantum
April2015,NISTWorkshoponCybersecurityinaPostͲQuantumWorld
http://www.nist.gov/itl/csd/ct/postͲquantumͲcryptoͲworkshopͲ2015.cfm

September2015,Dagstuhl SeminarͲ QuantumCryptanalysis
https://www.dagstuhl.de/en/program/calendar/semhp/?semnr=15371

https://www.research.ibm.com/ibmͲq/

November2015,ESTI Workshop onQuantumͲsafeCryptography

February2016,PQCrypto 2016:https://pqcrypto2016.jp/

CurrentlyIBMQhas20qubitsinNovember2017,
andtheyplantoextenditto50qubitsinafewyears.

• BigResearchProjects
PostͲquantumcryptographyforlongͲtermsecurity:http://pqcrypto.eu.org/
CROSSING:https://www.crossing.tuͲdarmstadt.de/JSTCRESTCryptoMath:https://cryptomathͲcrest.jp/

Googlealsotriestobuilda72ͲqubitProcessor.
RecentDevelopmentsinPostͲQuantumCryptography

03/38

RecentDevelopmentsinPostͲQuantumCryptography

04/38

PQCrypto 2016

NISTPQCStandardizations
http://csrc.nist.gov/groups/ST/postͲquantumͲcrypto/

Deadline:November,2017
PublicͲKeyCryptographyPrimitives
Ͳ digitalsignaturesͲ encryption
Ͳ KeyͲestablishment(KEMs)• More than 240 participants(USA/Canada70,Europe60,
Asia60,Japan40,others10)

SomeCandidatesofPQC(NISTIR8105)
Ͳ HashͲbasedsignatureͲ CodeͲbasedcryptography
Ͳ MultivariatepolynomialcryptographyͲ LatticeͲbasedcryptography
Ͳ IsogenyͲbasedcryptography

• NIST announcedpreliminaryplansfortransitioningto
quantumresistantalgorithms.
RecentDevelopmentsinPostͲQuantumCryptography

05/38

69 propersubmissions•

RecentDevelopmentsinPostͲQuantumCryptography

06/38

TimelineofNISTPQCProjectLatticeͲbased (24submissions)

https://csrc.nist.gov/Projects/PostͲQuantumͲCryptography/WorkshopsͲandͲTimeline

CompactLWE,CRYSTALSͲDILITHIUM,CRYSTALSͲKYBER,DingKey Exchange,DRS,EMBLEMandR.EMBLEM,FALCON,Frodo,HILA5,KINDI,LAC,LIMA,Lizard,LOTUS,NewHope,NTRUͲHRSSͲKEM,
NTRUPrime,NTRUEncrypt,OddManhattan,pqNTRUSign,qTESLA,Round2,SABER,Titanium•• April2018:㻝㼟㼠㻌㻺㻵㻿㼀㻌㻼㻽㻯㻌㼃㼛㼞㼗㼟㼔㼛㼜㻌

CodeͲbased(16 submissions)㻔submitters’presentations)BIGQUAKE,BIKE,ClassicMcEliece,DAGS,EdonͲK,HQC,LEDAkem,LEDApkc,McNie,NTSͲKEM,
pqsigRM,QCͲMDPCKEM,RaCoSS,Ramstake,RLCEͲKEM,RQC•MultivariatePolynomial(10 submissions)• August2019:2ndNISTPQC Workshop

CFPKM,DME,DualModeMS,GeMSS,Gui,HiMQͲ3,LUOV,MQDSS,Rainbow,SRTPI•(smallernumberofsubmissions)

HashͲbased (2 submissions)

GravityͲSPHINCS,SPHINCS+•• 2020/2021:Selectalgorithmsorstarta3rdRound

IsogenyͲbased(1 submission)

SIKE•• 2022/2024:Draftstandardsavailable

Others(16 submissions)

Giophantus,GuessAgain,HK17,LAKE,Lepton,LOCKER,MersenneͲ756839,OKCN/AKCN/CNKE,
OuroborosͲR,Picnic,PostͲquantumRSAEncryption,PostͲquantumRSASignature,RankSign,RVB,
ThreeBears,WalnutDSA
RecentDevelopmentsinPostͲQuantumCryptography

07/38

RecentDevelopmentsinPostͲQuantumCryptography

08/38

SecurityEvaluationCycle
New Scheme

ExampleofRSApublickey

discussion in public conferences

StressTest

ᵱᶍᶋᶃᴾᶕᶃᵿᶉᴾᶁᶊᵿᶑᶑᵝ
ᵬᶃᶕᴾᵿᶒᶒᵿᶁᶉᴾᵿᶊᶅᶍᶐᶇᶒᶆᶋ

Security Evaluationᵦᶍᶕᴾᶋᵿᶌᶗᴾᶀᶇᶒᶑᴾᵿᶐᶃᴾᶑᶃᶁᶓᶐᶃᵝ

Expiring
key size

Practical Use
Computer speed-up
New cryptoanalyses
RecentDevelopmentsinPostͲQuantumCryptography

09/38

10/38

CryptographyResearchandEvaluation
CommitteesinJapan

Currentrecordforfactoringintegers• January2010,768bits,1500 CPUyears,Aokietal.
•RecentDevelopmentsinPostͲQuantumCryptography

http://www.cryptrec.go.jp/

12301866845301177551304949583849627207728535695953347921973
22452151726400507263657518745202199786469389956474942774063
84592519255732630345373154826850791702612214291346167042921
4311602221240479274737794080665351419597459856902143413=33478071698956898786044169848212690817704794983713768568912
431388982883793878002287614711652531743087737814467999489
㽢36746043666799590428244633799627952632279158164343087642676
032283815739666511279233373417143396810270092798736308917

Numberfieldsieve
RecentDevelopmentsinPostͲQuantumCryptography

11/38

RecentDevelopmentsinPostͲQuantumCryptography

12/38

EstimationforKeyLengthofRSA

FLOPS

RSA2048bits

RSA1536bits

MultivariatePublicͲKeyCryptography(MPKC)
RSA1024bits
RSAͲ768

http://www.cryptrec.jp/

RecentDevelopmentsinPostͲQuantumCryptography

13/38

MultivariateQuadraticpolynomial
problem(MQProblem)

14/38

RecentDevelopmentsinPostͲQuantumCryptography

MQproblem
MPKCarepublickeycryptosystemswhosesecuritydependsonthedifficultyinsolvinga
systemofmultivariatequadraticpolynomialswithcoefficientsinafinitefield‫ܭ‬.

Anexample:2 variablesand3equationsoverfinitefieldGF(7)

f1 ( x1 , x2 )2 x12  5 x1 x2  x22  3x1  5 x2  1

f 2 ( x1 , x2 )6 x  4 x1 x2  2 x1  6 x2  2

f1 ( x1 ,..., xn )f 3 ( x1 , x2 )3x12  6 x1 x2  6 x1  2 x2  3

f 2 ( x1 ,..., xn )MQproblem:findasolutionofthesystemofmultivariateequations:21¦ a x x  ¦b x  c

1di , j d n

(1)
ij
i

j

1di d n

(1)
ii

(1)

¦ a x x  ¦b x  c

1di , j d n( 2)ijij

1di d n( 2)ii

d1( 2)d2Wetrytofindacommonsolutionoffi(x1,x2)=0fori=1,2,3.

f m ( x1 ,..., xn )¦a1di , j d nx x j  ¦ bi( m ) xi  c ( m )

(m)
iji

1di d ndm

Itisbelievedthatitisdifficulttosolve(general)MQproblem.
RecentDevelopmentsinPostͲQuantumCryptography

15/38

RecentDevelopmentsinPostͲQuantumCryptography

16/38

FukuokaMQChallenge

Gröbner basisattack
A fundamental tool for solving MQ problem is Gröbner basis. Faugère
proposed efficient algorithms as F4 and F5 to improve original algorithm[1][2].

StartingfromApril2015https://www.mqchallenge.org/

Complexity for solving MQ problem[3]1

O((m  (dreg reg ))Z )ndwhere 2 < ʘ < 3, and dreg is an invariant determined by the multivariate
polynomial system.
Reference:
[1]Faugère,J.C.,ANewEfficientAlgorithmforComputingGröbner Bases(F4)",JournalofPureandAppliedAlgebra,vol.139,1999.
[2]Faugère,J.C.,ANewEfficientAlgorithmforComputingGröbner Bases(F5)",ISSAC,ACMpress,2002.
[3]Bettale,L.,Faugère,J.C.andPerretL.,Hybridapproachforsolvingmultivariatesystemsoverfinitefields", J.Math.Crypt.vol.2,2008.

17/38

RecentDevelopmentsinPostͲQuantumCryptography

Simulated encryptionscheme

18/38

RecentDevelopmentsinPostͲQuantumCryptography

Simulated signature scheme• UOV, Rainbow (multilayered UOV), …

• Simple matrix scheme, ExtensionFieldCancellation, …
• We choose parameters m=2n.
• To ensure the success of decryption, parameters n чm are used
• m=2n is suggested by Simple matrix scheme.

• We choose parameters n~1.5m.
• suggested by Rainbow scheme• Due to the free variables, the complexity is equal to n=m.

d1,…,dn is chosen tohave a solution

We can assign random value tofree variables xm+1,…,x[1.5m]

2015/3/18

RecentDevelopmentsinPostͲQuantumCryptography

19/38

RecentDevelopmentsinPostͲQuantumCryptography

20/38

Base fields

6TypesofChallenges• In MPKC scheme, finite field with small size are used.
• In order to get efficient arithmetic operation.

• m:#equations,n:#variables,q:basefieldGF(q)• Howtochoose base field for the MQ problem

TypeIIIIIIIVVVI• Binary field : GF(2)• The most typical field.
• More solvers can solve systems over binary field, ex, SATsolver.
• Binary extension field : GF(28)• Binary extension field are used in many applications.
• GF(28) is the reasonable size for the cryptanalysis.
• Prime field : GF(31)• Another typical field used in cryptography is prime field.
• GF(31) also had the reasonable size for the cryptanalysis.
21/38

RecentDevelopmentsinPostͲQuantumCryptography଼଼

Encryption
Encryption
Encryption
Signature
Signature
Signature

RecentDevelopmentsinPostͲQuantumCryptography

22/38

Current Record – Type I (GF(2), m = 2n)
n
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

time
time
Chou,
time*0.01
Ning,
m Niederhagen,
Joux
Niederhagen
Yang
120
122
124
126
128
130
132
134
136
138
140
142
144
146
148

23537
80245
30553
2664606547801001580676200
-5976
11268
21888
35316
49824
92484
1842843542047720208247601629540
34099206722784
1332313229649780

2211844055045529601179648221184039223296871449
14515200 (?)

MQ Challenge Type I Record
35000000
30000000
25000000

LatticeͲbasedCryptography

20000000
15000000
10000000
5000000
060 61 62 63 64 65 66 67 68 69 70 71 72 73 74
Chou, Niederhagen, Yang

Ning, Niederhagen

Joux

unit: second
RecentDevelopmentsinPostͲQuantumCryptography

23/38

RecentDevelopmentsinPostͲQuantumCryptography

24/38

LatticeͲbasedCryptography

LatticeͲbasedCryptographyAlatticeࡸ isthesetofallintegercombinationsof݊ linearlyindependentvectors‫܊‬ଵ ǡ ǥ ǡ ‫܊‬௡ ‫א‬Թ௠ଵ,, ௡௡௧ୀଵ ௧ ௧௧Alatticeࡸ isthesetofallintegercombinationsof݊ linearlyindependentvectors‫܊‬ଵ ǡ ǥ ǡ ‫܊‬௡ ‫א‬Թ௠.

ଵ,, ௡௡௧ୀଵ ௧ ௧.

௧ShortestVectorProblem(SVP)
Input:basis ଵ௡ oflattice
Output:nonͲzeroshortestvectorin

ShortestVectorProblem(SVP)
Input:basis ଵ௡ oflattice
Output:nonͲzeroshortestvectorinNPͲhardproblem
SVPisusedincryptography
Ajtai 1996,Regev 2005

NPͲhardproblem
SVPisusedincryptography
Ajtai 1996,Regev 2005

ଵଶ

Shortestvectors
25/38

RecentDevelopmentsinPostͲQuantumCryptography

ଵ,, ௡

௡
௧ୀଵ ௧ ௧

௧.

ShortestVectorProblem(SVP)
Input:basis ଵ௡ oflattice
Output:nonͲzeroshortestvectorin

26/38

DarmstadtLatticeChallenge

LatticeͲbasedCryptographyAlatticeࡸ isthesetofallintegercombinationsof݊ linearlyindependentvectors‫܊‬ଵ ǡ ǥ ǡ ‫܊‬௡ ‫א‬Թ௠

RecentDevelopmentsinPostͲQuantumCryptography

https://www.latticechallenge.org/• SVPChallenge/LatticeChallenge(since2008)
• IdealLatticeChallenge(since2013)• LWEChallenge(since2016)

ଵଶNPͲhardproblem
SVPisusedincryptography
Ajtai 1996,Regev 2005
RecentDevelopmentsinPostͲQuantumCryptography

27/38

RecentDevelopmentsinPostͲQuantumCryptography

28/38

AlgorithmsforsolvingtheSVP

IdeaofprogressiveBKZ

Ͳ polynomialͲtime(+exponentialͲtimeexhaustivesearch)(2)Enumeration(Extremepruning[GamaͲNguyenͲRegev 2010])
Ͳ time:2O(݊2),space:polynomialsize(3)Sieving(Gausssievealgorithm[MicciancioͲVoulgaris 2010])
Ͳ time:heuristically2O(݊),space:2O(݊)(4)Others

CostofatourinBKZ(ߚ).

(1) Latticebasisreduction(LLL/BKZalgorithm)
TotalcostofBKZ(40).

Inputbasis

TotalcostfromBKZ(10)
increasingtoBKZ(40).

Targetqualityߚ ൌ ͵Ͳߚ ൌ ʹͲߚ ൌ ͳͲ

#oftours

RecentDevelopmentsinPostͲQuantumCryptography

29/38

30/38

RecentDevelopmentsinPostͲQuantumCryptography

LearningwithErrors(LWE)Problem

Darmstadt Lattice Challenge

Dimension݊;Standarddeviationߪ ofdiscreteGaussiandistribution‫ܦ‬ఙ ;Numberofsamples݉;
Modulus‫ݍ‬Ǣ
Relativeerrorsize:ߙ ൌ ߪȀ‫;ݍ‬

CostEstimationofProgressive BKZ

S

224.0 secWehavesolvedSVPof652dimensions.

EUROCRYPT2016
RecentDevelopmentsinPostͲQuantumCryptography

31/38

b=
௠௤

+ e mod௠ൈ௡௤

RecentDevelopmentsinPostͲQuantumCryptography

௠ఙ
32/38

ExperimentalResults:TUDarmstadtLWEChallenge

EmbeddingTechnique onLWE

Input:aninstance ‫ۯ‬ǡ ‫ ܛۯ ؠ ܊‬൅ ‫܍‬ሺ‫ݍ‬ሻ ‫ א‬ሺԺ௠ൈ௡ǡ Ժ௠௤௤ ሻ.
௡.
Output:secretvector‫ א ܛ‬Ժ௤
Step1.constructbasis۰ୌ୒୊ of‫ܮ‬ଵ ൌ ‫ א ܞ‬Ժ௠  ‫ܛۯ ؠ ܞ‬ሺ‫ݍ‬ሻǡ ‫ א ܛ‬Ժ௡ ሽ.
்
Step 2. Rescale۰ுேி to۰ ᇱ ൌ ۰ுேி ‫ ܊‬asabasisof‫ܮ‬ଶ toreduceͲ‫ܯ‬BDDtouniqueͲSVP.
Step3.Process۰ ᇱ usingreductionalgorithmtoderiveashortvector‫܍‬‫ܝ‬‫ܟ‬ൌൌ ۰Ԣெଵߙ ൌ ߪȀ‫ݍ‬Embeddingtechnique[Kannan@1987]:
ReduceLWEproblemtouniqueͲSVPproblem.

(ɲ,n)=(0.005,70)
Embeddingtechnique+ProgressiveBKZ
E5Ͳ2697v2@2.70GHz

whichsatisfies ‫ ܟ‬൑‫ ܍‬ଶ ൅  ‫ܯ‬ଶ ,here ‫ ܍‬ൎ ݉ ߪ.
Step4.Computetheerrorvector‫ ܍‬ൌ ‫ ܊‬െ ۰‫;ܝ‬andcomputethesecretvector‫ ܛ‬inሺ‫ ܊‬െ ‫܍‬ሻ  ൌ ‫ܛۯ‬.
RecentDevelopmentsinPostͲQuantumCryptography

Conventional
Cryptography

AlgebraicGeometry Theoryof
Number Computation
Theory33/38

AdvancesofMathematical
TheoryrequiredforCryptographyMathematical
ModelingofMultiͲFunctional
NextͲGeneration
CryptographyusingwideͲrangeMathematical
Theories

Quantum
Computation
Mathematics
Representation
TheoryQuantum
FieldTheory
LatticeTheory
Mathematical Multivariate
Physics
Polynomial
TheoryCrypto Group

RecentDevelopmentsinPostͲQuantumCryptography

Synergy Groupsecurity evaluation

Takagi GroupDuong
H. Dung

TsuyoshiTakagi

Zeta function
Lattice crypto

Algebraic Geometry

AtsushiTakayasu

MasaakiUmehara

Synergy Group

Computational
TheoryKeisuke
TanakaSecurity Modelling
Tanaka GroupYuji
Nishiya
Sadayoshi
Kojima Terashima Nishibata
Knott theory

Lattice TheoryTopology

Asymptotic stabliity

Non-commutative
KirillMasahiro Hideyuki
Harmonic Oscillator
Morozov
Miura
Ishii
Secretsharing
Isogeny
CryptoDiffusion
equation
MasatoYasufumi
HashimotoMultivariate Crypto
Representation Theory
Combinatorics
Quantum
Field Theory

MathObject
Reduction Map

Differential
geometry

Crypto, Computer Algebra

MasayaYasudaYsuhikoIkematsu

Physical attack model

2SWLPL]DWLRQ

Provable Security

Functional
CryptoHayatoWaki

Fumio
Hiroshima

Quantum
Information Theory

RabiModelQuantuminteraction

35/38

NoboruKunihiro

High-performance computing

Goichiro
HanaokaKatsuyuki
Takashima

Hash Functions

Katsuyuki
Fujisawa

Needs
fromSociety

AttackModel
Industry
Application

Cryptography
Kunihiro Group
Hyungrok
Jo

SecurityEvaluation
LargeͲscale
Cryptoaslysis

MultivariateCrypto

ModelingoftheStrongestPossible
Attacks

34/38

RecentDevelopmentsinPostͲQuantumCryptography

Research Group

Startedin2014

Interaction:CryptoandMathHistoricalSuccess

32.73singlecorehours

Wakayama
Masao
Ishikawa

Jun
Muramatsu

Kazufumi Spectral zeta function
KimotoYoshinori
Yamasaki Ramanujan Graph

Math Group

ShingoSugiyama
Math modeling
L function
Wakayama Group
Automorphic formRecentDevelopmentsinPostͲQuantumCryptography

Pure
Mathematics
36/38

Conclusion

Book“CREST CryptoͲMath”• RecentdevelopmentsinPostͲQuantumCryptography

• PublishedonJuly2017fromSpringer

Ͳ NISTPQCStandardization

MathematicalModellingforNextͲGeneration Cryptography
Mathematics forIndustry Vol.29,Springer,2017. (359䝨䞊䝆)
http://www.springer.com/in/book/9789811050640• MultivariatePolynomialCryptography

19papersaboutresearchresults,technicalsurvey,openproblemsinthisproject.

Ͳ FukuokaMQ Challenge• LatticeͲbasedCryptographyPartIMathematicalCryptography
Ͳ HashͲbasedSignature,CodeͲbasedCrypto,MultivariatePolynomialCrypto,IsogenyͲbasedCrypto,PartIIMathematicsTowardsCryptography

Ͳ Darmstadt Lattice ChallengeͲ QuantumRabiModel,GroupͲSubgroupPairGraphs,RamanujanCayleyGraphsPartIIILatticesandCryptography• JSTCRESTCryptoͲMathProjectͲ LearningwithErrorsProblem,IntegerQuadraticProgramming,LogUnitsandLͲfunction

Ͳ MathematicalModellingforNextͲGenerationCryptographyPartIVCryptographicProtocols
Ͳ SecurityinLeakageModel,FullyHomomorphicEncryptions,IdentityͲbasedEncryptions

RecentDevelopmentsinPostͲQuantumCryptography

37/38

RecentDevelopmentsinPostͲQuantumCryptography

38/38