Source-linked AI summary
Universally Composable Quantum Multi-Party Computation
Dominique Unruh
TL;DR
Quantum cryptography needs a security framework that remains secure under arbitrary composition. The paper defines quantum UC security, proves oblivious transfer from commitments and a classical-to-quantum security-lifting theorem, and derives general multi-party computation from commitments. Its guarantees are specific to the UC setting, since analogous lifting is not known for the stand-alone model.
Problem
Prior oblivious-transfer protocols may lose security when composed, motivating a quantum security framework with strong composability guarantees.
Method
The paper defines quantum UC security, proves a quantum lifting theorem for classical statistically UC-secure protocols, and composes commitment-based oblivious transfer with multi-party computation protocols.
Results
The paper establishes statistically quantum-UC-secure oblivious transfer from commitments and obtains quantum UC-secure protocols for general multi-party computation.
Takeaways & Limitations
In the quantum setting, commitments suffice for general statistically secure UC multi-party computation, unlike in the classical setting.
Takeaways & Limitations
The quantum lifting theorem is not known for the stand-alone model, and the construction relies on commitments despite unconditional statistically secure quantum commitments being impossible.
Abstract
from arXiv · showhide
The Universal Composability model (UC) by Canetti (FOCS 2001) allows for secure composition of arbitrary protocols. We present a quantum version of the UC model which enjoys the same compositionality guarantees. We prove that in this model statistically secure oblivious transfer protocols can be constructed from commitments. Furthermore, we show that every statistically classically UC secure protocol is also statistically quantum UC secure. Such implications are not known for other quantum security definitions. As a corollary, we get that quantum UC secure protocols for general multi-party computation can be constructed from commitments.
4 Relation to the stand-alone model 20
This section contains a funding acknowledgment for the Cluster of Excellence “Multimodal Computing and Interaction.”
- The work was funded by the Cluster of Excellence “Multimodal Computing and Interaction.”
- The acknowledgment identifies “Multimodal Computing and Interaction” as the funding program.
- No substantive relationship to the stand-alone model is stated in the supplied passage.
1 Introduction
The paper develops quantum UC security, proves composable oblivious transfer from commitments, and lifts classical statistical UC security to the quantum setting. These results yield general statistically secure quantum multi-party computation from commitments while highlighting limits of other models and assumptions.
- The paper introduces a quantum UC-security definition and uses it to establish statistically secure, universally composable oblivious transfer from commitments.
- 1.3 Quantum lifting and multi-party computation: Every statistically classical-UC-secure classical protocol is also statistically quantum-UC-secure under the paper’s quantum lifting theorem.
- 1.3 Quantum lifting and multi-party computation: Combining quantum-secure oblivious transfer with the lifting and composition theorems gives statistically secure general multi-party computation using a commitment and a quantum channel.
- 1.5 Compositionality restrictions in prior work: The quantum lifting theorem has no known counterpart in the stand-alone model, where composition may require security definitions already involving quantum adversaries.
- 1.4 How to interpret our result: The result assumes a commitment, although statistically secure quantum commitments cannot be constructed without additional assumptions.
- 1.4 How to interpret our result: In the quantum setting, commitment is complete for general statistically secure multi-party computation, whereas classically it is insufficient even for the AND-function.
2 Quantum Universal Composability
The paper defines a quantum UC framework with quantum message handling, network execution, corruptions, and real–ideal security comparisons. It establishes reflexivity, dummy-adversary completeness, universal composition, and transitivity for quantum-UC emulation.
- Framework: Quantum machines use separate state, classical-message, and quantum-message registers, with uniform quantum circuits implementing their state transitions.Messages carry classical and quantum parts; a machine may send an empty message.
- Network execution: A network executes by repeatedly applying a global superoperator, measuring communication, activating addressed machines, and returning the environment’s output.The output distribution is denoted Exec_N(k, z).
- Security definition: Quantum-UC security compares real and ideal networks for every corruption set, adversary, and environment, requiring an efficient simulator whenever the adversary is efficient.Statistical and computational definitions differ in whether adversaries and environments are unrestricted or quantum-polynomial-time.
- Composition properties: Quantum UC emulation is reflexive and transitive, so security can be chained across protocols and ideal functionalities.These properties hold for both statistical and computational quantum-UC security.
3 Relating classical and quantum-UC
The paper relates classical and quantum UC security by showing that statistically classical-secure classical protocols lift to statistical quantum UC security. A computational analogue holds under QPPT security, but rewinding creates an unresolved obstacle.
- Statistical lifting: Every classical protocol that statistically classical-UC-emulates another protocol also statistically quantum-UC-emulates it.This quantum lifting theorem allows classical UC-secure protocols to be composed with quantum protocols.
- Statistical lifting: The lifting proof measures messages and simulates quantum machines classically, yielding perfect indistinguishability for the classical protocol execution.The classical simulation may incur exponential overhead, but the resulting simulator is still quantum-polynomial-time in the statistical argument.
- Computational lifting: A computational lifting theorem holds when classical UC security is defined for QPPT adversaries, simulators, and environments.Under this stronger premise, QPPT classical UC emulation implies computational quantum-UC emulation.
- Computational lifting: The computational lifting result cannot directly reuse existing classical UC proofs when their constructed machines rewind quantum-polynomial-time adversaries.Black-box simulation without rewinding remains straightforward, whereas efficient simulation of rewinding is unresolved.
- Open problem: The paper formulates an oracle conjecture asserting that QPPT machines may be perfectly represented by probabilistic-polynomial-time oracle machines.A positive answer would permit rewinding QPPT machines and could affect other quantum security settings.
4 Relation to the stand-alone model
The paper gives conditions under which statistical quantum stand-alone security implies quantum UC security for a two-party protocol with a corrupted recipient. The proof packages the environment and adversary into simulator components while preserving their output state.
- Model relation: The stand-alone model views security as simulating attacks using only access to an ideal functionality, paralleling the real–ideal structure of UC.The paper uses this relationship to reuse an existing OT security proof.
- Lifting theorem: If Alice takes no input, stops accepting messages after output, and the stand-alone simulator is efficient, black-box, non-rewinding, and output-preserving, stand-alone security lifts to quantum UC security.The result applies to the case of corrupted Bob.
- Proof strategy: The proof replaces the environment and dummy adversary with a joint machine, then uses stand-alone indistinguishability between the real and ideal joint states.A measurement on the joint state reproduces the environment’s output distribution.
- Proof strategy: The final simulator internally combines the adversary and the stand-alone simulator while remaining independent of the environment.Its quantum-polynomial-time property follows from the stand-alone simulator and the adversary’s efficiency.
5 Oblivious transfer
The paper defines randomized quantum oblivious transfer and variants using either an ideal commitment functionality or a commitment scheme. It establishes quantum-UC security for several corruption cases as the basis for the OT construction.
- Protocol definitions: π_QROT is a randomized oblivious-transfer protocol, while π_com_QROT replaces the ideal commitment functionality with a commitment scheme.π_QOT additionally handles Alice’s two input strings by masking them with randomized-transfer outputs.
- Security results: π_QROT statistically quantum-UC-emulates the randomized OT functionality when no parties are corrupted or when both parties are corrupted.These are stated as the trivial corruption cases.
- Security results: π_QROT statistically quantum-UC-emulates the randomized OT functionality when Alice is corrupted.The real model includes the environment, adversary, corruption party, honest Bob, and commitment-functionality instances.
B AC FROT ˜B Z s0,s1 s0,s1 c
The proof transforms the real quantum OT network through perfectly indistinguishable games into an ideal network with a quantum-polynomial-time simulator. This establishes statistical quantum-UC emulation under the stated commitment assumptions.
- Game transformations: The proof first replaces the commitment functionality with FFakeCOM, allowing Bob to provide the committed bit when opening.It also uses trivially extractable commitments as an intermediate construction, although such commitments are not hiding.
- Game transformations: Game 2 delays Bob’s measurements until the relevant protocol steps without changing the network distribution.The passage states that this modification yields a perfectly indistinguishable network.
- Game transformations: Game 4 replaces Bob’s random bases with a random partition because only the induced sets I0 and I1 matter.The resulting network is perfectly indistinguishable because the partition has the same distribution and θB is unused elsewhere.
- Game transformations: Game 5 rewrites Bob’s computation using s0 and s1 so that the choice bit only selects which value is output.The rewritten computation produces the same s as the original and preserves perfect indistinguishability.
- Simulator construction: The real and ideal networks are perfectly indistinguishable after the Game 6 simulator construction.The simulator internally simulates Adv, AC, FFakeCOM, and Bob, while FROT supplies the selected value to the dummy party.
- Simulator construction: The simulator is quantum-polynomial-time when Adv is, and its construction is independent of the environment Z.Therefore πQROT statistically quantum-UC-emulates the OT functionality when Alice is corrupted.
6 Multi-party computation
The paper lifts quantum UC-secure OT to general multi-party computation while proving that the analogous classical construction is impossible for AND. The resulting quantum protocol uses commitments and a quantum channel under stated technical restrictions.
- Quantum construction: Theorem 28 constructs a protocol in the commitment-hybrid model that statistically quantum-UC-emulates any classical PPT functionality F.The theorem assumes a constant number of parties.
- Quantum construction: The general construction replaces each FOT call in a classical UC-secure protocol with the quantum OT protocol πQOT.Quantum lifting, OT composition, and transitivity yield statistical quantum UC security for the resulting protocol.
- Classical impossibility: The impossibility argument relies on indistinguishable views for Alice across (0,0)/(0,1) and Bob across (0,0)/(1,0), while both parties must output a·b.These conditions hold for honest-but-curious parties and lead to a contradiction in the final communicated output.
- Scope: The functionality’s technical restrictions reveal input lengths to the adversary and allow adversarial scheduling of output timing.These restrictions stem from the proof used for the classical UC construction.
- Classical impossibility: No classical polynomial-round protocol in the commitment-hybrid model statistically classical-UC-emulates the AND functionality.The impossibility follows by combining indistinguishable party views with distinguishable outputs on different input pairs.
7 Conclusions
The paper defines quantum UC security with strong composability guarantees and uses it to obtain commitment-based quantum OT and general multi-party computation. It also identifies efficiency and model-lifting questions for future work.
- Conclusions: The framework is intended to provide strong composability guarantees for quantum protocols.This is the paper’s central modeling conclusion.
- Conclusions: Quantum UC security supports statistically secure OT from commitments and commitment-based UC-secure general multi-party computation.The paper also establishes that statistically classical-UC-secure protocols remain statistically quantum-UC-secure.
- Future work: Future directions include combining UC with bounded quantum storage and with long-term classical UC-secure commitments.The stated goals include commitment-based general MPC under bounded quantum storage and practical setup assumptions if quantum security can be shown.
- Future work: The protocol commits to each qubit sent by Alice, which can be expensive in settings such as bounded quantum storage.Using fewer string commitments instead of committing to each bit individually could considerably improve efficiency.
- Future work: The paper leaves open whether classical security lifts to quantum security in the stand-alone model and for general zero-knowledge proofs.It calls for analogues of the quantum lifting theorem in other security models.
Index
The index lists terms covering UC security, quantum and classical variants, composition, functionalities, communication, and related protocol concepts.
- Index: It includes composition terms such as universal, sequential, and composition theorem.Related entries include composed systems and functionality.
- Index: Additional entries cover quantum states, operators, message transfer, channels, protocol security, and multi-party computation.The entries include density operators, superoperators, secure channels, and classical impossibility.
- Index: The index covers adversarial and system roles including corruption, dummy adversary, corruption party, and ideal model.It also lists ideal functionality and classical dummy adversary.
- Index: The index groups entries for classical, quantum, statistical, and computational UC security and emulation.It includes terms such as quantum-UC-emulate and statistically quantum-UC-emulate.