PROCEDURE FOR A MULTIPLE DIGITAL SIGNATURE

• US 20140164765A1
• Filed: 05/09/2012
• Published: 06/12/2014
• Est. Priority Date: 05/13/2011
• Status: Active Grant

• Current Assignee: Telefonica Cybersecurity & Cloud Tech SLU (Telefonica SA)
• Original Assignee: Telefonica SA
• Inventors: Hernndez Encinas, Luis, Muoz Masqu, Jaime, Durn Daz, Jos Ral, Hernndez lvarez, Fernando, Gayoso Martnez, Victor
• Granted Patent: US 9,191,214 B2
• Time in Patent Office: Days
• US Class Current: 713/156
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/3255 using group based signatures, e.g. ring or threshold signatures

Abstract

It comprises:

• • i) generating, by a Trusted Third Party (T), a private key for each signer or member (F₁, F₂, . . . , F_t) of a group of signers (G);
  • ii) generating, each of said signers (F₁, F₂, . . . , F_t), a partial signature of a document (M) using their private keys;
  • iii) generating a multiple signature from said partial signatures; and
  • iv) verifying said multiple signature.

It further comprises generating, by the Trusted Third Party (T), a common public key for all of said signers (F₁, F₂, . . . , F_t) and using said common public key for performing said multiple signature verification of iv).

Claims

1. Procedure for a multiple digital signature, comprising:

i) generating, by a Trusted Third Party (T), a private key for each signer or member (F₁, F₂, . . . , F_t) of a group of signers (G);

ii) generating, each of said signers (F₁, F₂, . . . , F_t), a partial signature of a document (M) using their private keys;

iii) generating a multiple signature from said partial signatures; and

iv) verifying said multiple signature;

wherein the procedure is characterised in that it comprises generating, by said Trusted Third Party (T), a common public key for all of said signers (F₁, F₂, . . . , F_t) and using said common public key for performing said multiple signature verification of iv).

2. Procedure as per claim 1, wherein:

said step ii) comprises generating each of said signers (F₁, F₂, . . . , F_t) its respective partial signature on a digest (m) of said document (M) and sending them to the Trusted Third Party (T); and

said step iii) comprises generating, the Trusted Third Party (T), said multiple signature using the received partial signatures.

3. Procedure as per claim 2, comprising, the Trusted Third Party (T), verifying the validity of all the received partial signatures and, if they are valid, performing said step iii) by adding all of the partial signatures.

4. Procedure as per claim 1, wherein:

said step ii) comprises;

a first one (F₁) of said signers (F₁, F₂, . . . , F_t) performing a partial signature on a digest (m) of said document (M);

a second one (F₂) of said signers (F₁, F₂, . . . , F_t) performing a partial signature on said first signer (F₁) partial signature, and

successively performing the rest of signers (F₃, . . . , F_t) their respective partial signatures on a partial signature performed by a previous one (F₂, . . . , F_t-1) of said signers (F₁, F₂, . . . , F_t); and

said multiple signature is the partial signature performed by the last (F_t) of said signers (F₁, F₂, . . . , F_t).

5. Procedure as per claim 4, comprising, each of said signers (F₁, F₂, . . . , F_t) broadcasting its respective partial signature among the group of signers (G).

6. Procedure as per claim 5, comprising arbitrarily establishing an order in the group of signers (G) for said first (F₁), second (F₂) and successive signers (F₃, . . . , F_t).

7. Procedure as per claim 4, 5 or 6, comprising each of said signers (F₁, F₂, . . . , F_t) verifying the partial signature of the previous signer before signing thereon.

8. Procedure as per any of claims 4 to 7, wherein each of said partial signatures performed by said second and successive signers (F₂, . . . , F_t) is a partial accumulative signature performed by partially signing said digest (m) of the document (M) and adding the result to the partial signature of the previous signer (F₁, F₂, . . . , F_t-1).

9. Procedure as per any of claims 2 to 8, wherein each of the signers (F₁, F₂, . . . , F_t) performing its respective partial signature on said digest (m) of the document (M), at said step ii), carries it out as follows:

f_i=a_i+c_i·

m(mod r),

g_i=b_i+d_i·

m(mod r),

where i=1, t;

a_i=(h−

s·

b_i) (mod r);

c_i=(k−

s·

d_i) (mod r);

b_i, d_i are pairs of random numbers generated by said Trusted Third Party (T);

m is the digest or hash of the document (M) to be signed;

r is a prime number;

s is a random secret number generated by said Trusted Third Party (T);

h=(a₀+s·

b₀) (mod r);

k=(c₀+s·

d₀) (mod r); and

a₀, b₀, c₀, d₀ are integer numbers randomly generated by the Trusted Third Party (T).

10. Procedure as per claim 9 when depending on any of claims 4 to 8, performing each of the second (F₂) and subsequent signers (F₃, . . . , F_t) its respective partial accumulative signature as follows:

f_i=f_i-1+a_i+c_i·

m(mod r)=a₁+ . . . +a_i+(c₁+ . . . +c_i)m(mod r),

g_i=g_i-1+b_i+d_i·

m(mod r)=b₁+ . . . +b_i+(d₁+ . . . d_i)m(mod r),

where f_i-1, g_i-1 represent the partial signature already calculated by the previous signer.

11. Procedure as per claim 9 or 10, wherein a_i, c_i, b_i, d_iε

_r where _r is the set of integers modulo r, s>

r, and belongs to a subgroup S_r of _n;

where _n is the set of integers modulo n and a₀, b₀, c₀, d₀ε

_r are the Trusted Third Party (T) private keys.

12. Procedure as per claim 11 when depending on claim 3, wherein said verifying of the validity of all the received partial signatures performed by the Trusted Third Party (T), is carried out by checking if:

P·

Q^m(mod n)=α

<sup>fi·

β

gi</sup>(mod n)

where P and Q form said common public key, α

ε

_n⁺ and is an integer number chosen by the Trusted Third Party (T) with multiplicative order r, module n, and β

=α

^s(mod n).

13. Procedure as per claim 11 when depending on claim 7, wherein said verifying of the partial signature of the previous signer is performed by each of said signers (F₁, F₂, . . . , F_t) by checking if:

P^i-1·

Q^(i-1)m=α

^fi-1·

β

^gi-1(mod n)

where f_i-1, g_i-1 represent the partial accumulate signature already calculated by the previous signer, P and Q form said common public key, α

ε

_n⁺ and is an integer number chosen by the Trusted Third Party (T) with multiplicative order r, module n, and β

=α

^s (mod n).

14. Procedure as per claim 12 or 13, where:

P=α

^ai·

β

^bi(mod n);

Q=α

^ci·

β

^di(mod n);

α

=g<sup>2v1·

v2</sup>-p<sup>1·

q1</sup>(mod n)

β

=α

^s(mod n);

n=p·

q;

g is an element randomly chosen which meet gε

_n⁺ whose order is λ

(n)

p₁, q₁ are prime numbers;

u₁ and u₂ are integer numbers, where u₁=2·

v₁ and u₂=2·

v₂;

v₁, v₂ are coprimes;

p=u₁·

r·

p₁+1;

q=u₂·

r·

q₁+1;

φ

(n)=(p−

1)(q−

1)=u₁·

u₂·

r²·

p₁·

q₁;

where φ

(n) is the Euler function;

λ

(n)=lcm(p−

1,q−

1)=2·

v₁·

v₂·

r·

p₁·

q₁;

where lcm represents the least common multiple, and λ

(n) is the Carmichael function; and

a meets the condition;

gcd(α

,φ

(n))=gcd(α

,u₁·

u₂·

r²·

p₁·

q₁)=1

where gcd is the greatest common divisor.

15. Procedure as per claim 12 or 14 when depending on claim 12, comprising, the Trusted Third Party (T), performing said adding of the partial signatures at step iii) by:

f=Σ

_{i=1, . . . ,t}f_i(mod r),

g=Σ

_{i=1, . . . ,t}g_i(mod r).

the procedure further comprising publishing f, g as the multiple signature of the group of signers (G) to the digest (m) of the document (M).

16. Procedure as per claim 13 or claim 14 when depending on claim 13, comprising the last signer (F_t) publishing f_t, g_r as the multiple signature f, g of the group of signers (G) to the digest (m) of the document (M).

17. Procedure as per claim 15 or 16, comprising carrying out said step iv) of verifying said multiple signature f, g by using the following expression:

P^t·

Q<sup>t·

m</sup>=α

^f·

β

^g(mod n).