# US 2008/0313465 A1 · Signature schemes using bilinear mappings

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0313465 A1
- Document ID: US20080313465A1
- Status: Published application
- Kind: A1
- Application number: 11/955,167
- Filed: 2007-12-12
- Published: 2008-12-18
- Earliest claimed: 2002-04-15
- Assignees: Ntt Docomo, Inc.
- Inventors: Craig B. Gentry
- Web page: https://patentgrep.com/patent/US20080313465A1

## CPC

- H04L 9/3073: {involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing}
- H04L 9/3255: {using group based signatures, e.g. ring or threshold signatures}
- H04L 2209/463: Electronic voting
- H04L 2209/76: Proxy, i.e. using intermediary entity to perform cryptographic operations
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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.

## Claims

### Claim at position 1

1-40. (canceled)

### Claim 41

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.

### Claim 42

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
′
)
.

### Claim 43 (depends on 42)

A method of generating and verifying a signature Sig as in claim 42, wherein:
both the first group G1 and the second group G2 are of the same prime order q.

### Claim 44 (depends on 42)

A method of generating and verifying a signature Sig as in claim 42, wherein:
the first cyclic group G1 is an additive group of points on a supersingular elliptic curve or abelian variety, and the second cyclic group G2 is a multiplicative subgroup of a finite field.

### Claim 45 (depends on 42)

A method of generating and verifying a signature Sig as in claim 42, wherein:
the function e is an admissible pairing.

### Claim at position 7

46-47. (canceled)

### Claim 48

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.

### Claim 49

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.

### Claim 50

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.

### Claim 51 (depends on 50)

The method of claim 50 wherein G1 is a cyclic group.

### Claim 52 (depends on 51)

The method of claim 51 wherein P0 is a generator of the first group G1.

### Claim 53 (depends on 52)

The method of claim 52 wherein the first group G1 has a prime order.

### Claim 54 (depends on 50)

The method of claim 50 wherein the signer's secret key is equal to a sum of values si−1Pi for all levels i of the signer and above the signer in the hierarchical system except for a root's level, wherein each si−1 is an integer kept secret from the verifier and each Pi is associated with an identity of the signer or the signer's parent at level i.

### Claim 55 (depends on 50)

The method of claim 50 wherein the integer coefficient in (5) is equal to M′+r′s′t.

### Claim 56 (depends on 50)

The method of claim 50 wherein Sig is the sum of the signer's secret key and the value stPM′.

### Claim 57 (depends on 50)

The method of claim 50 wherein the operations (7) and (8) are performed after (6).

### Claim 58

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.

### Claim 59 (depends on 58)

The method of claim 58 wherein the linear combination in (4) is equal to MP0+rQ′t, where Q′t is independent of the message M.

### Claim 60 (depends on 58)

The method of claim 58 wherein the operation (4) is performed after (3).

### Claim 61 (depends on 58)

The method of claim 58 wherein G1 is a cyclic group.

### Claim 62 (depends on 58)

The method of claim 58 wherein P0 is a generator of the first group G1.

### Claim 63 (depends on 58)

The method of claim 58 wherein the first group G1 has a prime order.

### Claim 64 (depends on 58)

The method of claim 58 wherein the second group G2 is a cyclic group.

### Claim 65 (depends on 41)

A computer program product containing program code for performing the method of claim 41.

### Claim 66 (depends on 42)

A computer program product containing program code for performing the method of claim 42.

### Claim 67 (depends on 49)

A computer program product containing program code for performing the method of claim 49.

### Claim 68 (depends on 50)

A computer program product containing program code for performing the method of claim 50.

### Claim 69 (depends on 57)

A computer program product containing program code for performing the method of claim 57.

### Claim 70 (depends on 42)

A system comprising one or more computer processors and memory which stores program code for execution by the one or more computer processors, the program code being for performing the method of claim 42.

### Claim 71 (depends on 49)

A system comprising one or more computer processors and memory which stores program code for execution by the one or more computer processors, the program code being for performing the method of claim 49.

### Claim 72 (depends on 50)

A system comprising one or more computer processors and memory which stores program code for execution by the one or more computer processors, the program code being for performing the method of claim 50.

### Claim 73 (depends on 57)

A system comprising one or more computer processors and memory which stores program code for execution by the one or more computer processors, the program code being for performing the method of claim 57.
