CAPYBARA and TSUBAKI: Verifiable Random Functions from Group Actions and Isogenies

Yi-Fu Lai

Paper 2023/182

CAPYBARA and TSUBAKI: Verifiable Random Functions from Group Actions and Isogenies

Yi-Fu Lai

, University of Auckland, Ruhr University Bochum

Abstract

In this work, we propose two post-quantum verifiable random functions (VRFs) constructions based on group actions and isogenies, one of which is based on the standard DDH assumption. VRF is a cryptographic tool that enables a user to generate a pseudorandom output along with a publicly verifiable proof. The residual pseudorandomness of VRF ensures the pseudorandomness of unrevealed inputs, even if an arbitrary number of outputs and proofs are revealed. Furthermore, it is infeasible to generate proofs to validate distinct values as outputs for the same input. In practical applications, VRFs have a wide range of uses, including in DNSSEC protocols, blockchain and cryptocurrency. Currently, most VRF constructions rely on elliptic curve cryptography (ECC), pairing, or Decisional Diffie-Hellman (DDH) type assumptions. These assumptions, however, cannot thwart the threats from quantum adversaries. In light of this, there is a growing need for post-quantum VRFs, which are currently less widely developed in the literature. We contribute to the study by presenting two VRF proposals from group actions and isogenies. Our constructions are fairly simple and derived from number-theoretic pseudorandom functions. We present a proof system that allows us to prove the factorization of group actions and set elements, providing a proof for our VRFs. The first one is based on the standard DDH problem. For the proof we introduce a new problem, the master decisional Diffie-Hellman problem over group actions, which we prove to be equivalent to the standard DDH problem. Furthermore, we present a new use of quadratic twists to reduce costs by expanding the input size and relaxing the assumption to the square DDH problem. Additionally, we employ advanced techniques in the isogeny literature to optimize the proof size to 39KB and 34 KB using CSIDH512 without compromising VRF notions. To the best of our knowledge, they are the first two provably secure VRF constructions based on isogenies.

Note: Update: 16 Feb 2023: Correct errors; Include/Update the information of 2022/141; 2022/993; 2023/186 in Sec 1 and Sec 7. Update: 23 Dec 2023: Update information of 2023/1251; improve the wording in the literature review.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Post-quantum cryptography verifiable random functions zero-knowledge proof isogeny cryptography group action
Contact author(s): Yi-Fu Lai @ ruhr-uni-bochum de
History: 2023-12-23: last of 2 revisions; 2023-02-13: received; See all versions
Short URL: https://ia.cr/2023/182
License: CC BY

BibTeX

@misc{cryptoeprint:2023/182,
      author = {Yi-Fu Lai},
      title = {CAPYBARA and TSUBAKI: Verifiable Random Functions from Group Actions and Isogenies},
      howpublished = {Cryptology ePrint Archive, Paper 2023/182},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/182}},
      url = {https://eprint.iacr.org/2023/182}
}