CHAPTER 3 Families of Post-quantum Schemes 29 resulting point ⃗�� is still closer to the original point ⃗ �� than to any other point in the lattice. This distorted point ⃗�� is the cipher text which is sent to the receiver. Since the receiver is in possession of the secret, well-formed basis s of the lattice, he can recover the original lattice point ⃗ �� (the lattice point that is closest to the distorted cipher point) with low computational effort and obtain the original message. s0 s1 p0 p1 m c Figure 3.2: Example for lattice-based encryption in a two-dimensional lattice: The secret, well-formed based is {��⃗0, ��⃗1}; the public, »scrambled« base is {��⃗0, ⃗ ��1}. The sender uses { ��⃗0, ⃗ ��1} to map the message to a lattice point ⃗ �� and adds an error vector to obtain the point ⃗��. The point ⃗�� is closer to ⃗ �� than to any other lattice point. Therefore, the receiver can use the well-formed secret base { ⃗ ��0, ⃗ ��1,} to easily recover ⃗ �� (dotted vectors); this is a hard computation for an attacker who only has the scrambled base { ��⃗0, ⃗ ��1}. For a secure scheme, the dimension of the lattice must be much higher than 2 as in this example. The basic assumption for the security of this scheme is that an attacker who is not in possession of the well-formed base but only of the public scrambled base needs to spend an infeasible amount of computation in order to decipher the message. Finding a closest lattice point using the scrambled base (closest vector problem, CVP) and recomputing the well-formed base from the scrambled base (shortest vector problem, SVP) is believed to be computationally hard even for quantum computers. Other lattice-based schemes are based on the more general »learning with errors« (LWE) problem, which is closely related to coding theory and has security reductions to variants of SVP. NTRUEncrypt is a commercial public-key encryption scheme based on lattices. The scheme has been patented by the company NTRU Cryptosystems which
PQC_for_Dummies
To see the actual publication please follow the link above