1
$\begingroup$

I took a look at the Kyber and Frodo procedures and found that the ciphertext consists of two components. In Kyber these are the lines 5-7 in algorithm 2 $c := (\mathbf{u},v)$ and in Frodo line 8 of algorithm 10 $c \leftarrow (C_1,C_2)$.

One part of the ciphertext pair contains the message to be encrypted, that is $v$ in Kyber and $C_2$ in Frodo. My question is, therefore, why do you need the other ciphertext component $\mathbf{u}$ in Kyber and $C_1$ in Frodo? Wouldn't it be sufficient to work with only one, which "hides" the message, that is in Kyber $v$ and in Frodo $C_2$?

$\endgroup$

1 Answer 1

2
$\begingroup$

Wouldn't it be sufficient to work with only one, which "hides" the message, that is in Kyber $v$ and in Frodo $C_2$?

Actually, they are both taking a similar approach to El Gamal.

With El Gamal, you have a generator $g$ and a public key $pub$; to generate a ciphertext for a message $m$, you pick a random value $r$ and generate the ciphertext $g^r, pub^r \cdot m$

So, in El Gamal, the first part of the ciphertext doesn't do anything to "hide" the message, why doesn't we just send the $pub^r \cdot m$ part? Well, if we did, the decryptor wouldn't be able to decrypt - after all, he doesn't know what $r$ is (and the private key doesn't help him with that), and would be unable to recover $m$ from that. By including $g^r$, the decryptor (with the private key) is able to recompute $pub^r$ and so can remove that from $pub^r \cdot m$ to recover $m$.

Kyber and Frodo do pretty much the same thing, just with rings/matrices rather than modular multiplication - they both generate two values (related by the private key), and use one of them to 'hide' the message. The decryptor can use the private key to convert the other value (included in the ciphertext) into the first value (actually, an approximation - both Kyber and Frodo introduce intentional errors) which allows the decryptor to 'unhide' the message.

The obvious follow up question would be "could Kyber or Frodo be redesigned to use a single ring/matrix value, rather than two?" Well, perhaps you could (however, remember that decryption has to be easy with the private key, and infeasible without it - most obvious ways don't do one or the other). And what you would end up with wouldn't look that much like Kyber or Frodo (and the security proofs would look quite different)

$\endgroup$

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.