On the Security of KOS

Benjamin E. Diamond

Paper 2022/1371

On the Security of KOS

Benjamin E. Diamond, Irreducible

Abstract

We study the security of the random oblivious transfer extension protocol of Keller, Orsini, and Scholl (CRYPTO '15), whose security proof was recently invalidated by Roy (CRYPTO '22). We show that KOS is asymptotically secure. Our proof involves a subtle analysis of the protocol's "correlation check", and introduces several new techniques. We also study the protocol's concrete security. We establish concrete security for security parameter values on the order of 5,000. We present evidence that a stronger result than ours—if possible—is likely to require radically new ideas.

Note: Significant overhauls to the exposition; also added numerous new examples and remarks.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Contact author(s): benediamond @ gmail com
History: 2024-07-14: last of 5 revisions; 2022-10-12: received; See all versions
Short URL: https://ia.cr/2022/1371
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1371,
      author = {Benjamin E. Diamond},
      title = {On the Security of {KOS}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1371},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1371}
}