Repository files navigation

The TNO PET Lab consists of generic software components, procedures, andfunctionalities developed and maintained on a regular basis to facilitate andaid in the development of PET solutions. The lab is a cross-project initiativeallowing us to integrate and reuse previously developed PET functionalities toboost the development of new protocols and solutions.

The package tno.zkp.templates is part of the TNO Python Toolbox.

The research activities that led to this implementation is made possible by

• The Alliance of Privacy Preserving Detection of Financial Crime, consisting ofDe Volksbank, TMNL, CWI, ABN AMRO, Rabobank, TNO.
• The confidential 6G project
• The Early Research Project of TNO "Next generation crypto"

Limitations in (end-)use: the content of this software package may solely beused for applications that comply with international export control laws.
This implementation of cryptographic software has not been audited. Use at yourown risk.

Documentation of the tno.mpc.encryption_schemes.shamir package can be foundhere.

Easily install the tno.mpc.encryption_schemes.shamir package using pip:

$python -m pip install tno.zkp.templates

If you wish to run the tests you can use:

$python -m pip install'tno.zkp.templates[tests]'

This library contains the templates with which we can create a zero-knowledgeproof(ZKP). The templates are protocols, which should to be inherited by any ofthe classes to support ZKPs. An example has been added in this repository. Theexample is the modulus linear form. The modulus linear form is a separatemodule, which is a basic building block that can be used to create ZKPs.

The ZKP library is based on Thomas Attema's dissertation Compressed$\Sigma$-protocol Theory, which can be foundhere.Many concepts are taken from it, and there will be references throughout thecode to the dissertation. In this README the crucial concepts from thedissertation needed to use this library will be explained in short. If anythingis unclear, feel free to raise an issue at the code repository.

Before explaining how to use the library several concepts need to be explained.The concepts are used throughout the interface and knowing them beforehand makesit easier to use the library.

A zero-knowledge proof of knowledge (referred to as ZKP in this README) can beused to show you possess information without revealing the information itself.This can be used in many different settings, but currently uses with adistributed ledger are common.

A homomorphism is a fundamental building block of the ZKP. The homomorphismevaluates a function on a vector of input elements. A homomorphism isrepresented in the literature as$\psi_n$, where$n$ is the length of the inputvector.

The homomorphism maps the input vector from an abelian group$\mathbb{G}^n$ to asingle element of another group$\mathbb{H}$. In particular the original domainand target image groups can have different group operators. In the dissertationa mapping is made from an additive group$\mathbb{G}$ to a multiplicative group$\mathbb{H}$.

A sigma protocol is a three-step process which creates a zero knowledge proof.The three-step process uses a homomorphism, an input vector and random elementsfrom a group.

The three steps are shown in the sequence diagram below. Each step is explainedin this section.

Figure 1.Two parties exchange information in which the Prover wants toconvince the Verifier that he knows secret input $x$ without revealing $x$.

Before starting a sigma protocol certain pieces of information are calculated.The information consists of the following:

• Private input:$x$ secret of the prover
• Public input:$P$ and the homomorphism$\psi \in \texttt{Hom}(\mathbb{G}^n,\mathbb{H})$
• Prover's claim:$P=\psi(x)$

In the first a commitment is made by the prover. The commitment is made bygenerating a random input$r$. The random input$r$ is evaluated by thehomomorphism$\psi$ giving$A$.$A$ is the commitment sent to the verifier.

The verifier sends a challenge$c$ to the prover. The challenge is a singleelement (as opposed to a vector). The challenge needs to be able to do thefollowing operations:

• Multiply with homomorphism input, which is a vector of elements from group$\mathbb{G}$. This operation is needed to create the response mentioned in thethird step.
• Take to the power of the resulting group$\mathbb{H}$. This operation isneeded to verify the proof.

In this library the homomorphism maps input from additive group operation to agroup with multiplicative operations. Depending on your use-case and the chosenimplementation different operations might be needed.

Create the response by calculating a new input for the homomorphism. The inputis based on$r$, the challenge$c$ and the secret input$x$. The response iscalculated as follows:$z=r+cx$.

The verifier can now check the proof of knowledge by testing if$\psi(z)$ isequal to$A\cdot P^c$.

To be able to make the proof of knowledge non-interactive we need to be able toreplace the challenge of the verifier. Replacing the challenge can not be doneby just picking one as the prover. To replace the challenge we use theFiat-Shamir transformation. The transformation uses a hashing algorithm tocreate the challenge.

Making the proof non-interactive prevents communication overhead and enables theoption for the prover to create a proof of knowledge without the verifier beingpresent. The verifier can then check the proof of knowledge on its own when thenecessary information has been retrieved.

To support the creation of a sigma protocol the template classes have beencreated. The template classes can be split into two categories.

The first category are the classes needed to create a basic sigma protocol. Thebasic sigma protocol creates a proof of knowledge in a non-interactive way. TheStandardSigmaProtocol object contains all the information needed for theverification and none of the private information. The object can therefore beshared with the verifier for verification.

To create aStandardSigmaProtocol you need some random input and ahomomorphism. For this example we will use theModulusLinearForm homomorphismincluded in this package. TheModulusLinearForm implements theHomomorphismobject and is located in the namespacetno.zkp.modulus_linear_form.

In the code snippet below we create aModulusLinearForm corresponding to thefollowing formula$1\cdot x_1 + 2\cdot x_2 + 3 \cdot x_3$ with the modulus$13$.The secret input is a random input generated by the homomorphism.

Generating the proof of knowledge is relatively straight forward. You call themethodgenerate_proof with the homomorphism, the secret input and the hashfunction. The class will handle the process as described in the steps above.

To verify the proof of knowledge you only need to call theverify function.

fromtno.zkp.modulus_linear_formimportModulusLinearFormfromtno.zkp.templatesimportStandardSigmaProtocolhomomorphism=ModulusLinearForm([1,2,3],13)secret_input_x=homomorphism.random_input()proof_of_knowledge=StandardSigmaProtocol.generate_proof(homomorphism,secret_input_x,"sha256")assertproof_of_knowledge.verify()

To compress a proof of knowledge there are some requirements on the homomorphismand the input. The requirements are enforced using theCompressibleHomomorphism and theCompressibleHomomorphismInput abstractclasses.

Compressing a proof of knowledge makes the verification of the protocolcheaper. The cost savings occur due to a compression mechanism. Thecompression mechanism is described in detail in the dissertation.

TheModulusLinearForm from the previous example satisfies the requirements.Therefore, we can use the previous proof of knowledge for compression.

To apply the compression we need to use a compression mechanism. The compressionmechanism from the dissertation has been implemented in this template. To applyit you need to do the following:

fromtno.zkp.templatesimportfull_compression# compress the proof of knowledge as much as possiblecompressed_protocol=full_compression(proof_of_knowledge)assertcompressed_protocol.verify()

The functionfull_compression reduces the ZKP from length$n$ until it can notbe compressed anymore, which is a length of 1. The function used for thecompression is calledcompression and is available to the user as well. Thecompression function halves the length of the ZKP.