Paper 2023/451

Non-interactive VSS using Class Groups and Application to DKG

Aniket Kate, Purdue University West Lafayette, Supra Research
Easwar Vivek Mangipudi, Supra Research
Pratyay Mukherjee, Supra Research
Hamza Saleem, Supra Research, University of Southern California
Sri Aravinda Krishnan Thyagarajan, University of Sydney

We put forward a non-interactive verifiable secret sharing (NI-VSS) scheme using class groups – we call it cgVSS. Our construction follows the standard framework of encrypting the shares to a set of recipients and generating a non-interactive proof of correct sharing. However, as opposed to prior works, such as Groth’s [Eprint 2021], or Gentry et al.’s [Eurocrypt 2022], we do not require any range proof - this is possible due to the unique structure of class groups, that enables efficient encryption/decryption of large field elements in the exponent of an ElGamal-style encryption scheme. Importantly, this is possible without destroying the additive holomorphic structure, which is required to make the proof-of-correctness highly efficient. This approach not only substantially simplifies the NI-VSS process, but also outperforms the state-of-art schemes significantly. For example, our implementation shows that for a 150 node system cgVSS outperforms (a simplified implementation of) Groth’s protocol in overall communication complexity by 5.6x, about 9.3 − 9.7x in the dealer time and 2.4 − 2.7x in the receiver time per node. Additionally, we formalize the notion of public verifiability, which enables anyone, possibly outside the participants, to verify the correctness of the dealing. In fact, we re-interpret the notion of public verifiability and extend it to the setting when potentially all recipients may be corrupt and yet can not defy public verifiability – to distinguish from state-of-art, we call this strong public verifiability. Our formalization uses the universal composability framework. Finally, through a generic transformation, we obtain a non-interactive distributed key generation (NI-DKG) scheme for threshold systems, where the secret key is the discrete log of the public key. Our security analysis in the VSS-hybrid model uses a formalization that considers a (strong) public verifiability notion for DKG, even when more than threshold parties are corrupt. Instantiating with cgVSS we obtain a NI-DKG scheme from class groups – we call it cgDKG.

Available format(s)
Cryptographic protocols
Publication info
Verifiable secret sharingNon-interactive VSSClass Groups
Contact author(s)
e mangipudi @ supraoracles com
pratyay85 @ gmail com
hamzasaleemzpr @ gmail com
t srikrishnan @ gmail com
2024-06-30: last of 6 revisions
2023-03-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aniket Kate and Easwar Vivek Mangipudi and Pratyay Mukherjee and Hamza Saleem and Sri Aravinda Krishnan Thyagarajan},
      title = {Non-interactive {VSS} using Class Groups and Application to {DKG}},
      howpublished = {Cryptology ePrint Archive, Paper 2023/451},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.