THESIS
2021
1 online resource (xi, 76 pages) : illustrations (some color)
Abstract
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.
Post a Comment