Verifiable One-Time Programs Enable Open Secure Computation ∞ Research

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

A clear, multifaceted crystalline formation, illuminated by an internal luminescence of blue light and scattered particles, connects to a sophisticated white mechanical device. This device exhibits detailed internal mechanisms and a smooth, transparent glass lens

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, faceted, crystalline object rests on a dark surface, partially enclosing a dark blue, textured component. A central metallic gear-like mechanism is embedded within the blue material, from which a black cable extends across the foreground towards a blurred, multi-toned mechanical device in the background

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 contemporary office space is depicted with its floor partially submerged in reflective water and covered by mounds of white, granular material resembling snow or foam. Dominating the midground are two distinct, large circular forms: one a transparent, multi-layered ring structure, and the other a solid, textured blue disc

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.

A central, clear, multi-faceted geometric object is encircled by a segmented white band with metallic accents, all set against a backdrop of detailed blue circuitry and sharp blue crystalline formations. This arrangement visually interprets abstract concepts within the cryptocurrency and blockchain domain

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 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

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