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$ Oct 17, 2014 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, 2014 at 20:15
  • $\begingroup$ Well, I didn't know that! Thanks for the heads up guys! $\endgroup$
    – Cobe
    Oct 17, 2014 at 20:25
  • $\begingroup$ @ThomasM.DuBuisson Maybe change that into an answer? Negative answers are answers just as well. $\endgroup$
    – Maarten Bodewes
    Oct 19, 2014 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, 2017 at 19:30

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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