Transcription
Post-quantum cryptographyTanja Lange23 March 2016BeNeLux Mathematical Congress
CryptographyIIMotivation #1: Communication channels are spying on ourdata.Motivation #2: Communication channels are modifying ourdata.Alice//BobUntrustworthy network“Eavesdropper”IILiteral meaning of cryptography: “secret writing”.Achieves various security goals by secretly transformingmessages.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography2
Cryptographic applications in daily lifeIIIIIIIMobile phones connecting to cell towers.Credit cards, EC-cards, access codes for Rabobank.Electronic passports; soon ID cards.Internet commerce, online tax declarations, webmail.Any webpage with https.Encrypted file system on iPhone (see Apple vs. FBI).Facebook, WhatsApp, iMessage on iPhone.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography5
Cryptographic applications in daily lifeIIIIIIIIMobile phones connecting to cell towers.Credit cards, EC-cards, access codes for Rabobank.Electronic passports; soon ID cards.Internet commerce, online tax declarations, webmail.Any webpage with https.Encrypted file system on iPhone (see Apple vs. FBI).Facebook, WhatsApp, iMessage on iPhone.PGP encrypted email, Signal, Tor, Tails Qubes OSTanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography5
Cryptographic applications in daily lifeIIIIIIIIMobile phones connecting to cell towers.Credit cards, EC-cards, access codes for Rabobank.Electronic passports; soon ID cards.Internet commerce, online tax declarations, webmail.Any webpage with https.Encrypted file system on iPhone (see Apple vs. FBI).Facebook, WhatsApp, iMessage on iPhone.PGP encrypted email, Signal, Tor, Tails Qubes OSSnowden in Reddit AmAArguing that you don’t care about the right to privacybecause you have nothing to hide is no different thansaying you don’t care about free speech because you havenothing to say.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography5
Cryptographic toolsMany factors influence the security and privacy of dataI Secure storage, physical security; access control.I Protection against alteration of data digital signatures, message authentication codes.I Protection of sensitive content against reading encryption.Cryptology is the science that studies mathematical techniques inorder to provide secrecy, authenticity and related properties fordigital information.Currently used crypto (check the lock icon in your browser) startswith RSA, Diffie-Hellman (DH) in finite fields, or elliptic curve DHfollowed by AES or ChaCha20.Newer systems: Curve25519, and Ed25519.Security is getting better, but lots of bugs and no secure hardwareTanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography6
Cryptographic toolsMany factors influence the security and privacy of dataI Secure storage, physical security; access control.I Protection against alteration of data digital signatures, message authentication codes.I Protection of sensitive content against reading encryption.Cryptology is the science that studies mathematical techniques inorder to provide secrecy, authenticity and related properties fordigital information.Currently used crypto (check the lock icon in your browser) startswith RSA, Diffie-Hellman (DH) in finite fields, or elliptic curve DHfollowed by AES or ChaCha20.Newer systems: Curve25519, and Ed25519.Security is getting better, but lots of bugs and no secure hardware– let alone anti-security measures such as the Dutch“Hackvoorstel”.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography6
In the long term, all encryption needs to be post-quantumIMark Ketchen, IBM Research, 2012, on quantum computing:“Were actually doing things that are making us think like,‘hey this isn’t 50 years off, this is maybe just 10 years off, or15 years off.’ It’s within reach.”Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography9
In the long term, all encryption needs to be post-quantumIMark Ketchen, IBM Research, 2012, on quantum computing:“Were actually doing things that are making us think like,‘hey this isn’t 50 years off, this is maybe just 10 years off, or15 years off.’ It’s within reach.”IFast-forward to 2022, or 2027. Quantum computers exist.Shor’s algorithm solves in polynomial time:IIIIIInteger factorization.The discrete-logarithm problem in finite fields.The discrete-logarithm problem on elliptic curves.This breaks all current public-key encryption on the Internet!Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography9
In the long term, all encryption needs to be post-quantumIMark Ketchen, IBM Research, 2012, on quantum computing:“Were actually doing things that are making us think like,‘hey this isn’t 50 years off, this is maybe just 10 years off, or15 years off.’ It’s within reach.”IFast-forward to 2022, or 2027. Quantum computers exist.Shor’s algorithm solves in polynomial time:IIIIInteger factorization.The discrete-logarithm problem in finite fields.The discrete-logarithm problem on elliptic curves.IThis breaks all current public-key encryption on the Internet!IAlso, Grover’s algorithm speeds up brute-force searches.IExample: Only 264 quantum operations to break AES-128.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography9
In the long term, all encryption needs to be post-quantumIMark Ketchen, IBM Research, 2012, on quantum computing:“Were actually doing things that are making us think like,‘hey this isn’t 50 years off, this is maybe just 10 years off, or15 years off.’ It’s within reach.”IFast-forward to 2022, or 2027. Quantum computers exist.Shor’s algorithm solves in polynomial time:IIIIInteger factorization.The discrete-logarithm problem in finite fields.The discrete-logarithm problem on elliptic curves.IThis breaks all current public-key encryption on the Internet!IAlso, Grover’s algorithm speeds up brute-force searches.IExample: Only 264 quantum operations to break AES-128.INeed to switch the Internet to post-quantum encryption.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography9
Confidence-inspiring crypto takes time to buildIMany stages of research from cryptographic design todeployment:IIIExplore space of cryptosystems.Study algorithms for the attackers.Focus on secure cryptosystems.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography10
Confidence-inspiring crypto takes time to buildIMany stages of research from cryptographic design todeployment:IIIIIIIIIExplore space of cryptosystems.Study algorithms for the attackers.Focus on secure cryptosystems.Study algorithms for the users.Study implementations on real hardware.Study side-channel attacks, fault attacks, etc.Focus on secure, reliable implementations.Focus on implementations meeting performance requirements.Integrate securely into real-world applications.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography10
Confidence-inspiring crypto takes time to buildIMany stages of research from cryptographic design todeployment:IIIIIIIIIExplore space of cryptosystems.Study algorithms for the attackers.Focus on secure cryptosystems.Study algorithms for the users.Study implementations on real hardware.Study side-channel attacks, fault attacks, etc.Focus on secure, reliable implementations.Focus on implementations meeting performance requirements.Integrate securely into real-world applications.IExample: ECC introduced 1985; big advantages over RSA.Robust ECC is starting to take over the Internet in 2015.IPost-quantum research can’t wait for quantum computers!Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography10
Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography11
Even higher urgency for long-term confidentialityIToday’s encrypted communication is being stored by attackersand will be decrypted years later with quantum computers.Danger for human-rights workers, medical records, journalists,security research, legal proceedings, state secrets, . . .Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography12
Impact of PQCRYPTO (EU project in Horizon 2020)IIIAll currently used public-key systems on the Internet arebroken by quantum computers.Today’s encrypted communication can be (and is being!)stored by attackers and can be decrypted later with quantumcomputer.Post-quantum secure cryptosystems exist but areunder-researched – we can recommend secure systems now,but they are big and slowTanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography13
Impact of PQCRYPTO (EU project in Horizon 2020)IIIAll currently used public-key systems on the Internet arebroken by quantum computers.Today’s encrypted communication can be (and is being!)stored by attackers and can be decrypted later with quantumcomputer.Post-quantum secure cryptosystems exist but areunder-researched – we can recommend secure systems now,but they are big and slow hence the logo.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography13
Impact of PQCRYPTO (EU project in Horizon 2020)IIIIIAll currently used public-key systems on the Internet arebroken by quantum computers.Today’s encrypted communication can be (and is being!)stored by attackers and can be decrypted later with quantumcomputer.Post-quantum secure cryptosystems exist but areunder-researched – we can recommend secure systems now,but they are big and slow hence the logo.PQCRYPTO will design a portfolio of high-securitypost-quantum public-key systems, and will improve the speedof these systems, adapting to the different performancechallenges of mobile devices, the cloud, and the Internet.PQCRYPTO will provide efficient implementations ofhigh-security post-quantum cryptography for a broadspectrum of real-world applications.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography13
Initial recommendations of long-term securepost-quantum systemsDaniel Augot, Lejla Batina, Daniel J. Bernstein, Joppe Bos,Johannes Buchmann, Wouter Castryck, Orr Dunkelman,Tim Güneysu, Shay Gueron, Andreas Hülsing,Tanja Lange, Mohamed Saied Emam Mohamed,Christian Rechberger, Peter Schwabe, Nicolas Sendrier,Frederik Vercauteren, Bo-Yin YangTanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography14
Initial recommendationsISymmetric encryption Thoroughly analyzed, 256-bit keys:IIAES-256Salsa20 with a 256-bit keyEvaluating: Serpent-256, . . .ISymmetric authentication Information-theoretic MACs:IIIGCM using a 96-bit nonce and a 128-bit authenticatorPoly1305Public-key encryption McEliece with binary Goppa codes:Ilength n 6960, dimension k 5413, t 119 errorsEvaluating: QC-MDPC, Stehlé-Steinfeld NTRU, . . .IPublic-key signatures Hash-based (minimal assumptions):IIXMSS with any of the parameters specified in CFRG draftSPHINCS-256Evaluating: HFEv-, . . .Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography15
Hamming codeParity check matrix (n 7, k 4): 1 1 0 1 1 0 0H 1 0 1 1 0 1 0 0 1 1 1 0 0 1An error-free string of 7 bits b (b0 , b1 , b2 , b3 , b4 , b5 , b6 ) satisfiesthese three equations:b0 b1 b3 b4 0b0 b2 b3 b5 0b1 b2 b3 b6 0If one error occurred at least one of these equations will not hold.Failure pattern uniquely identifies the error location,e.g., 1, 0, 1 meansTanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography16
Hamming codeParity check matrix (n 7, k 4): 1 1 0 1 1 0 0H 1 0 1 1 0 1 0 0 1 1 1 0 0 1An error-free string of 7 bits b (b0 , b1 , b2 , b3 , b4 , b5 , b6 ) satisfiesthese three equations:b0 b1 b3 b4 0b0 b2 b3 b5 0b1 b2 b3 b6 0If one error occurred at least one of these equations will not hold.Failure pattern uniquely identifies the error location,e.g., 1, 0, 1 means b1 flipped.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography16
Hamming codeParity check matrix (n 7, k 4): 1 1 0 1 1 0 0H 1 0 1 1 0 1 0 0 1 1 1 0 0 1An error-free string of 7 bits b (b0 , b1 , b2 , b3 , b4 , b5 , b6 ) satisfiesthese three equations:b0 b1 b3 b4 0b0 b2 b3 b5 0b1 b2 b3 b6 0If one error occurred at least one of these equations will not hold.Failure pattern uniquely identifies the error location,e.g., 1, 0, 1 means b1 flipped.The failure pattern H · b is called the syndrome.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography16
Coding theoryIIINames: code word c, error vector e, received word b c e.Very common to transform the matrix to have identity matrixon the right (no need to store that). 1 1 0 1 1 0 01 1 0 1 1 0 1 1 H 1 0 1 1 0 1 0 0 1 1 1 0 0 10 1 1 1Many special constructions discovered in 65 years of codingtheory:IIIILarge matrix H.Fast decoding algorithm to find e given s H · (c e),whenever e does not have too many bits set.Given large H, usually very hard to find fast decodingalgorithm.Use this difference in complexities for encryption.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography17
Code-based encryptionII1971 Goppa: Fast decoders for many matrices H.1978 McEliece: Use Goppa codes for public-key cryptography.IIIIOriginal parameters designed for 264 security.2008 Bernstein–Lange–Peters: broken in 260 cycles.Easily scale up for higher security.1986 Niederreiter: Simplified and smaller version of McEliece.IIIIPublic key: H with 1’s on the diagonal.Secret key: the fast Goppa decoder.Encryption: Randomly generate e with t bits set.Send H · e.Use hash of e to encrypt message with symmetric crypto (with256 bits key).Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography18
Security analysisISome papers studying algorithms for 20132015Prange; 1981 Omura; 1988 Lee–Brickell; 1988 Leon;Krouk; 1989 Stern; 1989 Dumer; 1990 Coffey–Goodman;van Tilburg; 1991 Dumer; 1991 Coffey–Goodman–Farrell;Chabanne–Courteau; 1993 Chabaud; 1994 van Tilburg;Canteaut–Chabanne; 1998 Canteaut–Chabaud;Canteaut–Sendrier; 2008 ers–van Tilborg;Bernstein (post-quantum); 2009 Finiasz–Sendrier;Bernstein–Lange–Peters; 2011 May–Meurer–Thomae;Becker–Coron–Joux; 2012 �Lange–Meurer (post-quantum);May–Ozerov.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography19
Security analysisISome papers studying algorithms for 20132015IIIPrange; 1981 Omura; 1988 Lee–Brickell; 1988 Leon;Krouk; 1989 Stern; 1989 Dumer; 1990 Coffey–Goodman;van Tilburg; 1991 Dumer; 1991 Coffey–Goodman–Farrell;Chabanne–Courteau; 1993 Chabaud; 1994 van Tilburg;Canteaut–Chabanne; 1998 Canteaut–Chabaud;Canteaut–Sendrier; 2008 ers–van Tilborg;Bernstein (post-quantum); 2009 Finiasz–Sendrier;Bernstein–Lange–Peters; 2011 May–Meurer–Thomae;Becker–Coron–Joux; 2012 �Lange–Meurer (post-quantum);May–Ozerov.256 KB public key for 2146 pre-quantum security.512 KB public key for 2187 pre-quantum security.1024 KB public key for 2263 pre-quantum security.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography19
Security analysisISome papers studying algorithms for 20132015IIIIPrange; 1981 Omura; 1988 Lee–Brickell; 1988 Leon;Krouk; 1989 Stern; 1989 Dumer; 1990 Coffey–Goodman;van Tilburg; 1991 Dumer; 1991 Coffey–Goodman–Farrell;Chabanne–Courteau; 1993 Chabaud; 1994 van Tilburg;Canteaut–Chabanne; 1998 Canteaut–Chabaud;Canteaut–Sendrier; 2008 ers–van Tilborg;Bernstein (post-quantum); 2009 Finiasz–Sendrier;Bernstein–Lange–Peters; 2011 May–Meurer–Thomae;Becker–Coron–Joux; 2012 �Lange–Meurer (post-quantum);May–Ozerov.256 KB public key for 2146 pre-quantum security.512 KB public key for 2187 pre-quantum security.1024 KB public key for 2263 pre-quantum security.Post-quantum (Grover): below 2263 , above 2131 .Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography19
Binary Goppa codeLet q 2m . A binary Goppa code is often defined byIIIa list L (a1 , . . . , an ) of n distinct elements in IFq ,called the support.a square-free polynomial g(x) IFq [x] of degree t such thatg(a) 6 0 for all a L. g(x) is called the Goppa polynomial.E.g. choose g(x) irreducible over IFq .The corresponding binary Goppa code Γ(L, g) is c IIIFn2c2cnc1 ··· 0 mod g(x)S(c) x a1 x a2x an This code is linear S(b c) S(b) S(c) and has length n.What can we say about the dimension and minimum distance?Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography20
Dimension of Γ(L, g)Ig(ai ) 6 0 implies gcd(x ai , g(x)) 1, thus get polynomials 1(x ai ) gi (x) t 1Xgi,j xj mod g(x)j 0Ivia XGCD. All this over IFq IF2m .In this form, S(c) 0 mod g(x) means !t 1t 1 XnnXXXci gi,j xj ci gi,j xj 0,i 1j 0j 0i 1meaning that for each 0 j t 1:nXci gi,j 0.i 1IIThese are t conditions over IFq , so tm conditions over IF2 .Giving an (n tm) n parity check matrix over IF2 .Some rows might be linearly dependent, so k n tm.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography21
Nice parity check matrixAssume g(x) 1Pti 0 gi x01imonic, i.e., gt 1.001. gt 1 H gt 2 gt 1 . .g1g2 g3 . . . 10g(a1 )1 0 g(a2 ) 00· . . .00Tanja Lange 0 0 0 · . . 1001g(a3 ).01a1a21.1a2a22.1a3a23.·········.a1t 1 at 1at 1···23 .0.0 .0 . . . . . g(a1n )https://pqcrypto.eu.org1ana2n. at 1nPost-quantum cryptography22
Minimum distance of Γ(L, g). Put s(x) S(c)s(x) nXci /(x ai )i 1Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography23
Minimum distance of Γ(L, g). Put s(x) S(c)s(x) nXci /(x ai )i 1 nXi 1II ciY(x aj ) /j6 inY(x ai ) 0 mod g(x).i 1g(ai ) 6 0 implies ai , g(x)) 1,Pgcd(xQnso g(x) divides i 1 ci j6 i (x aj ).Let c 6 0 have small weight wt(c) w t det(g).For all i with ci 0, x ai appears in every summand.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography23
Minimum distance of Γ(L, g). Put s(x) S(c)s(x) nXci /(x ai )i 1 nXi 1IIII ciY(x aj ) /j6 inY(x ai ) 0 mod g(x).i 1g(ai ) 6 0 implies ai , g(x)) 1,Pgcd(xQnso g(x) divides i 1 ci j6 i (x aj ).Let c 6 0 have small weight wt(c) w t det(g).For all i with ci 0, x ai appears in every summand.Cancel out those x ai withQ ci 0.The denominator is now i,ci 6 0 (x ai ), of degree w.The numerator now has degree w 1 and deg(g) w 1implies that the numerator is 0 (without reduction mod g),which is a contradiction to c 6 0, so wt(c) w t 1.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography23
Better minimum distance for Γ(L, g)IIIIIILet c 6 0 havewt(c) w.Qn small weightciPut f (x) i 1 (x ai ) withP ci Q{0, 1}.Then the derivative f 0 (x) ni 1 ci j6 i (x ai )ci .Thus s(x) f 0 (x)/f (x) 0 mod g(x).As before this implies g(x) divides the numerator f 0 (x).Note that over IF2m :(f2i 1 x2i 1 )0 f2i 1 x2i , (f2i x2i )0 0 · f2i x2i 1 0,Ithus f 0 (x) contains only terms of even degree anddeg(f 0 ) w 1. Assume w odd, thus deg(f 0 ) w 1.Note that over IF2m : (x 1)2 x2 1Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography24
Better minimum distance for Γ(L, g)IIIIIILet c 6 0 havewt(c) w.Qn small weightciPut f (x) i 1 (x ai ) withP ci Q{0, 1}.Then the derivative f 0 (x) ni 1 ci j6 i (x ai )ci .Thus s(x) f 0 (x)/f (x) 0 mod g(x).As before this implies g(x) divides the numerator f 0 (x).Note that over IF2m :(f2i 1 x2i 1 )0 f2i 1 x2i , (f2i x2i )0 0 · f2i x2i 1 0,Ithus f 0 (x) contains only terms of even degree anddeg(f 0 ) w 1. Assume w odd, thus deg(f 0 ) w 1.Note that over IF2m : (x 1)2 x2 1 and in general 2(w 1)/2(w 1)/2XXf 0 (x) F2i x2i F2i xi F 2 (x).i 0Ii 0Since g(x) is square-free, g(x) divides F (x), thus w 2t 1.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography24
Decoding of in Γ(L, g)IIIIIIDecoding works withQ polynomial arithmetic.Fix e. Let σ(x) i,ei 6 0 (x ai ). Same as f (x) before.σ(x) is called error locator polynomial. Given σ(x) can factorit to retrieve error positions, σ(ai ) 0 error in i.Split into odd and even terms: σ(x) a2 (x) xb2 (x).Note as before s(x) σ 0 (x)/σ(x) and σ 0 (x) b2 (x).Thusb2 (x) σ(x)s(x) (a2 (x) xb2 (x))s(x) mod g(x)IIb2 (x)(x 1/s(x)) a2 (x) mod g(x)pPut v(x) x 1/s(x) mod g(x) (from syndrome s(x)),then a(x) b(x)v(x) mod g(x).Use XGCD on v and g, stop part-way whena(x) b(x)v(x) h(x)g(x),with deg(a) bt/2c, deg(b) b(t 1)/2c.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography25
More exciting codesIIIIIIINiederreiter’s proposal was to use generalized Reed-Solomoncodes, this was broken in 1992 by Sidelnikov and Shestakov.In general we distinguish between generic attacks (such asinformation-set decoding) and structural attacks (that use thestructure of the code).Gröbner basis computation is a generally powerful tool forstructural attacks.Cyclic codes need to store only top row of matrix, rest followsby shifts. Quasi-cyclic: multiple cyclic blocks.QC Goppa: too exciting, too much structure.Interesting candidate: Quasi-cyclic Moderate-DensityParity-Check (QC-MDPC) codes, due to Misoczki, Tillich,Sendrier, and Barreto (2012).Most recent proposal: QcBits by Tung Chou.Hermitian codes, general algebraic geometry codes.Tanja Langehttps://pqcrypto.eu.orgPost-quantum cryptography26
IEncrypted le system on iPhone (see Apple vs. FBI). IFacebook, WhatsApp, iMessage on iPhone. IPGPencrypted email,Signal,Tor,TailsQubes OS . IExample: ECC introduced 1985; big advantages over RSA. Robust ECC is starting to take over the Internet in 2015. IPost-quantum research can't wait for quantum computers! Tanja Lange https://pqcrypto.eu .
