Understanding Lattices: Introduction to Lattice-Based Cryptography

LATTICES (AND STUFF) 1 Spring School on Lattice-Based Cryptography Oxford, 20 24 March, 2017.

Monday Intro to lattices, NTRU, Ring-LWE Tuesday Shor s algorithm, intro to SOLILOQUY Wednesday Number theory and quantum attacks FOUR TALKS Friday Now for something completely different 2

INTRODUCTORY MATERIAL 3

LATTICE A group group, isomorphic to N, for some finite integer N (rank rank) Together with a positive definite real positive definite real inner product (quadratic form) Elements of the lattice are called lattice points or lattice vectors because you can add them using the group structure and they have (Euclidean) length as given by the inner product You can identify a point using (intrinsic) integer coordinates integer coordinates and a fixed basis fixed basis Note that this is an intrinsic definition so different lattices need not be comparable intrinsic definition; it doesn t embed the lattice in any particular space, 4

EMBEDDING Sometimes it s nice to have a lattice be a subgroup of a larger object in which the lattice is embedded embedded. another lattice (such as Mfor M N), or it The larger object ( ambient space ) might be another lattice might be a vector space vector space (typically rational Mor real Mor complex M, finite- dimensional) The lattice inherits inherits its inner product structure from the ambient space The ambient space will typically have trivial inner product structure completely, so that lengths can be computed directly from (extrinsic) coordinates trivial inner product structure so that it factorises These coordinates make it possible to talk about other norms besides Euclidean length (2-norm); common examples in cryptography are the 1-norm and the -norm 5

TORUS When a lattice L is embedded in a vector space V, we have T = V/L, a flat manifold inheriting the metric structure of V If the dimensions of L and V agree, then T is compact the content content (or covolume covolume) of L compact (a torus), and its volume agrees with This is well defined, independent of any reference to a fundamental region sometimes a more useful concept than L itself fundamental region, and is If the ambient space V is simply a lattice, then T is instead a countable abelian group that describes how L injects into V The structure of the group T is revealed by the Smith Normal Form Smith Normal Form of a basis matrix for L 6

CANONICAL FORM An unembedded lattice unembedded lattice doesn t really have a canonical form. You just give a (real positive definite) Gram matrix Gram matrix, G. The idea is that there is then a basis b1 bN of lattice points for which Gij is the inner product of bi with bj. Then intrinsic coordinates are with respect to this given basis. But any other Gram matrix S*G*S-1 would do equally well, where S is a unimodular unimodular transform transform An embedded lattice embedded lattice may be subject to Hermite coordinates are commensurate commensurate, i.e. the ambient space is rational canonical and efficient canonical and efficient, given coordinates for the ambient space. Example (rank-4 L inside 6) : Hermite reduction reduction if (and only if) the extrinsic rational. This is entirely entirely ? 0 0 0 2 ? 0 0 7 7 0 0 0 0 ? 0 0 2 2 ? 4 1 5 2 If a rationally embedded lattice is to be used as a public key, Hermite reduction is the best way to enforce canonical form canonical form, removing extraneous data (side channels) 7

BASIS OR FLAG? A lattice (unembedded) may be presented via a (real positive definite) Gram matrix The idea is that there is then a basis basis b1 bN of lattice points for which Gij is the inner product of bi with bj. Then coordinates are with respect to this given basis. Gram matrix, G. Often the mathematical structure we actually want is a flag flag : {0} = L0 L1 L2 LN-1 LN = L Here, for each i, Li is some maximal lattice of rank i The relevant data structure for encoding a flag is a Gram inductively bi and Li-1 generate Li, and bi is the unique pair of points inside Lithat sit directly over the fundamental cuboid fundamental cuboid of Li. Gram- -Schmidt basis Schmidt basis, b1 bN, where 8

RING We use rings structure structure rings to generalise the basic lattice concepts and encode interesting multiplicative multiplicative additive structure isomorphic to n for The kind of ring I m interested in is small ; it has additive structure isomorphic to some finite integer n Here are some properties that a ring R may or may not have (and in general we don t care too much) : Be commutative commutative (a*b = b*a) Contain unity unity (1*a = a = a*1; actually I do generally insist on this condition) Be an integral domain integral domain (no zero divisors; a*b=0 implies a=0 or b=0) Be of the form [X]/f(X) for some univariate univariate polynomial polynomial f of degree n Be of the form [G] for some finite group group G of order n 9

RING STRUCTURE A ring R is algebraic algebraic, it has multiplicative structure that distributes over additive structure Since its additive structure is isomorphic to n, it looks like a lattice of rank n, but it does not automatically come equipped with any metric structure We can impose some metric structure by fiat matrix for it. Now it s a lattice by fiat, just fix any -basis for R and pick any Gram lattice! If you want for it to be an embedded lattice embed R embedded lattice, just find some vector space V in which to The multiplicative structure and the metric structure will only suit one another for cryptographic purposes cryptographic purposes if we can find some lemma to the effect that, suit one another for The product of one short element with another short element The product of one short element with another short element is (almost) always short is (almost) always short 10

MODULE It would be a mistake to stop at rings... A module over module over R is an abelian group that comes equipped with well-defined scalar multiplication by multiplication by R scalar A free module free module, M, is one that possesses an R-basis (because the rings we consider are small and so have the invariant basis number invariant basis number property) M = Rk is a free module of rank k free module of rank k, and it has an R-basis consisting of k elements Looking at additive structure only, M = Rk is isomorphic with nk, so set N = n*k, and then M looks like a lattice of rank N It actually is a lattice if we find some metric structure for it, and the nicest way to do that is simply to inherit the metric structure that we already imposed on R 11

EXAMPLES 12

NTRU AND RING-LWE, ETC Let R = [X]/(Xm - 1), or equivalently R = [Cyc(m)] Let a -basis for R be 1,X,X^2,...,Xm-1, or equivalently the elements of Cyc(m) Give R metric structure by associating the identity Gram matrix identity Gram matrix to the -basis Lemma Lemma: For a,b in R, if a is short in the 1-norm, and b is short in the -norm, then a*b is short in the -norm M = R2; let an R-basis for M be (1,0) and (0,1) Give M metric structure by associating the identity Gram matrix identity Gram matrix to the R-basis N = 2m, and M is a -lattice of rank N. This serves as the ambient space NTRU public key lattice NTRU public key lattice may be embedded. ambient space into which an 13

NTRU Dates back to 1996... Various versions have been considered over the years Fix a system parameter q in (more generally, an ideal q*R of R, but see later) Choose a reasonably short reasonably short private key (f,g) in M Full public key public key is the submodule (lattice) L generated by (f,g) and (q,0) and (0,q) By ensuring that ensuring that f f and q are coprime gives basis (1,h), (0,q), for some h that satisfies g = h*f+x*q, for some x and q are coprime, we can ensure that the Hermite form of L over R Although the Euclidean algorithm Euclidean algorithm need not be defined over R (not necessarily a Euclidean domain domain), we can use a bit of number theory to map the problem back to the integers, to find h (and x) efficiently Euclidean Then h alone encodes the public key (the system parameter q being fixed) 14

NTRU ENCIPHERMENT (GENERIC) Pick short short ephemeral ephemeral elements e1, e2 in R Combine these with public key to make ciphertext c = e1*h + e2 + q*R (a coset ciphertext ideal q*R) coset of the ideal To decipher, multiply by f and add q*R : c*f = (e1*h + e2 + q*R)*f + q*R = e1*(g x*q) + e2*f + q*R*f + q*R = e1*g + e2*f + q*R The ideal q*R has a nice fundamental region (Voronoi e1*g + e2*f is short enough is short enough (in -norm), one can simply read it by reducing coordinates of c*f independently Voronoi cell cell is a cube) and so provided that provided that Hence, information about the ephemeral elements e1,e2 may be extracted; and typically extra structure extra structure is included in e1,e2,f,g so as to expedite this process 15

NTRU HARD PROBLEMS Distinguish Distinguish ciphertext In M, coset (0,c) + L contains short element (-e1,e2); so this coset is special because it contains an atypical element atypical element Close Vector Problem Close Vector Problem: distinguish a special coset of L from a random one ciphertext from random from random Security reduction Security reduction: assume that no efficient algorithm exists that successfully distinguishes atypical cosets of L, then check that your primitive / scheme / protocol is provably secure under that assumption Cryptanalysis Cryptanalysis: generate compelling evidence(!) for/against the assumption Moreover, L itself contains the short (structured?) element (f,g); but depending on how parameters and structure are chosen, this may or may not be atypical, potentially leading to a key attack key attack (Short Vector Problem) 16

RING-LWE Fix q in , as before Fix b in R, another system parameter Public submodule L is generated by (1,b), (0,q), independent of key independent of key Choose a reasonably short reasonably short private key (f,g) in M Full public key public key is the coset (0,h) + L = (f,g) + L This is found by solving h + q*R = g b*f + q*R So again, we (Hermite-) reduce each coordinate of g b*f modulo q, to find public key h inside the cube Inhomogeneous Inhomogeneous version of NTRU; no conceptual need for Euclidean algorithm no conceptual need for Euclidean algorithm 17

RING-LWE ENCIPHERMENT (GENERIC) Pick short short ephemeral ephemeral elements e1, e2, e3 in R Combine these with public key to make ciphertext c1 = e1*b + e2 + q*R c2 = e1*h + e3 + q*R (cosets cosets of the ideal ciphertext ideal q*R) To decipher, combine linearly using f : c1*f + c2 = (e1*b + e2 + q*R)*f + e1*h + e3 + q*R = e1*b*f + e2*f + e1*h + e3 + q*R = e1*g + e2*f + e3 + q*R As before, provided by reducing coordinates of (c1*f + c2) independently provided e1*g + e2*f + e3 is short enough is short enough (in -norm), one can simply read it Hence, information about the ephemeral elements e1,e2,e3 may be extracted; and typically extra structure extra structure is included in e1,e2,e3,f,g so as to expedite this process 18

RING-LWE HARD PROBLEM Distinguish Distinguish ciphertext Ciphertext properties, such as coset (0,c1) + L containing short element (-e1,e2) ciphertext from random from random Moreover, coset (0,h) + L contains short element (f,g), which may be atypical, potentially leading to a key attack key attack Uniformize Uniformize to a single security assumption to a single security assumption by basing all secret variables on the same distribution The usual Ring from random, where bi = ai*s + ei+ q*R, but in fact we don t need to assume this much for most primitives / schemes / protocols Ring- -LWE assumption LWE assumption talks about distinguishing an arbitrarily long list arbitrarily long list (ai,bi) 19

DIFFIE-HELLMAN & SHOR S ALGORITHM 20

DIFFIE-HELLMAN Diffie-Hellman is a simple method in public key cryptography to achieve key establishment key establishment based on discrete logarithms discrete logarithms Syntactically, it works over any abelian module an efficiently computed group operation an efficiently computed ring action an efficiently computed canonical representation of elements canonical representation of elements [ ] abelian module with group operation, + ring action, * * *although* not all such modules offer any security Let s use an elliptic curve acted on by the ring /r , where r = |G| elliptic curve over a finite field, which is a finite cyclic group G, A group element ( point ) is canonically represented by affine coordinates affine coordinates 21

DISCRETE LOG Let P in G be a base-point that generates our group Let A = a*P be another point; a in /r is called the discrete log discrete log of A It s intended to be a hard problem hard problem to recover a from A The discrete log assumption discrete log assumption asserts that this problem is hard This assumption would seem to be unjustified for any module, if we consider Shor s quantum algorithm (in its various different guises) 22

DH PRIMITIVE AND HARD PROBLEM One user generates a fresh keypair (a,A), another generates keypair (b,B) Public keys A,B, are exchanged; the shared secret Key is then a*B = a*b*P = Key = b*a*P = b*A A canonical representation of Key denoted [Key], which is the same for either party can be fed into a KDF KDF or stream cipher stream cipher, to generate session keys or shared keystream It is intended to be a hard problem to recover Key from A and B; this is known as the Computational Computational Diffie Diffie- -Hellman Problem / Assumption Hellman Problem / Assumption This assumption implies the discrete log assumption (and is therefore stronger), yet Shor s algorithm targets the (harder) discrete log problem 23

QUANTUM COMPUTING NOTATION A quantum register can hold data (of a given type) in quantum superposition this e.g. by { j }domain, where j represents an element from the set domain Quantum states come with (complex) amplitudes, akin to quantum probabilities (but amplitude has magnitude the square root of probability, and can take arbitrary argument) quantum superposition; let s denote All transformations (without loss of generality) are reversible reversible and unitary unitary For simple algorithms, we need to consider the quantum Fourier transform the form /r , written { j } /r (1/ r) sum /r [x] exp( 2 i j*x /r ) { x } /r quantum Fourier transform over rings of In these notes, I ll suppress notation for constants in the amplitude, and most of the domains, so that leaves the QFT looking like { j } sum[x] exp( 2 i j*x /r ) { x } 24

SHORS ALGORITHM Input P and A=a*P Reserve two quantum registers for holding ring elements and one for holding module elements, and use this recipe : Start with sum[j,k] { j, k, 0 }, the first two registers in uniform superposition Compute [j*P + k*A] into the third register, obtaining sum[j,k] { j, k, [j*P + k*A] } Perform the quantum Fourier transform quantum Fourier transform on each of the first two registers; obtaining sum[j,k,x,y] exp( 2 i ( j*x + k*y ) /r ) { x, y, [j*P + k*A] } Rewrite using variable t = j + k*a, obtaining sum[t,x,y] exp( 2 i t*x /r ) { x, y, [t*P] } sum[k] exp( 2 i k*(y a*x) /r ) Measure x and y (discarding third register), and note that y a*x = 0 uniform superposition over /r Output y/x , which is generally a 25

MORE ON RINGS 26

VARYING THE RING OR MODULE It is trivial to construct analogous systems with M = Rk for k>2, if desired One will still have to reason about security reductions from lattice problems in the ambient space R2 (as well as in Rk)... ...But in some cases, by using k>2, it may be possible to obtain equivalent security with better parameters, e.g. use a smaller modulus (value of q) It is equally trivial to change R to something better Rather than use R = [X]/(Xm 1), preferable to use R = [X]/f(X) for some irreducible Using f(X) a cyclotomic cyclotomic polynomial polynomial enables one to continue using Fourier transforms implement the cryptography (this amounts to taking R to be an order next slide) Using f(X) of prime degree prime degree removes even more intermediate structure irreducible f Fourier transforms to order of a cyclotomic field, see intermediate structure (see e.g. NTRU-Prime) 27

CYCLOTOMIC FIELDS Polynomial (Xm 1) factors into cyclotomic polynomials The mth cyclotomic polynomial, m(X), has degree n= (m) The number field number field it generates, K = [ ], is a cyclotomic field Its ring of algebraic integers (maximal order), algebraic integers (maximal order), OK, happens to be [ ] exactly Cyclotomic fields are abelian extensions The Galois group Galois group G is naturally isomorphic with ( /m )*, which is isomorphic with Cyc(n) Let denote complex conjugation complex conjugation (the element of G of order 2, i.e. -1 in ( /m )*) The Minkowski Minkowski embedding embedding maps K to n, one coefficient per element of G The standard metric on n then agrees with the intrinsic inner product Trace[ x * y ] (where the trace is from K to ) So OK is naturally naturally a lattice, without needing to fix a basis and pick a Gram matrix by fiat We could impose a different metric, if we really wanted to, but that would be confusing... abelian extensions, and as such inherit a natural metric inherit a natural metric :- intrinsic inner product given by mapping (x,y) to 28

FOURIER TRANSFORMS Let a and b be polynomials (in X) of degree at most m-1 Informally speaking, the Fourier Transform of b is given by the homomorphism B = ( b(1), b(z), b(z2), ... b(zm-1) ), where z is an mth root of unity in any suitable ring If A and B are the Fourier transforms of a and b, then the coordinate-wise product A*B is the Fourier transform of the convolution convolution of polynomials a and b When working with short elements of OK, a common trick is to store their Fourier transforms in a finite field that possesses an mth root of unity, so that both addition and multiplication can be performed coordinate-wise When all arithmetic is required modulo q, and when /q contains mth roots of unity, it is a very suitable ring for this purpose (Number Theoretic Transform Number Theoretic Transform) 29

UNIT GROUP Let n = (m) K = [ ] is a cyclotomic field, OK = [ ] is its maximal order OK* is the unit group unit group, the set of invertible elements of OK (with inverses in OK) The group of torsion units is torsion units is generated by -1 and (recall m = 1) There are also real real cyclotomic cyclotomic units ( j j ) / ( ) units with generators of the form The group of cyclotomic cyclotomic units units is the group generated by all these The full unit group, OK*, will be a finite (quite possibly index = 1 in cases of interest) finite- -index extension index extension of this group 30

INTERMEDIATE FIELD STRUCTURE Let n = (m) The cyclotomic field K = [ ] of degree n contains a maximal real subfield K+= [ + ], of degree n/2 (and whose class number is probably 1) maximal real subfield, denoted Its maximal order is OK+= [ + ] Its unit group, OK+*, contains the real cyclotomic units, but the only torsion units are 1 This intermediate field turns out to be quite significant in the SOLILOQUY cryptanalysis, and so one might prefer to avoid systems with intermediate field structure (all other considerations being equal) 31

SOLILOQUY (INTRO) 32

CRYPTOGRAPHY WITHOUT MODULES Back in 2007, I tried to design a primitive that could work with a cyclotomic field, yet not require a high-rank module, i.e. with M = R1= R = OK = [ ] = [X]/( m(X)) This eventually led to the conclusion that Shor s algorithm could be generalised to attack lattices of this kind 33

SOLILOQUY OVERVIEW Main system parameter is m, a prime number of about 10 or 11 bits, so K is a cyclotomic field of degree n = (m) = m-1 A private key is a short element a of OK The corresponding public key is encoded by some p in , which is the algebraic norm (taken from K to ) algebraic norm of a One uses rejection sampling when choosing keys, to ensure that p is prime prime Although p is prime in , the principal n conjugates of a*OK, which are also principal ideals principal ideal ideal p*OK factors into the It can be arranged (by adjusting a) that a*OK = p*OK + ( 2(p-1)/n )*OK, so that the ideal itself represents the full public key 34

LATTICE PICTURE By Hermite reduction, OK/a*OK is naturally isomorphic with /p In fact, OK looks like an A* lattice, which is a rank-n sublattice of m Every lattice basis gives rise to a parallelotope of Babai s Babai s rounding algorithm rounding algorithm parallelotope fundamental domain fundamental domain, which is the subject By construction, a*OK has a cyclic therefore a rhomboid rhomboid cyclic -basis basis whose parallelotope fundamental domain is We can make sure that this rhomboid is not too thin when choosing the private key; then base the decipherment process on Babai rounding 35

SOLILOQUY KEY a = sum[j] aj j, for j in /m , chosen with small coefficients, such that... a*OK = p*OK + ( 2(p-1)/n )*OK, where p is prime If p is not probably prime , then resample; If 2(p-1)/n is not a primitive nth root of unity, then resample; If a*OK p*OK + ( 2(p-1)/n )*OK, then conjugate a; Make sure that max[j,k] Trace[ ( j - k)/a ] is not too big If it exceeds some threshold, then resample; Then store d = Trace[ p/a ]/n (mod p) 36

SOLILOQUY ENCIPHERMENT short ephemeral ephemeral element e in m, whose coordinates sum to zero Pick short sum to zero Combine it with public key p, to make ciphertext c = sum[j] ej* 2(p-1) j/n + p (a coset ciphertext coset of the ideal ideal p ) To decipher, use Babai s Rounding (parallelotope fundamental domain) : Build vector ( c*d/2(p-1) j/n(mod p) : j in /m ) with zero Convolve it with vector ( aj: j in /m ) Divide by p (abort if not divisible) This method should recover e = ( ej: j in /m ), assuming it was in the fundamental domain to start with zero- -centred coordinates centred coordinates (-p/2, p/2 ) 37

SOLILOQUY HARD PROBLEMS Distinguish Distinguish ciphertext ciphertext from random from random This is an example of a very structured knapsack type knapsack type problem Key attack Key attack : Recovering a from a*OK is known as the Short Principal Ideal Problem Short Principal Ideal Problem As with other schemes, there s no apparent reduction from the key attack (discrete log problem) to the message attack (computational Diffie-Hellman problem) We believe that just as with other schemes Shor s algorithm (in some form) is suited to the harder problem, meaning that SOLILOQUY should not be quantum-resistant 38

NUMBER THEORY 39

REDUCTION TO INTERMEDIATE REAL FIELD We found that it s enough to be able to solve the Short Principal Ideal Problem for OK+, because there s a classical reduction from the problem over OK Find a*a from a*a *OK+ Find a from a*a (not too tricky, [H-G S 2004]) OK+ is a good deal simpler to reason about than OK, because it contains the totally positive elements positive elements : if x 0 in OK then x*x is in OK+, and every homomorphism into maps x*x to a positive real number totally Find a*a from a*a *OK+, where a*a is totally positive 40

GROUP OF IDEALS OF OK+ If u in OK+*, then u*OK+ = OK+ So multiplication by u fixes the lattice OK+ overall, even though it moves every point in that lattice (x u*x); in fact, it fixes any ideal of OK+ The (fractional) ideals (fractional) ideals of OK+ form a group under multiplication identity group under multiplication, with OK+ itself being the There are efficient methods efficient methods for multiplying ideals, so the group operation is efficiently computed However, it isn t clear whether ideals have a canonical representation canonical representation We actually care only about the group of principal ideals theory in this analysis, and the class number is probably 1 anyway) principal ideals (there is no role for class field 41

MINKOWSKI EMBEDDING WITHOUT SIGNS K+is simpler to work with because every homomorphism into is actually into ; and moreover, if x 0 in K then x*x is in K+and every homomorphism into maps x*x to a positive real number Can extend this to other non-zero elements by discarding sign information are no longer distinguished), mapping to the positive quadrant discarding sign information (so x and x positive quadrant Therefore use the Minkowski Minkowski embedding embedding, but drop signs when addition is not needed For example, to multiply (fractional) ideal x*OK+ by field element y, simply stretch coordinate of every element of x*OK+ by factor |Conj(y,k)|, for all k stretch the kth More generally, multiplication of ideals multiplication of ideals amounts to dilation coordinatisation dilation along the fixed axes fixed axes of this 42

RING OF DILATIONS n/2 is a ring, if we compose coordinate-wise Pick any real vector v in n/2, and consider dilating space (i.e. the positive quadrant) by stretching stretching the kth coordinate by positive positive factor exp( vk ), for all k So n/2 has a ring action on space Moreover, K+ embeds into this ring (not injectively), because to every element of K+ is associated the corresponding dilation Consider an ideal of OK+ embedded in space (without signs); it can be dilated by exp( vk ) to produce another object, which may or may not be an ideal of OK+ analytic closure of the group of ideals of OK+ Thus the ring action extends to the analytic closure So we again want to describe this group as a module 43

LOGARITHMIC NOTATION AND UNITS The notation is a bit more natural if we take real logarithms of coordinates of points (which are in the positive quadrant) For example, the generators of the real cyclotomic units map as follows ( j j ) / ( ) ( log | Sin( 2 jk/m ) | log | Sin( 2 k/m ) | : k = 1...n/2 ) And so OK+* is mapped to a discrete additive group inside n/2, which is called the log log- -unit unit lattice lattice 44

SOLILOQUY & SHORS 45

DISCRETE LOGS AGAIN Elliptic Curve Example SOLILOQUY Let P in G be a base-point that generates our group OK+is now our base-point A = a*a *OK+is another point ; a*a in OK+ is the discrete log of A Let A = a*P be another point; a in /r is called the discrete log discrete log of A Any two points can be added , by multiplying them as ideals It s intended to be a hard problem from A hard problem to recover a A point can be stretched (in each direction by exp( vk )), but stretches by log-units have no effect ( hidden period ) The discrete log assumption discrete log assumption asserts that this problem is hard So the discrete log of a point is naturally an element of the torus obtained by quotienting n/2 by the log-unit lattice This assumption would seem to be unjustified for any module, if we consider Shor s quantum algorithm (in its various different guises) 46

WHAT DO WE NEED? To make Shor s algorithm work, we need canonical representation for points We need a version of Shor s algorithm that works over continuous continuous and unbounded unbounded modules Once Shor s algorithm returns some point inside the torus, we need to convert it to a short vector in the ambient space, so the log-unit lattice had better be Close-Vector-Problem friendly That short point can then be exponentiated to recover a*a (and there is no sign ambiguity if we know that a*a should be totally positive). Finite precision ought not be a problem here either, because we can round off a*a to the nearest point in OK+ A few other things... In essence, Shor s dlog algorithm in this context is the same as the [EHKS 2014] algorithm for finding the unit group finding the unit group, but applied to S S- -units units (where S is the singleton set {a*a }); though it is easier since we already know the unit group and have just one more generator to recover [BS 2015] 47

CONTINUOUS SHORS ALGORITHM (SKETCH) Input (base-point OK+ and) A = a*a *OK+ Reserve two quantum registers for holding elements of (n-1)/2 and , respectively, and use this recipe : Start with sum[j,k] { j, k, 0 }, the first two registers in uniform superposition Compute [stretch by exp(j) of Ak] into the third register; the hidden period is the log-unit lattice (for j) augmented by one more dimension encoding Log(a*a ) Perform (which??) quantum Fourier transform quantum Fourier transform on each of the first two registers; uniform superposition over ?? Measure first two registers to obtain sample from (or close to??) dual lattice to hidden period lattice Collect enough data about the dual lattice to recover the entire primal lattice, thereby determining some generator of A (see [EHKS 2014] and [BS 2016]) 48

LOG-UNIT LATTICE Turns out to have an unreasonably nice easily unreasonably nice easily- -found basis for cyclotomics in general [CDPR 2016] found basis (see slide #44), Gaussian, then the coefficients of a*a in If coefficients of a in OK are chosen approx. indep. Gaussian OK+ will be approx. indep. Exponential Exponential, so after the logarithm map the coefficients will be approx. indep. Gumbel Gumbel (as projected onto the convex hull of the log-unit lattice), therefore having small constant constant variance Think of this as a small ball sat at the centre of a cuboid fundamental domain (that is practically a cube) much larger than the ball... Experiment confirms that it is always trivial to solve this CVP, converting some generator of A into the causally short generator a*a 49

CANONICAL REPRESENTATION Need a canonical form for a lattice embedded in a real vector space, so that quantum superposition superposition works the way it s supposed to quantum Note that Hermite form won t work in this embedding (reals not commensurate) Canonical form doesn t need to be classical; a quantum state would do! Basic idea of a lattice fingerprint lattice fingerprint : represent a lattice by a superposition of many lattice points, so that the basis (after LBR) doesn t matter so much represent each point by the bin it lands in, or by a cloud of points in an net, or some other interpolation method, so that finite precision isn t a problem look for ways to do all this that are completely reversible 50