1
$\begingroup$

I understood garbled circuit can hide some function $f$ jointly by multi parties. With quantum computer, can we see the circuit inside it?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

Garbled circuits are not really a primitive, but more of a protocol.

Furthermore, garbled circuits are generally concealing their semantic values thanks to a cipher such as AES, see this answer to get more details on the whole protocol and the tools it relies on.

So, in order to break garbled circuit, you want to be able to break AES (or whatever cipher used to conceal the values), but the best speed up you might get against AES (and other secure block ciphers) through quantum computer would be thanks to Grover's search algorithm and would be of order $O(\sqrt{n})$, which shouldn't be a problem for AES-256, but could be a problem for AES-128. See also this paper, and its references, to learn more on quantum attacks against AES.

Hence garbled circuits shouldn't really be impacted by quantum computers, even more because you could actually plug a post-quantum cipher (when we got those) in the protocol and keep going.

$\endgroup$
2
  • $\begingroup$ Hi, I am studying garbled circuits recently. It seems we should use oblivious transfer (OT) in the protocol. But OT seems can be affected by quantum computers since OT mostly built by RSA primitives(see wiki here). And we all know RSA will be broken under quantum era. Can we say garbled circuits with broken OT still safe under quantum attack? Or we could replace RSA style OT with post quantum style OT? And then it will be ok under quantum attack? $\endgroup$
    – zbo
    Oct 9, 2022 at 7:57
  • $\begingroup$ @zbo RSA-based OTs aren't very commonly used, as RSA is not very communication efficient. Elliptic curves (using Diffie-Hellman assumptions) are much more common now, as it only takes 256 bits to send an elliptic curve point, while an RSA modulus has to be thousands of bits long. There are OTs based on other assumptions as well. This is one that I'm familiar with that can be based on the lattice assumption Learning With Errors (LWE), which is believed to be secure against quantum adversaries. $\endgroup$
    – qbt937
    Nov 27, 2022 at 11:50

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.