Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli- X or Z measurements. In this paper, we demonstrate a new technique that uses the entire range of qubit measurements from the XY -plane. We show the advantage of this approach in two applications. First, building on (Brakerski et al. 2018, Kalai et al. 2022), we show an optimized two-round proof of quantumness whose security can be expressed directly in terms of the hardness of the LWE (learning with errors) problem. Second, we construct a one-round protocol for blind remote preparation of an arbitrary state on the XY -plane up to a Pauli- Z correction.
Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli- X or Z measurements. In this paper, we demonstrate a new technique that uses the entire range of qubit measurements from the XY -plane. We show the advantage of this approach in two applications. First, building on (Brakerski et al. 2018, Kalai et al. 2022), we show an optimized two-round proof of quantumness whose security can be expressed directly in terms of the hardness of the LWE (learning with errors) problem. Second, we construct a one-round protocol for blind remote preparation of an arbitrary state on the XY -plane up to a Pauli- Z correction.
Properties of quantum mechanics such as entanglement and the no-cloning theorem enable new forms of cryptography that are unattainable in classical models of computation. Quantum information, however, is harder to process, store, and transmit than classical information. As such, it is desirable to construct semi-quantum cryptographic protocols where only a subset of the parties have quantum capabilities while the rest operate classically. In this dissertation, we analyze the security of semi-quantum protocols based on two approaches: (i) nonlocality-based techniques and (ii) the hardness of the Learning with Errors (LWE) problem. In the first part of the dissertation, we leverage a form of Bell test to construct a quantum position verification (QPV) protocol. Initial QPV protocols required verifiers to prepare and send quantum states to an honest prover to achieve security against adversaries with bounded memory or entanglement. Later work constructed QPV protocols with classical verifiers but required additional assumptions such as the hardness of LWE or of random circuit sampling. We construct a variant of QPV where classical verifiers verify the spatial locations of two provers. We use the nonlocal correlations produced by the two provers to show security against adversaries with bounded quantum memory without making any computational intractability assumptions. In the second part of the dissertation, we use trapdoor claw-free functions (TCFs) to construct semi-quantum cryptographic protocols. TCFs, which are constructible from the hardness of LWE, have been shown to be immensely valuable in the construction of classically verifiable quantum cryptographic protocols. As opposed to previous work where the server is asked to prepare a claw state and perform Pauli-X and Z measurements, we use a technique that leverages the entire range of qubit measurements on the XY-plane. We use this technique to construct three protocols: (i) a one-round blind remote state preparation protocol that delegates the preparation of an arbitrary state on the XY-plane up to a Pauli-X correction; (ii) a two-round proof of quantumness whose security is directly in terms of the hardness of LWE and only requires the prover to prepare and measure a single claw state; and (iii) a 1-of-2 Puzzle with a single qubit auxiliary state.
Trapdoor claw-free functions (TCFs) underpin much of classical-quantum cryptographic interaction, yet every TCF-based protocol states its guarantees relative to an honestly generated key. We give a family-agnostic abstraction of key certification for (noisy) TCF constructions, built on two notions: a certifiable key relation, an NP relation capturing a family's honest keys with witnesses recoverable from the trapdoor; and certified key generation, which emits with each key a certificate of membership satisfying completeness, certificate soundness with extractability, and key privacy. We instantiate certifiable key relations for different constructions, each met generically by a zero-knowledge argument of knowledge for the relation. As our main application, a generic compiler turns any TCF-based proof of quantumness into a zero-knowledge one, with each security property following from its counterpart in the certification scheme. Finally, we delimit the primitive's reach: for protocols resting on injective invariance, an accepting certificate is itself a family distinguisher, leaking exactly the bit such protocols must hide.
Classical client remote state preparation (CC − RSP) is a primitive where a fully classical party (client) can instruct the preparation of a sequence of random quantum states on some distant party (server) in a way that the description is known to the client but remains hidden from the server. This primitive has many applications, most prominently, it makes blind quantum computing possible for classical clients. In this work, we give a protocol for classical client remote state preparation, that requires minimal resources. The protocol is proven secure against honest-but-curious servers and any malicious third party in a game-based security framework. We provide an instantiation of a trapdoor (approximately) 2-regular family of functions whose security is based on the hardness of the Learning-With-Errors problem, including a first analysis of the set of usable parameters. We also run an experimentation on IBM’s quantum cloud using a toy function. This is the first proof-of-principle experiment of classical client remote state preparation.
Remote state preparation (RSP) is a central primitive in quantum cryptography, enabling classical parties to remotely construct quantum states using only classical communication. As a result, RSP serves as a key building block in numerous protocols involving classical clients and quantum servers, allowing classical parties to leverage the advantages offered by powerful quantum computers. All known constructions of RSP rely on strong cryptographic assumptions, typically variants of trapdoor claw-free functions (TCFs).
In this work, we initiate the study of a weaker form of remote state preparation, which we call eavesdropper-blind remote state preparation (EB-RSP). Informally, EB-RSP requires blindness only against external observers who see the transcript of the honest protocol, rather than against the quantum server itself. Despite this relaxed adversarial model, the resulting notion remains sufficient for useful cryptographic applications. In particular, we show that two-message EB-RSP already suffices to construct quantum public-key encryption with classical public keys and quantum ciphertexts. We then construct two-message EB-RSP protocols from specific one-way group actions, yielding a first step toward RSP-type primitives based on assumptions that do not rely on trapdoors. Finally, we observe that existing RSP constructions are likely naturally adaptable to the two-message EB-RSP notion; we demonstrate this explicitly for a concrete TCF-based RSP construction.
\emph{Noisy trapdoor claw-free function} (NTCF) as a powerful post-quantum cryptographic tool can efficiently constrain actions of untrusted quantum devices. However, the original NTCF is essentially \emph{2-to-1} one-way function (NTCF21). In this work, we attempt to further extend the NTCF21 to achieve \emph{many-to-one} trapdoor claw-free functions with polynomial bounded preimage size. Specifically, we focus on a significant extrapolation of NTCF21 by drawing on extrapolated dihedral cosets, thereby giving a model of NTCFκ1 where κ is a polynomial integer. Then, we present an efficient construction of NTCFκ1 assuming \emph{quantum hardness of the learning with errors (LWE)} problem. We point out that NTCF can be used to bridge the LWE and the dihedral coset problem (DCP). By leveraging NTCF21 (resp. NTCFκ1), our work reveals a new quantum reduction path from the LWE problem to the DCP (resp. extrapolated DCP). Finally, we demonstrate the NTCFκ1 can naturally be reduced to the NTCF21, thereby achieving the same application for proving the quantumness.
Recent advances in quantum technologies raise the urgent need of verifying the correct functionality of a quantum device. Certifying the correctness of a quantum device in a fully classical manner is an important research branch. In this paper, we present a measurement protocol that allows a classical verifier to interact with an efficient quantum prover to verify the computational basis or the XY-plane basis measurement on a quantum state. With the help of two adaptive hardcore bit properties of a noisy trapdoor claw-free family, the security of measurement protocol is proved, which is under quantum hardness of the learning with error. The security characterizes the distance between the output distribution of measurement protocol and the distribution obtained by measuring certain quantum states in the designated basis, with or without the presence of honest behavior of the prover. Moreover, exploiting the measurement protocol, we present two device-noise-independent verification protocols of graph states and a classical verification protocol of delegated quantum computing whose soundness is 0.5757.