Verifiable One-Time Programs Enable Open Secure Computation → Research

A clear, faceted crystalline object is centrally positioned within a broken white ring, superimposed on a detailed, luminous blue circuit board. This imagery evokes the cutting edge of digital security and decentralized systems

A sleek, white, spherical robot head featuring a bright blue visor and a multi-jointed hand is depicted emerging from a dynamic formation of jagged blue and clear ice shards. The robot appears to be breaking through or being revealed by these crystalline structures against a soft grey background

Briefing

This paper tackles the critical problem of realizing advanced quantum internet applications that typically demand sophisticated quantum resources, a capability currently beyond reach. It proposes a foundational breakthrough by introducing Verifiable One-Time Programs (Ver-OTPs), which enable a receiver to cryptographically verify the integrity of a one-time program before execution, without revealing its secret data. Building upon Ver-OTPs, the research then constructs Open Secure Computation (OSC), a novel single-round secure computation model that eliminates the need for pre-registration. This new theoretical framework allows for practical, near-term quantum-assisted cryptography by consciously trading classical computational complexity for quantum simplicity, with the most important implication being the immediate feasibility of complex, privacy-preserving distributed applications like single-round sealed-bid auctions and honest-majority atomic proposals, which are crucial building blocks for future blockchain architectures and security paradigms.

A clear geometric cube sits centered on a detailed, dark blue circuit board, surrounded by numerous faceted, luminous blue crystals. A thick, white conduit loops around the scene, connecting to the board

Context

Prior to this research, the development of advanced quantum internet applications faced a significant hurdle → the requirement for highly sophisticated quantum resources, such as fault-tolerant quantum computation, which remain far beyond current technological capabilities. While one-time programs (OTPs) could be constructed from simple quantum states, their ephemeral nature limited their utility, as a receiver needed to be online and prepared for immediate use. The prevailing theoretical limitation was the inability to verify the well-formedness of an OTP without compromising its one-time use property or revealing its secret program-specific data, thereby restricting their practical deployment in scenarios demanding trust and security in computation.

A large, faceted, translucent blue object, resembling a sculpted gem, is prominently displayed, with a smaller, dark blue, round gem embedded on its surface. A second, dark blue, faceted gem is blurred in the background

Analysis

The paper’s core mechanism introduces Verifiable One-Time Programs (Ver-OTPs), a new primitive that extends traditional one-time programs by allowing a receiver to non-interactively verify an OTP’s correctness against public data before use, without revealing any secret program-specific information. This is achieved by combining a garbled circuit, whose correctness is ensured by a Non-Interactive Zero-Knowledge Proof (NIZK) for the garbling and a relation on secret data, with verifiable one-time memories (OTMs) constructed using a cut-and-choose technique alongside secret sharing. The main novelty in OTMs involves generating multiple secret shares for each wire label, placing them into single-bit input OTPs, and using a cut-and-choose verification process where a subset of shares are opened and proven valid via NIZKs. The secret sharing threshold is set to prevent the receiver from reconstructing both possible wire labels, preserving the one-time property.

Building on Ver-OTPs, the research then constructs Open Secure Computation (OSC), a novel single-round secure computation model that requires no pre-registration. OSC utilizes Ver-OTPs in conjunction with multi-key homomorphic encryption (MHE). Each sending party encrypts their input under their public key and creates a Ver-OTP that, when evaluated by the receiver, provides a partial decryption of the homomorphically evaluated function on all inputs. The receiver verifies the Ver-OTPs, homomorphically evaluates the function on valid inputs, and then combines the partial decryptions from the Ver-OTPs to obtain the final output, ensuring privacy and verifiability.

The visual presents a complex, multi-faceted blue object with detailed, circuit board-like pathways. This abstract entity is cradled within a geometric, open-ended blue frame, hinting at a system or environment

Parameters

Core Primitive 1 → Verifiable One-Time Programs (Ver-OTPs)
Core Primitive 2 → Open Secure Computation (OSC)
Key Authors → Lev Stambler
Underlying Quantum Requirement → Single-qubit BB84-like states
Classical Cryptographic Components → Multi-key Homomorphic Encryption (MHE), Non-Interactive Zero-Knowledge Proofs (NIZKs), Garbled Circuits, Commitment Schemes, Secret Sharing
Security Model → Simulation-based security
Communication Rounds for OSC → Single-round
Applications Demonstrated → Single-round sealed-bid auctions, honest-majority atomic proposals, differentially private statistical aggregation

A translucent, faceted sphere, illuminated from within by vibrant blue circuit board designs, is centrally positioned within a futuristic, white, segmented orbital structure. This visual metaphor explores the intersection of advanced cryptography and distributed ledger technology

Outlook

This research opens significant avenues for near-term quantum-assisted cryptography, particularly in decentralized systems. In the next 3-5 years, Ver-OTPs could enable real-world applications such as blockchain-assisted fair exchange, secure pay-to-run software licensing, and enhanced building blocks for other protocols, provided quantum memory challenges are addressed. OSC’s single-round, pre-registration-free nature could unlock more efficient and private decentralized applications, including secure lotteries and voting systems with weaker security guarantees, and potentially “compile down” existing multi-round distributed protocols into single-round executions.

Future research will focus on optimizing Ver-OTP efficiency, enhancing fault-tolerance in noisy quantum environments, achieving UC-security, and extending these primitives to the full quantum computational setting with quantum inputs and functionalities. Addressing the stronger security definition required for multi-key homomorphic encryption or modifying the OSC construction to use standard MHE schemes also remains a critical next step.

This research fundamentally advances practical quantum-assisted cryptography by introducing verifiable one-time programs and a novel open secure computation model, significantly impacting future blockchain privacy and efficiency.

Signal Acquired from → arxiv.org