Score:1

Composition of ciphertexts in post quantum schemes Kyber and Frodo

sa flag

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$?

Score:2
my flag

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)

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.