Executable Proofs, Input-Size Hiding Secure Computation and a New Ideal World

In STOC 1987, Goldreich, Micali and Wigderson [GMW87 (opens in new tab)] proved a fundamental result: it is possible to securely evaluate any function. Their security formulation consisted of transforming a real-world adversary into an ideal-world one and became a de facto standard for assessing security of protocols.

In this work we propose a new approach for the ideal world. Our new definition preserves the unconditional security of ideal-world executions and follows the spirit of the real/ideal world paradigm. Moreover we show that our definition is equivalent to that of [GMW87 (opens in new tab)] when the input size is public, thus it is a strict generalization of [GMW87 (opens in new tab)].

In addition, we prove that our new formulation is useful by showing that it allows the construction of protocols for input-size hiding secure two-party computation for any two-party functionality under standard assumptions and secure against malicious adversaries. More precisely we show that in our model, in addition to securely evaluating every two-party functionality, one can also protect the input-size privacy of one of the two players. Such an input-size hiding property is not implied by the standard definitions for two-party computation and is not satisfied by known constructions for secure computation. This positively answers a question posed by [LNO13 (opens in new tab)] and  [CV12 (opens in new tab)]. Finally, we show that obtaining such a security notion under a more standard definition (one with a more traditional ideal world) would imply a scheme for “proofs of polynomial work”, a primitive that seems unlikely to exist under standard assumptions.

Along the way, we will introduce the notion of “executable proof”, which will be used in our ideal-world formulation and may be of independent interest.