5
$\begingroup$

I've found numerous places that claim that the paper "How to Generate and Exchange Secrets" by Andrew Yao introduces garbled circuits as a solution to the secure multiparty computation problem. However, I can only seem to locate the extended abstract which lacks proofs and does not seem to mention garbled circuits. It only appears to define useful properties for solving the problem and state several theorems without proof. A complete version of the paper is mentioned at the end of this extended abstract, but I cannot locate it. Is the complete version under a different name?

I have already found expositions that explain garbled circuits. At this point I am interested in finding the complete paper, if possible.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Is your goal to find the full paper, or to learn the ideas of Yao's garbled circuits construction? If the latter, there are lots of expositions of it (in cryptography lecture notes, textbooks, more recent papers). Which are you looking for? $\endgroup$ – D.W.♦ Jun 14 '14 at 18:10
  • $\begingroup$ I have found expositions that explain garbled circuits, but I am also interested in finding the complete paper. $\endgroup$ – user2309167 Jun 14 '14 at 18:13
  • 1
    $\begingroup$ Complete versions don't always exist. If you can't find it, it's probably not there. $\endgroup$ – Yuval Filmus Jun 14 '14 at 23:37
  • 2
    $\begingroup$ Interesting. In the bibliography of the Turing award page it says that garbled circuits were only implicit in the paper, and that he only introduced them explicitly in the talk he gave at the conference. amturing.acm.org/bib/yao_1611524.cfm#bib_6 $\endgroup$ – Wandering Logic Jun 15 '14 at 13:04
  • 1
    $\begingroup$ Please five a full reference; it may be important for a question like this. $\endgroup$ – Raphael♦ Jul 15 '14 at 13:09
1
$\begingroup$

Garbled circuits were only implied by the extended abstract. They were only explicitly introduced in the talk given by Andrew Yao at the conference.

This is clear from a footnote on the Turing Award Page:

The first of these two papers introduces secure function evaluation, and gives a > protocol for the famous Millionaires’ Problem. In talks related to these papers > Yao introduced a technique for secure computation known as garbled circuits.

which may be found here: http://amturing.acm.org/bib/yao_1611524.cfm#bib_6

Credit is due to Wandering Logic for giving this very helpful answer in the comments above.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Wikipedia now has a brief survey of the history of garbled circuits with reference to published materials:

https://en.wikipedia.org/wiki/Garbled_circuit

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.