3
$\begingroup$

NIST's main recommendation for encryption/decryption mechanism is CRYSTALS-KYBER. Whereas, the BSI (German equivalent) chooses FrodoKEM.

As far as my knowledge goes both these mechanisms use LWE lattice problem for their cryptographic security.

  • Then what makes the two mechanisms different?
  • Is it just the parameterization of the lattices?
  • Is one better than the other, if so why?
$\endgroup$

1 Answer 1

5
$\begingroup$

There are a few cosmetic differences but the principal difference is the matrix $A$ in the LWE problem. In Frodo it is consciously unstructured, but in Kyber it has some symmetry.

Specifically in both systems there are public values $$\mathbf a = A\mathbf s_a + \mathbf e_a$$ and $$\mathbf b =A^t\mathbf s_b + \mathbf e_b,$$ and an notional shared secret value $\mathbf s_b^tA\mathbf s_a$ which one user approximates as $\mathbf s_b^t\mathbf a$ and the other as $\mathbf b^t\mathbf s_a$. In Frodo the matrix $A$ is essentially arbitrary, in Kyber512 it is of the form $$\begin{pmatrix}C_{0,0} &C_{0,1}\\ C_{1,0} & C_{1,1}\\ \end{pmatrix}$$ in Kyber768 it is of the form $$\begin{pmatrix}C_{0,0} &C_{0,1}&C_{0,2}\\ C_{1,0} & C_{1,1} &C_{1,2}\\C_{2,0} & C_{2,1} &C_{2,2}\\ \end{pmatrix}$$ in Kyber1024 it is of the form $$\begin{pmatrix} C_{0,0} & C_{0,1} & C_{0,2} & C_{0,3}\\ C_{1,0} & C_{1,1} & C_{1,2} & C_{1,3}\\ C_{2,0} & C_{2,1} & C_{2,2} & C_{2,3} \\ C_{3,0} & C_{3,1} & C_{3,2}& C_{3,3}\\ \end{pmatrix}$$ where the $C_{i,j}$ are 256x256 negacirculant matrices (matrices where each row is a rotation of the previous row by one entry with wrap around entries changing sign).

The symmetry of Kyber allows for more efficient calculation. The matrices can also be described more compactly for Kyber (though in both cases $A$ is typically communicated with a seed value from which $A$ can be reconstructed; Kyber's reconstruction might be faster).

Some researchers think that the symmetry around Kyber might be exploitable in some way to break the system (so that Frodo is the more conservative choice for security), but thus far no significant advantage has been demonstrated.

ETA 20230118: As @mark points out, the symmetry of Kyber also admits significant bandwidth savings. As described, the approximate shared secret is only a single mod $q$ value which can only reliably encapsulate a handful of bits. However, in Kyber negacyclic transformations of the public values correspond to negacyclic transformations of the secret values so that 256 approximate shared secrets can be derived from a single public exchange in Kyber. In FRODO both participants exchange 8 public values to allow 64 approximate shared secrets to be established and multiple bits are encapsulated in each shared secret.

$\endgroup$
1
  • 3
    $\begingroup$ It is worth emphasizing that this symmetry allows for more efficient calculations, but (perhaps more importantly) it allows for smaller ciphertexts. Ciphertext size is a significant issue with post-quantum KEMs/signatures, and iirc are one of the main reasons why FrodoKEM (with >=10kb pk+ctxt size I think?) was omitted from being a NIST finalist. $\endgroup$
    – Mark Schultz-Wu
    Commented Jan 17, 2023 at 21:55

Your Answer

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

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