Server-aided computation method and distributed information processing unit

• US 5,046,094 A
• Filed: 02/02/1990
• Issued: 09/03/1991
• Est. Priority Date: 02/02/1989
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Takabayashi, Kyoto, Shimbo, Atsushi, Kawamura, Shinichi
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): Swann, Tod
• Application Number:
  US07/474,404
• Time in Patent Office: 578 Days
• Field of Search: 380/23-25, 380/28, 380/30, 380/44, 380/46, 340/825.31, 340/825.34
• US Class Current: 380/46
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme

Abstract

A server-aided computation method using a main unit for processing secret information and at least one auxiliary unit for supporting a computation that said main unit executes, said method comprising the steps of generating d'"'"' from a secret key d'"'"' using m random numbers R_i (where i=l, . . . , m) generated by said main unit having secret keys n and d, transferring d'"'"' and n from said main unit to said auxiliary unit, computing the following equation from a message block C in said auxiliary unit

M'"'"'=C.sup.d'"'"' mod n

computing X using said random numbers R_i and n in said main unit while computing M'"'"' in said auxiliary unit, transferring M'"'"' from said auxiliary unit to said main unit, and computing a message block M using the following equation in said main unit.

M=M'"'"'·X mod n

Claims

1. A server-aided computation method for computing d-th power of integer C modulo n using a main unit for executing said computation with secret key d and at least one auxiliary unit for supporting a computation that said main unit executes, said method comprising the steps of:

generating d'"'"' from a secret key d using m random numbers R_i (where i=1, ..., m) generated by said main unit having secret keys n and d;

transferring d'"'"' and n from said main unit to said auxiliary unit;

computing the following equation from a message block C in said auxiliary unit

space="preserve" listing-type="equation">M'"'"'=C.sup.d'"'"' mod n

computing X using said random numbers R_i and n in said main unit while computing M'"'"' in said auxiliary unit;

transferring M'"'"' from said auxiliary unit to said main unit; and

computing a message block M using the following equation in said main unit

space="preserve" listing-type="equation">M=M'"'"'·

X mod n·

2. A server-aided computation method for computing d-th power of integer C modulo n using a main unit for executing said computation with secret key d and at least one auxiliary unit for supporting a computation that said main unit executes, said method comprising the steps of:

generating d'"'"' from a secret key d using m random numbers R_i (where i=1, ..., m) generated by said main unit having secret keys n and d;

transferring d'"'"' and n from said main unit to said auxiliary unit;

computing the following equation from a message block C in said auxiliary unit

space="preserve" listing-type="equation">M'"'"'=C.sup.d'"'"' mod n

computing X^-1 using said random numbers R_i and n in said main unit while computing M'"'"' in said auxiliary unit;

transferring M'"'"' from said auxiliary unit to said main unit; and

computing a message block M using the following equation in said main unit

space="preserve" listing-type="equation">M=m'"'"'·

X.sup.-1 mod n ·

3. A server-aided computation method for computing d-th power of integer C modulo n using a main unit for executing said computation with secret key d and at least one auxiliary unit for supporting a computation that said main unit executes, said method comprising the steps of:

generating d'"'"' from a secret key d using m random numbers R_i (where i=1, ..., m) generated by said main unit having secret keys n and d;

transferring d'"'"' and n from said main unit to said auxiliary unit;

computing the following equation from a message block C in said auxiliary unit

space="preserve" listing-type="equation">M'"'"'=C.sup.d'"'"' mod n

computing X and X^-1 using said random numbers R_i and n in said main unit while computing M'"'"' in said auxiliary unit;

transferring M'"'"' from said auxiliary unit to said main unit; and

computing a message block M using M'"'"', X, and X^-1.

4. A server-aided computation method for executing a computation to raise a positive integer M to the d-th power modulo n, using a main unit which has secret information d and at least one auxiliary unit for supporting said computation, said method comprising the steps of:

(a) decomposing said integer n into k (k≧

1) positive factors n_j (where j=1, ..., k), which are relatively prime to each other;

(b) decomposing said positive integer d into (m+1) k secret integers D_1J =[d_j0, f_j1, f_j2, ..., f_jm ] (for j=1, ..., k) stored in said main unit and m×

k public integers D_2j =[d_j1, d_j2, ..., d_jm ] (j=1, ..., k)

which satisfy the following k sets of equations

space="preserve" listing-type="equation">d≡

d.sub.j0 +f.sub.j1 ·

d.sub.j1 +f.sub.j2 ·

d.sub.j2 +...+f.sub.jm ·

d.sub.jm (mod λ

(n.sub.j))

where j=1, ..., k and λ

(n_j) is the Carmichael function of said positive integer n_j ;

(c) computing in said auxiliary unit Y_ji =M^dji mod n where i=1, ..., m and j=1, ..., k and sending the results to said main unit; and

(d) computing in said main unit the following k values S_j using Y_j0 =M^dj0 mod n and Y_ji which have been computed by said main unit;

space="preserve" listing-type="equation">S.sub.j ≡

Y.sub.j0 ·

Y.sub.ji.sup.fj1 ·

Y.sub.j2.sup.fj2...Y.sub.jm.sup.fjm mod n.sub.j

where j=1, ...k and

(e) obtaining a result S which satisfies the k simultaneous equations concerning S as follows;

space="preserve" listing-type="equation">S.sub.j =S mod n.sub.j (for j=1, ..., k) .

5. The server-aided computation method of claim 4 wherein said integer n is a prime number.

6. The server-aided computation method of claim 4 wherein said integer is a product of two prime numbers.

7. The server-aided computation method of claim 4 wherein each of m×

k non-negative integers f_j1, f_j2, ..., f_jm is 1 or 0.

8. The sever-aided computation method of claim 4 wherein values d_ij are defined so that they satisfy a condition d_ij =d_uv at least for one set of integer pairs (i, j) and (u, v) where i, j, u and v are arbitrary subscripts.

9. A distributed information processing unit having a main unit for storing secret information and at least one auxiliary unit for supporting a transformation that said main unit executes, for executing a distributed process without disclosing said secret information necessary for said transformation to other than said main unit, said distributed information processing unit comprising:

transformation means for transforming input information inverse transformation means for inversely transforming the transformation results; and

verification means for comparing the inverse transformation results of said inverse transformation means with said input information so as to verify the transformation results of said transformation means, said main unit having said verification means.

11. The distributed information processing unit of claim 9 wherein said secret information is not disclosed to said auxiliary unit and distributively processed in said main unit and said auxiliary unit.

10. A distributed information processing unit having a main unit for storing secret information and at least one auxiliary unit for supporting a transformation that said main unit executes, for executing a distributed process without disclosing said secret information necessary for said transformation to other than said main unit, said distributed information processing unit comprising:

a plurality of transformation means for executing said transformation of input information; and

verification means for mutually comparing the transformation results of said plurality of transformation means, said main unit having said verification means.

12. A distributed information processing unit having a main unit for storing secret information and at least one auxiliary unit for supporting a transformation that said main unit executes, for executing a distributed process without disclosing said secret information necessary for said transformation to other than said main unit, said distributed information processing unit comprising:

first transformation means for executing said transformation of input information;

second transformation means for executing an identity transformation; and

comparison means for comparing the transformation results of said second transformation means with said input information so as to verify the transformation results of said first transformation means, said main unit having said comparison means.