Hard Problems in Post-Quantum Cryptography
Problems on Lattices
Problems on Codes
Problems on Multivariate Systems
Problems on One-Way and Hash Functions
Problems on Isogenies
1Problems on Lattices
The most well-known problems based on lattices are Learning With Errors (LWE) [Reg05; LPR10], Short Integer Solution (SIS) [Ajt96; LS15] and “NTRU” [HPS98].
Given a monic polynomial and an integer modulus , let be a ring, and be uniformly random.
: Find a short nonzero such that Let , where and are sampled from the 'secret' distribution and 'error' distribution, respectively.
Decision: Distinguish from uniform. Search: Find . : Let , where are 'short.' Given , find
SIS, LWE, and NTRU exist in many variants [Reg05; LPR10; LS15; PP19], obtained by changing , or the error distributions.
To give a rough idea, a common choice is to take , with a power-of-two, and such that and are in the order of magnitude of 1000 .
The most common way to attack these problems is to interpret them as lattice problems, then run lattice reduction algorithms [APS15; ACD+18].
For example, the BKZ algorithm [SE94] with a blocksize is estimated to solve these in time classically [BDG+16], and quantumly [LMP15] via Grover's algorithm.
2Problems on Codes
The Syndrome Decoding (SD) problem: Given a matrix and a syndrome , to find of Hamming weight such that .
Note that it is similar to SIS.
Since 1962 , several algorithms have been presented to solve the SD problem, their complexity gradually improving from [Pra62] to [BM18]. These algorithms share similarities in their designs and [TS16] recently showed that when , they all have the same asymptotic complexity . For many of these algorithms, quantum variants have been proposed. They achieve quantum complexities that are essentially square roots of the classical ones, by using either Grover or quantum walks.
Hardness of distinguishing a code in a family from a pseudorandom one.For a given family of codes, a matrix generating a code is hard to distinguish from a random matrix.
For example, two variants of [ABB+19] assume that it is hard to distinguish from random either of these quasi-cyclic codes (or QC codes):
where is random and have small Hamming weight.
Note that they are reminiscent of NTRU and (ring-)LWE, respectively. Hence all the lattice problems we have defined have code counterparts, and reciprocally.
Besides the QC codes, another popular family of codes are Goppa codes [McE78; CFS01; BCL+19a].
3Problems on Multivariate Systems
In practice, only multivariate quadratics (i.e., of degree 2) are used.
They are the Multivariate Quadratic (MQ) and Extended Isomorphism of Polynomials (EIP) problems.
Let be a finite field. Let of the form , where each is a multivariate polynomial of degree at most 2 in the coefficients of .
Given and the map
Decision: Is there an such that ? Search: Find such that : Let and be uniformly random affine maps. Given and the promise that the map is in a publicly known set , find .
Note that MQ is solvable in polynomial time for or therefore this problem is more interesting when , which we assume henceforth.
Also note that EIP can be parameterized by the set to which the secret map belongs. For example, the Unbalanced Oil and Vinegar (UOV) and Hidden Field Equation (HFEv) problems, used by Rainbow [DCP+19] and GeMSS [CFM+19] respectively, are instantiations of the EIP "framework".
Algorithms solving MQ or EIP include F4/F5 [Fau02], XL [CKP+00; Die04] or Crossbred [JV17]. The best ones [YC04; BFP12; JV17] combine algebraic techniques - e.g., solving Gröbner bases - with exhaustive search, which can be sped up using Grover's algorithm in the quantum setting, see e.g. [BY17].
The asymptotic complexities of these algorithms are clearly exponential in , but we did not find simple formulae to express them (either classically or quantumly), except for special cases and which do not accurately reflect concrete instantiations such as the signature schemes Rainbow [DCP+19] and [SCH+19] .
4Problems on One-Way and Hash Functions
Let be a function, where .
Problems on hash functions.
Preimage: Given , find such that Second preimage: Given , find such that Collision: Find such that
The best classical algorithm against (second) preimage is exhaustive search, hence a complexity . Grover's famous quantum algorithm [Gro96] performs this search with a quadratic speed-up, hence a complexity Regarding collision, the best classical algorithm is the birthday attack with a complexity , and (disputed) results place the complexity of the best quantum attack between and [Zha15].
5Problems on Isogenies
Isogeny-based cryptography posits that given elliptic curves and over , it is hard to find a surjective group morphism (or isogeny, in this context) .
Elliptic curves can be ordinary or supersingular . Recall that the torsion subgroup is the kernel of the map . Most isogeny schemes work with supersingular curves, which parameters scale better. Two problems (or variations thereof) have emerged.
Problems on isogenies
Supersingular Isogeny Diffie-Hellman (SIDH): Given two elliptic curves and the value of an isogeny on , find . Commutative SIDH (CSIDH) : Given two elliptic curves , find an efficiently computable isogeny s.t. , where is the class group of .
Note that the CSIDH problem adapts DDH to the isogeny setting, and one can similarly adapt CDH.
Note that both problems are quantumly equivalent [GPS+18], whereas CDH and DDH are not known to be classically equivalent, except in special cases.
For SIDH, the best classical attack is via a claw-finding algorithm due to van Oorschot-Wiener [vW99]. Surprisingly, a recent result [JS19] shows that the best known quantum attack performs worse than [vW99].
The hardness of CSIDH reduces to solving a hidden shift problem, for which Kuperberg proposed quantum sub-exponential algorithms [Kup05; Kup13]. The actual quantum security of CSIDH is still being debated [BS20; Pei20].