ETSI TR 103 965 V1.1.1 (2024-10)

CYBER; Quantum-Safe Cryptography (QSC); Impact of Quantum Computing on Cryptographic Security Proofs

DTR/CYBER-QSC-0020

General Information

• Status: Not Published
• Technical Committee: CYBER QSC - Quantum-Safe Cryptography
• Current Stage: 12 - Completion
• Due Date: 21-Oct-2024
• Completion Date: 03-Oct-2024

Standards Content (Sample)

TECHNICAL REPORT
CYBER; Quantum-Safe Cryptography (QSC);
Impact of Quantum Computing on
Cryptographic Security Proofs
2 ETSI TR 103 965 V1.1.1 (2024-10)

Reference
DTR/CYBER-QSC-0020
Keywords
Quantum Safe Cryptography, security

ETSI
650 Route des Lucioles
F-06921 Sophia Antipolis Cedex - FRANCE

Tel.: [phone]  Fax: [phone]

Siret N° 348 623 562 00017 - APE 7112B
Association à but non lucratif enregistrée à la
Sous-Préfecture de Grasse (06) N° w061004871

Important notice
The present document can be downloaded from the
ETSI Search & Browse Standards application.
The present document may be made available in electronic versions and/or in print. The content of any electronic and/or
print versions of the present document shall not be modified without the prior written authorization of ETSI. In case of any
existing or perceived difference in contents between such versions and/or in print, the prevailing version of an ETSI
deliverable is the one made publicly available in PDF format on ETSI deliver.
Users should be aware that the present document may be revised or have its status changed,
this information is available in the Milestones listing.
If you find errors in the present document, please send your comments to
the relevant service listed under Committee Support Staff.
If you find a security vulnerability in the present document, please report it through our
Coordinated Vulnerability Disclosure (CVD) program.
Notice of disclaimer & limitation of liability
The information provided in the present deliverable is directed solely to professionals who have the appropriate degree of
experience to understand and interpret its content in accordance with generally accepted engineering or
other professional standard and applicable regulations.
No recommendation as to products and services or vendors is made or should be implied.
No representation or warranty is made that this deliverable is technically accurate or sufficient or conforms to any law
and/or governmental rule and/or regulation and further, no representation or warranty is made of merchantability or fitness
for any particular purpose or against infringement of intellectual property rights.
In no event shall ETSI be held liable for loss of profits or any other incidental or consequential damages.

Any software contained in this deliverable is provided "AS IS" with no warranties, express or implied, including but not
limited to, the warranties of merchantability, fitness for a particular purpose and non-infringement of intellectual property
rights and ETSI shall not be held liable in any event for any damages whatsoever (including, without limitation, damages
for loss of profits, business interruption, loss of information, or any other pecuniary loss) arising out of or related to the use
of or inability to use the software.
Copyright Notification
No part may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying and
microfilm except as authorized by written permission of ETSI.
The content of the PDF version shall not be modified without the written authorization of ETSI.
The copyright and the foregoing restriction extend to reproduction in all media.

© ETSI 2024.
All rights reserved.
ETSI
3 ETSI TR 103 965 V1.1.1 (2024-10)
Contents
Intellectual Property Rights . 5
Foreword . 5
Modal verbs terminology . 5
Executive summary . 5
Introduction . 6
1 Scope . 7
2 References . 7
2.1 Normative references . 7
2.2 Informative references . 8
3 Definition of terms, symbols and abbreviations . 11
3.1 Terms . 11
3.2 Symbols . 11
3.3 Abbreviations . 12
4 Cryptographic Security Proofs and Quantum Attackers . 12
5 Mathematical preliminaries . 13
5.1 Indistinguishability . 13
5.1.0 Introduction. 13
5.1.1 Chosen Plaintext Attack (CPA) . 13
5.1.2 Non-Adaptive Chosen Ciphertext Attack (CCA1) . 13
5.1.3 Adaptive Chosen Ciphertext Attack (CCA2) . 14
5.2 Qubits . 14
5.3 Cryptographic Hash Functions . 14
5.4 Proofs of Knowledge . 15
5.4.0 Introduction. 15
5.4.1 Correctness or Completeness . 15
5.4.2 Soundness . 15
5.4.3 Zero-Knowledge . 15
5.4.4 Sigma Protocols . 15
6 The Rewinding Technique for Zero-Knowledge Proofs . 16
7 Security Proofs in The Quantum Random Oracle Model. 17
7.1 The Quantum Random Oracle Model . 17
7.2 The Fiat-Shamir Transformation . 17
7.3 The Fujisaki-Okamoto Transformation and Related Constructions . 18
7.3.0 History of Transformations . 18
7.3.1 The Original Fujisaki-Okamoto Transform . 19
7.3.2 Solving The Correctness Problem . 19
7.3.3 Solving the Q-ROM Problem . 20
7.3.4 Solving the User Setting Problem . 20
7.3.5 Crystals-Kyber . 21
8 Commitment Schemes . 21
9 Security Under Parallel Composition . 23
9.0 Introduction . 23
9.1 The Universal-Composability Framework . 23
9.1.1 The Classical Universal-Composability Framework . 23
9.1.2 Universal Composability and Quantum Adversaries . 24
9.2 The Indifferentiability Framework . 24
9.2.1 The Classical Indifferentiability Framework . 24
9.2.2 Quantum Indifferentiability . 25
9.3 Limitations . 25
ETSI
4 ETSI TR 103 965 V1.1.1 (2024-10)
10 Pseudo-random functions . 26
10.1 The Quantum Security of Pseudo-Random Functions . 26
10.2 Pseudo-Random Functions and Message Authentication Codes . 26
Annex A: Change history . 28
History . 29

ETSI
5 ETSI TR 103 965 V1.1.1 (2024-10)
Intellectual Property Rights
Essential patents
IPRs essential or potentially essential to normative deliverables may have been declared to ETSI. The declarations
pertaining to these essential IPRs, if any, are publicly available for ETSI members and non-members, and can be
found in ETSI SR 000 314: "Intellectual Property Rights (IPRs); Essential, or potentially Essential, IPRs notified to
ETSI in respect of ETSI standards", which is available from the ETSI Secretariat. Latest updates are available on the
ETSI Web server (https://ipr.etsi.org/).
Pursuant to the ETSI Directives including the ETSI IPR Policy, no investigation regarding the essentiality of IPRs,
including IPR searches, has been carried out by ETSI. No guarantee can be given as to the existence of other IPRs not
referenced in ETSI SR 000 314 (or the updates on the ETSI Web server) which are, or may be, or may become,
essential to the present document.
Trademarks
The present document may include trademarks and/or tradenames which are asserted and/or registered by their owners.
ETSI claims no ownership of these except for any which are indicated as being the property of ETSI, and conveys no
right to use or reproduce any trademark and/or tradename. Mention of those trademarks in the present document does
not constitute an endorsement by ETSI of products, services or organizations associated with those trademarks.
DECT™, PLUGTESTS™, UMTS™ and the ETSI logo are trademarks of ETSI registered for the benefit of its

Members. 3GPP™ and LTE™ are trademarks of ETSI registered for the benefit of its Members and of the 3GPP
Organizational Partners. oneM2M™ logo is a trademark of ETSI registered for the benefit of its Members and of the ®
oneM2M Partners. GSM and the GSM logo are trademarks registered and owned by the GSM Association.
Foreword
This Technical Report (TR) has been produced by ETSI Technical Committee Cyber Security (CYBER).
Modal verbs terminology
In the present document "should", "should not", "may", "need not", "will", "will not", "can" and "cannot" are to be
interpreted as described in clause 3.2 of the ETSI Drafting Rules (Verbal forms for the expression of provisions).
"must" and "must not" are NOT allowed in ETSI deliverables except when used in direct citation.
Executive summary
There is a common misconception that to make a classically secure cryptosystem quantum-safe, it suffices to replace its
underlying computational-hardness assumptions with "quantum-hard" assumptions. However, this is not always the
case. The present document provides an overview of the impact of quantum computing on cryptographic security
proofs; it illustrates how for certain classes of cryptographic systems the security proofs need to be adapted, for which
classes this has already successfully been done, and what the practical implications of these adaptations are.
The present document is meant for cryptographic experts who want to get insight into practical changes that need to be
made to existing systems to make those systems quantum-safe, or who want to understand the fundamental challenges
in proving security against a quantum adversary.
ETSI
6 ETSI TR 103 965 V1.1.1 (2024-10)
Introduction
The advent of a cryptographically-relevant quantum computer (or CRQC for short) will severely impact most currently-
used cryptographic systems. Notably, a CRQC can factor integers and compute discrete logarithms in polynomial time,
thereby breaking systems based on the hardness of these problems.
However, simply replacing these problems by others which are (believed to be) impervious even to a quantum computer
does not completely solve the issue. This is due to the fact that many security proofs of cryptographic systems are no
longer valid in the presence of a quantum-capable attacker; while this does not automatically imply that the affected
systems would be broken by a quantum computer, it does raises questions on the exact security guarantees that the
systems can provide.
The present document analyses the impact of quantum computers on cryptographic security proofs, describing the
current knowledge on the topic and the expected effects on security.

ETSI
7 ETSI TR 103 965 V1.1.1 (2024-10)
1 Scope
The present document is intended to provide an overview of the impact of quantum computing on the security proofs of
several cryptographic protocols. It focuses on cryptographic protocols that can be run on classical hardware; further, it
discusses which security proofs are invalidated, or otherwise affected, in the presence of an attacker with access to a
CRQC, and discusses for each affected system whether:
a) an alternative proof has been found that does provide security against quantum attacks, but possibly with a
reduced security level;
b) no alternative proof has been found, but security is expected to still hold;
c) the cryptographic system is expected to be broken by quantum attacks, in a way which is not captured by the
classical security proof, although no concrete quantum attack exists yet; or
d) a concrete quantum attack that breaks security, in a way which is not captured by the classical proof, is
available.
In terms of the security proofs and problems under consideration, the present document includes the following:
1) The quantum random oracle model, and in particular its usage in:
a) The Fiat-Shamir transformation.
b) The Fujisaki-Okamoto transformation.
2) The rewinding technique for zero-knowledge proof systems.
3) The binding property of commitment schemes.
4) The universal-composability framework.
5) The indifferentiability framework.
6) Security proofs of pseudo-random functions.
In addition to presenting the theoretical developments on these topics, the present document elaborates on the practical
consequences. In some cases, the security of classically secure schemes is uncertain in the face of a quantum adversary.
In other cases, the security of the scheme holds, but the parameters need to be adjusted to retain the same level of
security.
NOTE: The present document does not discuss so-called "quantum-annoying" schemes, which still base their
security on computational problems that can be solved (relatively) efficiently by a quantum computer, but
force such an attack to perform a high number of operations, hence making it impractical for the expected
first generation of quantum computers.
2 References
2.1 Normative references
Normative references are not applicable in the present document.
ETSI
8 ETSI TR 103 965 V1.1.1 (2024-10)
2.2 Informative references
References are either specific (identified by date of publication and/or edition number or version number) or
non-specific. For specific references, only the cited version applies. For non-specific references, the latest version of the
referenced document (including any amendments) applies.
NOTE: While any hyperlinks included in this clause were valid at the time of publication ETSI cannot guarantee
their long-term validity.
The following referenced documents are not necessary for the application of the present document but they assist the
user with regard to a particular subject area.
[i.1] IETF RFC 2313 (1998): "PKCS# 1: RSA encryption version 1.5".
[i.2] D. Bleichenbacher: "Chosen ciphertext attacks against protocols based on the RSA encryption
standard PKCS# 1". Annual International Cryptology Conference. Springer, Berlin, Heidelberg,
1998.
[i.3] N. Koblitz, A.J. Menezes: "The random oracle model: a twenty-year retrospective". Designs,
Codes and Cryptography 77.2 (2015): pp. 587-610.
[i.4] R. Canetti, et al.: "The random oracle methodology, revisited". Journal of the ACM (JACM) 51.4
(2004): pp. 557-594.
[i.5] J. Coron, et al.: "Universal padding schemes for RSA". Annual International Cryptology
Conference. Springer, Berlin, Heidelberg, 2002.
[i.6] J. Van De Graaf: "Towards a formal definition of security for quantum protocols". Université de
Montréal, 1997.
[i.7] D. Unruh: "Quantum proofs of knowledge". Annual international conference on the theory and
applications of cryptographic techniques. Springer, Berlin, Heidelberg, 2012.
th
[i.8] J. Watrous: "Zero-knowledge against quantum attacks". Proceedings of the 38 annual ACM
symposium on Theory of Computing. 2006.
[i.9] J. Don, et al.: "Security of the Fiat-Shamir transformation in the quantum random-oracle model".
th
Advances in Cryptology-CRYPTO 2019: 39 Annual International Cryptology Conference, Santa
Barbara, CA, USA, August 18-22, 2019, Proceedings, Part II 39. Springer International
Publishing, 2019.
[i.10] V. Lyubashevsky et al.: "Crystals-dilithium". Algorithm Specifications and Supporting
Documentation (2020).
[i.11] R. El Bansarkhani and A. El Kaafaran: "Post-quantum attribute-based signatures from lattice
assumptions." Cryptology ePrint Archive (2016).
[i.12] D. Pointcheval, and J. Stern: "Security arguments for digital signatures and blind signatures".
Journal of cryptology 13 (2000): pp. 361-396.
[i.13] C. Schnorr: "Efficient signature generation by smart cards". Journal of cryptology 4 (1991):
pp. 161-174.
[i.14] Q .Liu and M. Zhandry: "Revisiting post-quantum fiat-shamir". Advances in Cryptology-
th
CRYPTO 2019: 39 Annual International Cryptology Conference, Santa Barbara, CA, USA,
August 18-22, 2019, Proceedings, Part II 39. Springer International Publishing, 2019.
[i.15] M. Barbosa et al.: "Fixing and mechanizing the security proof of fiat-shamir with aborts and
dilithium". Cryptology ePrint Archive (2023).
[i.16] E. Fujisaki and T. Okamoto: "Secure integration of asymmetric and symmetric encryption
schemes". In CRYPTO'99, volume 1666 of LNCS, pp. 537-554. Springer, Heidelberg,
August 1999.
ETSI
9 ETSI TR 103 965 V1.1.1 (2024-10)
[i.17] E. Fujisaki and T. Okamoto: "Secure integration of asymmetric and symmetric encryption
schemes". Journal of Cryptology, 26(1): pp. 80-101, January 2013.
[i.18] D. Hofheinz, et al: "A modular analysis of the Fujisaki-Okamoto transformation". In TCC 2017,
Part I, volume 10677 of LNCS, pp. 341-371. Springer, Heidelberg, November 2017.
[i.19] J. Duman et al.: "Faster Kyber and Saber via a generic Fujisaki-Okamoto transform for multi-user
security in the Q-ROM". 2021.
[i.20] J. Bos et al.: "CRYSTALS - Kyber: A CCA-secure module-lattice-based KEM". 2018 IEEE
European Symposium on Security and Privacy (EuroS P), pp. 353-367.
[i.21] M. Bellare et al.: "Public-key encryption in a multi-user setting: Security proofs and
improvements". In EUROCRYPT 2000, volume 1807 of LNCS, pp. 259-274. Springer,
Heidelberg, May 2000.
[i.22] A. Ambainis et al.: "Quantum attacks on classical proof systems: The hardness of quantum
th
rewinding". In 2014 IEEE 55 Annual Symposium on Foundations of Computer Science, pages
474-483, Oct 2014.
[i.23] D. Unruh: "Computationally Binding Quantum Commitments". In Proceedings, Part II, of the
th
35 Annual International Conference on Advances in Cryptology. 2016 pp. 497-527.
[i.24] D. Unruh: "Collapse-binding quantum commitments without random oracles". In Advances in
nd
Cryptology-ASIACRYPT 2016: 22 International Conference on the Theory and Application of
Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings,
Part II 22 (pp. 166-195). Springer Berlin Heidelberg.
[i.25] J. Czajkowski, et al.: "Post-quantum security of the sponge construction". In International
Conference on Post-Quantum Cryptography (pp. 185-204). Cham: Springer International
Publishing.
[i.26] S. Fehr: "Classical proofs for the quantum collapsing property of classical hash functions". In
th
Theory of Cryptography: 16 International Conference, TCC 2018, Panaji, India,
November 11-14, 2018, Proceedings, Part II 16 (pp. 315-338). Springer International Publishing.
[i.27] M. Zhandry: "New constructions of collapsing hashes". In Annual International Cryptology
Conference (pp. 596-624). Cham: Springer Nature Switzerland.
[i.28] J. Czajkowski: "Quantum Indifferentiability of SHA-3". In IACR Cryptol. ePrint Arch. 2021.
[i.29] T. Saito et al.: "Tightly-secure key-encapsulation mechanism in the quantum random oracle
model". IACR Cryptology ePrint Archive report 2017/1005. 2017.
[i.30] N. Bindel et al.: "Tighter proofs of CCA security in the quantum random oracle model". In
TCC 2019, Part II, volume 11892 of LNCS, pp. 61-90. Springer, Heidelberg, December 2019.
[i.31] J. Håstad: "Solving simultaneous modular equations of low degree". SIAM J. Comput., 17(2):
pp. 336-341, 1988.
[i.32] R. Cramer and V. Shoup: "Design and analysis of practical public-key encryption schemes secure
against adaptive chosen ciphertext attack". SIAM Journal on Computing 33(1), pp. 167-226. 2003.
[i.33] K. Hövelmanns et al.: "Generic authenticated key exchange in the quantum random oracle model".
In PKC 2020. LNCS, vol. 12111, pp. 389-422. Springer, Cham (2020).
[i.34] U. Maurer et al.: "Indifferentiability, impossibility results on reductions, and applications to the
random oracle methodology". In Theory of Cryptography, First Theory of Cryptography
Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004, Proceedings, volume 2951
of Lecture Notes in Computer Science, pp. 21-39. Springer, 2004.
[i.35] T. Carstens et al.: "On quantum indifferentiability". IACR Cryptol. ePrint Arch., 2018: pp. 257,
2018.
ETSI
10 ETSI TR 103 965 V1.1.1 (2024-10)
[i.36] T. Ristenpart et al.: "Careful with composition: Limitations of the indifferentiability framework".
th
In Advances in Cryptology - EUROCRYPT 2011 - 30 Annual International Conference on the
Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15-19, 2011.
Proceedings, volume 6632 of Lecture Notes in Computer Science, pp. 487-506. Springer, 2011.
[i.37] J. Coron et al.: "Merkle-Damgård Revisited: How to Construct a Hash Function". In Advances in
Cryptology CRYPTO 2005, volume 3621, pp. 430-448. Springer Berlin Heidelberg, Berlin,
Heidelberg, 2005. Series Title: Lecture Notes in Computer Science.
rd
[i.38] M. Zhandry: "How to construct quantum random functions". In 53 Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012,
pp. 679-687. IEEE Computer Society, 2012.
th
[i.39] O. Goldreich et al.: "How to construct random functions (extended abstract) ". In 25 Annual
Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA,
24-26 October 1984, pp. 464-479. IEEE Computer Society, 1984.
[i.40] H. Kuwakado and M. Morii: "Quantum distinguisher between the 3-round feistel cipher and the
random permutation". In IEEE International Symposium on Information Theory, ISIT 2010,
June 13-18, 2010, Austin, Texas, USA, Proceedings, pp. 2682-2685. IEEE, 2010.
[i.41] H. Kuwakado and M. Morii: "Security on the quantum-type even-mansour cipher". In Proceedings
of the International Symposium on Information Theory and its Applications, ISITA 2012,
Honolulu, HI, USA, October 28-31, 2012, pp. 312-316. IEEE, 2012.
[i.42] D. Boneh and M. Zhandry: "Quantum-secure message authentication codes". In Advances in
nd
Cryptology - EUROCRYPT 2013, 32 Annual International Conference on the Theory and
Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings,
volume 7881 of Lecture Notes in Computer Science, pp. 592-608. Springer, 2013.
[i.43] M. Kaplan et al.: "Breaking symmetric cryptosystems using quantum period finding". In Advances
th
in Cryptology - CRYPTO 2016 - 36 Annual International Cryptology Conference, Santa Barbara,
CA, USA, August 14-18, 2016, Proceedings, Part II, volume 9815 of Lecture Notes in Computer
Science, pp. 207-237. Springer, 2016.
[i.44] NIST: "Post-Quantum Cryptography Standardization - Post-Quantum Cryptography".
Csrc.nist.gov. 3 January 2017. Retrieved 24 November 2023.
[i.45] E. Fujisaki et al.: "RSA-OAEP is secure under the RSA assumption". J. Cryptology, 17(2):
pp. 81-104, 2004.
[i.46] E. Ebrahimi: "Post-quantum Security of Plain OAEP Transform". In Public-Key
Cryptography - PKC 2022. PKC 2022. Lecture Notes in Computer Science, vol 13177. Springer,
Cham.
[i.47] C. Peikert: "Lattice cryptography for the Internet". Cryptology ePrint Archive, Report 2014/070,
2014.
[i.48] J. Coron et al.: "GEM: A generic chosen-ciphertext secure encryption method". In CT-RSA 2002,
volume 2271 of LNCS, pp. 263-276. Springer, Heidelberg, February 2002.
[i.49] M. Bellare and P. Rogaway: "Optimal Asymmetric Encryption -- How to encrypt with RSA
(Extended abstract) ". In Advances in Cryptology - Eurocrypt '94 Proceedings, Lecture Notes in
Computer Science Vol. 950, A. De Santis ed, Springer-Verlag, 1995.
[i.50] J. Czajkowskiet al.: "Quantum Indifferentiability of SHA-3". IACR Cryptol. ePrint Arch., 192.
[i.51] D. Unruh: "Universally Composable Quantum Multi-party Computation". In Advances in
Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and
Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010.
Proceedings (pp. 486-505). Springer.
[i.52] A. Fiat and A. Shamir: "How to prove yourself: Practical solutions to identification and signature
problems". In Advances in Cryptology - CRYPTO' 86, pp. 186-194.
ETSI
11 ETSI TR 103 965 V1.1.1 (2024-10)
[i.53] R. Canetti: "Universally composable security: A new paradigm for cryptographic protocols". In
nd
Proc. 42 IEEE Symp. Foundations of Computer Science, pp. 136-145, 2001.
3 Definition of terms, symbols and abbreviations
3.1 Terms
For the purposes of the present document, the following terms apply:
asymmetric cryptography: cryptographic system that utilizes a pair of keys, a private key known only to one entity,
and a public key which can be openly distributed without loss of security
cryptographic hash function: function that maps a bit string of arbitrary length to a fixed length bit string (message
digest or digest for short) with specific mathematical properties
NOTE: See clause 5.3 for details.
cryptographic key: binary string used as a secret by a cryptographic algorithm
EXAMPLE: AES-256 requires a random 256-bit string as a secret key.
cryptographic protocol: system of rules that allows two or more communicating entities to reach a security-related
goal using cryptographic algorithms
entity: person, device or system
key encapsulation mechanism: method to secure the establishment of a cryptographic key for transmission using
public key cryptography
message digest/digest: fixed-length output of a cryptographic hash function over a variable length input
private key: key in an asymmetric cryptographic scheme that is kept secret
public key: key in an asymmetric cryptographic scheme that can be made public without loss of security
public-key cryptography: See asymmetric cryptography.
quantum-safe: resistant to quantum attacks
random oracle: theoretical black box that responds to every unique query with a uniformly random selection from the
set of possible responses, with repeated queries receiving the same response
security level: measure of the strength of a cryptographic algorithm
�
NOTE: If 2 operations are required to break the cryptographic algorithm/scheme/method, then the security level
is �. Sometimes also referred to as bit-strength.
3.2 Symbols
For the purposes of the present document, the following symbols apply:
� ≫� Informal notation to denote that a quantity � is much larger than another quantity �.
� ≈� Informal notation to denote that a quantity � is approximately as large as another quantity �.
� =�(�) Given two function �(�) and ����, taking as input non-negative integers, there exists a positive
constant � and a positive number �′ such that ���� ≤�(�) for all � ≥�′.
ETSI
12 ETSI TR 103 965 V1.1.1 (2024-10)
3.3 Abbreviations
For the purposes of the present document, the following abbreviations apply:
CBC Cipher Block Chaining
CRQC Cryptographically relevant quantum computer
DEM Data-encapsulation mechanism
EUF-CMA Existential UnForgeability under Chosen Message Attack
FO Fujisaki-Okamoto
GMAC Galois Message Authentication Code
IND-CCA INDistinguishability under Chosen Ciphertext Attack
IND-CPA INDistinguishability under Chosen Plaintext Attack
ITM Interactive Turing Machine
KEM Key-encapsulation mechanism
MAC Message Authentication Code
MPC Multi-Party Computation
OAEP Optimal Asymmetric Encryption Padding
OW-CPA One-Way under Chosen Plaintext Attack
OW-PCA One-Way under Plaintext Checking Attacks
PKE Public Key Encryption
PMAC Parallelizable Message Authentication Code
PRF Pseudo-Random Function
QPRF Quantum Pseudo-Random Function
Q-ROM Quantum random-oracle model
ROM Random-oracle model
RSA Rivest, Shamir, Adleman
UC Universal Composability
ZKPoK Zero-Knowledge Proof of Knowledge
4 Cryptographic Security Proofs and Quantum
Attackers
Reasoning about the security of a cryptographic primitive is not a trivial task. A naive way to design a cryptographic
system would be to go through the following steps: first, create a functional design for a system and deploy it. Then
wait until someone finds an attack that breaks the system; at this point, change the system to prevent said attack or
change the recommended parameters and wait for a new attack. If no new attack is published in reasonable time, one
might assume that the cryptographic scheme is secure. However, it is unclear what a "reasonable time" should be:
historically, there are for instance cryptographic systems that were broken after five years of silence, such as those used
in the PKCS#1 family of standards [i.1]. More precisely, PKCS#1 version 1.5 [i.1] contained a padding protocol for
RSA that was standardized in 1993, but it was not until 1998, that a chosen-ciphertext attack was found by
Bleichenbacher [i.2]. Therefore, this approach is risk-prone and not satisfactory.
To make more meaningful statements about the security of a scheme, a definition of security needs to be in place. Such
a definition should specify how an attacker is modelled and what the objective of the attacker is. The general aim is to
show that an hypothetical attacker that can break the system can also solve some well-studied computational problem
with a comparable effort. Under the assumption that such a computational problem is intractable (due to years of study
and scrutiny of its hardness), one can therefore rule out the existence of such an hypothetical attacker. In other words,
the security of the system is reduced to the hardness of a mathematical problem. More formally, such a reduction is
proved as follows:
• Assume there exists a probabilistic polynomial-time algorithm � (modelling a hypothetical attacker) that can
compromise a certain security goal of the scheme in time �, given certain powers. Here � is polynomial in �,
the desired security level of the scheme (typically chosen to be equal to 128 or 256).
� =���� (possibly probabilistic) that, given �, can solve the mathematical problem in
• Create an algorithm
time ���� for some function �.
ETSI
13 ETSI TR 103 965 V1.1.1 (2024-10)
This is called a security reduction. If the powers of an attacker are correctly modelled, such a reduction implies that the
attacker has to attack either the implementation of the scheme or the underlying mathematical assumption to
� �
compromise the security goal. Ideally, � � ≈�, in which case it is shown that breaking the cryptographic system takes
approximately as much time as solving the mathematical problem. By contrast, if ���� ≫�, then breaking the
cryptographic system might be significantly easier than solving the mathematical problem. How close ���� is to � is
referred to as the tightness of the reduction. Basing the security of a cryptographic scheme on a non-tight reduction,
�
e.g. ���� =� , might result in overly conservative parameter choices and impractical cryptographic protocol
instantiations. However, these reductions do show that there is no structural weakness in the cryptographic system.
This is the reason that modern cryptographic systems generally base their security on the assumed hardness of some
computational problem. When considering attackers that can use a CRQC, a general misconception is that simply
swapping the computational problems underlying a cryptographic system for "quantum-hard" computational problems
(i.e. problems that are considered intractable even for a quantum computer) is enough to make the system quantum-safe.
Unfortunately, this is not always true. As discussed above, all mathematical proofs of security have to specify the
powers of the attacker. A quantum attacker has properties that are not modelled in classical proofs. Therefore, in
addition to using quantum-hard computational problems, the proofs themselves often need to be modified as well.
Modifying a security proof in such a way that it accommodates for quantum attackers is often not trivial, and sometimes
no such proof is available. While this does not directly mean that the corresponding scheme is broken (since it might be
the case that such a proof exists, but cryptographers have been unable to find it yet), it does raise concerns on their
quantum-security. Moreover, even when a "quantum" proof is available, this often has an impact on the security level
that is attained against quantum adversaries; the reduction might be less tight than their classical counterparts.
Finally, the formulation itself of the security goals of cryptographic schemes is a delicate task, and given the often
counter-intuitive properties of quantum computing, some formulations turn out to be insufficient to achieve the desired
level of security. In this case, new formulations and associated proofs are needed.
5 Mathematical preliminaries
5.1 Indistinguishability
5.1.0 Introduction
The notion of indistinguishability is often used to argue about the security of encryption schemes. The general idea
behind such arguments is that an attacker with certain powers cannot tell the difference between encryptions of two
different messages. Since the attacker cannot distinguish, they do not learn anything about the message. Within the
domain of indistinguishability for encryption, there are three different ways to model the adversary's powers. These
different models correspond to specific real-life situations. The three attacker models are chosen plaintext attack, non-
adaptive chosen ciphertext attack and adaptive chosen ciphertext attack. The strongest guarantees are obtained when an
encryption scheme is indistinguishable under adaptive chosen ciphertext attacks (IND-CCA2). IND-CCA2 security is
considered to be the norm for general-purpose encryption schemes to be deployed in practice. It is common to
abbreviate IND-CCA2 to IND-CCA. The following subsections provide more details on the attacker models.
5.1.1 Chosen Plaintext Attack (CPA)
If an encryption scheme attains indistinguishability under Chosen Plaintext Attacks (IND-CPA), then an adversary is
not able to obtain any information about messages that are freshly encrypted, even if they can encrypt messages of their
own choice.
5.1.2 Non-Adaptive Chosen Ciphertext Attack (CCA1)
If an encryption scheme attains indistinguishability under non-adaptive Chosen Ciphertext Attacks (IND-CCA1), then
an adversary is not able to obtain any information about messages that are freshly encrypted even if they have access to
encryptions (ciphertexts) of messages of their own choice and even if they get access to decryptions of ciphertexts of
their own choice. It is assumed, however, that the decryptions of ciphertexts should be executed before the selection of
the messages to be freshly encrypted. This security notion was believed to be sufficient for security against real-world
threats. However, Bleichenbacher published a practical attack against an IND-CCA1-secure version of RSA in
1998 [i.2], proving this security notion inadequate in practice.
ETSI
14 ETSI TR 103 965 V1.1.1 (2024-10)
5.1.3 Adaptive Chosen Ciphertext Attack (CCA2)
If an encryption scheme attains indistinguishability under adaptive Chosen Ciphertext Attack (IND-CCA2), then an
adversary is not able to obtain any information about messages that are freshly encrypted even if they have access to
encryptions (ciphertexts) of messages of their own choice and can get access to decryptions of ciphertexts of their own
choice. The subtlety here is that the adversary is allowed to obtain decryptions of ciphertexts even after the message to
be encrypted has been selected (and encrypted), although it is not allowed to ask for a decryption of this target
ciphertext. This security notion is now believed to be sufficient for security against real-world threats. Specifically, a
newer IND-CCA2-secure version of RSA is resistant to Bleichenbacher's attack.
5.2 Qubits
The main difference between classical computers and quantum computers is that quantum computers operate on qubits,
whereas classical computer operate on classical bits. Loosely speaking, while a classical bit can assume a value of either
0 or 1, a qubit can be in a state which is a combination of 0 and 1. This is called superposition. When a qubit is
measured (in the so-called computational basis), its superposition collapses to a classical 0 or 1, according to a
probability distribution associated with the superposition.
Qubits can be modelled mathematically independently of their physical implementation. The state of a qubit can be
�
� �
denoted using a vector � � of length two with complex coefficients �,�such that |�| +|�| =1. The "zero" state is
�
�
0 1
interpreted as � � and the "one" state is interpreted as � �. A qubit � � is therefore a superposition of � times "zero"
�
1 0
plus � times "1". The coefficients of this linear combination relate to the probability of a 0 or 1 after the superposition
collapses.
A more common and convenient notation for qubits is the so-called bra-ket notation. The zero state is represented by
�
| ⟩
|0⟩ and the one state is represented by |1⟩. A qubit � � can therefore be expressed as � 0 +�|1⟩. Most quantum
�
algorithms require more than two qubits. The shorthand notation of � qubits in the zero state is |00…0⟩. A
superposition of � qubits is written as:
∑ �� |�⟩
�∈��,�� �
�
for complex coefficients � (commonly referred to as amplitudes) such that ∑|� � | =1. A collection of several
� �∈��,�� �
qubits is often referred to as a quantum register.
An important theory within the field of quantum information is the no-cloning theorem, which states that it is
impossible to make a perfect independent copy of an arbitrary unknown quantum state. In more formal terms, if given
an arbitrary qubit |�⟩ and a fixed qubit, say, |0⟩, it is impossible to make a copy of |�⟩ and "store" it in the qubit |0⟩. In
mathematical terms, there exists no quantum operator � such that ��|�⟩|0⟩)=|�⟩|�⟩ for every qubit |�⟩.
5.3 Cryptographic Hash Functions
A cryptographic hash function is a one-way function that maps an arbitrarily long bitstring - also referred to as a
message - to a fixed-size bitstring called a hash digest. Additionally, cryptographic hash functions have three important
properties:
1) Pre-image resistance: Given a hash digest, it is computationally infeasible to find a message that maps to it.
2) Second pre-image resistance: Given a message and its hash digest, it is computationally infeasible to find
another message that maps to the same hash digest.
3) Collision resistance: It is computationally infeasible to find two different messages that map to the same hash
digest.
ETSI
15 ETSI TR 103 965 V1.1.1 (2024-10)
5.4 Proofs of Knowledge
5.4.0 Introduction
An interactive proof-of-knowledge protocol involves two entities: a prover � and a verifier �. The goal of the protocol
is to convince the verifier � that the prover � knows a certain secret with certain properties. In a trivial
proof-of-knowledge protocol, the prover would simply send the secret to the verifier, proving that they know the sec
...