Accueil > Research > Code-based cryptography > Code-based cryptosystems : implementations > Implementation of signature schemes with additional properties

Implementation of signature schemes with additional properties

mercredi 31 août 2011, par Julian Oleg Arenz and Sarah Magin

In the summer term 2011 our task was to implement an identity-based identification and signature scheme proposed in Identity-based identification and signature schemes using correcting codes and Improved identity-based
identification using correcting codes
as well as the implementation of a Threshold Signature scheme proposed in A New Efficient Threshold Ring Signature Scheme based on Coding Theory.
Both schemes were to be implemented in C and Java. The following article will give you a quick overview over the results. A complete record is attached as well.

Identity-based identification and signature scheme using correcting code

This protocol was first proposed by Pierre-Louis Cayrel, Philippe Gaborit and Marc Girault in 2007 in their paper Identity-based identification and signature schemes using correcting codes and then in 2009 with Improved identity-based
identification using correcting codes
.
The basic idea is to combine the CFS signature scheme and the Stern protocol to create an identity-based public identifier. Therefore the id for the Stern protocol is :

id=h(identity||index)=H’*s

First of all the CFS scheme is used to compute the secret s matching the identity. Then the same public key H’ is used for the Stern Protocol.

General implementation aspects

This scheme uses Goppa Codes[2m, 2m-tm, t]. For this kind of codes the proportion of decodable syndromes is about 1/t ! which is relatively good. The goal is to make the computation of s as fast as possible. Higher density means fewer iterations for CFS.

The Java Implementation

The Java implementation is based on the CFS implementation and Stern which can both be found here.
All needed methods can be found in the classes IdentityBasedProver and IdentityBasedVerifier. A detailed explanation of how to use these classes is inlcuded in the report. The full source code is attached.

The C Implementation

The C implementation contains a new CFS implementation based on the Niederreiter Crypto system and the Stern implementation. It is only runnable on a Linux machine.
The functions for the CFS scheme are contained in the cfs.c-File, all funtions needed for the whole identity-based identification can be accessed by the idp.c-File. A detailed explanation of how to use the C implementation can be found in the report. The full source code is attached.

Timing Results

The timing results are computed with the parameters m=16 and t=9 because those were proposed to be good values. The tests were performed on an Intel(R) Core(TM)2 Duo CPU T5550 at 1.83 GHz. The following table shows the results for the Java and the C implementation :

{{}} Java C
Key Generation 3799ms 3799ms
Compuation of secret s 10389470ms 10389470ms
Computation of Commitment 53324ms 53324ms
Computation of Challenge 1ms 1ms
Computation of Answer 1ms 1ms
Computation of Verification 51314ms 51314ms

A New Efficient Threshold Ring Signature Scheme based on Coding Theory
This t-out-of-N Threshold Ring Signature Scheme was first proposed by Carlos Aguilar Melchor, Pierre-Louis Cayrel and Philippe Gaborit in their paper A New Efficient Threshold Ring Signature Scheme based on
Coding Theory
.
It uses a slight variation of the Identification Scheme by Stern to allow multiple provers to share the same public Key. It is based on the Minimum Distance Problem (Stern uses the more general Syndrom Decoding Problem).

General implementation aspects

The implementations (both java and c) are based on the stern implementations which can be found here.
We implemented only the t-out-of-N authentication protocol ; the Fiat-Shamir Paradigm can be applied to create the signature scheme.

The Java Implementation

The Java Implementation resides in a subpackage within the Java implementation of Stern. The Stern classes have not been changed besides the StaticConfigurator.class which now points to a different configuration file which stores the additional parameters t and N. The supported parameters and some details about the implementation can be found in the report. The source files including the necessary packages can be downloaded from this page.

The C Implementation

The source files for the C Implementation are in the same directory as the source files for the stern implementation which was used. Several files of the original stern implementation have been modified. The sources are attached to this page in ringquellcodeC.zip. Some implementations details and and explanation of the available command line parameters can be found in the report.

Timing

The timing results were reached on an Athlon X2 4200+, 2 GB memory and the parameters n=1024, r=512, w=32, N=10 and t=10.

{{}} Key Generation, 20 key pairs Key Generation, average time per keypair Authentication, 20 rounds Authentication, average time per round
Java 65254ms 3262ms 62871ms 3143 ms
C 166890ms 8344ms 19381 ms 969ms

The key generation is faster in the java implementation ; the authentication is faster in the c implementation.