FIELD OF THE INVENTION

The present invention relates, in general, to computing engineering and, more particularly, to a method and a system for anonymously identifying a user as a member of a group of users.

BACKGROUND OF THE INVENTION

The task of proving membership of an entity in a certain local community has been set and solved differently in the course of development of public relationships and technical means. Nowadays, in order to solve such tasks, various electronic identification solutions are mostly employed using suitable computing techniques of cryptography and electronic means. Electronic means are often organized in a distributed manner, in which case exchange of (encrypted) messages between them is involved when performing identification. For example, US4748668 describes implementation of user identification based on issuance, by a trusted center, of a smart card for each user belonging to a certain group of users in order to enable the user to subsequently authenticate himself or herself by using the issued smart card.

In view of the increasing urgency and complexity of the considered task, at the present stage identification protocols are being developed and improved for the purpose of providing required reliability and/or security of the identification, on the one hand, and increasing performance and efficiency of using resources involved thereby, on the other hand. In particular, US4933970 describes implementation of an identification protocol based on improvement of the well-known Fiat-Shamir Scheme.

In the above-mentioned context, constructive ideas described in article [1] where the terms "one-way quasi-commutative function" and "accumulator" were first introduced, have served as an impulse for creating a new identification protocol.

SUMMARY OF THE INVENTION

The object of the present invention is to create an anonymous identification witness hiding protocol intended to verify membership in a local community of registered participants based on one-way accumulators developed using quasi- commutative one-way elliptic curve functions. The key aspect of the present invention is that particularly the mechanism of elliptic curves is applied for developing the one- way accumulators. Transition from the group and from the prime order subgroup of the group to a similar subgroup of the group of elliptic curve points fully corresponds to the current trends in the applied cryptography.

According to the first aspect of the invention, a method of anonymously identifying a user as a member of a group of users is provided. The method is performed in a computing system comprising at least one computing device of a trusted party and a plurality of computing devices of users.

The method comprises (1) a preliminary stage including steps performed in the computing device of the trusted party, the steps comprising:

(1a): for each j-th user from n users of the group, 1 ≤ j ≤ n, computing a unique private identifier ^x j for the j-th user, wherein ^x j does not enable to restore therefrom any personal information of the j-th user, and wherein each of the computed private identifiers has the same number of digits Λ;

(lb): for each i- th user from n users of the group, 1 ≤ i ≤ n , computing a personal secret for the z-th user as where is a common secret available only to the trusted party, is a generator of a subgroup ^G 1 of a prime order m of an additive group of points ^E ( ^F p) on an elliptic curve ^E / ^F p over a finite field ^F p, p > 3 is an odd prime, [·] denotes scalar product; and sending, to a computing device of the z-th user, the private identifier ^x i of the z- th user and the personal secret of the z-th user, and

(lc): computing a public group key for the group as where is symmetric pairing which represents mapping ^G 1 x ^G 1 → ^G 3, wherein ^G 3 is a subgroup of the prime order m of a multiplicative group of an extended finite field with a generator with an embedding degree k > 1. p , m, ^G 1, ^G 3, e _m (·, ·) are preset in the computing device of the trusted party and are publicly known, ^β is preset in the computing device of the trusted party, wherein β € _R (0, m — 1] , 2 ^λ-1 < m < 2 ^λ where n < m.

The method further comprises (2) an identification session including steps comprising: (2a): in a computing device of a user to be identified, computing a witness as where ^P is a personal secret of the user to be identified, v is a first random number selected in the computing device of the user to be identified, the first random number being usable only once (i.e. ephemeral) for each identification session, v ∈ _R (0, m — 1], and sending, from the computing device of the user to be identified to the computing device of a verifying party, a first message containing the computed witness;

(2b): in the computing device of the verifying party, computing a query as

^P 2 [Φ] ^G 1, where Φ is a second random number selected in the computing device of the verifying party, the second random number being ephemeral for each identification session, Φ ∈ _R (0, m — 1], and sending, from the computing device of the verifying party to the computing device of the user to be identified, a second message containing the computed query;

(2c): in the computing device of the user to be identified, computing a response as where z is a private identifier of the user to be identified, and sending, from the computing device of the user to be identified to the computing device of the verifying party, a third message containing the computed response,

(2d): in the computing device of the verifying party, verifying the response for equality to a verification factor computed as and identifying the user to be identified as a member of the group only if the response is equal to the computed verification factor.

Step (la) of the preliminary stage (1) preferably further comprises, prior to said computing: for each j-th user from n users of the group, 1 ≤ / ≤ n , assigning to the 1 - th user a registration identifier ^a j, where ^a j is a sequence of symbols. The unique private identifier ^x j for the j-th user is preferably computed based on ^a j, without possibility to restore ^a j from ^x j. In particular, the private identifier ^x i for the i-th user, 1 ≤ i ≤ n , is preferably computed as cryptographic hash function, h ⁱ (·) denotes i-time iterative application of denotes concatenation.

Prior to computing the witness, step (2a) of the identification session (2) preferably comprises: verifying whether a condition is met respect to the selected v, and, if said condition is not met, selecting a new v.

Prior to computing the response step (2c) of the identification session (2) preferably comprises: ensuring that wherein if the identification session (2) is terminated.

Preferably, computing the public group key for the group includes steps comprising: creating a public group key certificate including information about the trusted party, the public group key, and a digital signature (DS) of the public group key certificate; placing the public group key certificate into a public data storage.

Prior to verifying the response for equality to the verification factor, the method preferably further includes steps performed in the computing device of the verifying party, said steps comprising: reading the public group key certificate from the public data storage, and verifying the DS of said certificate, wherein said verification of the response is performed only if the DS of the public group key certificate is successfully verified.

The DS of the public group key certificate is preferably computed as where Sign(·, ·) a function of generating the is a secret key of the trusted party, is the information about the trusted party, is a second cryptographic hash function. The DS of the public group key certificate is preferably verified with where Verify (·, ·, ·) is a function of verifying the D S, wherein a value of is True if the DS is valid, and False otherwise, is a public key of the trusted party, said public key being paired to wherein said verification of the response is performed if

According to an embodiment, when at least one new user is added to the group, steps (la) of the preliminary stage (1) are further performed with respect to said at least one new user, and steps (lb) to (lc) of the preliminary stage (1) are newly performed with respect to the entire group of users whereto the at least one new user has been added. According to an embodiment, upon each exclusion of at least one user from the group of users, the preliminary stage (1) further comprises a step performed in the computing device of the trusted party, said step comprising: selecting a new common secret b' such that b' is not equal to a previously used common secret, wherein steps (lb) to (lc) of the preliminary stage (1) are newly performed with respect to the entire group of users from which said at least one user has been excluded.

According to the second aspect of the invention, a computing system configured for anonymously identifying a user as a member of a group of users is provided. The computing system comprises, at least, a computing device of a trusted party and a plurality of computing devices of users. The computing device of the trusted party and the computing devices of the users each comprise, at least: one or more processors; communication means; and one or more data storage devices having computer- executable instructions stored therein for execution by the one or more processors.

The computing device of the trusted party, when executing the instructions by the one or more processors of the computing device of the trusted party, is configured to perform a preliminary stage (1) comprising the following operations:

(la): for each j -th user from n users of the group, 1 ≤ j ≤ n , computing a unique private identifier ^x j for the j-th user, wherein ^x j does not enable to restore therefrom any personal information of the j-th user, and wherein each of the computed private identifiers has the same number of digits A;

(lb): for each z-th user from n users of the group, 1 ≤ i ≤ n , computing a personal secret for the z-th user as where is a comm secret available only to on the trusted party, is a generator of a subgroup ^G 1 of a prime order m of an additive group of points E(Fp) on an elliptic curve over a finite field ^F p, p > 3 is an odd prime, [·] denotes scalar product; and sending, to a computing device of the z-th user, the private identifier ^x i of the i- th user and the personal secret of the i-th user; and

(1c): computing a public group key for the group as where ^e m(·, ·) is symmetric pairing which represents mapping ^G 1 x ^G 1 ^{→ G} 3, wherein ^G 3 is a subgroup of the prime order m of a multiplicative group of an extended finite field with a generator 8 with an embedding degree k > 1. p , ^m , ^G 1, ^G 3, ^e m(·, ·) are preset in the computing device of the trusted party and are publicly known, b is preset in the computing device of the trusted party, wherein

A computing device of a verifying party, when executing the instructions by the one or more processors of the computing device of the verifying party, and a computing device of a user to be identified, when executing the instructions by the one or more processors of the computing device of the user to be identified, are configured to perform an identification session (2) comprising the following operations:

(2a): in the computing device of the user to be identified, computing a witness as

^P 1 ^{= [v]P} , where ^P is a personal secret of the user to be identified, v is a first random number selected in the computing device of the user to be identified, the first random number being ephemeral for each identification session, ^v∈ R (0, m - 1] and sending, from the computing device of the user to be identified to the computing device of the verifying party, a first message containing the computed witness;

(2b): in the computing device of the verifying party, computing a query as where Φ is a second random number selected in the computing device of the verifying party, the second rahdom number being ephemeral for each identification session, Φ ^∈ R (0, m - 1] and sending, from the computing device of the verifying party to the computing device of the user to be identified, a second message containing the computed query;

(2c): in the computing device of the user to be identified, computing a response where z is a private identifier of the user to be identified, and sending, from the computing device of the user to be identified to the computing device of the verifying party, a third message containing the computed response,

(2d): in the computing device of the verifying party, verifying the response for equality to a verification factor computed as , where , and identifying the user to be identified as a member of the group only if the response is equal to the computed verification factor. The identification protocol according to the present invention provides the required level of cryptographic security with low operational efforts and resource consumption. Thus, since verification complexity and the amount of public storage to store public information do not depend on the number of participants, the asymptotic estimate of verification complexity and reserved storage amount is 0(1).

BRIEF DESCRIPTION OF THE DRAWINGS

Fig. 1 is the schematic illustration of the message-exchange protocol in accordance with the present invention;

Fig. 2 is the schematic illustration of an embodiment of a computing system where the present invention is implemented;

Fig. 3 is the flowchart illustrating the preliminary stage of the anonymous identification method in accordance with the present invention;

Fig. 4 is the flowchart illustrating the identification session in accordance with the present invention.

DETAILED DESCRIPTION OF THE INVENTION

Reference is further made to exemplary embodiments of the present invention which are shown in the accompanying figures where identical reference numbers indicate similar parts. It should be appreciated that embodiments of the present invention may have different forms and are not intended to be limited by the descriptions presented herein. Consequently, the exemplary embodiments given below are described with reference to figures for explaining the essence of the aspects of the present invention.

1. INTRODUCTION

Section 2 below gives interpreted description of one-way quasi-commutative functions and accumulator. Sections 3 and 4 give an overview of some facts of the theory of elliptic curves and bilinear mappings for better understanding of Section 5 which discloses development of one-way elliptic curve accumulators, as proposed in the present application. Section 6 gives a short overview of identification protocols. Section 7 describes processes of developing and analyzing cryptographic security of the interactive identification witness hiding protocol in accordance with the present invention. It should be noted that this protocol is suitable for solving a number of practical tasks, including the one described in subsection 2.1. is hereinafter designated as 2. ONE-WAY QUASI-COMMUTATIVE FUNCTIONS In [1], such terms as "one-way quasi-commutative function" and "one-way accumulation function" also referred to as "one-way accumulator" were introduced.

Definition 2.1. denotes a set of all variable-length binary sequences. Let a functio n is given. The function is called a one-way function if:

• The function f(·, ·) is surjective.

• For all there is an algorithm A such that the time to compute ^f(x,y) is limited by a certain polynomial function of the number of binary symbols at the input of A.

• For all there is no knowledge of an algorithm B such that at a given x the time to compute is limited by a certain polynomial function of the number of binary symbols at the input of B and which allows to unambiguously identify the case where is the interval in which the function f(·, ·) is defined.

In [2], [3] it is shown that one-way hash functions exist if and only if one-way functions exist which, in their turn, exist if and only if digital signature (DS) schemes exist. In addition, in [4] it is proven that existence of one-way functions is equivalent to existence of cryptographic generators of pseudo-random numbers.

Definition 2.2. is a commutative function if where is a random permutation on the set

Definition 2.3. ^{f : X x Y →} is a one-way quasi-commutative function if p _or given x E X and the task of finding x' E X such that relates to the class of computationally hard problems. In other words, there is no known algorithm for which the time of finding the solution is limited by a polynomial function of ^lgx' . The term "quasi-commutative function" emphasizes the fact that in general if definition intervals of Y and X are the same, is a one-way quasi-commutative function such that

Definition 2.4. A family of one-way accumulators is a family of one-way functions, where each function is quasi-commutative.

Next, another property of one-way accumulators is given.

Definition 2.5. Let Then (1)

It follows from Definition 2.3 that equation (1) is true in the case of permutation as well. If then

For one-way accumulators it is essential that

It i s assumed that ^{x,f (·, ·)} and the set are given. There are ⁿ participants, and each of them is associated with one of elements of the given set. Then An owner of ^y i can compute Subsequently, by submitting the pair a 1-th participant can prove that ^y j belongs to the set by checking On the other hand, in order t y' o successfully force a certain , an intruder has to solve a hard computational problem and find such x' that . It should be noted that elements of the set are not secret, because all of them are used in computing

In [1] it is noted that one-way accumulators can be considered as some alternative to digital signatures (DSs). In fact, if each participant stores G in a local long- term memory, it is sufficient to submit in order to prove authenticity of ^y j.

Respective verification can be performed by someone who knows ^{f(·, ·)} and has access to

2.1. Exemplary Practical Implementation

The following practical problem is considered herein. Let there is a certain local community formed by participants of a scientific conference, for example. Besides the participants, there is a trusted registration authority. Each participant passes through a registration procedure and is given a unique registration identifier. Different types of interaction are possible:

• Between registered participants within the local community.

• Between the registered participants and all the others.

It is assumed that fully functional operation is only possible when an entity can prove that he/she belongs to the local community. Several solutions exist.

The easiest one is to make a list of identifiers and to distribute it among interested entities. Disadvantages are obvious: a substantial part of expenses refers to the accompanying overhead that arises when transmitting and storing the list. Thus, if only registered participants have access to the list, then the overhead is associated with ensuring privacy and integrity of information distributed via unprotected channels and saved in memory of personal devices of the participants. Moreover, it is not possible to avoid disclosure of the identifiers in the case of proving membership in the local community when a registered participant interacts with extraneous (unregistered) entities. Let the registration authority certifies identifiers with an DS, and then provides them to participants along with the signature. Anyone can verify the signature using a public key of the registration authority. Validity of the signature confirms the fact of membership in the local community. Now, anyone can perform this verification, even a non-registered entity. However, in this case the identifiers are transmitted openly and their privacy is not ensured.

The basic conditions to be met when solving the problem outlined above are given hereinbelow:

1. A valid proof of the fact that a registered participant owns an identifier.

2. Keeping the identifier secret when interacting with both a non-registered entity and another registered participant.

The solution scheme based on one-way accumulators is generally described thereafter. Let there are n participants. A function f is given. Each participant is given a registration identifier Then, the participants exchange with the identifiers and calculate an accumulated value G. A participant with number j knows f and stores in memory of his/her personal computing device. The function f and G are publicly available. In order to prove membership in the local community, it is required to submit a certain pair Any interested party can perform the following check: Equality means that the membership is confirmed. It should be noted that it is not necessary to store since every participant has access to the pair and, therefore, can always compute by using f. However, if the check is performed by extraneous entities, then they must know f and have access to G. Thus, any participant can prove his/her membership in the local community without disclosing identifiers.

The solution of this task by using the interactive witness hiding protocol is described in Section 7.

In [5] an alternative solution is proposed, however, different values are required to verify membership, and if each of them is obtained by means of a cryptographic hash function, then at least bits of memory are required to store them. Asymptotic verification complexity is

For one-way accumulators, the memory amount and verification complexity are constant values which do not vary over time and do not depend on n.

3. ELLIPTIC CURVES OVER ^F p

An elliptic curve E over a finite field is denoted as ^{E/Fp, p > 3} is an odd prime. Let an additive group of points of an order is set on ^E/Fp . where ¥ is a point at infinity, and The point Q has coordinates

The point G of a prime order m is also set, where said order is such that m I #E(Fp) It means that G generates a subgroup E[m] of the prime order m (m-torsion points) of the additive group of points In case of we have:

E/Fp : y ¹ = x ³ + ax + b. (2)

Order of group Let the curve ^E/Fp is given and

Then (see [6] subsection 13.1.8)

Otherwise, if ^E/Fp is given, then where

Since is small compared to ^p , then In [73], a method for computing bit operations is provided. A high score for has been registered.

Example. for and

Scalar product. Scalar product is introduced such that

Example. It is assumed that Then

1. Now let us take the point ^ .

2. If we double

3. If we double

4. If we double

5. If we double

6. If we double

7. If we double

8. If we double

To sum up, the computation of the scalar product requires seven doubling operations and four additions. More efficient methods for computing the scalar product are known (see [6], subsection 13.1.2).

Addition and doubling (affine coordinates) [6] (13.2.1.a). A point If A and B are different points, such that , where

There are other known coordinate systems: projective, Jacobian, Chudnovsky- Jacobian, modified Jacobian, and mixed coordinate systems [6] (see subsections 13.2.1.b, 13.2.1.C, 13.2.1.d, 13.2.2). The choice of a coordinate system influences complexity of computing a sum and doubling points.

Compact representation of a point of the curve (affine coordinates) [6]

(13.2.5). The equation for the point where r is a quadratic residue, and in this case exactly two solutions exist:

If is odd, and vice versa. In general, one of the two solutions is always even, while the other one is always odd.

Let Q is represented by the coordinate is saved, where is a feature that enables to identify the required solution from the pair of possible ones. The feature s = 0 is indicative of parity, and the feature s = 1 is indicative of oddness. For example, for the pair should be obtained, and then the odd solution should be selected from this pair. bits of memory are required to store an arbitrary point of the curve. In the square root is computed according to the Tonelli-Shanks algorithm [6] (see subsection 11.1.5) having asymptotic complexity of 4. BILINEAR MAPPINGS

Let us use an alternative designation with the generator is a subgroup of the prime order m of the multiplicative group of with the generator is referred to as symmetric pairing. Since there are two generators It means that there is also asymmetric pairing where different subgroups of the prime order m. From [7] it follows that symmetric pairing can be used in cryptographic applications along with asymmetric pairing. Several different types of pairing are known, for example, Weil pairing or Tate-

Lichtenbaum pairing [8], [9], [10]. The latter type is applied in practice more often. Bilinear mappings are discussed in detail in [6] (Chapter 6).

The following properties of symmetric pairing are interesting:

3. Computability. A method of computing ^e m(·, ·) of polynomial complexity is known, and OQSP) bits of memory are enough for storing the result (computation methods for different types of pairing are given in [11]).

The embedding degree for Weil pairing refers to the smallest integer k such that contains all points or embedding degree for Tate-

Lichtenbaum pairing is the smallest integer k such that Some special elliptic curves, such as supersingular curves (in case of equation embedding degree . Said limitation is true for finite fields with characteristic 3 but not 2, where ] (see subsection 5.2.2). In [14] it is shown that it is possible to build ordinary (non-supersingular) curves, where

Definition 4.1. A problem is called "easily solvable" if it can be solved with a polynomial complexity algorithm. In other words, the computation time is limited by a polynomial function of the number of binary symbols at the algorithm input. A problem for which such an algorithm is not known will be referred to as a hard one.

Subexponential complexity is such a complexity which is asymptotically more efficient (lower) than exponential complexity, but is not efficient as compared to polynomial complexity.

Definition 4.2. of the prime order m and are given. The discrete logarithm problem (DLP) is to find such that For the DLP, subexponential complexity solutions are known [15], [16].

Definition 4.3. of the prime order m and are given. The elliptic curve discrete logarithm problem (ECDLP) is to find such that Currently, for the ECDLP, exponential complexity solutions are known [17]. Cryptographic security directly depends on complexity of solving the

DLP/ECDLP. For symmetric pairing, cryptographic security in ^G 1 is determined by cryptographic security in i _n [12], [9] it is shown that solving the ECDLP can be reduced to solving the DLP in provided the curve is supersingular and The reduction method is applicable to different types of curves [26], [27], [28]. As a result, plural curves, which had originally been proposed as a basis for constructing cryptographic systems, such as supersingular curves or single-trace curves were rejected due to low cryptographic security, since the reduction method allowed to solve the DLP in subexponential or even linear time.

For asymmetric pairing ^G 1 x ^G 2 → ^G 3, solving the ECDLP in ^G 1 is also reduced to solving the DLP in G3 . to this end, it is required to find a point such that mapping ) is injective and forms homomorphism of . Consequently, instead of solving the ECDLP in ^G 1 _} it is possible to transition the solving into G3, where complexity thereof may be lower.

Basically, the reduction method comprises constructing suitable bilinear mapping. Weil/Tate-Lichtenbaum pairing has polynomial complexity in k and lg P. On the one hand, the smaller k is, the lower the complexity of computation of pairing is; on the other hand, solutions of subexponential complexity are known for the DLP, and they are the more efficient, the smaller k is.

When a constructive application of is implied, then should be selected in such a way that an acceptable level of cryptographic security is ensured based on balanced complexity of solving the DLP in ^G 3 and the ECDLP in ^G 1, provided k is not too high. For example, should be selected in order to provide an 80-bit level of cryptographic security. The method of finding elliptic curves with large order and small embedding degree that is based on complex multiplication [6] (Section 18) is proposed in [20], [21] and additionally studied in [22], [23], [24], [14]. Supersingular curves are suitable for these purposes, however, as shown in [6] (subsection 6.4.2), the upper bound for k substantially depends on P, in particular: For example, for this means that should be selected in order to provide an 80-bit level of cryptographic security, since for this level it should be obvious that such a selection adversely affects complexity of computation of

There are special embedding degrees for finite fields with characteristics 2 and 3. In [25], efficient techniques are proposed for where d is a prime integer, which allow to select such an elliptical cu rve that . Then, complexity of solving the DLP in a subgroup of a prime order guarantees 80-bit cryptographic security.

Another approach to solving the problem is to use hyperelliptic supersingular curves or build ordinary curves with a suitable embedding degree [6] (subsections 24.2.2 and 24.2.3).

Definition 4.4. The computational Diffie-Hellman problem (CDH) for The designation is introduced. The designation

Complexity of solving the CDH problems is not harder than complexity of solving the DLP/ECDLP - it is obvious that, in order to solve the CDH problem, it is enough to compute one discrete logarithm. Therefore, if the CDH problem is hard for some group, then it means that the DLP/ECDLP is also hard in this group. However, it has not been formally proven that complexity of the DLP ensures complexity of the CDH problems. Equivalence of complexity of the CDH and the ECDLP has been proven for groups of the prime order m [30], [31]. In particular, it has been proven that the assumption of equivalence is true if an elliptical curve with specified properties can be built over a certain prime field. The proof does not guarantee equivalence in the general case, since for a random group the method of building such curves is not known.

Definition 4.5. The decision Diffie-Hellman (DDH) problem for

It is obvious that, in the best case, complexity of solving the CDH is as hard as the DDH: first is to be obtained, then is to be verified. However, for most known groups, it has not been proven that complexity of solving the DDH is lower than complexity of solving the CDH.

Definition 4.6. The gap Diffie-Hellman (GDH) problem for is to solve with the help of the DDH oracle.

The DDH oracle gives an answer to a question formulated in the context of the DHH problem, in particular, for certain . Since it is required to find a solution of the CDH for the GDH, then the GDH is not harder than the CDH. However, it would be incorrect to state that complexity of solving the GDH is significantly lower than complexity of solving the CDH, since this fact has not been proven [29]. Groups in which the CDH is hard, while the DDH is easily solvable will be referred to as GDH groups.

Definition 4.7. The bilinear Diffie-Hellman (BDH) problem for The designation is introduced.

It is obvious that complexity of solving the BDH is not harder than the CDH in can be easily calculated (the same is true for The BDH also depends on complexity of solving the CDH in ^G 3. For instance, in order to calculate and is necessary to find a solution for is simultaneously a solution for the BDH. Therefore, complexity of solving the BDH depends on complexity of solving the CDH in both ^G 1 and ^G 3. Equivalence of complexity of solving the BDH and the CDH in ^G 1 and ^G 3 has not been proven. A method for solving the BDH in ^G 1 without preliminarily solving the CDH in ^G 3 is not known. There is a direct connection between pairing and the GDH. As follows from non-degeneracy of pairing and cyclicity of generates Therefore, pairing allows to solve 1 (to make a decision regarding Due to bilinearity, we have the following: if and only if Thus, for symmetrical pairing, the DDH in ^G 1 is an easily solvable problem. Since it is assumed that the CDH is equivalent in computational hardness to the ECDLP, ^G 1 belongs to GDH groups.

As an example, let us consider the implementation of a DS based on a GDH group [32]. It should be noted that a similar DS scheme was first proposed for a group with a hard computational solution of the DDH [33]. The one who generates a DS will be referred to hereinafter as "authenticator".

An authenticator selects a private key and then computes a public key . It is assumed that a m essage should be signed. Then the authenticator performs the following actions: 1. Computes

2. Computes a signature

A verifier has a message M' and performs the following actions to verify a signature S':

1. Computes

Tampering of the signature is possible if an intruder is able to solve Therefore, the CDH should be not less hard than the ECDLP. On the other hand, verification of the signature is in solving the DDH, therefore, the latter one should be easily computable.

The signature is considered to be confirmed if and it is rejected if

Note 1. It follows from the aforesaid that the usage of pairing for constructive purposes makes sense only in those cases when the usage of a GDH group is essential for implementing necessary properties of a cryptographic transformation.

5. ONE-WAY ACCUMULATORS ON The accumulated value is invariant regarding the random permutation xi and is therefore invariant regarding the similar permutation S,·.

It is assumed that If the parameters have been selected in such a way that complexity of solving the DLP in is not lower than complexity of solving the ECDLP in is unknown, then is a one-way accumulator, since, in order to find it is required to solve the DLP under condition of

Based on scalar product. Let is given, where

Then, by construction, It is obvious that the point Q is invariant regarding the random permutation is unknown, then scalar product is a one-way accumulator, since, in order to obtain u, it is required to solve the ECDLP under condition of Q'. If the compact point representation is used (see Section 3), then storage of the curve point requires k times less bits of memory, as compared to the pairing.

Note 2. As follows from the disclosure given in [32], at the 160-bit level of cryptographic security, scalar product for a point of the curve is at least 16 times more efficient than pairing. The time taken by verification of a signature for the ECDSA and Boneh-Lynn-Shacham (BLS) algorithms was compared (5.17 ms vs 81.0 ms with PIII 1 GHz). The signature verification using the ECDSA algorithm is comprised of a sum of two scalar products, as well as of three multiplications and multiplicative inversion in while the signature verification according to the BLS algorithm comprises computing two pairings.

6. ZERO-KNOWLEDGE PROOF

A certain z, a secret associated therewith, and a set X are given. There are two participants: (Prover) is someone who atempts to convince an opposite party that he/she owns z ∈ X, and provides some witness to this end. (Verifier) is someone who accepts/rejects the provided witness.

The prover has some information which is stored in secret. Verification is performed by using public data. Both the prover and the verifier will be referred to as honest if they observe the order of selection of variables, as defined by the protocol, follow the specified rules of computations, and carry out targeted transmission of messages. Nevertheless, the possibility of deception by the prover is admitted, for example, he/she may attempt to convince the verifier that he/she owns z, while he/she does not actually know the associated secret. On the other hand, the verifier, or any other intruder, acting as the prover may use a transcription (data transmitted in interaction according to the protocol) of a particular implementation or a combination of different implementations of the protocol to prove the fact of owning z. It is also assumed that the intruder intends to disclose z and/or the associated secret.

Zero-Knowledge Proof (ZKP) is an interactive protocol for two participants that has the following properties [34], [35]: Completeness. If the prover knows the associated secret, then he/she can prove the fact of owning z, and this proof will be accepted with overwhelming likelihood (rejected with negligibly small likelihood).

Soundness. If the prover does not know the associated secret, then the fact of owning z can be proven by him/her with negligibly small likelihood (the proof will be rejected with overwhelming likelihood).

Zero-Knowledge. The verifier (or the intruder) does not retrieve any information about z and/or associated secret after analyzing stored transcripts of various implementations of the protocol, while available information can be obtained by means of a certain polynomial-complexity algorithm, not involving interactive interaction when doing this.

The prover selects some random secret variable with a discrete uniform distribution (i commitment ) and computes a randomized public witness based on this variable. It is done to guarantee uniqueness of data of a current session. In addition, the witness is used to verify a response to the challenge which is made during the session and formulated by the verifier in the form of a random variable with a discrete uniform distribution. The prover provides his/her response to the challenge made, and sends the response to the opposite party which verifies it. It is crucial that all the three above- mentioned components (witness, challenge, and response ) are used in the verification. The protocol is configured in such a way that only the one who knows the associated secret is indeed able to respond to the challenge; moreover, the received response does not disclose any information (even partially) about this secret and z. During the session, the only bit of information is disclosed whose value indicates one of two possible outcomes: whether the prover owns z E X or not. In order to minimize the probability of fraud by the prover, the protocol may be repeated several times.

Generally, the protocol is comprised of three messages, and exchange thereby is shown in Fig. 1.

Identification protocols. There are many different identification protocols. The most known are [36], [37], [38], [39], [41], [42]. The protocols solve the same task but in different ways: by means of interactive interaction, the prover tries to convince the verifier that he/she knows a secret which is not disclosed during this interaction. For some protocols, e.g. [36], the property of ZKP is rigorously proven, for others, e.g. [39], such proof does not exist. For a number of protocols, e.g. [42], the WI (Witness- Indistinguishability) and WH (Witness Hiding) properties are proven. The WI property means that the verifier is unable to identify which witness is used during a current session, even if he/she has access to all such witnesses used in previous sessions (for example, stores the witness of each individual session in long-term memory). The WH property means that the verifier is unable to compute himself/herself a new witness which is relevant in the context of the protocol being implemented, but is different from the one previously submitted by the prover during any session. Since the WI and WH properties are related, the WI property is usually proven first, and then, based on this fact, the proof of the WH property is built.

In [43] it is shown that WH is a useful practical property and can be considered as an alternative to ZKP. It is known [43] that the ZKP property is not ensured if an intruder has access to transcripts of different sessions of the same ZKP protocol, which are carried out simultaneously (in parallel), and is able to actively intervene and influence the course of execution thereof. However, it is proven [43] that the WH property is preserved in this case. As compared to ZKP, WH ensures that the verifier does not retrieve any meaningful information which could help him/her act as the prover. Protocols with WH are usually more efficient than ZKP protocols, since they do not require multiple repetition to minimize the likelihood of fraud.

Identification protocols belong to a more common class of S-protocols that were first introduced in [44]. The prover and the verifier are simulated using a probabilistic interactive Turing machine, and a itself is an interactive proof scheme in the style of the Arthur-Merlin game [48] in which the verifier always chooses a random variable with a discrete uniform distribution.

The following section describes the identification protocol that solves a different task — in particular, it enables to prove the fact of owning a secret that is indicative of membership in some local community. Furthermore, if the community consists of the only one participant, the protocol solves the same task as the known identification protocols. It should be noticed that an ideologically close task is described in [45], but the method according to the present invention differs from previously published ones.

7. VERIFICATION OF MEMBERSHIP IN A LOCAL COMMUNITY

Let W* is a set of all sequences of letters of an arbitrary length in a finite alphabet W (set of letters). A A-bit cryptographic hash function h(.) is given such that There are n < m participants. Each participant has a unique registration identifier Let us provide identifiers as a set where The described method of generating X ensures that all ^x i are different, and even if

The author assumes that there is a trusted party T responsible for selection of parameters, preliminary computations, and data distribution. are given. Then T performs the following actions: generates and publishes the set (explanations regarding X are given in Section 8). 2. Computes

3. Secretly provides an i-th participant with

4. Secretly computes and then publishes a public group key assumed that authenticity and functions for generating and verifying the DS, then a certificate is issued, where is _a cryptographic hash function, is a secret key of the trusted party is information about T. Before using it is necessary to verify where is a paired public key of the trusted party T, while the value of the variable is True when is valid, and False otherwise.

If T is not a certification authority within the current public key infrastructure, then a respective certificate is issued for T.

5. Stores in secret.

Explanation 1. Let us explain the purpose of the long-term secret which is known only to T and used to compute and By construction, secretly provides the z-th participant with and publishes It is emphasized at this point that nobody except T knows and it is necessary to solve the DLP under the condition of or the ECDLP under the condition of in order to disclose it. It should be noted that if the personal secret ^P i is disclosed, for example as a result of a leak, then it can be used to prove the fact of owning not only ^x i, but also an Indeed, The following statements are true:

1. Since X is publicly available, anyone can attempt to prove their membership in the community with the help of but only the one who knows the personal secret ^p « can actually do it.

2. Anyone can compute G and/or but, in order to compute it is necessary to known the secret which is known only to T.

3. Since the z-th participant does not know , then he/she cannot compute the personal secret ^p * himself/herself.

4. As follows from public availability of the set X, the i-th participant can prove the fact of owning not only ^x i, but also an arbitrary (explanations are given in Section 8).

5. The participant with the number i can verify soundness of since

6. T can verify that is a prototype of since

The prover initially knows z and the associated secret where while the verifier knows and X

Protocol 7.1 Confirmation/disproof of the fact of owning 1. Protocol messages. The following messages are transmitted: at he/she owns z G X. To this end,

(a) The prover selects ( commitment ) and verifies fulfillment of the condition If the condition is fulfilled, the prover computes the point Pi (witness); otherwise, the prover selects a new v.

(b) The verifier selects computes the point P2 (challenge).

(c) The prover verifies that and then computes (response).

(d) The verifier reads from the public storage and verifies the signature with the help of where is the public key of then the verifier verifies where Equality confirms the fact of owning otherwise, the proof is rejected.

Comment 1. The usage of a GDH group is explained hereinafter. The proof is accepted for given and rejected if Moreover, for the verification it is required to compute pairing, one discrete exponentiation, and product in _G 3.

Comment 2. It is assumed that a transcription of each session is saved. The transcription includes P1, P2, and Question: can an intruder use a transcription of some session in order to fool an honest verifier during a new session? Anyone can act as the intruder, including the verifier. The intruder does not know u, but may or may not know Furthermore, the intruder follows the strategy comprising: sending Pi in the first message; receiving, from the honest verifier, for a certain ; and then sending, in the third message, such that the verification condition with respect to is met. It should be reminded at this point that authenticity/integrity of is guaranteed by the DS.

By construction, depends on will be used in the verification. If is fixed, it is necessary to generate in such a way that dependence on is imparted thereby. If such dependence is lacking, then

By construction, _is computed. It should be noticed that the fact of knowing does not give additional benefits, since, in order to achieve the desired result, it is required to solve is computed. Then it is An alternative method is to solve the ECDLP under the condition of For the GDH group, all these solutions have the same computational complexity by construction.

Explanation 2. This subsection explains the necessity of pairing in step of Protocol 7.1. It is assumed that the prover, instead of , computes and submits verifier, then verification does not depend on the intruder may initiate a new session and fool the verifier by using respectively. If pairing is used to compute the intruder has to solve in order to fool the verifier (see Comment 2).

Explanation 3. The question may arise: why is the challenge set as the point Comment 3. It is shown herein that Protocol 7.1 satisfies the properties according to Section 6.

Completeness.

Zero-Knowledge. The prover knows the secret P and some z, while the verifier has access to 8 whose authenticity and integrity has been confirmed as a result of verifying the DS. Then, provided the verifier and the prover are honest, information about z and P is not disclosed, since other scenarios are also possible.

Honest prover and dishonest verifier. The verifier seeks to disclose z, P and, to this end, chooses so that distribution thereof differs from a uniform one. For example, he/she can use in each session. But disclosure does not occur, since and have a uniform distribution due to v.

Honest verifier and dishonest prover. It is assumed that the prover knows z, P and seeks to disclose them. Such a scenario is of minor practical value, since the prover can always disclose them without relying on Protocol 7.1. If the prover does not know z, P, but seeks to disclose them, then all the possible attempts eventually come to disclosure of the secret

Dishonest prover and dishonest verifier. If z, P need to be disclosed, this scenario is of no sense, since the prover can disclose z, P himself/herself, without participation of the verifier (see the previous scenario).

8. COMMENTS REGARDING THE SET X

The reasoning of Section 7 is based on the assumption that the set X is publicly available. Since the trusted party T secretly sends to the z-th participant, then disclosure of X contradicts common sense and has no practical reasons. The only purpose of this assumption is to demonstrate cryptographic security of Protocol 7.1 with the known X. Section 7 shows that this assumption does not affect cryptographic security, and if P is unknown, then or the ECDLP must be solved in order to prove the fact of owning some z. However, a side effect exists in this case — the z-th participant is able to prove the fact of owning not only ^x i that he/she has received from T in the registration stage, but also any other It is clear that this effect disappears if the set X is not published, because the z-th participant will not be able to and unknown It should be recalled herein that, in order to compute it is necessary to know the secret Moreover, if are disclosed, for example as a result of a leak, then the intruder is able to prove only the fact of owning ^x i, but is not able to do it for other x/, such that

Statement 8.1. Given the known secret unknown X, in addition to proving the fact of owning ^x f, the fact of owning z = 1 can also be proven. This possibility does not contradict the basic principle: only the one can prove membership in the community who owns a respective personal secret which has not been disclosed in the course of the proving.

Comment 4. It makes sense to consider z = 1 as a selected element of the set can prove the fact of owning this element along with ^x i.

It is assumed that the local community changes over time: some members are excluded from it, and others, on the contrary, are included. Such dynamics leads to change of the set X. The description of how this affects Protocol 7.1 is given hereinbelow. member does not receive an updated personal secret pair, but he/she still has a secret should be noted that, by construction, it follows from Statement 8.1 that the excluded f-th member is able to exhibit membership in the community by proving the fact of owning z = 1.

If more than one member is excluded, then If the possibility of conspiracy between the excluded members is assumed, then it would be reasonable to suppose that the member knows while the ^2-th member knows Initially, the member has a secret Therefore, member can prove membership in the community by proving the fact of owning z = 1. Similar arguments are true for the member. Therefore, there is a common problem when excluding both an individual member and a non-empty subset of members. The combination of exclusion operations will be referred to hereinafter as the exclusion cycle.

An obvious solution can be used. The trusted party T chooses such a long-term that in the f- th exclusion cycle it is necessary to access and should be saved in memory after succes sful completion of the cycle so that the amount of computations is reduced. Then in the next f-th cycle after updating the group key and the personal secrets, is saved in memory instead of As a result, we have a single access to of long-term memory should be reserved for data storage.

Thus, inclusion/exclusion causes updating the group public key, as well as members' personal secrets. The difference is that in the f-th exclusion cycle, when computing personal secrets and the group key, the previously used long-term secret b should be denied and should be used instead, while the inclusion process does not require such action.

9. ILLUSTRATIVE EMBODIMENTS 9.1. Illustrative computing environment

With reference to Fig. 2, the exemplary embodiment of a computing system 200 in which the present invention is implemented is described below.

The computing system 200 comprises at least one computing device 201 of the trusted party and a plurality of user computing devices 202-1, 202-2, 202-3, ..., 202-N which may be commonly referred to hereinafter as 202. Such broadly known devices as personal computer (PC), laptop, tablet, smartphone, etc. can be used as the computing devices 201, 202. The computing system 200 typically includes other components as well (various storages/databases, etc.). Components of the computing system 200 are interconnected via at least one communication network and/or environment which is commonly denoted as 203 in Fig. 2. Broadly known wired and/or wireless communication networks (including publicly available ones), through which the components of the computing system 200 interact with each other and with other devices/networks using appropriate broadly known network and communication technologies, can be used as the communication network(s) employed herein. In particular, implementations of the computing system 200 are possible where devices, such as 201, 202, can interact directly with each other using such technologies as NFC.

The computing devices, such as 201, 202, used to implement the proposed technology, include well-known hardware, such as processors, memory units, input/output devices, mass storage devices, communication means (for example, communication interfaces), etc., and basic software, such as operating systems, protocol stacks, drivers, etc., which may be commercially available or custom. Furthermore, the approach described herein is preferably implemented by designing special software using known programming technologies and environments and by deploying and running it on the respective components of the proposed computing system 200.

9.2. Exemplary methods in accordance with the present invention

The exemplary embodiment of the method of anonymously identifying a user as a member of a group of users in accordance with the present invention is described below with reference to Figs. 3, 4, It is assumed that the embodiment of the method according to the present invention described hereinbelow is implemented in the computing system 200.

The anonymous identification method includes a preliminary stage 300 described below with reference to Fig. 3, and an identification session 400 described below with reference to Fig. 4. The preliminary stage 300 is implemented in the computing device 201 of the trusted party T with respect to the group of n users.

In step 310, each 7 is registered by assigning to him/her a registration identifier which corresponds to the user. In according with the aforesaid, in general, represents a sequence of symbols and, in particular, may include name, registration number, personal insurance policy number, and/or other known character identifier(s) of the 7

In step 320, for each a unique private identifier ^x i is computed based on According to the preferred embodiment, ^x / is computed as where, as noted above, is the cryptographic hash function, denotes z ^' -fold iterative hashing, denotes concatenation. Accordingly, each of the computed private identifiers has the same number of digits Any suitable known hash function with the required number of digits, for example, the one generated by the algorithm from FIPS PUB 180-4, may serve as The recommendations according to first requires to apply y = and then to use values A of less significant digits of y as the output of the is a standard cryptographic hash function from FIPS PUB 180-4.

As discussed previously, the obtained set can be published by the trusted party T by using any of the known digital publication methods.

It should be noticed at this point that this preferred embodiment of computing unique private identifiers is not the only possible one, and other known techniques may be used to compute private identifiers of users, without the possibility of reconstructing any personal information of a user from a corresponding private identifier. Moreover, not only registration character identifiers of users can be used as a basis to compute their private identifiers: for instance, a vector of values of digitized bio-identification information (e.g. facial features) of a user may be used to this end. trusted party, is the generator of the subgroup ^G 1 of the prime order m of the additive

In step 340, the computing device 201 of the trusted party transmits, to the computing device 202 of each a pair including his/her private identifier ^x i and personal secret computed is steps 320 and 330, respectively.

In step 350, the public group key for the group is computed as is symmetric pairing which represents mapping is the subgroup of the prime order m of the multiplicative group of the extended finite field with the generator with the embedding degree are preferably preset in the computing device 201 of the trusted party and are publicly available; the secret is preset in the computing device 201 of the trusted party so that The computed group key can be placed into some public data storage. This public data storage may have a known implementation and may either be part of the computing system 200 or be external with respect thereto (such as a cloud storage).

According to the preferred embodiment, step 350 includes substep 351, wherein a certificate of the public group key is issued, where is information regarding the trusted party T is a DS of this certificate. The DS of the public group key is computed as where, in accordance with the aforesaid,

Sign(·, ·) is the function for generating the DS, S is the secret key of the trusted party T, is the cryptographic hash function. The information regarding the trusted party may include some unique identifiers, references to resources, etc., and, in general, corresponds to information which is typically included in a public key certificate to unambiguously identify its owner (see e.g. the X.509 standard). It should be noted here that any known hash function with the required number of digits can be employed as the cryptographic hash function used to generate the DS, but in general it should not be identical to the cryptographic hash function used to compute the unique private user identifiers (see step 320). More particularly, the hash function is defined by the method of generating/verifying the DS. For example, a hash function with a suitable number of digits from FIPS 202 (SHA-3, Keccak) can be used. Then, in substep 352, the issued certificate is deposited in the public data storage.

As discussed above, if at least one new user is added to the considered group, then, in accordance with the method according to the present invention, steps 310, 320 of the preliminary stage 300 are additionally performed with respect to this at least one new user, and steps 330-350 of the preliminary stage 300 are repeated with respect to the entire extended user group whereto the at least one new user has been added. With each exclusion of at least one user from the considered group of users, when performing the preliminary stage 300 in the computing device 201 of the trusted party, a new secret b' is selected such that b' is not equal to the previously used secret, thereafter steps 330-350 of the preliminary stage are repeated with respect to the entire reduced user group wherefrom this at least one user has been excluded. As noted before, it may be assumed in general that where Ms a sequence number of the exclusion cycle: for example, , , and so on. It is ensured thereby that

The discussion of the preliminary stage 300 is now finished, and transition is made to the discussion of the identification session 400 with reference to Fig. 4.

In step 401 of the identification session 400, a random number selected in a computing device of a user U to be identified (for example, the computing device 202-1), said random number being ephemeral for each identification session.

The method 400 preferably includes step 402 of performing, in the computing device 202-1, verification of whether the following condition is met with respect to the selected v, and if this condition is not met, a new v is chosen.

In step 403, a witness is computed as in the computing device 202-1, where P is a personal secret of the user to be identified.

In step 404, a first message containing the computed witness is sent from the computing device 202-1 to a computing device of a verifying party (for example, the computing device 202-N).

Then, in the computing device 202-N: in step 405, a secret random number which is ephemeral for each identification session is selected; and, in step 406, a query is computed as

In step 407, a second message containing the computed query is sent from the computing device 202 -N to the computing device 202-1.

The method 400 preferably includes step 408 of performing, in the computing device 202-1, verification of whether the following is true with respect to the query that was received from the computing device identification session 400 is terminated.

In step 409, a response is computed as computing device 202-1, where z is a private identifier of the user U, and, in step 410, a third message containing the computed response is sent from the computing device 202-1 to the computing device 202-N.

The method 400 includes step 411 which is performed in the computing device 202-N and comprises obtaining the public group key. According to the specific implementation of step 411, the certificate of the public group key is read from the public data storage, and verification of the DS of this certificate is carried out. Moreover, the DS of the public group key certificate is verified with function of verifying the DS, the value of is True when the DS is valid or False otherwise, T is the public key of the trusted party T, said public key being paired to

It should be noticed at this point that the above mentioned functions generally correspond to the algorithm for generating and verifying the DS ¾, respectively.

In step 412 performed in the computing device 202-N, if the response received from the computing device 202-1 is checked for equality to the verification factor computed as , where The user U is identified as a member of the group of the identification session 400 only if the response 81 is equal to the computed verification factor.

10. MEMORY AMOUNT, TRANSMISSION OVERHEAD, COMPUTATIONAL COMPLEXITY

1. Practical requirements for cryptographic security are such that 160 (see recommendations of the European Union Agency for Network and Information Security).

2. For the purpose of efficient implementation of arithmetic,

4. The selected V and m are fixed, do not depend on n, and are interpreted as long-term parameters which are replaced only as a result of adjusting the requirements for cryptographic security.

10.1. Memory Amount in a long-term public storage. Each member will need in a local long-term storage to store ^P i in the case of the compact curve point representation (see Section 5) and bits to store ^x i.

Since memory consumption does not depend on n, then the asymptotic estimate of the amount of long-term public storage is

10.2. Transmission overhead

If the compact curve point representation is used, then bits in total are required to deliver The transmission overhead can be reduced if is a cryptographic hash function (obviously, this increases cryptographic security, since the possibility of any transformations of 8i is eliminated). Then verification is performed according to the rule: will be transmitted.

If the compact curve point representation is not used, then, in total, are transmitted.

10.3. Computational Complexity

The prover computes the sum modulo m, two scalar products, and one pairing. The verifier computes scalar product, pairing, discrete exponentiation, and product in , then both the prover and the verifier additionally compute the value of the hash function If the compact curve point representation is used, then the square root in is to be computed using the Tonelli-Shanks algorithm of asymptotic complexity The verifier does it for while the prover does it for

^P 2. The actions to be performed are summarized in Table 1.

Since computational complexity does not depend on n , then its asymptotic estimate is

Table 1. Computational complexity

11. CONCLUSION

One-way quasi-commutative functions over elliptic curves are applied to build one-way accumulators which are used in the witness hiding protocol in order to verify membership in a local community of registered members. Since complexity of the verification and the amount of publicly available memory to store public information do not depend on the number of participants, then the asymptotic estimate of complexity of the verification and reserved memory amount is Examples of software implementation of various types of pairing can be found in the PBC Library at the Stanford University website.

It should be appreciated that the described embodiments are just preferable but not the only possible examples of the present invention. On the contrary, the scope of the invention is defined by the following claims and their equivalents.

12. BIBLIOGRAPHY [1] Benaloh, Josh C. and de Mare, M. “One-Way Accumulators: A

Decentralized Alternative to Digital Signatures (Extended Abstract).” Advances in Cryptology EUROCRYPT’93, Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, 274-285.

[2] Naor, M. and Yung, M. “Universal One-way Hash Functions and their Cryptographic Applications. "Proc. 21st ACM Symp. on Theory of Computation,

Seattle, WA (May 1989), 33-43.

[3] Rompel, J. “One-way Functions are Necessary and Sufficient for Secure Signatures. "Proc. 22nd ACM Symp. on Theory of Computation, Baltimore, MD (May 1990). [4] Impagliazso, R., Levin, L. and Luby, M. “Pseudorandom Generation from One-way Functions.” Proc. 21st ACM Symp. on Theory of Computation, Seattle, WA (May 1989), 12-24.

[5] Merkle, R. “Protocols for Public Key Cryptosystems.” Proc. 1980 Symp. on Security and Privacy, IEEE Computer Society (April 1980), 122-133.

[6] Cohen, H., Frey, G., Roberto Avanzi, R., Doche C., Lange, T., Nguyen, K. and Vercauteren, F. Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall/CRC, 2006.

[7] Verheul, E. “Evidence that XTR Is More Secure than Supersingular Elliptic Curve Cryptosystems.” Advances in Cryptology Eurocrypt 2001, LNCS 2045, Springer-Verlag (2001), 195-210.

[8] Silverman, J.H. The Arithmetic of Elliptic Curves, Springer-Verlag, New York, 1986.

[9] Frey, G. and Ruck, H.G. “A remark concerning the m-divisibility and the discrete logarithm in the divisor class group of curves.” Mathematics of Computation, 62 No.206 (1994), 865-874.

[10] Frey, G., Muller, M. and Ruck, H.G. “The Tate Pairing and the Discrete Logarithm Applied to Elliptic Curve Cryptosystems.” IEEE Transactions on Information Theory 45(5) (1999), 1717-1719.

[11] Baretto, P.S.L.M., Kim, H.Y., Lynn, B. and Scott, M. “Efficient Algorithms for Pairing-Based Cryptosystems.” Advances in Cryptology Crypto 2002, LNCS 2442, Springer-Verlag (2002), 354-368.

[12] Menezes, A., Okamoto, T., and Vanstone, S. “Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field.” IEEE Trans. Information Theory, 39(5) (1993), 1639-1646.

[13] Menezes, A. J. Elliptic Curve Public Key Cryptosystems, Kluwer International Series in Engineering and Computer Science, 1993.

[14] Miyaji, A., Nakabayashi, M., and Takano, S. “New Explicit Conditions of Elliptic Curve Traces for FR-Reduction.” IEICE Trans. Fundamentals, Vol. E84 A, no. 5, May 2001.

[15] Hankerson, D., Menezes, A. and Vanstone, S. Guide to Elliptic Curve Cryptography, Springer-Verlag, 2004. [16] Menezes, A., van Oorschot, P. and Vanstone, S. Handbook of Applied Cryptography, CRC-Press, 1996.

[17] Odlyzko, A. “Discrete Logarithms: The Past and the Future. "Designs, Codes, and Cryptography, Vol. 19, No. 2-3, 2000,129-145.

[18] Jacobsen Jr., M.J., Koblitz, N., Silverman, J.H., Stein, A. and Teske, E. “Analysis of the Xedni calculus attack. "Designs, Codes and Cryptography, Vol 20 (2000) 41-64.

[19] Silverman, J.H. “The Xedni calculus and the elliptic curve discrete logarithm problem. "Designs, Codes and Cryptography, Vol. 20 (2000) 5-40.

[20] Atkin, A. and Morain, F. “Elliptic Curves and Primality Proving.” Math. Comput., 61(203) (1993) 29-68.

[21] Morain, F. “Building cyclic elliptic curves modulo large primes.” In Advances in Cryptology- EUROCRYPT’ 9 1 (Brighton, 1991), volume 547 of Lecture Notes in Comput. Sci., Springer, Berlin, 328-336.

[22] Brezing, F. and Weng, A. “Elliptic Curves Suitable for Pairing Based Cryptography.” Des. Codes Cryptogr., 37(1) (2005) 133-141.

[23] Dupont, R., Enge, A. and Morain, F. “Building Curves with Arbitrary Small MOV Degree Over Finite Prime Fields.” J. Cryptol., 18(2) (2005) 79-89.

[24] Freeman, D. “Constructing Pairing-Friendly Elliptic Curves With Embedding Degree 10.” In Algorithmic number theory, vol. 4076 of Lecture Notes in Comput. Sci., Springer, Berlin, (2006), 452-465.

[25] Galbraith, S. D., Harrison, K. and Soldera, D. “Implementing the Tate pairing.” Algorithm Number Theory Symposium ANTS V, Lecture Notes in Comput. Sci., vol. 2369, Springer- Verlag, (2002), 324-337.

[26] Satoh, T. and Araki, K. “Fermat Quotients and the Polynomial Time Discrete Log Algorithm for Anomalous Elliptic Curves.” Comm. Math. Univ. Sancti Pauli, 47 (1998), 81-92.

[27] Smart, N.P. “The Discrete Logarithm Problem on Elliptic Curves of Trace One.” Journal of Cryptology, Vol. 12, No. 3, (1999), 193-196.

[28] Semaev, I.A. “Evaluation of Discrete Logarithms in a Group of p-Torsion Points of an Elliptic Curve in Characteristic p.” Math, of Comput., 67 (1998), 353-356.

[29] Okamoto, T. and Pointcheval, D. “The Gap-Problems: A New Class of Problems for the Security of Cryptographic Schemes.” Practice and Theory in Public Key Cryptography PKC 2001, LNCS 1992, Springer- Verlag (2001), 104-118.

[30] Maurer, U.M. “Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms.” Advances in Cryptology Crypto’94, LNCS 839, Springer- Verlag (1994), 271-281.

[31] Maurer, U.M. and Wolf, S. “The Relationship between Breaking the Diffie- Hellman Protocol and Computing Discrete Logarithms.” Advances in Cryptology Crypto ’96, LNCS 1109, Springer- Verlag (1999), 268-282.

[32] Boneh, D., Shacham, H. and Lynn B. “Short Signatures from the Weil Pairing,” J. Cryptol., Vol. 17, No. 4, (2004), 297-319.

[33] Chaum, D. “Zero-Knowledge Undeniable Signatures.” Advances of Cryptology Eurocrypt’90, LNCS 473, Springer- Verlag (1991), 458-464.

[34] De Santis, A., Micali, S. and Persiano, G. “Non-Interactive Zero- Knowledge Proof Systems.”

Advances in Cryptology CRYPTO ’87 Proceedings, Springer- Verlag, (1988)

52-72.

[35] Goldwasser, S., Micali, S. and Rackoff, C. “The knowledge complexity of interactive proof systems.” SIAM J. Comput., Vol. 18, Iss. 1, (1989) 186-208.

[36] Fiat, A. and Shamir, A. “How to prove yourself: Practical solutions to identification and signature problems.” Advances in Cryptology CRYPTO’ 86 (LNCS 263), (1987) 186-194.

[37] Feige, U., Fiat A. and Shamir, A. “Zero-knowledge proofs of identity.” Journal of Cryptology, 1 (1988) 77-94.

[38] Guillou, L.C. and Quisquater, J.-J. “A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory.” Advances in Cryptology EUROCRYPT’88 (LNCS 330), (1988) 123-128.

[39] Schnorr, C.P. “Efficient identification and signatures for smart cards.” Advances in Cryptology CRYPTO’89 (LNCS 435), (1990) 239-252.

[40] Schnorr, C.P. “Efficient signature generation by smart cards.” Journal of Cryptology, 4 (3), (1991) 161-174.

[41] Brickell, E.F. and Mccurley, K.S. “An interactive identification scheme based on discrete logarithms and factoring.” Journal of Cryptology, 5 (1992) 29-39. [42] Okamoto, T. “Provably secure and practical identification schemes and corresponding signature schemes.” Advances in Cryptology CRYPTO’92 (LNCS 740), (1993) 31-53.

[43] Feige, U. and Shamir, A. “Witness Indistinguishable and Witness Hiding Protocols.” In Proceedings of 22nd STOC, ACM Press, (1990) 416-426.

[44] Cramer, R. “Modular Design of Secure, yet Practical Cryptographic Protocols.” PhD Thesis, University of Amsterdam, 1996.

[45] Cramer, R. and Damgard, I.B. “Fast and Secure Immunization against Man- in-the-Middle Impersonations.” Advances in Cryptology EUROCRYPT’97, International Conference on the Theory and Application of Cryptographic Techniques, Konstanz, Germany, May 11-15, Proceedings, ed. Walter Fumy, Springer, (1997) 75- 87.

[46] Bengio, S., Brassard, G., Desmedt, Y., Goutier C., Quisquater, J.J. “Secure Implementation of Identification Systems.” Journal of Cryptology, (4), (1991) 175-183.

[47] Desmedt, Y., Goutier C., Bengio, S. “Special uses and abuses of Fiat- Shamir passport protocol.” In C. Pomerance, editor, Advances in Cryptology, Proc. of Crypto’ 87 (LNCS 293), (1988) 21-39.

[48] Babai, L. and Moran, S. “Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes.” Journal of Computer and System Sciences, Volume 36, Issue 2, April (1988) 254-276.

[49] Paterson, K.G. “ID-based signatures from pairings on elliptic curves.” IEEE Electronic Letters, (2002) 38(18): 1025— 1026.

[50] Hess, F. “Efficient Identity Based Signature Schemes Based on Pairings.” Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography SAC’02, (2003) 310-324.

[51] Cha, J.C. and Cheon, J.H. “An identity based signature from Gap Diffie- Hellman groups.” (LNCS 2567), (2003) 18-30.

[52] Yi, X. “An identity based signature scheme from the Weil pairing.” IEEE Communications Letters, (2003) 7(2):76-78.

[53] Boneh, D., Mironov, I. and Shoup, V. “A secure signature scheme from bilinear maps.” In Proceeding of the Topics in Cryptology CT-RSA 2003, (LNCS 2612), (2003), 98-110. [54] Zhang, F., Safavi-Naini, R. and Susilo, W. “An efficient signature scheme from bilinear pairing and its applications.” Public Key Cryptography, (LNCS 2947), (2004) 277-290.

[55] Boneh, D. and Boyen, X. “Short Signatures Without Random Oracles.” EUROCRYPT 2004, (LNCS 3027), (2004) 56-73.

[56] Shim, K.A. “An ID-based Aggregate Signature Scheme with Constant Pairing Computations.” The Journal of Systems and Software, Vol. 83, (2010) 1873— 1880.

[57] Hafizul Islam, SK and Biswas, G.P. “An efficient and provably-secure digital signature scheme based on elliptic curve bilinear pairings.” Theoretical and Applied Informatics, Vol. 24, no. 2, (2012) 109-118.

[58] Mishra, S., Yaduvanshi, R., Rai, A.K. and Singh, N. P. “An ID-Based Signature Scheme from Bilinear Pairing Based on Ex-K-Plus Problem.” Trans Tech Publications, Vols. 403-408, (2012) 929-934.

[59] Gopal, P.V.S.S.N. and Vasudeva Reddy, P. “Efficient ID-Based Signature Scheme using Pairings.” Int. J. of Network Security, Vol. 6, (April 2014) 78-85.

[60] Huang, Z., Chen, K. and Wang, Y. “Efficient identity-based signature and blind signatures.” (LNCS 3810), (2005) 120-133

[61] Paterson, K. G. and Schuldt, J.C.N. “Efficient identity based signature secure in the standard model.” (LNCS 4058), (2006) 207-222.

[62] Rodriguez-Henriquez, F., Diaz-Perez, A., Saqib, N. A. and Ko,c, C, . K. Cryptographic

Algorithms on Reconfigurable Hardware, ser. Signals and Communication Technology. Boston, MA: Springer US, 2006.

[63] Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E., Shirase, M. and Takagi, T. “Algorithms and Arithmetic Operators for Computing the hT Pairing in Characteristic Three.” IEEE Transactions on Computers, vol. 57, no. 11, (Nov. 2008) 1454-1468.

[64] Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E. and Rodriguez- Henriquez, F. “A Comparison Between Hardware Accelerators for the Modified Tate Pairing over F2m and F3m .” Pairing-Based Cryptography Pairing 2008, (2008) 297- 315. [65] Kammler, D., Zhang, D., Schwabe, P., Scharwaechter, H., Langenberg, M., Auras, D., Ascheid, G. and Mathar, R. “Designing an ASIP for Cryptographic Pairings over Barreto-Naehrig Curves.” Cryptographic Hardware and Embedded Systems CHES 2009 Springer Berlin/Heidelberg, (2009), 254-271. [66] Ghosh, S., Mukhopadhyay, D. and Roychowdhury, D. “High Speed

Flexible Pairing Cryptoprocessor on FPGA Platform.” Pairing-Based Cryptography Pairing 2010, vol. 6487, (2010) 450-466.

[67] Estibals, N. “Compact Hardware for Computing the Tate Pairing over 128- Bit Security Supersingular Curves.” Pairing-Based Cryptography Pairing 2010, vol. 6487, (2010) 397-416.

[68] Ghosh, S., Roychowdhury, D. and Das, A. “High Speed Cryptoprocessor for hT Pairing on 128-bit Secure Supersingular Elliptic Curves over Characteristic Two Fields.” Cryptographic Hardware and Embedded Systems CHES 2011, (2011) 442-458.

[69] Beuchat, J.-L., Detrey, J., Estibals, N., Okamoto, E. and Rodriguez- Henriquez, F. “Fast Architectures for the hT Pairing over Small-Characteristic

Supersingular Elliptic Curves.” IEEE Transactions on Computers, vol. 60, no. 2, (Feb. 2011) 266-281.

[70] Cheung, R. C. C., Duquesne, S., Fan, J., Guillermin, N., Verbauwhede, I. and Yao, G. X. “FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction.” Cryptographic Hardware and Embedded Systems CHES 2011, no. 07, (2011) 421-441.

[71] Adikari, J., Hasan, M. A. and Negre, C. “Towards Faster and Greener Cryptoprocessor for Eta Pairing on Supersingular Elliptic Curve over F21223” 19th International Conference, Selected Areas in Cryptography 2012, (2012) 166-183. [72] Menezes, A., van Oorschot, P. and Vanstone, S. Handbook of Applied

Cryptography, CRC Press, 1996.

[73] R. Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp., 44(170)483-494, 1985 (available at http ://www.mat.uniroma2.it/~schoof/ctpts .pdf)