I was just reading these notes on garbled (Yao) circuits and I just stuck trying to figure out how an implementation of Table 1 would work using RSA encryption. In RSA the public key is $(n,e)$. So for the first row, for example, I guess that ${\rm Enc}_{k_1^0}(k_2^0)$ means: "encrypt the "message" $k_2^0$ with the key $k_1^0$". So does the value of $k_1^0$ stand for $n$ or $e$ of RSA? What am I missing here?

  • 3
    $\begingroup$ Well for starters, Yao GC uses symmetric cryptography for the gates. Does that help or did I misunderstand your question? $\endgroup$ – Thomas M. DuBuisson Oct 17 '14 at 20:15
  • 1
    $\begingroup$ RSA typically isn't used for Yao's method. They define what they use for enc a little lower in the document $\endgroup$ – mikeazo Oct 17 '14 at 20:15
  • $\begingroup$ Well, I didn't know that! Thanks for the heads up guys! $\endgroup$ – Cobe Oct 17 '14 at 20:25
  • $\begingroup$ @ThomasM.DuBuisson Maybe change that into an answer? Negative answers are answers just as well. $\endgroup$ – Maarten Bodewes Oct 19 '14 at 16:29
  • $\begingroup$ As mentioned garbled circuits usually uses symmetric cryptography. However, it also seems you are a little confused about notation. I.e., even if RSA were used, when we talk about encrypting with the key $k^0_1$, then $k^0_1$ would not be either $n$ or $e$ it would be both. In other words we would have $k^0_1 = (n, e)$. $\endgroup$ – Guut Boy Apr 2 '17 at 19:30

The notation you are seeing is for symmetric crypto. Garbled circuits typically use symmetric crypto since it can and symmetric crypto is fast. You may be able to do garbled circuits with asymmetric crypto, but it is definitely non-standard and may have subtle issues.

|improve this answer|||||

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.