1
$\begingroup$

I am looking for examples post-quantum secure trapdoor functions. Ideally, the inversion knowing the trapdoor should be "simple" in the sense that it can be computed by a circuit in NC^1.

$\endgroup$

1 Answer 1

1
$\begingroup$

Lattice-based problems are the most common examples for this. In general, we need to generate a “hard” public basis $B'$ (chosen at random from some appropriate distribution) of some lattice $L$ together with a “good” trapdoor basis of $B$ whose GramSchmidt vectors are relatively short for a generating trapdoor structure.

Based on this construction, public key cryptosytems can be designed. For example, the idea underlying GGH cryptosystem is: given any basis for a lattice, it is easy to generate a vector which is close to a lattice point. However, it is hard to return from this "close-to-Iattice" vector to the original lattice point (given a "bad" lattice basis.) In this concept, "good” basis $B$ can be defined as a "trapdoor".

Problems like SIS or LWE are popular lattice-based problems for public key constructions and these problems are based on the idea mentioned above. There are many interrelated lattice-based problems in the literature.

Micciancio and Goldwasser presented a graphical representation of the relations between the classical hard lattice problems. In this picture, an arrow from problem A to problem B means that problem A can be reduced to problem B in polynomial time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.