Verifiable Random Sampling

• URL: http://arxiv.org/abs/2607.26734v1
• Date: Wed, 29 Jul 2026 10:27:08 GMT
• Title: Verifiable Random Sampling
• Abstract summary: Verifiable random functions (VRF) underpin a wide range of applications that require publicly verifiable evaluations of a pseudorandom function on a given input.<n>We introduce the formal notion of verifiable random sampling (VRS)<n>VRS supports multiparty protocols in which the verifier's final output is a sample that is statistically close to a specified target distribution.
• Score: 0.6085546687631446
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Continuous-Variable Source-Independent Quantum Random Number Generation with General POVMs [9.797328475012575]
  Continuous-variable source-independent quantum random number generators offer the highest generation rates among semi-device-independent protocols.<n>We propose a rigorous security proof framework that accommodates general, infinite-dimensional positive-operator-valued measures.<n>We experimentally validate our protocol on an optical platform using vacuum and weak coherent states, achieving a maximum secure randomness extraction of 1.11 bits per sample.
  arXiv  Detail & Related papers  (2026-06-30T01:48:49Z)
• Towards Verifiable AI with Lightweight Cryptographic Proofs of Inference [3.3323431541048385]
  We present a verification framework and protocol that replaces full proofs with a lightweight, sampling-based approach.<n>We formalize the conditions under which trace separation between functionally dissimilar models can be leveraged to argue the security of verifiable inference protocols.<n>Our approach reduces proving times by several orders of magnitude compared to state-of-the-art cryptographic proof systems.
  arXiv  Detail & Related papers  (2026-03-19T15:24:27Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Improvements on Device Independent and Semi-Device Independent Protocols of Randomness Expansion [0.0]
  Device Independent (DI) and Semi-Device Independent (semi-DI) protocols of randomness expansion are discussed. We introduce enhanced DI and semi-DI protocols that surpass existing ones in terms of output randomness rate, security, or in some instances, both. A notable contribution is the introduction of randomness expansion protocols that recycle input randomness, significantly enhancing finite round randomness rates for DI protocols based on the CHSH inequality violation.
  arXiv  Detail & Related papers  (2023-11-22T17:03:04Z)
• A privacy-preserving publicly verifiable quantum random number generator [48.7576911714538]
  We report the implementation of an entanglement-based protocol that allows a third party to publicly perform statistical tests without compromising the privacy of the random bits. limitations on computing power can restrict an end-user's ability to perform such verification.
  arXiv  Detail & Related papers  (2023-05-18T12:13:48Z)
• Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractions [59.605246463200736]
  We present a novel controller synthesis method that does not rely on any explicit representation of the noise distributions. First, we abstract the continuous control system into a finite-state model that captures noise by probabilistic transitions between discrete states. We use state-of-the-art verification techniques to provide guarantees on the interval Markov decision process and compute a controller for which these guarantees carry over to the original control system.
  arXiv  Detail & Related papers  (2023-01-04T10:40:30Z)
• Testing randomness of series generated in Bell's experiment [62.997667081978825]
  We use a toy fiber optic based setup to generate binary series, and evaluate their level of randomness according to Ville principle. Series are tested with a battery of standard statistical indicators, Hurst, Kolmogorov complexity, minimum entropy, Takensarity dimension of embedding, and Augmented Dickey Fuller and Kwiatkowski Phillips Schmidt Shin to check station exponent. The level of randomness of series obtained by applying Toeplitz extractor to rejected series is found to be indistinguishable from the level of non-rejected raw ones.
  arXiv  Detail & Related papers  (2022-08-31T17:39:29Z)
• Error-based Knockoffs Inference for Controlled Feature Selection [49.99321384855201]
  We propose an error-based knockoff inference method by integrating the knockoff features, the error-based feature importance statistics, and the stepdown procedure together. The proposed inference procedure does not require specifying a regression model and can handle feature selection with theoretical guarantees.
  arXiv  Detail & Related papers  (2022-03-09T01:55:59Z)
• Certified Random Number Generation from Quantum Steering [1.0820909926464386]
  Certified randomness protocols have been developed which remove the need for trust in devices by taking advantage of nonlocality. Here, we use a photonic platform to implement our protocol, which operates in the quantum steering scenario. We demonstrate an approach for a steering-based generator of public or private randomness, and the first generation of certified random bits, with the detection loophole closed.
  arXiv  Detail & Related papers  (2021-11-18T03:49:43Z)
• Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noise [59.47042225257565]
  We present a novel planning method that does not rely on any explicit representation of the noise distributions. First, we abstract the continuous system into a discrete-state model that captures noise by probabilistic transitions between states. We capture these bounds in the transition probability intervals of a so-called interval Markov decision process (iMDP)
  arXiv  Detail & Related papers  (2021-10-25T06:18:55Z)
• Certified Randomness From Steering Using Sequential Measurements [0.0]
  A single entangled two-qubit pure state can be used to produce arbitrary amounts of certified randomness. Motivated by these difficulties in the device-independent setting, we consider the scenario of one-sided device independence. We show how certain aspects of previous work can be adapted to this scenario and provide theoretical bounds on the amount of randomness which can be certified.
  arXiv  Detail & Related papers  (2020-08-03T08:18:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.