How is Crystal Kyber CPA-secure algorithms converted into a CCA-secure algorithm

Sujan SM

3/13/24, 7:14 AM

In Crystal Kyber specification, page no10, there are 3 algorithms namely KYBER.CCAKEM for making the CPA-secure Kyber into CCA-secure one.

Q1: How is the shared key K being generated in KYBER.CCAKEM.Enc & KYBER.CCAKEM.Enc related to the CPA-secure algorithms ?

Q2: Is the shared key K used as input parameter of sorts, for the CPA-secure algorithm ?

1 + 0

post-quantum-cryptography

chosen-plaintext-attack

chosen-ciphertext-attack

kyber

Score:1

Crypto

Daniel S

3/13/24, 8:41 AM

A1: $K$ is the result of applying a key derivation function to the hash of an output of the KYBER.CPAPKE.Enc() function concatenated with a hash of the message and public key. This can be seen on line 5 of the Kyber.CCAKEM.Enc() function specification (here $c$ is the output of KYBER.CPAPKE.Enc() per line 4). In KYBER.CCAKEM.Dec() the $K$ value returned is either the same as the value returned in KYBER.CCAKEM.Enc() or a fake value that is published if the $c$ is deemed to have been potentially maliciously generated.

A2: No, but the input $r$ to KYBER.CPAPKE.Enc() is now the output of a hash of the message and public key (see lines 3 and 4 of KYBER.CCAKEM.Enc()) rather than an arbitrary value.

The issue here is that (module) Learning with Errors schemes are prone to decryption failures and an adversary can gain information about private values based on these failures. In particular, if a CCA adversary maliciously crafts secret vectors and error values with larger values than the KYBER.CPAPKE.Enc() process permits, then failures are more likely to occur. The process in KYBER.CCAKEM.Enc() and KYBER.CCAKEM.Dec() (a variant of the a Fujisaki-Okamoto transform) ensures that the random secret and error values were legitimately created and checked to be legitimate as part of the decryption process.

+ 0

Elon Musk

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

EN: How is Crystal Kyber CPA-secure algorithms converted into a CCA-secure algorithm

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.