Must You Know the Code of f to Securely Compute f?

Date Added: Aug 2012
Format: PDF

When Alice and Bob want to securely evaluate a function of their shared inputs, they typically express the function as a (boolean or arithmetic) circuit and then securely evaluate that circuit, gate-by-gate. In other words, a secure protocol for evaluating f is typically obtained in a non-black-box-way from f itself. Consequently, secure computation protocols have high overhead (in communication & computation) that is directly linked to the circuit-description complexity of f. In other settings throughout cryptography, black-box constructions invariably lead to better practical efficiency than comparable non-black-box constructions.