Quantum 2-party cryptography differs from its classical counterpart in at least one important way: Given black-box access to a perfect commitment scheme there exists a secure 1-2 quantum oblivious transfer. This reduction proposed by Crépeau and Kilian was proved secure against any receiver by Yao, in the case where perfect commitments are used. However, quantum commitments would normally be based on computational assumptions. A natural question therefore arises: What happens to the security of the above reduction when computationally secure commitments are used instead of perfect ones? In this paper, we address the security of 1-2 QOT when computationally binding string commitments are available. In particular, we analyse the security of a primitive called Quantum Measurement Commitment when it is constructed from unconditionally concealing but computationally binding commitments. As measuring a quantum state induces an irreversible collapse, we describe a QMC as an instance of ``computational collapse of a quantum state''. In a QMC a state appears to be collapsed to a polynomial time observer who cannot extract full information about the state without breaking a computational assumption. We reduce the security of QMC to a weak binding criteria for the string commitment. We also show that secure QMCs implies QOT using a straightforward variant of the reduction above.
Quantum 2-party cryptography differs from its classical counterpart in at least one important way: Given black-box access to a perfect commitment scheme there exists a secure 1-2 quantum oblivious transfer. This reduction proposed by Crépeau and Kilian was proved secure against any receiver by Yao, in the case where perfect commitments are used. However, quantum commitments would normally be based on computational assumptions. A natural question therefore arises: What happens to the security of the above reduction when computationally secure commitments are used instead of perfect ones? In this paper, we address the security of 1-2 QOT when computationally binding string commitments are available. In particular, we analyse the security of a primitive called Quantum Measurement Commitment when it is constructed from unconditionally concealing but computationally binding commitments. As measuring a quantum state induces an irreversible collapse, we describe a QMC as an instance of ``computational collapse of a quantum state''. In a QMC a state appears to be collapsed to a polynomial time observer who cannot extract full information about the state without breaking a computational assumption. We reduce the security of QMC to a weak binding criteria for the string commitment. We also show that secure QMCs implies QOT using a straightforward variant of the reduction above.
We analyze the situation where computationally binding string commitment schemes are used to force the receiver of a BB84 encoding of a classical bitstring to measure upon reception. Since measuring induces an irreversible collapse to the received quantum state, even given extra information after the measurement does not allow the receiver to evaluate reliably some predicates apply to the classical bits encoded in the state. This fundamental quantum primitive is called quantum measure commitment (QMC) and allows for secure two-party computation of classical functions. An adversary to QMC is one that can both provide valid proof of having measured the received states while still able to evaluate a predicate applied to the classical content of the encoding. We give the first quantum black-box reduction for the security of QMC to the binding property of the string commitment. We characterize a class of quantum adversaries against QMC that can be transformed into adversaries against a weak form for the binding property of the string commitment. Our result provides a construction for 1--2-oblivious transfer that is computationally secure against the receiver and unconditionally secure against the sender from any string commitment scheme satisfying a weak binding property.
Oblivious transfer protocol is a basic building block in cryptography and is used to transfer information from a sender to a receiver in such a way that, at the end of the protocol, the sender does not know if the receiver got the message or not. Since Shor's quantum algorithm appeared, the security of most of the classical cryptographic schemes has been compromised, as they rely on the fact that factoring is infeasible. To overcome this, quantum mechanics has been used intensively in the past decades, and alternatives resistant to quantum attacks have been developed in order to fulfill the (potential) lack of security of a significant number of classical schemes. In this paper, we present a quantum computationally secure protocol for bit-string oblivious transfer between two parties, under the assumption of quantum hardness of state distinguishability and the constraint of performing at most few-qubit measurements (leaving open the question of general attacks performed on all qubits involved). The protocol is feasible, in the sense that it is implementable in polynomial time.
Most interesting cryptography happens in the computational realm where all parties can only perform efficient computations. On one hand, without this constraint many practically relevant cryptographic tasks are infeasible; on the other, this constraint still captures the power of any physical attacker with limited resources. Classically, if the task of attacking almost any interesting computational cryptography is provably hard, then we would also derive from it the existence of one-way functions, and thus P ≠ NP as well. Quantum mechanics offers a more complete model of physical information in the real world. Recent works have proved oracle separations (Kretschmer’21; Kretschmer, Qian, Sinha, Tal’23; Lombardi, Ma, Wright’23) suggesting that computationally secure quantum cryptography could exist even if P = NP, or in other words, that classical cryptography is infeasible. This hints at the possibility of constructing a quantum cryptosystem and establishing its security without unproven assumptions, liberating cryptographers from the perpetual cat-and-mousegame. In this dissertation, we make initial progress towards this goal by developing a theory of quantum computational cryptography without assuming the existence ofone-way functions. More specifically, we establish the following results: • We introduce a simple and natural quantum cryptographic primitive called EFI pairs, and prove its existential equivalence to various other quantum cryptographic primitives, including commitment schemes, oblivious transfer, and zero knowledge.• We establish the “minimality” of EFI pairs by showing that their existence is implied by many natural cryptographic primitives. EFI pairs thus appear easier to construct than other primitives. • We show that the existence of EFI pairs (and the existentially equivalent primitives) is robust by showing how to upgrade various notions of “weak” security to standard security without any additional assumption. • We finally construct commitment schemes, oblivious transfer, and zero knowledge unconditionally if a piece of quantum advice is allowed. In contrast, classical analogues of these are impossible without first settling P ≠ NP even if we allow randomized advice.
Bit commitment is an essential primitive in quantum cryptography. It is the basic building block of many cryptographic protocols in which it provides security over distrustful parties. This paper proposes a secured quantum two-bit commitment protocol for any two classical bits. The protocol contains two parties - a committer and a receiver - who share both quantum and classical communication channels. The main phases of this protocol are commitment and revealing phases where the concealing and binding conditions are proved in order to accept the commitment message. The proposed framework utilizes different security layers to hide specific quantum states in a superposition alongside trivial one qubit operations. The secured unitary transformations are applied by the two parties to meet the concealing and binding conditions. To verify the success of the proposed protocol, the measured output of the two parties are compared. The protocol operates under the assumption that the two parties might cheat and the possible existence of an eavesdropper.
The computational treatment of cryptography, and indeed any scientific treatment of a problem, is marked by its definitional side and by it constructive side. Results in this thesis better our understanding of both: on one side, they characterize the extent to which computational definitions capture the security of the basic task of symmetric encryption; on the other, they provide explicit bounds on the efficiency of commitment and secure two-party computation constructions. Specifically: • We relate the formal and computational treatments of symmetric encryption, obtaining a precise characterization of computational schemes whose computational semantics imply their formal semantics. We prove that this characterization is strictly weaker than previously-identified notions, and show how it may be realized in a simpler, more efficient manner. • We provide lower-bounds on the number of times a one-way permutation needsto be invoked (as a “black-box”) in order to construct statistically-binding commitments. Our bounds are tight for the case of perfectly-binding schemes. • We show that the secure computation of any two-party functionality can be performed in an optimal two rounds of communication even in a setting that accounts for concurrent execution with other protocols (i.e., the Universal Composability framework). Here, we rely on the assumption that parties have access to a common reference string; some sort of setup is known to be necessary.
Crépeau constructed a quantum 1-out-of-2 oblivious transfer (OT) in 1994 based on the transmission of polarized light and the existence of the secure quantum bit commitment (QBC) protocol [3].However, Mayers [12], Lo and Chau [10] claimed the impossibility of the quantum bit commitment in 1996.In 1997, Lo showed that quantum oblivious transfer couldn't be achieved with the same reason [11].These results imply severe setback for quantum cryptography.In the 1-out-of-2 oblivious transfer, Lo claimed that to prevent a dishonest Alice from learning anything, the reduced density matrices in Alice's hand for two cases must be the same.This requirement is too strong.In this paper, we find that to prevent a dishonest Alice from leaning anything, the qubits that Alice receives is encoded by different bases, Alice can learn nothing from them, just like the eavesdropper in the scheme BB84, cannot distinguish the photos encoded in two different bases [4].We construct a unconditionally secure quantum oblivious transfer using the secure property of quantum key distribution (QKD) [4].It bypasses Lo's attack.Furthermore, m-out-of-n quantum oblivious transfer, a more general oblivious transfer, is constructed.Finally, We show that quantum bit commitment can be constructed using QOT.