Abstract
Assume that Alice can do only classical probabilistic polynomialtime computing while Bob can do quantum polynomialtime computing. Alice and Bob communicate over only classical channels, and finally Bob gets a state x₀⟩+x₁⟩ with some bit strings x₀ and x₁. Is it possible that Alice can know {x₀,x₁} but Bob cannot? Such a task, called remote state preparations, is indeed possible under some complexity assumptions, and is bases of many quantum cryptographic primitives such as proofs of quantumness, (classicalclient) blind quantum computing, (classical) verifications of quantum computing, and quantum money. A typical technique to realize remote state preparations is to use 2to1 trapdoor collision resistant hash functions: Alice sends a 2to1 trapdoor collision resistant hash function f to Bob, and Bob evaluates it coherently, i.e., Bob generates ∑_xx⟩f(x)⟩. Bob measures the second register to get the measurement result y, and sends y to Alice. Bob’s postmeasurement state is x₀⟩+x₁⟩, where f(x₀) = f(x₁) = y. With the trapdoor, Alice can learn {x₀,x₁} 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 (nonverifiable) remote state preparations of x₀⟩+x₁⟩ secure against classical probabilistic polynomialtime Bob can be constructed from classicallysecure (fulldomain) trapdoor permutations. Trapdoor permutations are not likely to imply the collision resistance, because blackbox reductions from collisionresistant hash functions to trapdoor permutations are known to be impossible. As an application of our result, we construct proofs of quantumness from classicallysecure (fulldomain) trapdoor permutations.
BibTeX  Entry
@InProceedings{morimae_et_al:LIPIcs.ITCS.2023.87,
author = {Morimae, Tomoyuki and Yamakawa, Takashi},
title = {{Proofs of Quantumness from Trapdoor Permutations}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {87:187:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17590},
URN = {urn:nbn:de:0030drops175900},
doi = {10.4230/LIPIcs.ITCS.2023.87},
annote = {Keywords: Quantum cryptography, Proofs of quantumness, Trapdoor permutations}
}
Keywords: 

Quantum cryptography, Proofs of quantumness, Trapdoor permutations 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 