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


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.


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.