@article {2627, title = {Efficient Simulation of Random States and Random Unitaries}, journal = {In: Canteaut A., Ishai Y. (eds) Advances in Cryptology {\textendash} EUROCRYPT 2020. Lecture Notes in Computer Science, Springer, Cham}, volume = {12107}, year = {2020}, month = {5/1/2020}, pages = {759-787}, type = {inproceedings}, abstract = {

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.

}, doi = {https://doi.org/10.1007/978-3-030-45727-3_26}, author = {Gorjan Alagic and Christian Majenz and Alexander Russell} } @article {2628, title = {Quantum-Access-Secure Message Authentication via Blind-Unforgeability}, journal = {In: Canteaut A., Ishai Y. (eds) Advances in Cryptology {\textendash} EUROCRYPT 2020. Lecture Notes in Computer Science, Springer, Cham}, volume = {12-17}, year = {2020}, month = {5/1/2020}, pages = {788-817 }, type = {inproceedings}, abstract = {

Formulating 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.

}, doi = {https://doi.org/10.1007/978-3-030-45727-3_27}, author = {Gorjan Alagic and Christian Majenz and Alexander Russell and Fang Song} } @article {2308, title = {Quantum-secure message authentication via blind-unforgeability}, year = {2018}, abstract = {

Formulating 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.\ 

}, url = {https://arxiv.org/abs/1803.03761}, author = {Gorjan Alagic and Christian Majenz and Alexander Russell and Fang Song} } @article {2621, title = {Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts}, journal = {In: Coron JS., Nielsen J. (eds) Advances in Cryptology {\textendash} EUROCRYPT 2017. Lecture Notes in Computer Science, Springer, Cham}, volume = {10212}, year = {2017}, abstract = {

Recent 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.

}, doi = {https://doi.org/10.1007/978-3-319-56617-7_3}, author = {Gorjan Alagic and Alexander Russell} } @article {2617, title = {Spectral Concentration of Positive Functions on Compact Groups}, journal = {Journal of Fourier Analysis and Applications }, volume = {17}, year = {2011}, pages = {355-373}, abstract = {

The 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.

}, doi = {https://doi.org/10.1007/s00041-011-9174-5}, author = {Gorjan Alagic and Alexander Russell} } @article {2616, title = {Quantum Algorithms for Simon{\textquoteright}s Problem over Nonabelian Groups}, journal = {ACM Trans. Algorithms}, volume = {6}, year = {2010}, abstract = {

Daniel Simon\&$\#$39;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\&$\#$39;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\&$\#$39;s problem, each mi is either the identity or the conjugate of a known element m which satisfies κ(m) = \−κ(1) for some κ \∈ Gh. Our approach combines the general idea behind Kuperberg\&$\#$39;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.

}, doi = {https://doi.org/10.1145/1644015.1644034}, author = {Gorjan Alagic and Cristopher Moore and Alexander Russell} } @article {2615, title = {Uncertainty principles for compact groups}, journal = {Illinois J. Math. }, volume = {52}, year = {2008}, pages = {1315-1324}, abstract = {

We 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.

}, doi = {doi:10.1215/ijm/1258554365}, url = {http://projecteuclid.org/euclid.ijm/1258554365}, author = {Gorjan Alagic and Alexander Russell} } @article {2613, title = {Quantum Algorithms for Simon{\textquoteright}s Problem over General Groups}, journal = {SODA {\textquoteright}07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms}, year = {2007}, month = {1/25/2007}, pages = {1217{\textendash}1224}, abstract = {

Daniel Simon\&$\#$39;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\&$\#$39;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\&$\#$39;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\&$\#$39;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.

}, doi = {https://dl.acm.org/doi/10.5555/1283383.1283514}, url = {https://arxiv.org/abs/quant-ph/0603251}, author = {Gorjan Alagic and Cristopher Moore and Alexander Russell} } @article {2614, title = {Quantum Computing and the Hunt for Hidden Symmetry}, journal = {Bulletin of the EATCS}, volume = {93}, year = {2007}, pages = {53-75}, abstract = {

In 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\&$\#$39;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

}, url = {https://pdfs.semanticscholar.org/08f7/abc04ca0bd38c1351ee1179139d8b0fc172b.pdf?_ga=2.210619804.800377824.1595266095-1152452310.1595266095}, author = {Gorjan Alagic and Alexander Russell} } @article {2612, title = {Decoherence in Quantum Walks on the Hypercube }, journal = {Phys. Rev. A }, volume = {76}, year = {2005}, month = {12/5/2005}, pages = {062304}, abstract = {

We 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.

}, doi = {https://doi.org/10.1103/PhysRevA.72.062304}, url = {https://arxiv.org/abs/quant-ph/0501169}, author = {Gorjan Alagic and Alexander Russell} } @article {2611, title = {Strong Fourier Sampling Fails over Gn}, year = {2005}, month = {11/7/2005}, abstract = {

We 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.

}, url = {https://arxiv.org/abs/quant-ph/0511054}, author = {Gorjan Alagic and Cristopher Moore and Alexander Russell} }