Server-aided computation method and distributed information processing unit

Claim 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 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·

Claim 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 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 M=m'·X.sup.-1 mod n ·

Claim 4

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 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 M=m'·X.sup.-1 mod n ·

Claim 5

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

Claim 6

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

Claim 7

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 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; 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: S.sub.j =S mod n.sub.j (for j=1, ..., k) .

Claim 8

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 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; 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: S.sub.j =S mod n.sub.j (for j=1, ..., k) .

Claim 9

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

Claim 10

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

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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.