Modern proof of Kilian's result that OT is complete for 2PC

lamontap

7/27/24, 3:58 PM

I'm looking for a textbook or article that spells out the details of Kilian's paper on the completeness of oblivious transfer for secure two-party function evaluation (2PC). Kilian's paper is in the form of an extended abstract which doesn't include many of the details. Moreover, there have been many development in the 2PC theory since Kilian's seminal work, such as the universal composability framework of Canetti. An ideal reference would be one that gives a full proof of the completeness of OT in this framework.

I have read Oded Goldreich's book chapter on 2PC which uses commitments and ZKProofs to compile a semi-honest protocol into a maliciously secure protocol. However, I'm mostly interested in the OT-based approach of Kilian.

1 + 2

oblivious-transfer

multiparty-computation

reference-request

Mikero

7/27/24, 11:37 PM

Are you more interested in an exposition of Kilian's protocol, or any protocol establishing the completeness of OT? Also, do you care about information-theoretic security? Kilian's result is an information-theoretic protocol for any 2PC from OT. If you are OK with computational assumptions, then variants of Yao's protocol can give you any 2PC from OT.

lamontap

7/28/24, 2:06 PM

I'm interested in the information theoretic setting (where OT is the only assumption). References that use other techniques than Kilian's to establish the completeness of OT in an info theoretic setting are also welcome.

Score:3

Crypto

Mikero

7/29/24, 7:32 PM

The paper that comes to mind is:

Founding Cryptography on Oblivious Transfer – Efficiently: Yuval Ishai, Manoj Prabhakaran, Amit Sahai

You can tell by the title that it is following in Kilian's footsteps. The protocol is a bit more complicated, since it uses MPC-in-the-head techniques (so if you want to understand the complete protocol from scratch, you first have to understand an actively secure protocol in the honest majority setting and a passively secure protocol in the dishonest majority setting). But the paper gives rather full details. In other references, you'll see this construction referred to as "the IPS compiler."

+ 1

lamontap

7/31/24, 7:48 PM

This is very close to what I was looking for. Appendix B especially for the two-party case. Thanks!

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Modern proof of Kilian's result that OT is complete for 2PC

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.