Group signature generation system using multiple primes

• US 7,093,133 B2
• Filed: 12/20/2001
• Issued: 08/15/2006
• Est. Priority Date: 12/20/2001
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Hopkins, Dale W., Wierenga, Steven W., Collins, Thomas W.
• Primary Examiner(s): Peeso, Thomas R.
• Application Number:
  US10/037,238
• Publication Number:
  US 20030120931A1
• Time in Patent Office: 1,699 Days
• Field of Search: 713/176, 713/182, 713/200, 713/201
• US Class Current: 713/176
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

A method is provided for generating a group digital signature wherein each of a group of individuals may sign a message M to create a group digital signature S, wherein M corresponds to a number representative of a message, 0≦M≦n−1, n is a composite number formed from the product of a number k of distinct random prime factors p₁·p₂· . . . ·p_k, k is an integer greater than 2, and S≡M^d(mod n). The method may include: performing a first partial digital signature subtask on a message M using a first individual private key to produce a first partial digital signature S₁; performing at least a second partial digital signature subtask on the message M using a second individual private key to produce a second partial digital signature S₂; and combining the partial digital signature results to produce a group digital signature S.

Claims

1. A method for generating a group digital signature wherein each of a group of individuals may sign a message M to create a group digital signature S, wherein M corresponds to a number representative of a message, 0≦

M≦

n−

1, n is a composite number formed from the product of a number k of distinct random prime factors p₁·

p₂·

. . . ·

p_k, k is an integer greater than 2, and S≡

M^d (mod n), comprising the steps of;

a first individual in a group performing a first partial digital signature subtask on a message M using a first individual private key to produce a first partial digital signature S₁;

at least a second individual in said group performing a second partial digital signature subtask on said message M using a second individual private key to produce a second partial digital signature S₂; and

combining said partial digital signature results including said results S₁ and S₂ to produce the group digital signature S corresponding to said message M;

wherein said step of combining said results associated with said first and second partial digital signatures includes;

combining said results in accordance with a Chinese Remainder Algorithm.

2. A method for generating a group digital signature as recited in claim 1 wherein the group comprises z individuals whose private key moduli n_i are relatively prime, wherein said step of combining results of said sub-tasks is performed in accordance with the relations

Y_i≡

Y<sub>i−

1</sub>+((S_i−

Y<sub>i−

1</sub>)(w_i<sup>−

1</sup> mod n_i)mod n_i)·

w_i mod n,

wherein 2≦

i≦

z, and

3. A method for generating a group digital signature as recited in claim 1 wherein the group comprises z individuals whose private key moduli n_i are relatively prime, wherein said step of combining results of said sub-tasks is performed in accordance with the relations.

4. A method of creating and assigning individual private keys as recited in claim 3 wherein the keys are created and assigned in accordance with a symmetric distribution of the k prime factors of n, wherein each of the individual members of a group is assigned an individual private key based on a modulus formed as a product of m distinct prime factors, and wherein m<

k.

5. A method of creating and assigning individual private keys as recited in claim 3 wherein the keys are created and assigned in accordance with an asymmetric distribution of the k prime factors of n, wherein at least one of the individual members of a group is assigned an individual private key based on a modulus formed as a product of m₁ distinct prime factors, and wherein at least one other member of said group are assigned individual private keys each based on a modulus formed as a product of m₂ distinct prime factors, wherein m₁<

m₂<

k.

6. An apparatus for generating a group digital signature as recited in claim 5, wherein the secure key generation facility and secure group signature combining entity are combined within a common security boundary.

7. An apparatus for generating a group digital signature as recited in claim 5, including:

means for transferring individual private keys generated by the secure key generation facility into secure tokens for issuance to the assigned individual users of said private signing keys, and

means for securely transferring associated secret group combining parameters from the secure key generation facility to the secure combining entity.

8. An apparatus as recited in claim 5 wherein each of said tokens is a smart card.

9. A method for generating a group digital signature wherein each of a group of individuals may sign a message M to create a group digital signature S, wherein M corresponds to a number representative of a message, 0≦

M≦

n−

1, n is a composite number formed from the product of a number k of distinct random prime factors p₁·

p₂·

. . . ·

p_k is an integer greater than 2, and S≡

M^d(mod n), comprising the steps of;

a first individual in group performing a first partial digital signature subtask on a message M using a first individual private key to produce a first partial digital signature S₁;

at least a second individual in said group performing a second partial digital signature subtask on said message M using a second individual private key to produce a second partial digital signature S₂; and

combining said partial digital signature results including said results S₁ and S₂ to produce the group digital signature S corresponding to said message M;

wherein each of said individual private keys includes,

an associated individual modulus n_i that is a number formed as a product of one or more of said k prime factors of said group modulus n, and

an associated individual private exponent d_i that is determined based on a selected public group exponent e, and also based on the prime factors of said associated individual modulus n_i.

10. A method for generating a group digital signature as recited in claim 9 wherein each of said individual private exponents d_i is determined as a number congruent to the inverse of said public group exponent e, modulo the Euler Totient function of said associated individual modulus n_i.

11. A method for generating a group digital signature as recited in claim 9 wherein said first partial digital signature S₁ is generated based on the relationship

S₁≡

M^d1(mod n₁).

12. A method for generating a group digital signature wherein each of a group of individuals may sign a message M to create a group digital signature S, wherein M corresponds to a number representative of a message, 0≦

M≦

n−

1, n is a composite number formed from the product of a number k of distinct random prime factors p₁·

p₂·

. . . ·

p_k is an integer greater than 2, and S≡

M^d(mod n), comprising the steps of;

a first individual in a group performing a first partial digital signature subtask on a message M using a first individual private key to produce a first partial digital signature S₁;

at least a second individual in said group performing a second partial digital signature subtask on said message M using a second individual private key to produce a second partial digital signature S₂; and

combining said partial digital signature results including said results S₁ and S₂ to produce the group digital signature S corresponding to said message M;

wherein the first individual is assigned a first number m₁ of the k prime factors of said group modulus n and the second individual is assigned a second number m₂ of the k prime factors of said group modulus n, and wherein;

said first individual private key includes,

an associated individual modulus n₁ that is determined as the product of a number m₁ of distinct prime factors of said group modulus n, and

an associated individual private exponent d₁ that is determined based on a selected public key exponent e and based on the m₁ prime factors of said associated individual modulus in accordance with

13. A method for generating a group digital signature wherein each of a group of individuals may sign a message M to create a group digital signature S, wherein M corresponds to a number representative of a message, 0≦

M≦

n−

1, n is a composite number formed from the product of a number k of distinct random prime factors p₁·

p₂·

. . . p_k, k is an integer greater than 2, and S≡

M^d(mod n), comprising the steps of;

a first individual in a group performing a first partial digital signature subtask on a message M using a first individual private key to produce a first partial digital signature S₁;

at least a second individual in said group performing a second partial digital signature subtask on said message M using a second individual private key to produce a second partial digital signature S₂; and

combining said partial digital signature results including said results S₁ and S₂ to produce the group digital signature S corresponding to said message M;

wherein said first individual private key is created based on associated prime factors p_a and p_b of the group modulus n, said first individual private key including,

an individual modulus n₁ that is a composite number formed as the product P_a·

P_b of said associated primes, and

an associated individual private exponent d₁ that is determined based on a selected public key exponent e and said associated primes p_a and p_b in accordance with

d₁≡

e<sup>−

1</sup> mod((p_a−

1)(p_b−

1)).

14. A method for generating a group digital signature as recited in claim 13 wherein said first partial digital signature S₁ is generated based on the relationship,

S₁≡

M^d1(mod n₁).

15. A method of creating and assigning individual private keys to each member of at least one group of individuals, wherein the individuals in each group may, use their assigned keys to sign a message M to collectively create a group digital signature S associated with an entity that includes all of the groups, wherein M corresponds to a number representative of a message, 0≦

M≦

n−

1, n is a composite number formed from the product of a total number k of distinct random primes p₁·

p₂·

. . . ·

p_k, k is an integer greater than 2, and S≡

M^d(mod n) and wherein each such group of individuals collectively control all of the primes, but wherein no single one of the individuals controls all of the prime factors p₁·

p₂·

. . . ·

p_k, comprising;

assigning at least one of the total number k of prime numbers p₁·

p₂·

. . . ·

p_k to each of a plurality of members of each of at least one group, wherein all of the prime numbers assigned to the individuals within each group are distinct;

defining a unique individual modulus associated with each of the individuals formed as the product of the prime numbers assigned to the individual; and

defining a unique individual private key for each of the individuals based on the associated individual modulus formed for the individual;

whereby each of the individual private keys may be used to create an associated individual partial digital signature, wherein the individual partial digital signatures of the members of a group may be combined to form the group digital signature S, and wherein at least one of the partial digital signatures cannot be combined across different groups to form the group digital signature S.

16. A method of creating and assigning partial digital signature keys as recited in claim 15 wherein the number of combinations of the k prime factors taken in at a time dictates the number of distinct individual private keys that may be created based on the total number k prime factors, and wherein the number of combinations of k prime factors taken m at a time is expressed in accordance with

17. A method of creating and assigning individual private keys as recited in claim 16 wherein the keys are created and assigned in accordance with an asymmetric distribution of the k prime factors of n, wherein at least one private key is assigned across more than one group.