A (Zero-Knowledge) Vector Commitment with Sum Binding and its Applications. (18th November 2019)

• Record Type: Journal Article
• Authors: Wang, Qiang; Zhou, Fucai; Xu, Jian; Xu, Zifeng
• Is Part Of: Computer journal. Volume 63:Number 4(2020)
• Page Start: 633
• Page End: 647
• Publication Date: 2019-11-18
• Subjects: vector commitment -- commitment -- position binding -- sum binding -- verifiable databases -- zero knowledge; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz115
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Vector commitment (VC) schemes allow committing to an ordered sequence of ${q}$ values ${(m_1, \cdots, m_q)}$ in such a way that one can later open the commitment at specific positions. However, the existing VC schemes suffer from two substantial shortcomings that limit their use: (i) the commitments cannot be opened except at some specific positions, and (ii) their security only captures position-binding but offers no privacy: the client may learn additional information about the committed sequence through the proofs and the commitments. To resolve these problems, we first extend VC to a more expressive primitive called VC with sum binding (VCS), in which the commitment can also be opened to the sum of all elements in the committed sequence. VCS additionally satisfies the security of sum binding, which guarantees that the commitment cannot be opened to different sums. To enhance its privacy, we extend VCS to zero-knowledge VCS (ZKVCS), in which commitments and proofs constructed during the protocol execution leak nothing about the committed sequence. We formalize this new property by a standard real/ideal experiment. Meanwhile, the detailed performance analyses and simulations show that our proposed schemes are more practical. Finally, we introduce a novel notion of (zero-knowledge) verifiable database supporting sum and show how to construct it from our (ZK)VCS scheme.