Implementation of code-based zero-knowledge identification schemes

General Implementation Aspects

There are separated, stand-alone implementations for each of the three identification schemes. They all contain

 the Fast Syndrome-Based hash function
 a pseudorandom number generator based on the construction of Fischer and Stern
 a randomly chosen permutation over vectors of length n

Furthermore, the implementations allow for choosing one of the following matrix types:

 random matrix: the whole matrix (resp. the right block A of a matrix I|A) is chosen at random
 quasi-cyclic matrix: the first line of A (in I|A) is chosen at random and then shifted to produce the whole matrix
 quasi-dyadic matrix: the first line of A (in I|A) is chosen at random and then permuted for the other lines of A according to the quasi-dyadic scheme

Quasi-cyclic and quasi-dyadic matrices allow for a much smaller public key and lower storage overhead while introducing only little higher amount of computation overhead.

 C Implementation

You find the code of the C implementation attached as stern_C-code.zip,
veron_C-code.zip resp. cayrel_C-code.zip for the three schemes. In the following we give a short overview over the timing
results.

Timing Results

The tables below show our timing results for all three schemes each with all three matrix types, depending on the security parameter n and using a hash length of 160 bits. The results are shown for one round and a complete identification in 28 rounds for Stern and Véron (for 28 rounds the cheating probability is less than 2^-16) and 16 rounds for Cayrel et al. (for the same security level).

 New C Implementation

In total, six different schemes have been implemented:
the Stern, Veron and CVE identification schemes and the corresponding signature schemes based on the Fiat-Shamir transform.
You find the code of the the new implementation attached as stern_c.tgz,
cve_c.tgz,
veron_c.tgz,

The implementation assumes that the dimensions of the matrices are a multiple of 64. The public keys G and H are given in systematic form, i.e. G = I_k and H = I_n-k respectively, where only the redundant part R is used.

In the quasi-cyclic and quasi-dyadic cases, the matrices G and H consist of cyclic and dyadic submatrices of size 64x64, because 64 is the natural number to use on a 64-bit machine.

For the generation of random vectors and hash values used in our identification protocols we deployed Keccak (http://keccak.noekeon.org) one of the last five remaining candidates of the NIST hash function competition for SHA-3. We have chose Keccak, because it can be used as a hash function and as stream cipher at the same time. But note that it can be replaced by any other suitable scheme providing the necessary functionality.

Finally, all the tests have been carried out only on an Intel(R) Core(TM)2 Duo CPU E8400@3.00GHz machine running Linux 2.6.32-21 (Ubuntu). The implementation has been compiled with gcc 4.4.3, it assumes a 64-bit architecture.

Stern scheme
This scheme uses a binary parity check matrix H = I_n-k of size r x n, where r = n-k and k = n/2.

Due to the row-major order of C, the product sH^T is more efficient as Hs^T (s a binary vector of length n). Hence, the implementation uses the transposed matrix H^T instead of H.

Veron scheme
This scheme uses a binary generator matrix G = I_k of dimensions kxn, where k = n/2. Again, in the quasi-cyclic and quasi-dyadic case, the cyclic and dyadic submatrices have a size of 64x64 bits. As in Stern, if G is quasi-cyclic or quasi-dyadic, then the submatrix R would consist of 36 cyclic or dyadic submatrices of size 64x64 bits.

CVE scheme
It uses a parity check matrix H of size rxn over Fq, where q=2^m,
1 <= m <= 16, r = n-k and k = n/2. As in the Stern scheme, the implementation uses the transposed matrix H^T instead of H.

Again, if H is quasi-cyclic or quasi-dyadic, then the submatrix R would consist of 36 cyclic or dyadic submatrices of 64x64 field elements.

The matrix size is always measured in numbers of field elements. Each field element occupies invariably 2 bytes of memory. Strictly speaking, this would be necessary only in the case m=16. However, using only the necessary bits would complicate the code and slow down the computation. In environments in which memory is a very valuable resource, this fact had to be taken into account.

For the measurements we used m=8, q=256.

Signature schemes based on Fiat-Shamir transform
Using the Fiat-Shamir transform, one can transform identification schemes to signature schemes.

Note that the signer and verifier parts are always located in the same executable, thus the two parts can communicate in almost no time. In reality, they would reside on different machines, such that additional costs over some communication link had to be taken into account.

Stern signature scheme timings
For the Stern timing results we give the time for one round, separated in signing and verification time (s/v). The size of the message to be signed is given in MiB.

Veron signature scheme timings

CVE signature scheme timings

Remarks
The signature size (an average value of several runs over 28 resp. 16 rounds. for Stern and Veron is about 60.000 bytes and for CVE about 15.000 bytes.

The runtime is dominated by Keccak creating random vectors u[0],...,u[rounds-1]
before entering the loop of 28 resp. 16 rounds, which could also be confirmed
profiling the implementation directly with gprof (the profiler
contained in gcc).

 Java Implementation

You find the code of the Java implementation attached as stern_Java.zip, veron_Java.zip resp. cayrel_Java.zip for the three schemes. In the following we give a short overview over the timing results.

Timing Results

The tables below show our timing results for all three schemes each with all three matrix types, depending on the security parameter n and using a hash length of 160 bits. The results are shown for one round and a complete identification in 28 rounds for Stern and Véron (for 28 rounds the cheating probability is less than 2^-16) and 16 rounds for Cayrel et al. (for the same security level).