Signature schemes using bilinear mappings

A method of generating and verifying a ring signature Sig of a digital message M communicated between a signer and a verifier, wherein the signer is one of a plurality of t members of a set, wherein each of the members of the set is associated with an identity from the identity set {ID1, . . . , IDt}, wherein the signer is associated with the identity IDs, and wherein 1≦s≦t, the method comprising:

• generating a first cyclic group G1 of elements and a second cyclic group G2 of elements;
• selecting a bilinear, non-degenerate pairing e capable of generating an element of the second cyclic group G2 from two elements of the first cyclic group G1;
• selecting a first generator P of the first cyclic group G1 and a second generator P′ of the first cyclic group G1;
• selecting a first secret number s;
• selecting a second secret number s′;
• selecting a function H capable of generating an element of the first cyclic group G1 from a first string of binary digits;
• generating a public point Qi for each of the t members of the set using the function H and the identity IDi associated with the set member;
• generating a private point sP′+s′Qs for the signer;
• generating a message function value PM for the message M using a predetermined function;
• generating the ring signature Sig using at least the signer's private point sP′+s′Q1, the public point Qi of each of the t members of the set, and the message function value PM;
• and
• verifying that the ring signature Sig was generated by a member of the set using at least the public point Qi of each of the t members of the set.

A method of generating and verifying a ring signature Sig for a ring of t ring members, wherein each of the ring members is li, levels below a root PKG in a hierarchical system, and wherein each ring member is associated with a ring member ID-tuple (IDil, . . . , IDili) that includes identity information IDili associated with the recipient and identity information IDil associated with each of (li−1) lower-level PKGs in the hierarchy between the root PKG and the recipient, the method comprising:

• generating a first cyclic group G1 of elements and a second cyclic group G2 of elements;
• selecting a function e capable of generating an element of the second cyclic group G2 from two elements of the first cyclic group G1;
• selecting a root generator P0 of the first cyclic group G1;
• selecting a random root key generation secret s0 associated with and known only to the root PKG;
• generating a root key generation parameter Q0=s0P0;
• selecting a first function H1 capable of generating an element of the first cyclic group G1 from a first string of binary digits;
• selecting a second function H2 capable of generating a second string of binary digits from an element of the second cyclic group G2;
• generating a public element Pil for each of the li−1 ancestral lower-level PKGs associated with each of the t ring members, wherein Pil=H1(IDi1, . . . , IDil) for 1≦i≦t and 1≦l≦(li−1);
• selecting a lower-level key generation secret sil for each of the li−1 ancestral lower-level PKGs associated with each of the t ring members, wherein 1≦i≦t and 1≦l≦(li−1);
• generating a lower-level secret element Sil for each of the li−1 ancestral lower-level PKGs associated with each of the t ring members, wherein Sil=Si(l−1)+si(l−1)Pil for 1≦i≦t and 1≦l≦(li−1), wherein si0=s0, and wherein Si0 is defined to be zero;
• generating a lower-level key generation parameter Qil for each of the li−1 ancestral lower-level PKGs associated with each of the t ring members, wherein Qil=silP0 for 1≦i≦t and 1≦l≦(li−1);
• generating a ring member public element Pili for each of the t ring members, wherein Pili=H1(IDi1, . . . , IDili) for 1≦i≦t;
• generating a recipient secret element Sil for each of the t ring members, wherein
• Sili=Si(li−1)+si(li−1)Pili=Σl=1lisi(l−1)Pil
• for 1≦i≦t;
• signing the message M to generate the ring signature Sig using at least the signer's private point Sjlj and the ID-tuples (IDi1, . . . , IDili) for each of the (t−1) ring members other than the signer;
• and
• verifying the ring signature Sig to confirm that the signature was generated by one of the ring members, using at least the ID-tuples (IDi1, . . . , IDili) for each of the t ring members.

A method of generating an identity-based ring signature for a digital message, the method comprising:

• selecting a private key for each of a plurality of t members of a ring, wherein each member of the ring is associated with identity information, and wherein each of the private keys is related to the identity information associated with a respective ring member;
• computing a public key for each of the t members of the ring set using the respective member's private key, wherein each of the public keys is related to the identity information associated with the respective ring member;
• generating a message function value using a predetermined function;
• and
• generating the ring signature using at least the signer's private key, the public key of each of the (t−1) ring members other than a signer, and the message function values.

A computer-implemented method for generating a ring signature on a message by a signer which is a member of a group of members each of which is associated with an identity, the method comprising:

• the signer obtaining the signer's first secret from a key generator, the first secret being a sum of a plurality of terms of a first group G1, the plurality of terms including a term sP′ and a term s′Pi, wherein s and s′ are integer secrets of the key generator, and wherein P′ is a predefined element of the first group G1 and Pi is the signer's identity element which corresponds to the signer's identity and which is an element of the first group G1, wherein for a predefined element P of the first group G1, elements P, P′, sP, are to be made available to a verifier of the ring signature;
• the signer obtaining a value s′P;
• the signer generating a signature component Sig which is a sum of (a) the first secret, (b) a linear combination of identity elements of the group members with random integer coefficients, the identity element of each group member corresponding to the member's identity and being an element of the first group G1, (c) rMPM, wherein rM is a random integer and PM depends on the message and is an element of the group G1;
• for each said random integer coefficient of each group member other than the signer, the signer generating a signature component equal to the product of the random integer coefficient and the element P;
• the signer generating a signature component equal to a sum of (a) the signer's random integer coefficient times the element P, and (b) s′P;
• the signer generating a signature component rMP.

A computer-implemented method for verifying a digital signature to determine if the digital signature is a valid ring signature on a message by one of a group of members, the method comprising:

• obtaining a value PM which depends on the message and which is an element of a first group G1;
• obtaining predefined elements P, P′ of the group G1, and obtaining a value sP where s is kept secret from the verifier;
• for each group member i, obtaining a corresponding identity element Pi of the first group G1, the element Pi representing the group member's identity;
• obtaining, from the signature, a plurality of elements of the first group G1 comprising:
• (a) an element U;
• (b) for each group member i, a corresponding element Vi;
• and (c) an element VM;
• confirming that for a bilinear non-degenerate mapping ê of G1×G1 into a second group G2, a value ê(P,U) is equal to a product, in the second group G2, of terms ê(P′,sP), ê(PM,VM), and the terms ê(Pi,Vi) for all the group members.