Signature schemes using bilinear mappings
AssigneeNtt Docomo, Inc.
InventorCraig B. Gentry
Life of this patent
Estimating the term…
Abstract
Methods and systems are provided for generating and verifying signatures of digital messages communicated between signers and verifiers. Using bilinear mappings, such as Weil or Tate pairings, these methods and systems enable generation and verification of efficient multisignatures, identity-based ring signatures, hierarchical proxy signatures, and hierarchical online/offline signatures.
Claims33
1-40. (canceled)
A method of generating and verifying a signature of a digital message communicated between a signer and a verifier, wherein the signer is t levels below a root PKG in a hierarchical system, and wherein the signer is associated with a signer ID tuple (IDy1, . . . , IDyt) that includes identity information IDyt associated with the signer and identity information IDyi associated with each of (t−1) lower-level PKGs in the hierarchy between the root PKG and the signer, the method comprising:
- generating a lower-level public key for each of the (t−1) lower-level PKGs;
- generating a signer private key associated with the signer;
- selecting a random signer trapdoor secret;
- generating a public hash key using the random signer trapdoor secret;
- selecting a random message and a random number;
- generating an offline signature using the random message, the random number, the signer private key, and the trapdoor secret;
- identifying a matching random number that matches the offline signature to the digital message;
- and
- verifying the offline signature by confirming that the signature matches the digital message using at least the matching random number and the public hash key.
A method of generating and verifying a signature Sig of a digital message M communicated between a signer and a verifier, wherein the signer is t levels below a root PKG in a hierarchical system, and wherein the signer is associated with a signer ID tuple (IDy1, . . . , IDyt) that includes identity information IDyt associated with the signer and identity information IDyi associated with each of (t−1) lower-level PKGs in the hierarchy between the root PKG and the signer, 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 root generator P0 of the first cyclic group G1;
- selecting a random root key generation secret so 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;
- generating a public element Pyi for each of the t lower-level PKGs, wherein Pyi=H1(IDy1, . . . ,IDyi) for 1≦i≦(t−1);
- selecting a lower-level key generation secret syi for each of the n lower-level PKGs, wherein each lower-level key generation secret syi is known only to its associated lower-level PKG;
- generating a lower-level secret element Syi for each of the m lower-level PKGs, wherein Syi=Sy(i−1)+sy(i−1)Pyi for 1≦i≦(t−1);
- generating a lower-level key generation parameter Qyi for each of the m lower-level PKGs, wherein Qyi=syiP0 for 1≦i≦(t−1);
- generating a signer public element Pyt=H1(IDy1, . . . ,IDyt) associated with the signer;
- generating a signer secret element
- s
- yt
- =
- S
- y
-
- (
- t
- -
- 1
- )
- +
- s
- y
-
- (
- t
- -
- 1
- )
-
- P
- yt
- =
- ∑
- i
- =
- 1
- t
-
- s
- y
-
- (
- i
- -
- 1
- )
-
- P
- y
- i
- associated with the signer;
- selecting a random signer trapdoor secret s′ytεZ/qZ;
- generating a public hash key Q′yt=s′ytP0;
- selecting a random message M′ and a random number r′;
- signing the random message M′ to generate a digital signature
- Sig
- =
- (
- ∑
- i
- =
- 1
- t
-
- s
- i
- -
- 1
-
- P
- i
- )
- +
- s
- i
-
- P
- M
- ′
- ,
- wherein
- P
- M
- ′
- =
- H
-
- (
- (
- M
- ′
- +
- r
- ′
-
- s
- yt
- ′
- )
-
- P
- 0
- )
- ;
- generating r=(s′yt)−1(M′−M)+r′;
- and
- verifying the digital signature Sig by confirming that
- e
-
- (
- Sig
- ,
- P
- 0
- )
- =
- e
-
- (
- Q
- yt
- ,
- P
- M
- )
-
- ∏
- i
- =
- 1
- t
-
- e
-
- (
- Q
- y
-
- (
- i
- -
- 1
- )
- ,
- P
- i
- )
- ,
- wherein
- P
- M
- =
- H
- 1
-
- (
- MP
- 0
- +
- rQ
- yt
- ′
- )
- .
46-47. (canceled)
A system for generating a signature of a digital message communicated between a signer and a verifier, wherein the signer is t levels below a root PKG in a hierarchical system, and wherein the signer is associated with a signer ID tuple (IDy1, . . . , IDyt) that includes identity information IDyt associated with the signer and identity information IDyi associated with each of (t−1) lower-level PKGs in the hierarchy between the root PKG and the signer, comprising:
- a memory operable to store at least a lower-level public key associated with each of the (t−1) lower-level PKGs, and a signer private key associated with the signer;
- and
- a processor in communication with the memory, wherein the processor is operable in an offline state to select a random trapdoor secret, to select a random message and a random number, and to generate an offline signature using the random message, the random number, the signer private key, and the trapdoor secret, and wherein the processor is operable in an online state to identify a matching random number that matches the offline signature to the digital message.
A method of generating a signature for a digital message, the method comprising:
- generating a signer private key associated with a signer in a hierarchical identity-based system, wherein the signer private key is related to identity information associated with the signer;
- selecting a random signer trapdoor secret;
- selecting a random message and a random number;
- generating an offline signature using the random message, the random number, the signer private key, and the trapdoor secret;
- and
- identifying a matching random number that matches the offline signature to the digital message,
- wherein only the identifying needs to be performed online.
A computer-implemented method for generating a digital signature on a message M by a signer in a hierarchical identity-based system, the method comprising a signer performing operations of:
- (1) obtaining the signer's secret key equal to a sum, in a first group G1, of:
- (a) a value associated with the signer's immediate parent, and (b) a secret integer times a value associated with the signer's identity;
- (2) generating secret integers st, s′t;
- (3) for a predefined element P0 of the group G1, generating values stP0 and s′tP0, wherein the values P0, stp0 and s′tp0 are to be made available to a verifier of the digital signature;
- (4) generating a message M′ and a first integer parameter r′;
- (5) generating a value PM′ as a function h of a product of an integer coefficient with the element P0, the integer coefficient being a linear combination of at least the message M′ and the first integer parameter r′, wherein at least one of coefficients in the linear combination is obtained from the value st′;
- (6) generating a signature component Sig on the message M′ as a linear combination of the signer's secret key and a value stPM′;
- (7) receiving the message M;
- (8) determining a second parameter value r from the message M such that a value PM of the function h on the message M and the second parameter value r is equal to PM′, wherein the second parameter value r is part of the digital signature on the message M.
A computer-implemented method for verifying a digital signature on a message M of a signer in a hierarchical identity-based system, the method comprising a verifier performing operations of:
- (1) for each level i in the hierarchical identity-based system at or above the signer's level, obtaining:
- (a) an element Qi of the group G1, each element Qi being an integer multiple of a predefined element P0 of the group G1 with a secret integer coefficient not provided to the verifier, and (b) a value Pi associated with an identity of the signer or the signer's parent at level i;
- (2) obtaining signature components U, PM′ which are elements of a first group G1;
- (3) for a predefined bilinear non-degenerate mapping ê of G1×G1 into a second group G2, confirming that ê(U,P0) is equal to a product of ê(Qt,PM′) with values ê(Qi−1,Pi) for all levels i other than a root's level, wherein a level i−1 is the immediately preceding higher level relative to level i;
- (4) receiving the message M and an integer parameter r, and confirming that PM′ is equal to a value of a predefined function h on a linear combination of predefined elements of the first group G1 with integer coefficients obtained from the message M and the parameter r.
Dependencies are inferred from the claim text.