Paper 2017/381

Quantum one-way permutation over the finite field of two elements

Alexandre de Castro

Abstract

In quantum cryptography, a one-way permutation is a bounded unitary operator $U: H \mapsto H$ on a Hilbert space $H$ that is easy to compute on every input, but hard to invert given the image of a random input. Levin [Probl. Inf. Transm., vol. 39 (1): 92-103 (2003)] has conjectured that the unitary transformation $g(a,x) = (a,f(x)+ax)$, where $f$ is any length-preserving function and $a,x \in GF_{2^{||x||}}$, is an information-theoretically secure operator within a polynomial factor. Here, we show that Levin’s oneway permutation is provably secure because its output values are four maximally entangled two-qubit states, and whose probability of factoring them approaches zero faster than the multiplicative inverse of any positive polynomial $poly(x)$ over the Boolean ring of all subsets of $x$. Our results demonstrate through well-known theorems that existence of classical one-way functions implies existence of a universal quantum one-way permutation that cannot be inverted in subexponential time in the worst case.

Note: Journal reference: Quantum Information Processing (2017). 16:149. DOI: 10.1007/s11128-017-1599-6

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Quantum Information Processing (2017) 16:149
DOI
10.1007/s11128-017-1599-6
Keywords
Quantum one-way permutationCHSH inequalityControlled NOT gateNegligible probability(Pseudo)randomness
Contact author(s)
alexandre castro @ embrapa br
History
2017-05-01: received
Short URL
https://ia.cr/2017/381
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/381,
      author = {Alexandre de Castro},
      title = {Quantum one-way permutation over the finite field of two elements},
      howpublished = {Cryptology ePrint Archive, Paper 2017/381},
      year = {2017},
      doi = {10.1007/s11128-017-1599-6},
      note = {\url{https://eprint.iacr.org/2017/381}},
      url = {https://eprint.iacr.org/2017/381}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.