Petros Wallden

Oblivious transfer (OT) is a cryptographic primitive which is universal for multiparty computation. Unfortunately, perfect information-theoretically secure (ITS) quantum oblivious transfer is impossible. Imperfect information-theoretically secure quantum oblivious transfer is possible, but the smallest possible cheating probabilities are not known. We present an imperfect information-theoretically secure quantum oblivious transfer protocol with no restrictions on dishonest parties, and its experimental implementation. The cheating probabilities are 0.75 and 0.729 for sender and receiver respectively, which is lower than in existing protocols. Using a photonic test-bed, we have implemented the protocol with honest parties, as well as optimal cheating strategies.

Self-testing is a method to verify that one has a particular quantum state from purely classical statistics. For practical applications, such as device-independent delegated verifiable quantum computation, it is crucial that one self-tests multiple Bell states in parallel while keeping the quantum capabilities required of one side to a minimum. In this work, we use the $3 \times n$ magic rectangle games (generalisations of the magic square game) to obtain a self-test for $n$ Bell states where the one side needs only to measure single-qubit Pauli observables. The protocol requires small input sizes (constant for Alice and $O(\log n)$ bits for Bob) and is robust with robustness $O(n^{5/2} \sqrt{\varepsilon})$, where $\varepsilon$ is the closeness of the observed correlations to the ideal. To achieve the desired self-test we introduce a one-side-local quantum strategy for the magic square game that wins with certainty, generalise this strategy to the family of $3 \times n$ magic rectangle games, and supplement these nonlocal games with extra check rounds (of single and pairs of observables).

Oblivious transfer (OT) is a cryptographic primitive which is universal for multiparty computation. Unfortunately, perfect information-theoretically (IT) secure quantum oblivious transfer is impossible (except with restrictions on cheating parties). Imperfect IT secure quantum oblivious transfer remains possible, but the smallest possible cheating probabilities are not known. Informally, in 1-out-of-2 oblivious transfer, a sender Alice has two bits x0, x1. A receiver Bob obtains one of these, xb, where b= 0 or b= 1. Alice should not be able to guess b, and Bob should not be able to guess the bit value he did not obtain. Bounds on cheating probabilities in quantum oblivious transfer have previously been investigated for complete protocols. “Complete” means that if sender Alice and receiver Bob both follow the protocol, the bit value Bob obtains correctly matches Alice’s bit value. Here we instead investigate incomplete protocols, where Bob obtains an incorrect bit value with probability pf. For complete protocols, both “classical” and quantum, it holds that if one party can cheat no better than with a random guess, then the other party can cheat perfectly. For incomplete protocols, in contrast, even with no restrictions on cheating parties, and when one party can cheat no better than with random guess, it is possible that the other party still cannot cheat perfectly; their cheating probability can be lower than in complete protocols. We find the optimal non-interactive protocols where Alice’s bit values are represented by four symmetric pure quantum states, and where Alice cannot cheat better than with a random guess. “Optimal” means that for a given pf, Bob’s cheating probability pr is as low as possible, and vice versa. We also show that quantum protocols can outperform classical non-interactive protocols. Our results also provide a lower bound on Bob’s cheating probability in interactive quantum protocols. An advantage of the non-interactive protocols we investigate is that they require neither entanglement nor quantum memory. The optimal protocols could be readily implemented using standard optical components.

We study a generalization of the Mermin–Peres magic square game to arbitrary rectangular dimensions. After exhibiting some general properties, these rectangular games are fully characterized in terms of their optimal win probabilities for quantum strategies. We find that for $m \times n$ rectangular games of dimensions $m,n \geq 3$, there are quantum strategies that win with certainty, while for dimensions $1 \times n$ quantum strategies do not outperform classical strategies. The final case of dimensions $2 \times n$ is richer, and we give upper and lower bounds that both outperform the classical strategies. Finally, we apply our findings to quantum certified randomness expansion to find the noise tolerance and rates for all magic rectangle games. To do this, we use our previous results to obtain the winning probability of games with a distinguished input for which the devices give a deterministic outcome and follow the analysis of C. A. Miller and Y. Shi (2017).

Classical remote state preparation (RSPCC) is a primitive that allows an honest client to prepare a quantum state remotely with the help of an (untrustworthy) server using only a classical communication channel. With this primitive quantum protocols (such as secure delegation of quantum computations) become accessible to classical clients, by removing the need for a quantum channel. Since this cryptographic primitive’s main role is to be a building block within larger protocols, it is of utmost importance to examine its security under composition. In this work we present three results related to the composability of RSPCC protocols: 1. As our first main result, we show that no classical remote state preparation protocol RSPCC can be composable in the Abstract Cryptography framework [MR11], even when the distinguisher is computationally bounded. In other words, remote state preparation cannot be constructed with only a classical channel. 2. We further show that any classical-client delegated quantum computing protocol that uses the universal blind quantum computation (UBQC) protocol [BFK09] and a RSPCC protocol as a subroutine cannot be composable. 3. Upon relaxing the security requirement, we show that replacing the quantum channel of the UBQC protocol by the particular RSPCC protocol of [CCKW19] is secure in the game-based security framework.

Bitcoin and its underlying blockchain protocol have received recently significant attention in the context of building distributed systems as well as from the perspective of the foundations of the consensus problem. At the same time, the rapid development of quantum technologies brings the possibility of quantum computing devices from a theoretical concept to an emerging technology. Motivated by this, in this work we revisit the formal security of the core of the Bitcoin protocol, called the Bitcoin backbone, in the presence of an adversary that has access to a scalable quantum computer. We prove that the protocol’s essential properties stand in the post-quantum setting assuming a general quantum adversary with suitably bounded number of queries in the Quantum Random Oracle (QRO) model. In order to achieve this, we investigate and bound the quantum complexity of a Chain-of-Proofs-of-Work search problem which is at the core of the blockchain protocol. Our results imply that security can be shown by bounding the quantum queries so that each quantum query is worth O(p^{−1/2}) classical ones and that the wait time for safe settlement is expanded by a multiplicative factor of O(p^{−1/6}), where p is the probability of success of a single classical query to the protocol’s underlying hash function.