ETSI GR QSC 001 V1.1.1 (2016-07)

Quantum-Safe Cryptography (QSC); Quantum-safe algorithmic framework

DGR/QSC-001

General Information

• Status: Published
• Publication Date: 25-Jul-2016
• Technical Committee: QSC - Quantum Safe Cryptography
• Current Stage: 12 - Completion
• Due Date: 22-Jul-2016
• Completion Date: 26-Jul-2016

Standards Content (Sample)

ETSI GR QSC 001 V1.1.1 (2016-07)






GROUP REPORT
Quantum-Safe Cryptography (QSC);
Quantum-safe algorithmic framework

---------------------- Page: 1 ----------------------
2 ETSI GR QSC 001 V1.1.1 (2016-07)



Reference
DGR/QSC-001
Keywords
algorithm, authentication, confidentiality, security

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

Tel.: [phone]  Fax: [phone]

Siret N° 348 623 562 00017 - NAF 742 C
Association à but non lucratif enregistrée à la
Sous-Préfecture de Grasse (06) N° 7803/88

Important notice
The present document can be downloaded from:
http://www.etsi.org/standards-search
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 only prevailing document is the
print of the Portable Document Format (PDF) version kept on a specific network drive within ETSI Secretariat.
Users of the present document should be aware that the document may be subject to revision or change of status.
Information on the current status of this and other ETSI documents is available at
https://portal.etsi.org/TB/ETSIDeliverableStatus.aspx
If you find errors in the present document, please send your comment to one of the following services:
https://portal.etsi.org/People/CommiteeSupportStaff.aspx
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.

© European Telecommunications Standards Institute 2016.
All rights reserved.

TM TM TM
DECT , PLUGTESTS , UMTS and the ETSI logo are Trade Marks of ETSI registered for the benefit of its Members.
TM
3GPP and LTE™ are Trade Marks of ETSI registered for the benefit of its Members and
of the 3GPP Organizational Partners.
GSM® and the GSM logo are Trade Marks registered and owned by the GSM Association.
ETSI

---------------------- Page: 2 ----------------------
3 ETSI GR QSC 001 V1.1.1 (2016-07)
Contents
Intellectual Property Rights . 6
Foreword . 6
Modal verbs terminology . 6
1 Scope . 7
2 References . 7
2.1 Normative references . 7
2.2 Informative references . 7
3 Abbreviations . 16
4 Primitives under consideration . 17
4.1 Introduction . 17
4.2 Primitive families . 17
4.3 Primitive types . 17
4.4 Application-specific or restricted-use cases . 18
4.5 Other mechanisms . 18
5 Assessment framework. 18
5.1 Introduction . 18
5.2 Assessment criteria . 18
5.2.1 Security . 18
5.2.2 Efficiency . 19
5.2.3 Implementation and deployment issues . 19
5.3 Security considerations . 19
5.3.1 Classical security . 19
5.3.2 Quantum security . 19
5.3.3 Provable security . 20
5.3.4 Forward security . 20
5.3.5 Active security . 20
6 Lattice-based primitives . 21
6.1 Introduction . 21
6.2 Provable security . 21
6.3 Key establishment . 22
6.3.1 Key agreement primitives . 22
6.3.1.1 Peikert . 22
6.3.1.2 Zhang et al . 22
6.3.1.3 Ghosh-Kate . 22
6.3.2 Key transport primitives . 22
6.3.2.1 NTRUEncrypt . 22
6.3.3 Other key establishment primitives. 23
6.3.3.1 HIMMO . 23
6.3.4 Forward security . 23
6.3.5 Active security . 23
6.4 Authentication . 23
6.4.1 Fiat-Shamir signatures . 23
6.4.1.1 Lyubashevsky . 23
6.4.1.2 Güneysu-Lyubashevsky-Pöppelmann . 23
6.4.1.3 BLISS . 24
6.4.2 Hash-and-sign signatures . 24
6.4.2.1 NTRU-MLS . 24
6.4.2.2 Aguilar et al . 24
6.4.2.3 Ducas-Lyubashevsky-Prest . 24
6.4.3 Other authentication primitives . 24
6.4.3.1 HIMMO . 24
6.5 Quantum security . 24
7 Multivariate schemes . 25
ETSI

---------------------- Page: 3 ----------------------
4 ETSI GR QSC 001 V1.1.1 (2016-07)
7.1 Introduction . 25
7.2 Provable security . 25
7.3 Key establishment . 26
7.3.1 Key transport primitives . 26
7.3.1.1 Simple Matrix . 26
7.3.1.2 HFE . 26
7.3.1.3 ZHFE . 26
7.3.1.4 Polly Cracker Revisited . 26
7.3.2 Forward security . 26
7.3.3 Active security . 27
7.4 Authentication . 27
7.4.1 Fiat-Shamir signatures . 27
7.4.1.1 Sakumoto-Shirai-Hiwatari . 27
7.4.2 Hash-and-sign signatures . 27
7.4.2.1 Quartz . 27
7.4.2.2 Gui. 27
7.4.2.3 UOV . 27
7.4.2.4 Rainbow . 28
7.5 Quantum security . 28
8 Code-based primitives . 28
8.1 Introduction . 28
8.2 Provable security . 28
8.3 Key establishment . 29
8.3.1 Key transport primitives . 29
8.3.1.1 McEliece and Niederreiter . 29
8.3.1.2 Wild McEliece . 29
8.3.1.3 MDPC McEliece . 29
8.3.1.4 LRPC McEliece . 29
8.3.2 Forward security . 29
8.3.3 Active security . 29
8.4 Authentication . 30
8.4.1 Fiat-Shamir signatures . 30
8.4.1.1 Cayrel et al . 30
8.4.2 Hash-and-sign signatures . 30
8.4.2.1 CFS . 30
8.4.2.2 RankSign . 30
8.5 Quantum security . 30
9 Hash-based primitives . 30
9.1 Introduction . 30
9.2 Provable security . 31
9.3 Authentication . 31
9.3.1 Stateful signatures . 31
9.3.1.1 Merkle . 31
9.3.1.2 XMSS . 31
9.3.2 Stateless signatures . 31
9.3.2.1 SPHINCS . 31
9.4 Quantum security . 32
10 Isogeny-based primitives . 32
10.1 Introduction . 32
10.2 Provable security . 32
10.3 Key establishment . 32
10.3.1 Key agreement primitives . 32
10.3.1.1 Jao-De Feo . 32
10.3.2 Forward security . 33
10.3.3 Active security . 33
10.4 Authentication . 33
10.4.1 Other authentication primitives . 33
10.4.1.1 Jao-Soukharev . 33
10.4.1.2 Sun-Tian-Wang . 33
10.5 Quantum security . 33
ETSI

---------------------- Page: 4 ----------------------
5 ETSI GR QSC 001 V1.1.1 (2016-07)
11 Key length summary . 33
11.1 Introduction . 33
11.2 Key establishment . 34
11.3 Authentication . 35
12 Conclusions . 36
Annex A: Classical key size comparison . 38
A.1 Key establishment . 38
A.2 Authentication . 39
Annex B: Quantum key size comparison . 40
B.1 Key establishment . 40
B.2 Authentication . 41
History . 42

ETSI

---------------------- Page: 5 ----------------------
6 ETSI GR QSC 001 V1.1.1 (2016-07)
Intellectual Property Rights
IPRs essential or potentially essential to the present document may have been declared to ETSI. The information
pertaining to these essential IPRs, if any, is 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 IPR Policy, no investigation, 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.
Foreword
This Group Report (GR) has been produced by ETSI Industry Specification Group (ISG) Quantum-Safe Cryptography
(QSC).
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.

ETSI

---------------------- Page: 6 ----------------------
7 ETSI GR QSC 001 V1.1.1 (2016-07)
1 Scope
The present document gives an overview of the current understanding and best practice in academia and industry about
quantum-safe cryptography (QSC). It focuses on identifying and assessing cryptographic primitives that have been
proposed for efficient key establishment and authentication applications, and which may be suitable for standardization
by ETSI and subsequent use by industry to develop quantum-safe solutions for real-world applications.
QSC is a rapidly growing area of research. There are already academic conference series such as PQC and workshops
have been established by ETSI/IQC [i.1] and NIST. The European Commission has recently granted funding to two
QSC projects under the Horizon 2020 framework: SAFEcrypto [i.2] and PQCrypto [i.3] and [i.4]. The present
document draws on all these research efforts.
The present document will cover three main areas. Clauses 4 and 5 discuss the types of primitives being considered and
describe an assessment framework; clauses 6 to 10 discuss some representative cryptographic primitives; and clause 11
gives a preliminary discussion of key sizes.
2 References
2.1 Normative references
Normative references are not applicable in the present document.
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] ETSI White Paper No. 8 (2015): "Quantum safe cryptography and security".
[i.2] NIST PQC workshop (2015): "SAFEcrypto Project", M. O'Niell.
[i.3] NIST Workshop on Cybersecurity in a Post-Quantum World (2015): "PQCrypto project",
T. Lange.
[i.4] PQCrypto (2015): "Initial recommendations of long-term secure post-quantum systems".
NOTE: Available at http://www.pqcrypto.eu.org/.
[i.5] John Wiley and Sons (1996): "Applied cryptography", B. Schneier.
[i.6] ACM Symposium on Theory of Computing (1977): "Universal classes of hash functions",
J. Carter and M. Wegman.
[i.7] IETF RFC 4120 (2005): "The Kerberos network authentication service (V5)", C. Neuman, T. Yu,
S. Hartman and K. Raeburn.
[i.8] EUROCRYPT (2006): "QUAD: A practical stream cipher with provable security", C. Berbain,
H. Gilbert and J. Patarin.
[i.9] C. Blanchard: "Security for the third generation (3G) mobile system", Information Security
Technical Report, vol. 5, no. 3, pp. 55-65, 2000.
[i.10] IETF RFC 4279 (2005): "Pre-Shared Key Ciphersuites for TLS", P. Eronen and H. Tschofenig.
ETSI

---------------------- Page: 7 ----------------------
8 ETSI GR QSC 001 V1.1.1 (2016-07)
®
[i.11] ZigBee (2015): "Zigbee alliance website".
NOTE 1: Available at http://www.zigbee.org/.
NOTE: 2 ZigBee is an example of a suitable porduct available commercially. This information is given for the
convenience of users of the present document and does not constitute an endorsement by ETSI of this
product.
[i.12] TU Darmstadt (2015): "Lattice challenge".
NOTE: Available at www.latticechallenge.org.
[i.13] Philips (2015): "HIMMO challenge".
NOTE: Available at www.himmo-scheme.com.
[i.14] ACM Communications in Computer Algebra, vol. 49, no. 3, pp. 105-107 (2015): "A multivariate
quadratic challenge toward post-quantum generation cryptography", T. Yasuda, X. Dahan,
Y.-J. Huang, T. Takagi and K. Sakurai.
[i.15] IACR ePrint Archive 2015/374 (2015): "On the impossibility of tight cryptographic reductions",
C. Bader, T. Jager, Y. Li and S. Schäge.
[i.16] PQC (2014): "A note on quantum security for post-quantum cryptography", F. Song.
[i.17] CT-RSA (2003): "Forward-security in private-key cryptography", M. Bellare and B. Yee.
[i.18] draft-ietf-tls-tls13-012 (21 March 2016): "The Transport Layer Security (TLS) protocol version
1.3", E. Resorla.
[i.19] NIST Workshop on Cybersecurity in a Post-Quantum World (2015): "Failure is not an option:
standardization issues for post-quantum key agreement", M. Motley.
[i.20] CRYPTO (1998): "Chosen ciphertext attacks against protocols based on the RSA encryption
standard PKCS#1", D. Bleichenbacher.
[i.21] CRYPTO (2000): "Differential fault attacks on elliptic curve cryptosystems", I. Biehl, B. Meyer
and V. Müller.
[i.22] IACR ePrint Archive 2015/939 (2015): "A decade of lattice cryptography", C. Peikert.
[i.23] CRYPTO (1998): "Public-key cryptosystems from lattice reduction problems", O. Goldreich,
S. Goldwasser and S. Halevi.
[i.24] CT-RSA (2003): "NTRUSign: Digital signatures using the NTRU lattice", J. Hoffstein,
N. Howgrave-Graham, J. Pipher, J. Silverman and W. Whyte.
[i.25] EUROCRYPT (2006): "Learning a parallelepiped: Cryptanalysis of GGH and NTRU signatures",
P. Q. Nguyen and O. Regev.
[i.26] ASIACRYPT (2012): "Learning a zonotope and more: Cryptanalysis of NTRUSign
countermeasures", L. Ducas and P. Q. Nguyen.
[i.27] Designs, Codes and Cryptography (2014): "Finding shortest lattice vectors faster using
...