From Privacy-Only to Simulatable OT: Black-Box, Round-Optimal, Information-Theoretic

Daniele Venturi, Varun Madathil, Chris Orsini, Alessandra Scafuro, Daniele Venturi 0001Itc 2022 · DOI

TL;DR

This paper presents a novel, black-box compiler that transforms any 2-round Oblivious Transfer (OT) protocol with basic privacy guarantees into a 4-round protocol that achieves simulation-based security. This is a significant advancement as it's information-theoretic, works in the plain model (no setup assumptions), and offers a substantial improvement in communication complexity over previous methods.

What Problem Does This Paper Address?

Oblivious Transfer (OT) is a fundamental cryptographic primitive where a sender with two secrets and a receiver with a choice bit can interact such that the receiver learns only their chosen secret, and nothing else. While "privacy-only" OT protocols exist, they offer weaker security guarantees than "simulatable" OT. Simulatable OT is crucial for building more complex cryptographic tasks, as it allows a simulator to mimic real protocol executions without knowing the parties' secret inputs.

Previous work has shown how to achieve simulatable OT, but often required setup assumptions (like a Common Reference String or Random Oracle) or were not "round-optimal" (meaning they used more communication rounds than theoretically necessary). Specifically, achieving round-optimal simulatable OT in the "plain model" (without any setup) is challenging, and existing black-box compilers for this task were inefficient. The core problem this paper tackles is bridging the gap between readily available, weaker privacy-only OT protocols and the more robust, round-optimal simulatable OT, all while adhering to strict efficiency and security requirements (black-box, information-theoretic, plain model).

Methods

The paper introduces a black-box compiler that takes a 2-round privacy-only OT protocol as input and outputs a 4-round simulatable OT protocol. The key innovation lies in how it achieves the necessary "extraction" and "consistency" properties for simulation without relying on additional cryptographic primitives or complex setup assumptions.

Here's a breakdown of their approach:

  • Leveraging Existing OT: The compiler works with any 2-round OT protocol that provides "privacy against defensible receivers" and "privacy against malicious senders." The paper shows that privacy against malicious senders is a natural consequence of 2-round OT protocols with semi-honest privacy.
  • Cut-and-Choose with Defenses: The core of the compiler involves running multiple parallel sessions of the underlying 2-round OT protocol. In later rounds, parties provide "defenses" to justify their actions. This is combined with a cut-and-choose mechanism, where some sessions are opened up for verification, allowing the simulator to extract information.
  • Information-Theoretic and Black-Box: The compiler is "information-theoretic," meaning it doesn't rely on any cryptographic assumptions beyond the existence of the underlying OT protocol. It's also "black-box," meaning it treats the underlying OT protocol as an opaque oracle, without needing to understand its internal workings.
  • Plain Model: Crucially, the compiler operates in the "plain model," meaning it doesn't require any pre-shared keys, reference strings, or other setup assumptions.
  • Improved Communication Complexity: The paper claims a significant improvement in communication complexity, reducing it from quartic to cubic in the security parameter compared to prior work.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Security Gap Efficiently: The most significant insight is demonstrating that a robust compiler from weaker privacy-only OT to stronger simulatable OT is possible without additional cryptographic assumptions and in the plain model. This is a major step towards more practical and secure cryptographic constructions.
  • The Power of "Defensible Privacy": The paper highlights that "defensible privacy" for receivers is a key property that, when combined with privacy against malicious senders, is sufficient for their compiler. This suggests that sometimes slightly weaker, but more achievable, security notions can still lead to powerful results.
  • Cut-and-Choose as a General Tool: The successful application of a cut-and-choose strategy, combined with "defenses," to achieve simulation-based security in the plain model showcases its versatility beyond traditional uses.
  • Round Optimality is Achievable: The compiler achieves 4-round simulatable OT, which is known to be round-optimal in the plain model, demonstrating that efficiency and strong security can be met simultaneously.

Key Results

  • A Black-Box, Information-Theoretic Compiler: The paper presents a compiler that transforms any 2-round privacy-only OT protocol into a 4-round simulatable OT protocol in the plain model.
  • Improved Communication Complexity: The compiler offers a cubic improvement in communication complexity over the best previously known transformations.
  • Minimal Assumptions: The compiler only requires the existence of a 2-round OT protocol with privacy against defensible receivers and malicious senders, and does not rely on any additional cryptographic assumptions.

Limitations and Future Work

  • Open Problem: The authors note that it remains an open problem to find a similar transform that starts from OT protocols satisfying only privacy against semi-honest receivers (rather than defensible receivers) in the plain model.
  • Hardness Assumptions: They also suggest exploring constructions of 2-round OT protocols in the plain model that are private against defensible receivers and rely on hardness assumptions from which we don't currently know how to derive 2-round OT protocols private against malicious receivers. This could lead to even broader applicability.

Summary updated

BibTeX
@inproceedings{venturi2022from,
  author = {Daniele Venturi and Varun Madathil and Chris Orsini and Alessandra Scafuro and Daniele Venturi},
  title = {{From Privacy-Only to Simulatable OT: Black-Box, Round-Optimal, Information-Theoretic}},
  booktitle = {Itc},
  year = {2022},
  doi = {10.4230/lipics.itc.2022.5},
}
Figure