Zero-knowledge proof (ZKP) systems help principals to verify the
veracity of a piece of information without sharing the data. They are
widely used to preserve confidentiality and ownership of data. ZKP can
be seen as a reusable building block for making the future internet
trustworthy and secure. In this project (0KNOW) we aimed to develop a
lightweight group-theoretic zero-knowledge proof system that can be
employed as a cryptographic primitive in many security protocols such as
identification, authentication, or credential ownership.
In 0KNOW, we have studied NP group-theoretic problems and selected the
search version of the subgroup distance problem within the Hamming
metric. Breifly, for given distance $k$, given element $g$, given
subgroup H from the symmeric group of degree $n$ ($S_n$), problem asks
to find an element h from the subgroup H which is at most $k$ distance
from $g$. Our choice as platform subgroup is an elementary abelian
subgroup. We have designed a novel black-box 3-round statistical zero
knowledge proof of knowledge protocol called the Subgroup Distance Zero
Knowledge Proof (SDZKP). It can be seen as a Stern-type protocol. It has
3-special-soundness property which assures knowledge soundness with
error $\frac{2}{3}$.
All in all, we present a new zero-knowledge identification scheme rooted
in the complexity of the subgroup distance problem within the Hamming
metric. SDZKP incorporates a cryptographically secure pseudorandom
number generator to obscure secrets and employs a Stern-type algorithm
to ensure strong security features.