Paper 2023/419

Asynchronous Remote Key Generation for Post-Quantum Cryptosystems from Lattices

Nick Frymann, University of Surrey
Daniel Gardham, University of Surrey
Mark Manulis, Universität der Bundeswehr München

Asynchronous Remote Key Generation (ARKG), introduced by Frymann et al. at CCS 2020, allows for the generation of unlinkable public keys by third parties, for which corresponding private keys may be later learned only by the key pair's legitimate owner. These key pairs can then be used in common public-key cryptosystems, including signatures, PKE, KEMs, and schemes supporting delegation, such as proxy signatures. The only known instance of ARKG generates discrete-log-based keys. In this paper, we introduce new ARKG constructions for lattice-based cryptosystems. The key pairs generated using our ARKG scheme can be applied to lattice-based signatures and KEMs, which have recently been selected for standardisation in the NIST PQ process, or as alternative candidates. In particular, we address challenges associated with the noisiness of lattice hardness assumptions, which requires a new generalised definition of ARKG correctness, whilst preserving the security and privacy properties of the former instantiation. Our ARKG construction uses key encapsulation techniques by Brendel et al. (SAC 2020) coined Split KEMs. As an additional contribution, we also show that Kyber (Bos et al., EuroS&P 2018) can be used to construct a Split KEM. The security of our protocol is based on standard LWE assumptions. We also discuss its use with selected candidates from the NIST process and provide an implementation and benchmarks.

Note: Updated citation.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. EuroS&P 2023
Aysynchronous Remote Key GenerationlatticesKEMs
Contact author(s)
daniel gardham @ surrey ac uk
2023-03-31: revised
2023-03-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nick Frymann and Daniel Gardham and Mark Manulis},
      title = {Asynchronous Remote Key Generation for Post-Quantum Cryptosystems from Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2023/419},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.