{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T04:48:23Z","timestamp":1778215703547,"version":"3.51.4"},"reference-count":33,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T00:00:00Z","timestamp":1770076800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["VI.Veni.222.397"],"award-info":[{"award-number":["VI.Veni.222.397"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["RGPIN-2022-03187"],"award-info":[{"award-number":["RGPIN-2022-03187"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","award":["ALLRP 578463-22"],"award-info":[{"award-number":["ALLRP 578463-22"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2026,4,22]]},"abstract":"<jats:p>Practical deployments of key encapsulation mechanisms (KEMs) may entail large servers each using their public keys to communicate with potentially millions of clients simultaneously. While the standard IND-CCA security definition for KEMs considers only a single challenge public key and single challenge ciphertext, it can be relevant to consider multi-target scenarios where the adversary aims to break one of many challenge ciphertexts, for one of many challenge public keys. Many post-quantum KEMs have been built by applying the Fujisaki-Okamoto (FO) transform to a public key encryption (PKE) scheme. Although the FO transform incurs only a few bits of security loss for the standard, single-challenge IND-CCA property, this does not hold in the multi-target setting. Attacks have been identified against standards-track FO-based KEMs with 128-bit message spaces (FrodoKEM-640 and HQC-128) which become feasible if the adversary is given many challenge ciphertexts (say, 2^64). These attacks exploit the deterministic encryption induced by the FO transform which allows the IND-CCA experiment to be reduced to a search problem on the message space, which in some cases may not be large enough to avoid collisions between pre-computation and challenge values. A cost effective way to amplify the hardness of this search problem is to add a random but public salt during encapsulation. While revised versions of FrodoKEM and HQC have used salts, there has been no proof showing that salting provides multi-ciphertext security. In this work, we formally analyze a salted variant of the Fujisaki-Okamoto transform, in the classical and quantum random oracle model (ROM); for the classical ROM, we show that multi-target IND-CCA security of the resulting KEM tightly reduces to the multi-target IND-CPA security of the underlying PKE. Our results imply that, for FrodoKEM and HQC at the 128-bit security level, replacing the FO transform with the salted variant can recover 62 bits of multi-target security, at the cost of a very small overhead increase.<\/jats:p>","DOI":"10.62056\/a63zl83y6","type":"journal-article","created":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T18:09:08Z","timestamp":1777918148000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":1,"title":["On The Multi-target Security of Post-Quantum Key Encapsulation Mechanisms"],"prefix":"10.62056","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-7165-6150","authenticated-orcid":false,"given":"Lewis","family":"Glabush","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02s376052","id-type":"ROR","asserted-by":"publisher"}],"name":"EPFL","place":["Rte Cantonale, Lausanne, 1015, Switzerland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5478-0140","authenticated-orcid":false,"given":"Kathrin","family":"H\u00f6velmanns","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/02c2kyt77","id-type":"ROR","asserted-by":"publisher"}],"name":"Eindhoven University of Technology","place":["Groene Loper 3, Eindhoven, 5600 MB EINDHOVEN, The Netherlands"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9443-3170","authenticated-orcid":false,"given":"Douglas","family":"Stebila","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/01aff2v68","id-type":"ROR","asserted-by":"publisher"}],"name":"University of Waterloo","place":["200 University Ave W, Waterloo, N2L 3G1, Canada"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2026,5,4]]},"reference":[{"key":"ref1:C:FujOka99","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/3-540-48405-1_34","article-title":"Secure Integration of Asymmetric and Symmetric Encryption\n  Schemes","volume":"1666","author":"Eiichiro Fujisaki","year":"1999"},{"key":"ref2:JC:FujOka13","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1007\/s00145-011-9114-1","article-title":"Secure Integration of Asymmetric and Symmetric Encryption\n  Schemes","volume":"26","author":"Eiichiro Fujisaki","year":"2013","journal-title":"Journal of Cryptology"},{"key":"ref3:IMA:Dent03","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-540-40974-8_12","article-title":"A Designer's Guide to KEMs","volume":"2898","author":"Alexander W. Dent","year":"2003"},{"key":"ref4:TCC:HofHovKil17","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-319-70500-2_12","article-title":"A Modular Analysis of the Fujisaki-Okamoto\n  Transformation","volume":"10677","author":"Dennis Hofheinz","year":"2017"},{"key":"ref5:TCC:BHHHP19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-030-36033-7_3","article-title":"Tighter Proofs of CCA Security in the Quantum Random\n  Oracle Model","volume":"11892","author":"Nina Bindel","year":"2019"},{"key":"ref6:EC:SaiXagYam18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1007\/978-3-319-78372-7_17","article-title":"Tightly-Secure Key-Encapsulation Mechanism in the Quantum\n  Random Oracle Model","volume":"10822","author":"Tsunekazu Saito","year":"2018"},{"key":"ref7:C:JZCWM18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-319-96878-0_4","article-title":"IND-CCA-Secure Key Encapsulation Mechanism in the\n  Quantum Random Oracle Model, Revisited","volume":"10993","author":"Haodong Jiang","year":"2018"},{"key":"ref8:PKC:HKSU20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-030-45388-6_14","article-title":"Generic Authenticated Key Exchange in the Quantum Random\n  Oracle Model","volume":"12111","author":"Kathrin H\u00f6velmanns","year":"2020"},{"key":"ref9:PKC:JiaZhaMa19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/978-3-030-17259-6_21","article-title":"Key Encapsulation Mechanism with Explicit Rejection in the\n  Quantum Random Oracle Model","volume":"11443","author":"Haodong Jiang","year":"2019"},{"key":"ref10:EC:DFMS22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/978-3-031-07082-2_24","article-title":"Online-Extractability in the Quantum Random-Oracle Model","volume":"13277","author":"Jelle Don","year":"2022"},{"key":"ref11:AC:HovHulMaj22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/978-3-031-22972-5_15","article-title":"Failing Gracefully: Decryption Failures and the\n  Fujisaki-Okamoto Transform","volume":"13794","author":"Kathrin H\u00f6velmanns","year":"2022"},{"key":"ref12:PQCRYPTO:HovMaj24","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/978-3-031-62746-0_11","article-title":"A Note on Failing Gracefully: Completing the Picture for\n  Explicitly Rejecting Fujisaki-Okamoto Transforms Using Worst-Case\n  Correctness","author":"Kathrin H\u00f6velmanns","year":"2024"},{"key":"ref13:NISTPQC-R3:FrodoKEM20","volume-title":"FrodoKEM","author":"Michael Naehrig","year":"2020"},{"key":"ref14:NISTPQC-R4:HQC22","volume-title":"HQC","author":"Carlos Aguilar-Melchor","year":"2022"},{"key":"ref15:NISTPersonalCommunications","volume-title":"Multi-ciphertext attacks","author":"NIST PQC Team","year":"2021"},{"key":"ref16:EPRINT:Bernstein22d","volume-title":"Multi-ciphertext security degradation for lattices","author":"Daniel J. Bernstein","year":"2022"},{"key":"ref17:FrodoUpdates","volume-title":"Annex on FrodoKEM Updates","author":"Erdem Alkim","year":"2023"},{"key":"ref18:CCS:DHKLS21","doi-asserted-by":"publisher","first-page":"2722","DOI":"10.1145\/3460120.3484819","article-title":"Faster Lattice-Based KEMs via a Generic\n  Fujisaki-Okamoto Transform Using Prefix Hashing","author":"Julien Duman","year":"2021"},{"key":"ref19:EC:BelBolMic00","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/3-540-45539-6_18","article-title":"Public-Key Encryption in a Multi-user Setting: Security\n  Proofs and Improvements","volume":"1807","author":"Mihir Bellare","year":"2000"},{"key":"ref20:SaarinenHQC2025","volume-title":"IND-CCA2 issue in HQC (latest version)","author":"Markku-Juhani O. Saarinen","year":"2025"},{"key":"ref21:Hoevelmanns2021","doi-asserted-by":"publisher","DOI":"10.13154\/294-7758","volume-title":"Generic constructions of quantum-resistant cryptosystems","author":"Kathrin H\u00f6velmanns","year":"2021"},{"key":"ref22:PKC:DGJNVV19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/978-3-030-17259-6_19","article-title":"Decryption Failure Attacks on IND-CCA Secure\n  Lattice-Based Schemes","volume":"11443","author":"Jan-Pieter D'Anvers","year":"2019"},{"key":"ref23:PQCRYPTO:BinSch20","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-030-44223-1_12","article-title":"Decryption Failure Is More Likely After Success","author":"Nina Bindel","year":"2020"},{"key":"ref24:EC:DAnRosVir20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-45727-3_1","article-title":"(One) Failure Is Not an Option: Bootstrapping the Search\n  for Failures in Lattice-Based Encryption Schemes","volume":"12107","author":"Jan-Pieter D'Anvers","year":"2020"},{"key":"ref25:CCS:FKKDLD22","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1145\/3548606.3560673","article-title":"When Frodo Flips: End-to-End Key Recovery on FrodoKEM via\n  Rowhammer","author":"Michael Fahr","year":"2022"},{"key":"ref26:IMA:HeuSta21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-030-92641-0_5","article-title":"Tightness Subtleties for Multi-user PKE Notions","volume":"13129","author":"Hans Heum","year":"2021"},{"key":"ref27:C:AmbHamUnr19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-030-26951-7_10","article-title":"Quantum Security Proofs Using Semi-classical Oracles","volume":"11693","author":"Andris Ambainis","year":"2019"},{"key":"ref28:FIPS203","doi-asserted-by":"publisher","DOI":"10.6028\/NIST.FIPS.203","volume-title":"Module-Lattice-Based Key-Encapsulation Mechanism Standard","author":"National Institute of Standards","year":"2024"},{"key":"ref29:HQCDegradation","volume-title":"Multi-Instance Security Degradation of Code-Based KEMs","author":"Alexander May","year":"2026"},{"key":"ref30:PQCRYPTO:Sendrier11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-642-25405-5_4","article-title":"Decoding One Out of Many","author":"Nicolas Sendrier","year":"2011"},{"key":"ref31:FrodoKEM","volume-title":"FrodoKEM, Learning with Errors Encapsulation Preliminary\n  Standardization Proposal","author":"Erdem Alkim","year":"2023"},{"key":"ref32:EC:LanSteSte14","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-642-55220-5_14","article-title":"GGHLite: More Efficient Multilinear Maps from Ideal\n  Lattices","volume":"8441","author":"Adeline Langlois","year":"2014"},{"key":"ref33:Peikert2025priv","volume-title":"Private communication","author":"Chris Peikert","year":"2025"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T04:03:10Z","timestamp":1778040190000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/3\/1\/20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,4]]},"references-count":33,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,5,4]]}},"URL":"https:\/\/doi.org\/10.62056\/a63zl83y6","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,4]]},"assertion":[{"value":"2026-02-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-22","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc3-1-50"}}