  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 on superposition and measures the image. 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\}$, 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.
