Computational Indistinguishability between Quantum States and Its Cryptographic Application

Abstract

We introduce a computational problem of distinguishing between two specific quantum states as a new cryptographic problem to design a quantum cryptographic scheme that is "secure" against any polynomial-time quantum adversary. Our problem, QSCDff, is to distinguish between two types of random coset states with a hidden permutation over the symmetric group of finite degree. This naturally generalizes the commonly-used distinction problem between two probability distributions in computational cryptography. As our major contribution, we show that QSCDff has three properties of cryptographic interest: (i) QSCDff has a trapdoor; (ii) the average-case hardness of QSCDff coincides with its worst-case hardness; and (iii) QSCDff is computationally at least as hard as the graph automorphism problem in the worst case. These cryptographic properties enable us to construct a quantum public-key cryptosystem, which is likely to withstand any chosen plaintext attack of a polynomial-time quantum adversary. We further discuss a generalization of QSCDff, called QSCDcyc, and introduce a multi-bit encryption scheme that relies on similar cryptographic properties of QSCDcyc.

24 pages, 2 figures. We improved presentation, and added more detail proofs and follow-up of recent work

References in corpus (8)

• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• Applications of single-qubit rotations in quantum public-key cryptography
• Deterministic quantum-public-key encryption: forward search attack and randomization
• Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem
• The Symmetric Group Defies Strong Fourier Sampling: Part II
• The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
• On the Power of Quantum Encryption Keys
• Quantum Algorithms for many-to-one Functions to Solve the Regulator and the Principal Ideal Problem

Cited by in corpus (6)

• Quantum commitments and signatures without one-way functions
• Oblivious transfer based on quantum state computational distinguishability
• Quantum key distribution with post-processing driven by physical unclonable functions
• Bit-oriented quantum public-key encryption
• One-out-of-two Quantum Oblivious Transfer based on Nonorthogonal States
• A novel application of probabilistic teleportation: p-Rabin qubit-oblivious transfer