Douglas Stebila

Proof-of-possession for KEM certificates using verifiable generation

Performance and proof size for 128-bit security

Abstract

Certificate authorities in public key infrastructures typically require entities to prove possession of the secret key corresponding to the public key they want certified. While this is straightforward for digital signature schemes, the most efficient solution for public key encryption and key encapsulation mechanisms (KEMs) requires an interactive challenge-response protocol, requiring a departure from current issuance processes. In this work we investigate how to non-interactively prove possession of a KEM secret key, specifically for lattice-based KEMs, motivated by the recently proposed KEMTLS protocol which replaces signature-based authentication in TLS 1.3 with KEM-based authentication. Although there are various zero-knowledge (ZK) techniques that can be used to prove possession of a lattice key, they yield large proofs or are inefficient to generate. We propose a technique called verifiable generation, in which a proof of possession is generated at the same time as the key itself is generated. Our technique is inspired by the Picnic signature scheme and uses the multi-party-computation-in-the-head (MPCitH) paradigm; this similarity to a signature scheme allows us to bind attribute data to the proof of possession, as required by certificate issuance protocols. We show how to instantiate this approach for two lattice-based KEMs in Round 3 of the NIST post-quantum cryptography standardization project, Kyber and FrodoKEM, and achieve reasonable proof sizes and performance. Our proofs of possession are faster and an order of magnitude smaller than the previous best MPCitH technique for knowledge of a lattice key, and in size-optimized cases can be comparable to even state-of-the-art direct lattice-based ZK proofs for Kyber. Our approach relies on a new result showing the uniqueness of Kyber and FrodoKEM secret keys, even if the requirement that all secret key components are small is partially relaxed, which may be of independent interest for improving efficiency of zero-knowledge proofs for other lattice-based statements.

Keywords: public key infrastructure, certificates, key encapsulation mechanisms, proof of possession, zero knowledge proofs, post-quantum cryptography

Reference

Tim Güneysu, Philip Hodges, Georg Land, Mike Ounsworth, Douglas Stebila, Greg Zaverucha. Proof-of-possession for KEM certificates using verifiable generation. In Cas Cremers, Elaine Shi, editors, Proc. 29th ACM Conference on Computer and Communications Security (CCS) 2022. ACM, November 2022. © The authors.

Download

Code

• Software implementation and parameter estimation scripts

BibTeX

@misc{CCS:GHLOSZ22,
 	Author = {Tim G{" u}neysu and Philip Hodges and Georg Land and Mike Ounsworth and Douglas Stebila and Greg Zaverucha},
 	Booktitle = {Proc. 29th ACM Conference on Computer and Communications Security (CCS) 2022},
 	Doi = {10.1145/3548606.3560560},
 	Editor = {Cas Cremers and Elaine Shi},
 	Month = {November},
 	Publisher = {ACM},
 	Title = {Proof-of-possession for {KEM} certificates using verifiable generation},
 	Year = {2022}
 }

Funding

• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146
• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2022-03187
• NLnet Assure grant for the project "Standardizing KEMTLS"
• German Research Foundation under Germany’s Excellence Strategy – EXC 2092 CASA – 390781972
• H2020 project PROMETHEUS (grant agreement ID 780701)
• Federal Ministry of Education and Research of Germany through the QuantumRISC (16KIS1038) and PQC4Med (16KIS1044) projects