Welcome to the resource topic for 2023/182
Title:
CAPYBARA and TSUBAKI: Verifiable Random Functions from Group Actions and Isogenies
Authors: Yi-Fu Lai
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.
ePrint: https://eprint.iacr.org/2023/182
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .