What the study found
A salted variant of the Fujisaki-Okamoto transform can give multi-target IND-CCA security for key encapsulation mechanisms, and in the classical random oracle model this security tightly reduces to the multi-target IND-CPA security of the underlying public key encryption scheme. The authors also report that for FrodoKEM and HQC at the 128-bit security level, this change can recover 62 bits of multi-target security with only a very small overhead increase.
Why the authors say this matters
The study suggests this is relevant for practical deployments where one server may use a public key to communicate with many clients at the same time. The authors also note that their result addresses a gap: revised versions of FrodoKEM and HQC used salts, but there had been no proof that salting provides multi-ciphertext security.
What the researchers tested
The researchers formally analyzed a salted version of the Fujisaki-Okamoto transform in both the classical and quantum random oracle model. They examined security in a multi-target setting, where an attacker may try to break one of many challenge ciphertexts under one of many public keys.
What worked and what didn't
The classical random oracle model result shows a tight reduction from multi-target IND-CCA security of the KEM to multi-target IND-CPA security of the underlying public key encryption scheme. The abstract says that adding a random but public salt during encapsulation is a cost-effective way to strengthen the search problem, and that for FrodoKEM-640 and HQC-128 earlier attacks were feasible when many challenge ciphertexts were available. It does not give the detailed quantum-model result in the abstract.
What to keep in mind
The abstract focuses on the classical random oracle model result and only mentions that the salted transform was analyzed in the quantum random oracle model without stating the outcome there. The limitations described in the abstract are that the earlier attacks applied to 128-bit message spaces and depended on many challenge ciphertexts; no other caveats are described in the available summary.
Key points
- The paper analyzes a salted Fujisaki-Okamoto transform for key encapsulation mechanisms.
- In the classical random oracle model, multi-target IND-CCA security tightly reduces to multi-target IND-CPA security of the underlying encryption scheme.
- The authors say the result can recover 62 bits of multi-target security for FrodoKEM and HQC at the 128-bit level.
- Earlier attacks against FrodoKEM-640 and HQC-128 became feasible when many challenge ciphertexts were available.
- The abstract says salted variants had been used in revised schemes, but proof of multi-ciphertext security was previously missing.
Disclosure
- Research title:
- Salted FO transform restores multi-target KEM security
- Image credit:
- Photo by Alexei_other on Pixabay
Get the weekly research newsletter
Stay current with peer-reviewed research without reading academic papers — one filtered digest, every Friday.