7
$\begingroup$

Under the assumption that "secure" encryption exists, secure evaluation of functions represented by Boolean circuits is possible by Yao's garbling scheme [Y1]. My question is whether secure evaluation of functions represented by Boolean formulae is an easier problem (i.e., possible in the information theoretic setting).

(This is true, for example for secret sharing: Benaloh and Lichter [BL] gave an perfect scheme for access structures described by monotone Boolean formulae, but for monotone Boolean circuits one needs to assume secure encryption [Y2].)

References:

[BL]: Benaloh and Lichter. Generalized secret sharing and monotone functions. Crypto’88

[Y1]: Yao. How to generate and exchange secrets. FOCS’86.

[Y2]: Yao. Protocols for secure computations. FOCS'82

$\endgroup$
7
$\begingroup$

For log-depth circuits, it is possible to use an information-theoretic version of Yao's garbled circuits. Note that in a garbled gate, each key is used to encrypt twice. Thus, if the keys on the input wires are double the length of the keys on the output wires, then one-time pad encryption can be used and the result is information theoretically secure.

See the paper Gate Evaluation Secret Sharing and Secure One-Round Two-Party Computation by Vlad Kolesnikov, and references within.

| 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.