Universal test for quantum one-way permutations

DOI10.1016/J.TCS.2005.07.036MaRDI QIDQ2575756zbMATHOpenAlexFDO

Authors Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, Raymond H. Putra

Publication date 6 December 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0401013

zbMATH Keywords

Quantum computationOne-way functionComputational cryptographyOne-way permutationUniversal test

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Quantum computation (81P68)

Abstract: The next bit test was introduced by Blum and Micali and proved by Yao to be a universal test for cryptographic pseudorandom generators. On the other hand, no universal test for the cryptographic one-wayness of functions (or permutations) is known, though the existence of cryptographic pseudorandom generators is equivalent to that of cryptographic one-way functions. In the quantum computation model, Kashefi, Nishimura and Vedral gave a sufficient condition of (cryptographic) quantum one-way permutations and conjectured that the condition would be necessary. In this paper, we affirmatively settle their conjecture and complete a necessary and sufficient for quantum one-way permutations. The necessary and sufficient condition can be regarded as a universal test for quantum one-way permutations, since the condition is described as a collection of stepwise tests similar to the next bit test for pseudorandom generators.

Recommendations

• Mathematical Foundations of Computer Science 2004
• Quantum one-way permutation over the finite field of two elements
• Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives
• On quantum one-way permutations
• Perfectly concealing quantum bit commitment from any quantum one-way permutation

Cites work

• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2086396 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• A Pseudorandom Generator from any One-way Function
• Foundations of Cryptography
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Mathematical Foundations of Computer Science 2004
• On quantum one-way permutations
• Perfectly concealing quantum bit commitment from any quantum one-way permutation
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Strengths and Weaknesses of Quantum Computing
• Universal tests for nonuniform distributions

Cited in

(8)

• Statistical zero knowledge and quantum one-way functions
• Quantum public-key cryptosystem
• Quantum signature scheme using a single qubit rotation operator
• Quantum one-way permutation over the finite field of two elements
• Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives
• Mathematical Foundations of Computer Science 2004
• Universal construction of a full quantum one-way function
• Quantum signature scheme with weak arbitrator

This page was built for publication: Universal test for quantum one-way permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2575756)