LATTICE-BASED VECTOR COMMITMENT AND KEY-VALUE COMMITMENT WITH HOMOMORPHIC PROPERTIES

MPhil Thesis Defence


Title: "LATTICE-BASED VECTOR COMMITMENT AND KEY-VALUE COMMITMENT WITH 
HOMOMORPHIC PROPERTIES"

By

Mr. Arman HAGHIGHI


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 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 post-quantum era as 
their security assumption is broken using quantum computers. This raised 
the question if there are any secure vector commitment or key-value 
commitment schemes in the age of quantum computers. We answer this 
question positively by introducing a transparent lattice-based vector 
commitment and key-value commitment which security is based on a 
presumably post-quantum secure assumption called short integer 
solution(SIS) in lattices. Although 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 using a traditional 
Merkle tree using SHA-2, Although our construction is more update friendly 
and because of its structure it provides some algebraic properties that a 
traditional Merkle tree lack.

The general idea of our construction uses a primitive called generalized 
hash tree which has the same structure as a Merkle tree 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 
concatenation or their additions 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 in which the first one uses a vector commitment for a sparse 
vector and the other one improves it by using cuckoo hash.

In the end, we have implemented our constructions and benchmarked them in 
different aspects such as setup time, Commitment time and size, proof time 
size, etc.


Date:  			Thursday, 5 August 2021

Time:			2:30pm - 4:30pm

Zoom meeting: 
https://hkust.zoom.us/j/96388260083?pwd=Z2hyWWNzVWFwVVdWN2JpVUREMjdGZz09

Committee Members:	Dr. Dimitris Papadopoulos (Supervisor)
 			Prof. Cunsheng Ding (Chairperson)
 			Dr. Shuai Wang


**** ALL are Welcome ****