TL;DR
This paper introduces I-(OT)², a novel Oblivious Transfer (OT) protocol designed for resource-constrained IoT devices. It achieves significant reductions in receiver-side computation and communication by shifting the heavy lifting to the sender and an offline phase, making secure private computations more feasible on low-power hardware.
What Problem Does This Paper Address?
Oblivious Transfer (OT) is a cornerstone of secure computation, enabling private data exchange. While OT extension techniques have improved efficiency for large-scale operations, they often require substantial pre-computation and many base OTs, making them impractical for scenarios with a modest number of transfers or where low latency and minimal client-side computation are paramount. This is particularly true for Internet of Things (IoT) devices, which have limited processing power and battery life. Existing OT protocols often still impose a significant computational burden on the receiver, hindering their deployment in such environments. This paper aims to bridge this gap by developing an efficient base OT protocol specifically tailored for IoT devices.
Methods
The core of I-(OT)² is a 1-out-of-2 OT protocol built upon the quadratic residuosity problem. Key innovations include:
- Client-Optimal Design: The protocol is engineered to minimize the receiver's computational load and interaction during the online transfer phase. This is achieved by offloading most complex operations to the sender and an offline pre-computation phase.
- Lightweight Receiver Operations: The receiver's online tasks are reduced to a minimal set of operations, including a single modular squaring (which can be pre-computed), a hash function evaluation, and a bit-wise XOR.
- Efficient Communication: The protocol achieves a minimal communication overhead, requiring only six messages and four digests exchanged during the transfer phase.
- Quadratic Residuosity Foundation: The security relies on the hardness of the quadratic residuosity problem and the properties of numbers modulo $n=pq$ where $p, q \equiv 1 \pmod 4$. This specific choice allows for efficient root extraction and manipulation.
- Key Derivation Function (KDF): A KDF is used to derive message keys from computed roots, ensuring message confidentiality.
- Formal Security Proofs: The authors provide formal proofs of security against various threat models, including honest-but-curious senders and malicious receivers, demonstrating unconditional choice obliviousness and computational message security.
- Check Congruency Phase: A novel probabilistic game is introduced to allow receivers to verify the trustworthiness of the sender's modulus without relying on a trusted third party.
Datasets
Not discussed in the paper. The evaluation uses synthetic data generated for the protocol's operations.
Key Insights and Ideas
- Shifting the Burden: The most significant insight is the successful strategy of shifting the computational complexity from the resource-constrained receiver to the more capable sender and an offline phase. This is crucial for making advanced cryptographic primitives practical on IoT devices.
- Quadratic Residues as a Foundation: Leveraging the properties of quadratic residues modulo $n=pq$ (with $p, q \equiv 1 \pmod 4$) provides a mathematically sound and computationally efficient basis for OT, especially when combined with KDFs.
- Minimal Interaction is Key: Reducing the number of online messages and computations is paramount for IoT devices, where latency and power consumption are critical. I-(OT)² excels in this regard.
- Verifiable Modulus Trust: The Check Congruency phase is an important contribution, offering a practical way for receivers to gain confidence in the sender's setup without external trust assumptions.
Key Results
The paper presents a proof-of-concept implementation and empirical results that highlight the protocol's efficiency:
- Receiver Online Cost: For 128-bit security (3072-bit RSA modulus), the average receiver online cost is as low as 2.80 µs on desktop platforms and 39.90 µs on IoT devices (Raspberry Pi Zero 2W).
- Performance Improvement: This represents a more than 10x speedup compared to the well-known SimplestOT protocol. The IoT performance is even faster than SimplestOT running on a desktop.
- Sender Dominance: The computational load is overwhelmingly handled by the sender, accounting for over 99% of the total processing time, while the receiver's load remains minimal.
- Communication Efficiency: The protocol achieves a low communication overhead, with only two ring elements and four messages (encrypted) exchanged per transfer.
Limitations and Future Work
- Classical Security: The current protocol provides classical security and is not secure against quantum adversaries. The authors plan to explore post-quantum adaptations using lattice-based assumptions (e.g., LWE).
- Batch and Adaptive OT: Extending the protocol to support batch or adaptive OT could further reduce overhead, especially when multiple transfers are required.
- Composability: Integrating I-(OT)² within stronger composability frameworks like Universal Composability (UC) would provide more comprehensive security guarantees.
- Microcontroller Support: The authors aim to provide a more comprehensive framework for testing on extremely resource-constrained devices, such as microcontrollers without an operating system.
- Sender Impersonation: While the protocol is secure against receiver impersonation, sender impersonation is noted as being computationally infeasible due to the underlying cryptographic assumptions. Receiver authentication is considered orthogonal and can be added at the transport layer.
Summary updated