Welcome to the resource topic for 2022/1102
Title:
Proofs of Quantumness from Trapdoor Permutations
Authors: Tomoyuki Morimae, Takashi Yamakawa
Abstract:Assume that Alice can do only classical probabilistic polynomial-time computing while Bob can do quantum polynomial-time computing. Alice and Bob communicate over only classical channels, and finally Bob gets a state |x_0\rangle+|x_1\rangle with some bit strings x_0 and x_1. Is it possible that Alice can know \{x_0,x_1\} but Bob cannot? Such a task, called {\it remote state preparations}, is indeed possible under some complexity assumptions, and is bases of many quantum cryptographic primitives such as proofs of quantumness, (classical-client) blind quantum computing, (classical) verifications of quantum computing, and quantum money. A typical technique to realize remote state preparations is to use 2-to-1 trapdoor collision resistant hash functions: Alice sends a 2-to-1 trapdoor collision resistant hash function f to Bob, and Bob evaluates it coherently, i.e., Bob generates \sum_x|x\rangle|f(x)\rangle. Bob measures the second register to get the measurement result y, and sends y to Alice. Bob’s post-measurement state is |x_0\rangle+|x_1\rangle, where f(x_0)=f(x_1)=y. With the trapdoor, Alice can learn \{x_0,x_1\} from y, but due to the collision resistance, Bob cannot. This Alice’s advantage can be leveraged to realize the quantum cryptographic primitives listed above. It seems that the collision resistance is essential here. In this paper, surprisingly, we show that the collision resistance is not necessary for a restricted case: we show that (non-verifiable) remote state preparations of |x_0\rangle+|x_1\rangle secure against {\it classical} probabilistic polynomial-time Bob can be constructed from classically-secure (full-domain) trapdoor permutations. Trapdoor permutations are not likely to imply the collision resistance, because black-box reductions from collision-resistant hash functions to trapdoor permutations are known to be impossible. As an application of our result, we construct proofs of quantumness from classically-secure (full-domain) trapdoor permutations.
ePrint: https://eprint.iacr.org/2022/1102
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .