Computational Indistinguishability between Quantum States and Its Cryptographic Application

Details Computational Indistinguishability between Quantum States and Its Cryptographic Application Computational Indistinguishability between Quantum States and Its Cryptographic Application

2004-03-09

arxiv.org/abs/quant-ph/0403069v6

Journal of Cryptology 25(3): 528-555 (2012)

Physics

Quantum Physics

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computational Indistinguishability between Quantum States and Its Cryptographic Application does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computational Indistinguishability between Quantum States and Its Cryptographic Application, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computational Indistinguishability between Quantum States and Its Cryptographic Application will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-181173