Home > Research > Code-based cryptography > Code-based cryptosystems : implementations > Implementation of code-based zero-knowledge identification schemes

Implementation of code-based zero-knowledge identification schemes

Tuesday 19 April 2011, by Cayrel , Felix Günther and Holger Rother , Gerhard Hoffman

In the context of the Cryptography Lab in the winter term 2010/2011, our task was to implement three different code-based zero-knowledge identification schemes, namely the ones proposed by Stern in "A new identification scheme based on syndrome decoding" in 1993, Véron in "Improved identification schemes based on error-correcting codes" in 1996, and Cayrel, Véron, and El Yousfi in "A zero-knowledge identification scheme based on the q-ary Syndrome Decoding problem" in 2010.

We implemented these three schemes in C and Java.

This article gives a brief overview over the implementation including some timing results; a detailed report of our work as well as the complete source code are attached.

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).

Stern Timing Results
security level2^402^107
n, r, w:1024, 512, 321024, 512, 128
one round28 roundsone round28 rounds
Random12.0ms336.0ms156.9ms4393.2ms
Quasi-Cyclic14.6ms408.8ms156.3ms4376.4ms
Quasi-Dyadic11.1ms310.8ms135.7ms3799.6 ms
Véron Timing Results
security level2^402^107
n, r, w:1024, 512, 321024, 512, 128
one round28 roundsone round28 rounds
Random15ms420.0ms144.9ms4057.2ms
Quasi-Cyclic15.7ms439.6ms154.8ms4334.4ms
Quasi-Dyadic12.3ms344.4ms135.4ms3781.2ms
Cayrel et al. Timing Results
security level2^732^143
n, r, w, q:128, 64, 49, 256256, 128, 97, 256
one round16 roundsone round16 rounds
Random5.8ms92.8ms16.8ms268.8ms
Quasi-Cyclic9.1ms145.6ms23.3ms372.8ms
Quasi-Dyadic3.3ms52.8ms11.5ms184.0ms

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.

Stern timing results
Matrix TypeDim: nxrWeight1 rnd [ms]28 rnds [ms]Sec
Random768x384760.0421.0472^80
QC768x384760.0380.9592^80
QD768x384760.0781.5062^80

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.

Veron timing results
Matrix TypeDim: nxrWeight1 rnd [ms]28 rnds [ms]Sec
Random768x384760.0530.8962^80
QC768x384760.0490.9622^80
QD768x384760.0741.4942^80

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.

CVE timing results
Matrix TypeDim: nxrqWeight1 rnd [ms]16 rnds [ms]Sec
Random144x72256550.0350.5802^81
QC144x72256550.0720.7102^81
QD144x72256550.0540.6782^81

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.

Stern timing results
Matrix TypeDim: nxrWeights [ms]v [ms]Msg. [MiB]Sec
Random768x384765.7545.44512^80
768x3847656.87956.475102^80
768x38476142.215139.814252^80
QC768x384765.6905.40512^80
768x3847612.58011.773102^80
768x38476142.359139.844252^80
QD768x384765.7065.40712^80
768x3847656.87756.389102^80
768x38476142.155139.954252^80

Veron signature scheme timings

Veron timing results
Matrix TypeDim: nxrWeights [ms]v [ms]Msg. [MiB]Sec
Random768x384765.5485.56712^80
768x3847655.98456.533102^80
768x38476140.107141.926252^80
QC768x384765.4935.59412^80
768x3847655.92956.966102^80
768x38476139.998141.599252^80
QD768x384765.5175.55312^80
768x3847656.48556.402102^80
768x38476140.346141.743252^80

CVE signature scheme timings

CVE timing results
Matrix TypeDim: nxrWeights [ms]v [ms]Msg. [MiB]Sec
Random144x725510.3789.85412^80
144x7255111.543108.720102^80
144x7255278.473274.903252^80
QC144x725510.5169.82912^80
144x7255110.722109.276102^80
144x7255278.949274.194252^80
QD144x725510.4009.96212^80
144x7255110.866109.151102^80
144x7255278.591274.906252^80

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).

Stern Timing Results
security level2^402^107
n, r, w:1024, 512, 321024, 512, 128
one round28 roundsone round28 rounds
Random123.38ms3454.38ms131.12ms3671.50ms
Quasi-Cyclic145.69ms4079.50ms184.25ms5158.99ms
Quasi-Dyadic189.50ms5306.08ms309.84ms8675.53ms
Véron Timing Results
security level2^402^107
n, r, w:1024, 512, 321024, 512, 128
one round28 roundsone round28 rounds
Random140.68ms3939.08ms149.12ms4175.47ms
Quasi-Cyclic156.84ms4391.60ms199.63ms5589.79ms
Quasi-Dyadic189.29ms5300.05ms309.62ms8669.28ms
Cayrel et al. Timing Results
security level2^732^143
n, r, w, q:128, 64, 49, 256256, 128, 97, 256
one round16 roundsone round16 rounds
Random84.07ms1345.07ms91.85ms1469.63ms
Quasi-Cyclic107.13ms1714.02ms129.54ms2072.68ms
Quasi-Dyadic147.29ms2356.59ms207.24ms3315.92ms

Comment on this article

SPIP | | Site Map | Follow site activity RSS 2.0

Graphic design (c) Kozlika under License GPL