Paper 2022/703

Proof-of-possession for KEM certificates using verifiable generation

Tim Güneysu, Ruhr University Bochum, German Research Centre for Artificial Intelligence
Philip Hodges
Georg Land, Ruhr University Bochum, German Research Centre for Artificial Intelligence
Mike Ounsworth, Entrust
Douglas Stebila, University of Waterloo
Greg Zaverucha, Microsoft Research

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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
public key infrastructure certificates key encapsulation mechanisms proof of possession zero knowledge proofs
Contact author(s)
tim gueneysu @ rub de
georg land @ rub de
mike ounsworth @ entrust com
dstebila @ uwaterloo ca
gregz @ microsoft com
2022-09-27: revised
2022-06-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tim Güneysu and Philip Hodges and Georg Land and Mike Ounsworth and Douglas Stebila and Greg Zaverucha},
      title = {Proof-of-possession for KEM certificates using verifiable generation},
      howpublished = {Cryptology ePrint Archive, Paper 2022/703},
      year = {2022},
      doi = {10.1145/3548606.3560560},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.