Rafail Ostrovsky - Publications

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

Melissa Chase, Rafail Ostrovsky, Ivan Visconti


In STOC 1987, Goldreich, Micali and Wigderson [ GMW87] 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] when the input size is public, thus it is a strict generalization of [GMW87].

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] and [CV12]. 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 wil be used in our ideal-world formulation and may be of independent interest.

comment: EUROCRYPT 2015 pp: 532-560

Fetch PDF file of the paper

Back to Publications List