01905nas a2200157 4500008004100000245006300041210006300104260001300167300001200180490001000192520138200202100001901584700002201603700002301625856009901648 2020 eng d00aEfficient Simulation of Random States and Random Unitaries0 aEfficient Simulation of Random States and Random Unitaries c5/1/2020 a759-7870 v121073 a
We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access.
This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that t-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs.
In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar-random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error.
These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects.
1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander uhttps://www.quics.umd.edu/publications/efficient-simulation-random-states-and-random-unitaries02359nas a2200169 4500008004100000245007400041210006900115260001300184300001300197490001000210520178100220100001902001700002202020700002302042700001502065856010902080 2020 eng d00aQuantum-Access-Secure Message Authentication via Blind-Unforgeability0 aQuantumAccessSecure Message Authentication via BlindUnforgeabili c5/1/2020 a788-817 0 v12-173 aFormulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of “predicting an unqueried value” when the adversary can query in quantum superposition.
We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use “partially blinded” oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUF-CMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantum-query-secure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the “hash-and-MAC” paradigm and the Lamport one-time digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantum-secure hash functions called Bernoulli-preserving.
Finally, we demonstrate that blind unforgeability is strictly stronger than a previous definition of Boneh and Zhandry [EUROCRYPT ’13, CRYPTO ’13] and resolve an open problem concerning this previous definition by constructing an explicit function family which is forgeable yet satisfies the definition.
1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander1 aSong, Fang uhttps://www.quics.umd.edu/publications/quantum-access-secure-message-authentication-blind-unforgeability02448nas a2200133 4500008004100000245006700041210006500108520202500173100001902198700002202217700002302239700001502262856003702277 2018 eng d00aQuantum-secure message authentication via blind-unforgeability0 aQuantumsecure message authentication via blindunforgeability3 aFormulating and designing unforgeable authentication of classical messages in the presence of quantum adversaries has been a challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of "predicting an unqueried value" when the adversary can query in quantum superposition. In this work, we uncover serious shortcomings in existing approaches, and propose a new definition. We then support its viability by a number of constructions and characterizations. Specifically, we demonstrate a function which is secure according to the existing definition by Boneh and Zhandry, but is clearly vulnerable to a quantum forgery attack, whereby a query supported only on inputs that start with 0 divulges the value of the function on an input that starts with 1. We then propose a new definition, which we call "blind-unforgeability" (or BU.) This notion matches "intuitive unpredictability" in all examples studied thus far. It defines a function to be predictable if there exists an adversary which can use "partially blinded" oracle access to predict values in the blinded region. Our definition (BU) coincides with standard unpredictability (EUF-CMA) in the classical-query setting. We show that quantum-secure pseudorandom functions are BU-secure MACs. In addition, we show that BU satisfies a composition property (Hash-and-MAC) using "Bernoulli-preserving" hash functions, a new notion which may be of independent interest. Finally, we show that BU is amenable to security reductions by giving a precise bound on the extent to which quantum algorithms can deviate from their usual behavior due to the blinding in the BU security experiment.
1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander1 aSong, Fang uhttps://arxiv.org/abs/1803.0376102297nas a2200121 4500008004100000245006900041210006700110490001000177520184100187100001902028700002302047856010502070 2017 eng d00aQuantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts0 aQuantumSecure SymmetricKey Cryptography Based on Hidden Shifts0 v102123 aRecent results of Kaplan et al., building on work by Kuwakado and Morii, have shown that a wide variety of classically-secure symmetric-key cryptosystems can be completely broken by quantum chosen-plaintext attacks (qCPA). In such an attack, the quantum adversary has the ability to query the cryptographic functionality in superposition. The vulnerable cryptosystems include the Even-Mansour block cipher, the three-round Feistel network, the Encrypted-CBC-MAC, and many others.
In this article, we study simple algebraic adaptations of such schemes that replace (Z/2)n addition with operations over alternate finite groups—such as Z/2n —and provide evidence that these adaptations are qCPA-secure. These adaptations furthermore retain the classical security properties and basic structural features enjoyed by the original schemes.
We establish security by treating the (quantum) hardness of the well-studied Hidden Shift problem as a cryptographic assumption. We observe that this problem has a number of attractive features in this cryptographic context, including random self-reducibility, hardness amplification, and—in many cases of interest—a reduction from the “search version” to the “decisional version.” We then establish, under this assumption, the qCPA-security of several such Hidden Shift adaptations of symmetric-key constructions. We show that a Hidden Shift version of the Even-Mansour block cipher yields a quantum-secure pseudorandom function, and that a Hidden Shift version of the Encrypted CBC-MAC yields a collision-resistant hash function. Finally, we observe that such adaptations frustrate the direct Simon’s algorithm-based attacks in more general circumstances, e.g., Feistel networks and slide attacks.
1 aAlagic, Gorjan1 aRussell, Alexander uhttps://www.quics.umd.edu/publications/quantum-secure-symmetric-key-cryptography-based-hidden-shifts01537nas a2200133 4500008004100000245006700041210006700108300001200175490000700187520106700194100001901261700002301280856010001303 2011 eng d00aSpectral Concentration of Positive Functions on Compact Groups0 aSpectral Concentration of Positive Functions on Compact Groups a355-3730 v173 aThe problem of understanding the Fourier-analytic structure of the cone of
positive functions on a group has a long history. In this article, we develop the first
quantitative spectral concentration results for such functions over arbitrary compact
groups. Specifically, we describe a family of finite, positive quadrature rules for the
Fourier coefficients of band-limited functions on compact groups. We apply these
quadrature rules to establish a spectral concentration result for positive functions:
given appropriately nested band limits A ⊂ B ⊂ G, we prove a lower bound on the
fraction of L2-mass that any B-band-limited positive function has in A. Our bounds
are explicit and depend only on elementary properties of A and B; they are the first
such bounds that apply to arbitrary compact groups. They apply to finite groups as
a special case, where the quadrature rule is given by the Fourier transform on the
smallest quotient whose dual contains the Fourier support of the function.
Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding “hidden shifts” of Z2n provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m1,…,mn) ∈ Gn from an oracle f with the property that f(x ⋅ y) = f(x) ⇔ y ∈ {1, m}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form Gn, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two.
Although groups of the form Gn have a simple product structure, they share important representation--theoretic properties with the symmetric groups Sn, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called “standard method” requires highly entangled measurements on the tensor product of many coset states.
In this article, we provide quantum algorithms with time complexity 2O(√n) that recover hidden involutions m = (m1,…mn) ∈ Gn where, as in Simon's problem, each mi is either the identity or the conjugate of a known element m which satisfies κ(m) = −κ(1) for some κ ∈ Ĝ. Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the “missing harmonic” approach of Moore and Russell. These are the first nontrivial HSP algorithms for group families that require highly entangled multiregister Fourier sampling.
1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://www.quics.umd.edu/publications/quantum-algorithms-simon%E2%80%99s-problem-over-nonabelian-groups00912nas a2200133 4500008004100000245004600041210004600087300001400133490000700147520053100154100001900685700002300704856005100727 2008 eng d00aUncertainty principles for compact groups0 aUncertainty principles for compact groups a1315-13240 v523 aWe establish an uncertainty principle over arbitrary compact groups, generalizing several previous results. Specifically, we show that if P and R are operators on L2(G) such that P commutes with projection onto every measurable subset of G and R commutes with left-multiplication by elements of G, then ∥PR∥≤∥P⋅χG∥2∥R∥2, where χG:g↦1 is the characteristic function of G. As a consequence, we show that every nonzero function f in L2(G) satisfies μ(suppf)⋅∑ρ∈G^dρrankf^(ρ)≥1.
1 aAlagic, Gorjan1 aRussell, Alexander uhttp://projecteuclid.org/euclid.ijm/125855436502185nas a2200145 4500008004100000245006500041210006300106260001400169300001600183520173300199100001901932700002201951700002301973856004301996 2007 eng d00aQuantum Algorithms for Simon’s Problem over General Groups0 aQuantum Algorithms for Simon s Problem over General Groups c1/25/2007 a1217–12243 aDaniel Simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Zn2 provided one of the first algebraic problems for which quantum computers are exponentially faster than their classical counterparts. In this paper, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m1,...,mn) ε Gn from an oracle f with the property that f(x) = f(x · y) ⇔ y ε {1, m}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form Gn, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two.
Although groups of the form Gn have a simple product structure, they share important representation-theoretic properties with the symmetric groups Sn, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called "standard method" requires highly entangled measurements on the tensor product of many coset states.
Here we give quantum algorithms with time complexity 2O(√n log n) that recover hidden involutions m = (m1,..., mn) ε Gn where, as in Simon's problem, each mi is either the identity or the conjugate of a known element m and there is a character X of G for which X(m) = - X(1). Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the "missing harmonic" approach of Moore and Russell. These are the first nontrivial hidden subgroup algorithms for group families that require highly entangled multiregister Fourier sampling.
1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/060325102060nas a2200133 4500008004100000245005500041210005500096300001000151490000700161520157400168100001901742700002301761856014201784 2007 eng d00aQuantum Computing and the Hunt for Hidden Symmetry0 aQuantum Computing and the Hunt for Hidden Symmetry a53-750 v933 aIn 1994, Peter Shor gave e cient quantum algorithms for factoring integers and extracting discrete logarithms [20]. If we believe that nature will permit us to faithfully implement our current model of quantum computation, then these algorithms dramatically contradict the Strong Church-Turing thesis. The e ect is heightened by the fact that these algorithms solve computational problems with long histories of attention by the computational and mathematical communities alike. In this article we discuss the branch of quantum algorithms research arising from attempts to generalize the core quantum algorithmic aspects of Shor's algorithms. Roughly, this can be viewed as the problem of generalizing algorithms of Simon [21] and Shor [20], which work over abelian groups, to general nonabelian groups. The article is meant to be self-contained, assuming no knowledge of quantum computing or the representation theory of nite groups. We begin in earnest in Section 2, describing the problem of symmetry nding : given a function f : G → S on a group G, this is the problem of determining {g ∈ G | ∀x, f(x) = f(gx)}, the set of symmetries of f . We switch gears in Section 3, giving a short introduction to the circuit model of quantum computation. The connection between these two sections is eventually established in Section 4, where we discuss the representation theory of nite groups and the quantum Fourier transform a unitary transformation speci cally tuned to the symmetries of the underlying group. Section 4.2 is devoted to Fourier
1 aAlagic, Gorjan1 aRussell, Alexander uhttps://pdfs.semanticscholar.org/08f7/abc04ca0bd38c1351ee1179139d8b0fc172b.pdf?_ga=2.210619804.800377824.1595266095-1152452310.159526609500765nas a2200145 4500008004100000245005100041210005000092260001400142300001100156490000700167520036000174100001900534700002300553856004300576 2005 eng d00aDecoherence in Quantum Walks on the Hypercube 0 aDecoherence in Quantum Walks on the Hypercube c12/5/2005 a0623040 v763 aWe study a natural notion of decoherence on quantum random walks over the hypercube. We prove that in this model there is a decoherence threshold beneath which the essential properties of the hypercubic quantum walk, such as linear mixing times, are preserved. Beyond the threshold, we prove that the walks behave like their classical counterparts.
1 aAlagic, Gorjan1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/050116901168nas a2200133 4500008004100000245004200041210004200083260001400125520078800139100001900927700002200946700002300968856004300991 2005 eng d00aStrong Fourier Sampling Fails over Gn0 aStrong Fourier Sampling Fails over Gn c11/7/20053 aWe present a negative result regarding the hidden subgroup problem on the powers Gn of a fixed group G. Under a condition on the base group G, we prove that strong Fourier sampling cannot distinguish some subgroups of Gn. Since strong sampling is in fact the optimal measurement on a coset state, this shows that we have no hope of efficiently solving the hidden subgroup problem over these groups with separable measurements on coset states (that is, using any polynomial number of single-register coset state experiments). Base groups satisfying our condition include all nonabelian simple groups. We apply our results to show that there exist uniform families of nilpotent groups whose normal series factors have constant size and yet are immune to strong Fourier sampling.
1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/0511054