In LWE-based schemes the public key is generated by choosing a random matrix (or polynomial) $A$, and outputting the pair $(A, b = A\cdot s + e)$, where $s$ and $e$ are vectors/polynomials with coefficients taken from some error distribution.

In the Kyber encryption scheme the first part (the matrix/polynomial $A$) is not a part of the public key. Instead they save the seed to the (publicly known) extendable output function (EOF) that was used to generate $A$. If someone wants to know the public key, then he can just ask for the seed and generate $A$ himself. This saves a lot of space.

Why is this not proposed for schemes based on general lattices (standard LWE)? The big problem of these standard LWE schemes is the huge public key size, but this EOF solution would resolve that. However, it is not mentioned in any of the implementations that I found, like this one.


I believe it is also used in other lattice based schemes that use standard LWE. For example, the Frodo paper. They used a $seed_A$ and a Gen($\cdot$) function to compute $A$. Then Alice sends $seed_A$ instead of $A$ for the actually exchange. Gen($\cdot$) is a prior-agreed pseudorandom function that extracts and extends the seed.

  • $\begingroup$ thank you for your answer! I hadn't seen that paper before. $\endgroup$
    – Timo
    Dec 21 '17 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.