Efficient Certifiable Randomness from a Single Quantum Device
- URL: http://arxiv.org/abs/2204.11353v1
- Date: Sun, 24 Apr 2022 20:32:17 GMT
- Title: Efficient Certifiable Randomness from a Single Quantum Device
- Authors: Urmila Mahadev, Umesh Vazirani, Thomas Vidick
- Abstract summary: We use the leakage resilience properties of the Learning With problem to address the rate of generation of randomness.
Our new protocol can certify $Omega(n)$ fresh bits of randomness in constant rounds.
- Score: 6.531546527140474
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Brakerski et. al [BCM+18] introduced the model of cryptographic testing of a
single untrusted quantum device and gave a protocol for certifiable randomness
generation. We use the leakage resilience properties of the Learning With
Errors problem to address a key issue left open in previous work - the rate of
generation of randomness. Our new protocol can certify $\Omega(n)$ fresh bits
of randomness in constant rounds, where $n$ is a parameter of the protocol and
the total communication is $O(n)$, thus achieving a nearly optimal rate. The
proof that the output is statistically random is conceptually simple and
technically elementary.
Related papers
- Optimization of experimental quantum randomness expansion [0.0]
This work presents a comprehensive analysis of the design and performance optimization of a Quantum Random Number Generator (QRNG) based on Bell inequality violations.
We identify optimal ranges for $gamma$ and $p_Omega$ to balance the trade-off between randomness consumption and net randomness generation.
Our results indicate substantial developments in QRNG implementations and offer higher randomness expansion rates.
arXiv Detail & Related papers (2024-11-07T18:12:58Z) - Local contextuality-based self-tests are sufficient for randomness expansion secure against quantum adversaries [0.0]
We show that local contextuality-based self-tests are sufficient to construct a randomness expansion protocol that is secure against unbounded quantum adversaries.
Our protocol is based on self-testing from non-contextuality inequalities and we prove that our schemeally produces secure random numbers which are $mathcalO(mstepsilon)$-close to uniformly distributed and private.
arXiv Detail & Related papers (2024-09-30T08:31:46Z) - 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) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
We first examine the hardness of solving various search problems by hybrid quantum-classical strategies.
We then construct a hybrid quantum-classical search algorithm and analyze its success probability.
arXiv Detail & Related papers (2023-11-07T04:59:02Z) - A Game-theoretic Approach for Provably-Uniform Random Number Generation in Decentralized Networks [0.6216023343793144]
We provide a protocol for distributed generation of randomness.
It is trustless and generates unbiased random numbers.
It is also tamper-proof and no party can change the output or affect its distribution.
arXiv Detail & Related papers (2023-09-20T12:21:39Z) - Certified Randomness from Quantum Supremacy [5.313318620422295]
We propose an application for near-term quantum devices, namely, generating cryptographically certified random bits.
Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling.
We show that our protocol's output is unpredictable even to a computationally unbounded adversary.
arXiv Detail & Related papers (2023-03-02T23:28:31Z) - 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) - Improved, Deterministic Smoothing for L1 Certified Robustness [119.86676998327864]
We propose a non-additive and deterministic smoothing method, Deterministic Smoothing with Splitting Noise (DSSN)
In contrast to uniform additive smoothing, the SSN certification does not require the random noise components used to be independent.
This is the first work to provide deterministic "randomized smoothing" for a norm-based adversarial threat model.
arXiv Detail & Related papers (2021-03-17T21:49:53Z) - Coherent randomized benchmarking [68.8204255655161]
We show that superpositions of different random sequences rather than independent samples are used.
We show that this leads to a uniform and simple protocol with significant advantages with respect to gates that can be benchmarked.
arXiv Detail & Related papers (2020-10-26T18:00:34Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs"
We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM)
As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
arXiv Detail & Related papers (2020-09-29T08:41:53Z) - Black-Box Certification with Randomized Smoothing: A Functional
Optimization Based Framework [60.981406394238434]
We propose a general framework of adversarial certification with non-Gaussian noise and for more general types of attacks.
Our proposed methods achieve better certification results than previous works and provide a new perspective on randomized smoothing certification.
arXiv Detail & Related papers (2020-02-21T07:52:47Z)
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.