Paper 2023/456

Generalised Asynchronous Remote Key Generation for Pairing-based Cryptosystems

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

Asynchronous Remote Key Generation (ARKG, introduced in ACM CCS 2020) allows for a party to create public keys for which corresponding private keys may be later computed by another intended party only. ARKG can be composed with standard public-key cryptosystems and has been used to construct a new class of privacy-preserving proxy signatures. The original construction of ARKG, however, generates discrete logarithm key pairs of the form $(x, g^x)$. In this paper we define a generic approach for building ARKG schemes which can be applied to a wide range of pairing-based cryptosystems. This construction is based on a new building block which we introduce and call Asymmetric Key Generation (AKG) along with its extension $\phi$-AKG where $\phi$ is a suitable mapping for capturing different key structures and types of pairings. We show that appropriate choice of $\phi$ allows us to create a secure ARKG scheme compatible with any key pair that is secure under the Uber assumption (EUROCRYPT 2004). To demonstrate the extensive range of our general approach, we construct ARKG schemes for a number of popular pairing-based primitives: Boneh-Lynn-Shacham (JoC 2004), Camenisch-Lysyanskaya (CRYPTO 2004), Pointcheval-Sanders (CT-RSA 2016), Waters (EUROCRYPT 2005) signatures and structure-preserving signatures on equivalence classes (ASIACRYPT 2014). For each scheme we give an implementation and provide benchmarks that show the feasibility of our techniques.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. International Conference on Applied Cryptography and Network Security (ACNS 2023)
Asynchronous Remote Key GenerationPairings
Contact author(s)
n frymann @ surrey ac uk
daniel gardham @ surrey ac uk
mark @ manulis eu
hugo nartz @ unibw de
2023-03-31: approved
2023-03-29: received
See all versions
Short URL
Creative Commons Attribution


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