Related papers: Pseudorandom unitaries with non-adaptive security

Pseudorandom unitaries with non-adaptive security

URL: http://arxiv.org/abs/2402.14803v1
Date: Thu, 22 Feb 2024 18:56:37 GMT
Title: Pseudorandom unitaries with non-adaptive security
Authors: Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen
Abstract summary: We present a PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions.
Score: 43.15464425520681
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time algorithm with query access to the unitary. We present a simple PRU construction that is a concatenation of a random Clifford unitary, a pseudorandom binary phase operator, and a pseudorandom permutation operator. We prove that this PRU construction is secure against non-adaptive distinguishers assuming the existence of quantum-secure one-way functions. This means that no efficient quantum query algorithm that is allowed a single application of $U^{\otimes \mathrm{poly}(n)}$ can distinguish whether an $n$-qubit unitary $U$ was drawn from the Haar measure or our PRU ensemble. We conjecture that our PRU construction remains secure against adaptive distinguishers, i.e. secure against distinguishers that can query the unitary polynomially many times in sequence, not just in parallel.

Related papers

How to Construct Random Unitaries [2.8237889121096034]
We prove that PRUs exist, assuming that any quantum-secure one-way function exists. We prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer.
arXiv Detail & Related papers (2024-10-14T03:07:36Z)
Error Correction Capabilities of Non-Linear Cryptographic Hash Functions [56.368766255147555]
Linear hashes are known to possess error-correcting capabilities. In most applications, non-linear hashes with pseudorandom outputs are utilized instead. We show that non-linear hashes might also exhibit good error-correcting capabilities.
arXiv Detail & Related papers (2024-05-02T17:26:56Z)
Simple constructions of linear-depth t-designs and pseudorandom unitaries [40.72668922727092]
Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. Two different notions of derandomisation have emerged: $t-designs are random unitaries that reproduce the first $t moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random.
arXiv Detail & Related papers (2024-04-19T06:13:02Z)
Crooked indifferentiability of the Feistel Construction [53.572703605492904]
The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks.
arXiv Detail & Related papers (2024-04-15T04:29:24Z)
Real-Valued Somewhat-Pseudorandom Unitaries [5.294604210205507]
We show that even though real-valued unitaries cannot be completely pseudorandom, we can still obtain some pseudorandom properties without giving up on a real-valued unitary. Our analysis shows that an even simpler construction: applying a random (binary) phase followed by a random computational-basis permutation, would suffice.
arXiv Detail & Related papers (2024-03-25T12:37:50Z)
A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles. We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making unboundedly many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense.
arXiv Detail & Related papers (2024-01-25T17:13:51Z)
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)
On the Connection Between Quantum Pseudorandomness and Quantum Hardware Assumptions [1.4174475093445233]
This paper addresses the questions related to the connections between the quantum pseudorandomness and quantum hardware assumptions. We show that the efficient pseudorandom quantum states (PRS) are sufficient to construct the challenge set for the universally unforgeable qPUF. As an application of our results, we show that the efficiency of an existing qPUF-based client-server identification protocol can be improved without losing the security requirements.
arXiv Detail & Related papers (2021-10-22T11:55:06Z)
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)

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