Secure Database Commitments and
Universal Arguments of Quasi Knowledge
Melissa Chase (Microsoft Research
Ivan Visconti (
Abstract:
In this work we focus on a simple database
commitment functionality where besides the standard security properties, one
would like to hide the size of the input of the sender. Hiding the size of
the input of a player is a critical requirement in some applications, and
relatively few works have considered it. Notable exceptions are the work on
zero-knowledge sets introduced in [MRK03], and recent work on size-hiding
private set intersection [ADT11]. However, neither of these achieves a secure
computation (i.e., a reduction of a real-world attack of a malicious
adversary into an ideal-world attack) of the proposed functionality.
The first result of this submission consists in defining “secure”
database commitment and in observing that previous constructions do not
satisfy this definition. This leaves open the question of whether there is
any way this functionality can be achieved.
We then provide an affirmative answer to this question by using new
techniques that combined together achieve “secure” database
commitment. Our construction is in particular optimized to require only a
constant number of rounds, to provide non-interactive proofs on the content
of the database, and to rely on the existence of a family of CRHFs. This is the first result where input-size hiding
secure computation is achieved for an interesting functionality and moreover
we obtain this result with standard security (i.e., simulation in expected
polynomial time against fully malicious adversaries, without random oracles,
without non-black-box extraction assumptions, without hardness assumptions
against super-polynomial time adversaries).
A key building block in our construction is a universal argument enjoying an
improved proof of knowledge property, that we call quasi-knowledge. This
property is significantly closer to the standard proof of knowledge property
than the weak proof of knowledge property satisfied by previous
constructions.