We continue the study of vector commitments (VC) and key-value commitments (KVC) by proposing a lattice-based vector commitment and key-value commitment. Generally speaking, a vector commitment is a scheme that allows one to commit to an ordered set and later on be able to open a position in a verifiable manner by producing a corresponding proof. It should be hard for any adversary to be able to commit to a vector and be able to open a position with two different values by having valid proofs for both. This is known as position binding which is used as the security definition of a vector commitment scheme. Similarly, the key-value commitment creates a short digest over a map of key-value pairs which can be opened to any specific key while producing the corresponding proof. One can see a...[ Read more ]

We continue the study of vector commitments (VC) and key-value commitments (KVC) by proposing a lattice-based vector commitment and key-value commitment. Generally speaking, a vector commitment is a scheme that allows one to commit to an ordered set and later on be able to open a position in a verifiable manner by producing a corresponding proof. It should be hard for any adversary to be able to commit to a vector and be able to open a position with two different values by having valid proofs for both. This is known as position binding which is used as the security definition of a vector commitment scheme. Similarly, the key-value commitment creates a short digest over a map of key-value pairs which can be opened to any specific key while producing the corresponding proof. One can see a vector commitment as a key-value commitment scheme with keys substituted with indexes. Vector commitments and key-value commitments are finding more and more applications recently due to the overwhelming growth in areas such as cryptocurrencies, verifiable databases, accumulators, etc.

Several constructions for vector commitments and key-value commitments with assumptions like strong RSA or q – SDH over elliptic curves have been proposed but these constructions are not secure in the post-quantum era as their security assumption can be broken using quantum computers. This raises the question of whether there are vector commitment or key-value commitment schemes that are secure against quantum computers. We answer this question positively by introducing a transparent lattice-based vector commitment and key-value commitment whose security is based on a presumably post-quantum secure assumption called short integer solution (SIS) in lattices. However, this comes at the cost of larger proofs and larger commitments in comparison to previous methods.

A "naive" post-quantum vector commitment can be built by a traditional Merkle tree using a cryptographic hash function, but our construction is more update-friendly and because of its structure, it provides some algebraic properties that a traditional Merkle tree lacks.

The general idea of our construction is to use a primitive called generalized hash tree which has the same structure as a Merkle tree but with a different lattice-based hash with two inputs. We prove that this instantiation of generalized tree is collision resistant and can be used to build a vector commitment.

Another advantage of our construction is the homomorphic properties that lattices provide us. As an example, by having the commitment of two different vectors one can easily calculate the commitment of their addition without knowing the vectors themselves. Although some homomorphic features are available in previous constructions, they are mostly inefficient.

We expand our work by building two lattice-based key-value commitment schemes where the first one uses a vector commitment for a sparse vector and the second one improves it by using cuckoo hash.

Finally, we have implemented our constructions and benchmarked them in different aspects such as setup time, commitment time and size, proving time, proof size, etc.