Quantum one-way permutation over the finite field of two elements |
| |
Authors: | Alexandre de Castro |
| |
Affiliation: | 1.Laboratório de Matemática Computacional, Centro Nacional de Pesquisa Tecnológica em Informática para a Agricultura (Embrapa Informática Agropecuária),Empresa Brasileira de Pesquisa Agropecuária,Campinas,Brazil |
| |
Abstract: | In quantum cryptography, a one-way permutation is a bounded unitary operator (U:mathcal {H} rightarrow mathcal {H}) on a Hilbert space (mathcal {H}) that is easy to compute on every input, but hard to invert given the image of a random input. Levin (Probl Inf Transm 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 hbox {GF}_{{2}^{Vert xVert }}), is an information-theoretically secure operator within a polynomial factor. Here, we show that Levin’s one-way 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|