The Simplest Protocol for Oblivious Transfer

Tung Chou, Claudio Orlandi

TL;DR

This paper introduces the simplest and most efficient 1-out-of-n Oblivious Transfer (OT) protocol to date, by cleverly adapting the Diffie-Hellman key exchange. Their implementation, optimized for twisted Edwards curves, achieves an order of magnitude speedup over previous methods, making advanced cryptographic tasks more practical.

What Problem Does This Paper Address?

Oblivious Transfer (OT) is a fundamental cryptographic primitive that allows a receiver to obtain one of several messages from a sender, without the sender learning which message was chosen, and without the receiver learning anything about the other messages. While OT is crucial for building many advanced cryptographic protocols (like secure multi-party computation), existing protocols have often been complex and computationally expensive, especially when performing a large number of OTs. This paper aims to address this by developing a significantly simpler and more efficient OT protocol, particularly for the 1-out-of-n variant.

Methods

The core innovation lies in a clever modification of the Diffie-Hellman (DH) key exchange protocol. In standard DH, two parties Alice and Bob can agree on a shared secret key. The authors observe that by having Bob (the receiver) compute his DH value based on his choice bit, Alice (the sender) can derive different keys for each of her messages, while Bob can only derive the key corresponding to his chosen message. This forms the basis of their "random OT" protocol, where the sender effectively sends random keys and the receiver learns only one.

To achieve full OT, this random OT is combined with a symmetric encryption scheme. The sender encrypts each of their messages with the corresponding derived key, and the receiver decrypts the ciphertext corresponding to their chosen key.

For practical implementation, the authors leverage a twisted Edwards curve, specifically one used in the Ed25519 signature scheme, known for its efficiency and security. They detail optimizations for group element encoding and arithmetic operations, including vectorization to exploit modern CPU capabilities. They also emphasize constant-time implementation to resist timing attacks.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • DH as a building block for OT: The paper demonstrates that the Diffie-Hellman key exchange, with a simple tweak, can be repurposed to build a highly efficient Oblivious Transfer protocol. This is a significant conceptual simplification.
  • Random OT as a primitive: The concept of "random OT" (where the sender has no input but generates random keys, and the receiver learns one) is presented as a useful intermediate step, simplifying the overall protocol design.
  • Twisted Edwards curves for efficiency: The choice of a twisted Edwards curve, known for its performance in cryptographic applications, is crucial for achieving the reported speedups.
  • Vectorization for throughput: Exploiting 256-bit vector instructions on modern CPUs allows for parallel execution of field operations, leading to substantial performance gains.
  • Constant-time implementation for security: The focus on constant-time execution is vital for security against side-channel attacks like timing attacks, especially in a protocol that involves sensitive cryptographic operations.

Key Results

The paper reports a significant speedup for their 1-out-of-2 OT protocol. Their vectorized implementation is an order of magnitude faster than previous state-of-the-art implementations. Specifically, they achieve timings for random OT that are substantially better than those reported by Asharov et al. [ALSZ13], with their implementation being up to 10 times faster for a large number of OTs. They also show competitive performance for Diffie-Hellman key exchange operations compared to existing Curve25519 implementations.

Limitations and Future Work

The authors acknowledge that the proceeding version of their paper contained incorrect security claims regarding UC security and the CDH assumption. These claims have been removed in the current version. They also note that the proof of security for their protocol relies on the random oracle model, and that achieving UC security in practice without trusted setup assumptions is a complex area. Future work could explore further optimizations, different cryptographic assumptions, and broader applications of their efficient OT protocol.

Summary updated

BibTeX
@article{chou2015simplest,
  author = {Tung Chou and Claudio Orlandi},
  title = {{The Simplest Protocol for Oblivious Transfer}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
  url = {https://openreview.net/forum?id=YHHchhEYGc},
}
Figure