Search papers, labs, and topics across Lattice.
This paper introduces verifiable random sampling (VRS), a novel approach that enhances the security of random functions by allowing for publicly verifiable outputs while mitigating risks of collusion and precomputation attacks. By leveraging random quantum circuit sampling (RCS), the authors demonstrate how VRS can produce samples statistically close to a target distribution, ensuring both freshness and verifiability in multiparty protocols. The construction is rigorously modeled and proven secure within the constructive cryptography framework, paving the way for more robust applications requiring unpredictable randomness.
VRS guarantees fresh, verifiable randomness in multiparty protocols, thwarting collusion and precomputation attacks.
Verifiable random functions (VRF) underpin a wide range of applications that require publicly verifiable evaluations of a pseudorandom function on a given input. However, once the public key is published, the induced function is fixed and is a deterministic function of the input. This determinism can enable collusion and grinding-style attacks in which adversaries precompute and selectively exploit favorable input-output pairs. To address these limitations, we introduce the formal notion of verifiable random sampling (VRS). We propose a concrete VRS construction based on random quantum circuit sampling (RCS) executable on today's quantum computing devices. VRS supports multiparty protocols in which the verifier's final output is a sample that is statistically close to a specified target distribution, while remaining publicly verifiable. We model the construction and prove its security within the constructive cryptography (CC) framework, thereby ensuring composability with other cryptographic protocols. Overall, our results provide a mechanism for verifiable random sampling that simultaneously guarantees sample freshness and public verifiability, enabling applications that require unpredictable, fresh randomness while preserving fairness through public verifiability.
