Universal test for quantum one-way permutations

DOI10.1016/J.TCS.2005.07.036zbMATH Open1079.68030arXivquant-ph/0401013OpenAlexW2069693545MaRDI QIDQ2575756FDOQ2575756

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

Publication date: 6 December 2005

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A Pseudorandom Generator from any One-way Function
• Strengths and Weaknesses of Quantum Computing
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Foundations of Cryptography
• Universal tests for nonuniform distributions
• Mathematical Foundations of Computer Science 2004

Cited In (6)

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

   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 👍 👎

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)