Implementation of signature schemes with additional properties

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[2^m, 2^m-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 :

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.

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