Verifiable Self-Selecting Secret Sharing Based on Elliptic Curves

Introduction

Classical cryptography treats the notions of encryption, decryption, and hashing using secret keys are the actors of the cryptosystem. Those keys represent the security basis of the entire system according to Kerckhoffs principles. On the other hand, the question that could arises in our mind, is how to protect such an important key? Hence, the notion of threshold secret sharing, where the key is distributed over a group of participants in such a way that none of them possesses an information about the secret, but some candidates representing the access structure collaborate at its reconstitution. Several works have contributed to improve secret sharing since the first approach of Adi Shamir, such as verifiable approaches and proactive ones. However, the particularity of contemporary methods lies in the use of elliptic curves, for the reason that they revolutionized cryptosystems security by providing solutions to constraints caused by key size and operations complexity. In this paper, the researchers propose a method of securing visual cryptographic keys by multi secrets sharing scheme with self-selecting of private ones, based on ECDLP. The scheme takes as input an image matrix which represent the secret to share on a server–client network without information loss. In this method, the authors give the participants the capability to verify their received shares without secret reconstruction, to prove the validity of the dealer, shadows, and even candidates. The rest of the paper is structured as follows: Section II illustrates preliminaries technics for a good comprehension of the subject. Section III presents related works for sharing secrets using elliptic curves. Section VI describes steps of the proposed approach. Section V discuses results. Finally, section IV concludes and resumes the paper.

Preliminaries

In this section, the authors describe basic technics used for secret sharing with elliptic curves.

Elliptic Curve

An elliptic curve over a finite field is a set of pairs resolving the Equation union a particular element called point at infinity noted such that and (Paar, 2009) (Figure 1).

Some operations properties over should be mentioned:

• 1.

  Closure: , ifthen;

• 2.

  Associativity:;

• 3.

  Identity element: , ;

• 4.

  Inverse element: , ;

• 5.

  Commutativity: ;.

By inference: forms an abelian group.

The addition law in is defined as follows.

For each and :

and:

such that:

the inverse of point is obtained by .

Figure 1.

Elliptic curve over R (a) and over Finit Field F_p (b)

Several classical asymmetric cryptosystems are based on Discret Logarithm Problem (DLP):

so

Applying the same principle in a set of points of an alliptic curve on a finite field , a similar problem could be observed, the Elliptic Curve Discrete Logarithm Problem (ECDLP), noting that the set of points represents a cyclic group by applying a succession of addition operations:

so

By analogy with the DLP, is considered as a base point of the cyclic group, and the elliptic discret logarithm of , where and . Given a large prime number , finding can not be done in less than steps (Hoffstein, 2008).

Shamir’s Threshold Secret Sharing Scheme

A threshold secret sharing scheme consists to split a secret key and distribute it among participants in such a way its reconstitution requires only a qualified group of them.

In its paper, (Shamir, 1979) describes the conditions of a threshold sharing system:

• •

  Knowledge of any or more pieces of the secret, makes it easily computable;

• •

  Knowledge of any or fewer pieces of the secret, reveal no information about the secret.

To share a secret among persons with a threshold , a random polynomial of degree should be defined:

in which and .

To determine the different shares, points must be computed, and for the reconstruction phase, it is possible using Lagrange interpolation for given shares: