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 striking render showcases a central white sphere with segmented panels partially open, revealing a complex, glowing blue internal structure. This intricate core is composed of numerous small, interconnected components, radiating light and suggesting deep computational activity

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.

The image showcases a detailed view of complex mechanical structures, featuring dark metallic components interwoven with vibrant blue glowing elements, all partially obscured by a textured white foam. The foreground highlights a circular, gear-like mechanism, while background elements remain softly blurred, emphasizing the intricate design and dynamic interaction of its parts

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 close-up view reveals a complex, futuristic mechanical device, predominantly silver and dark blue, with striking electric blue glowing lines and rings. The device features intricate geometric shapes, metallic textures, and visible connecting wires, suggesting advanced technological functionality

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 sphere is enveloped by a dense cluster of translucent blue and opaque dark cubes, creating a vibrant, crystalline structure. This intricate formation is held within a framework of smooth, white toroidal rings, connected by dark metallic struts

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 close-up view reveals a complex, translucent structural network, adorned with a frosty texture and embedded with reflective spheres. A prominent, metallic blue spiral element grounds the intricate connections

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