  A proof of quantumness is an efficiently verifiable interactive test that an
efficient quantum computer can pass, but all efficient classical computers
cannot (under some cryptographic assumption). Such protocols play a crucial
role in the certification of quantum devices. Existing single-round protocols
(like asking the quantum computer to factor a large number) require large
quantum circuits, whereas multi-round ones use smaller circuits but require
experimentally challenging mid-circuit measurements. As such, current proofs of
quantumness are out of reach for near-term devices.
  In this work, we construct efficient single-round proofs of quantumness based
on existing knowledge assumptions. While knowledge assumptions have not been
previously considered in this context, we show that they provide a natural
basis for separating classical and quantum computation. Specifically, we show
that multi-round protocols based on Decisional Diffie-Hellman (DDH) or Learning
With Errors (LWE) can be "compiled" into single-round protocols using a
knowledge-of-exponent assumption or knowledge-of-lattice-point assumption,
respectively. We also prove an adaptive hardcore-bit statement for a family of
claw-free functions based on DDH, which might be of independent interest.
  Previous approaches to constructing single-round protocols relied on the
random oracle model and thus incurred the overhead associated with
instantiating the oracle with a cryptographic hash function. In contrast, our
protocols have the same resource requirements as their multi-round counterparts
without necessitating mid-circuit measurements, making them, arguably, the most
efficient single-round proofs of quantumness to date. Our work also helps in
understanding the interplay between black-box/white-box reductions and
cryptographic assumptions in the design of proofs of quantumness.
