Re-encrypted data verification program, re-encryption apparatus and re-encryption system

1. An at least one non-transitory computer readable medium including a re-encrypted data verification program used in a re-encryption system comprising an encryption apparatus executing an encryption process on plain data using a public key corresponding to a private key of a re-encryption key generation apparatus and transmitting resultant encrypted data to a re-encryption apparatus, the re-encryption apparatus then executing a re-encryption process on the encrypted data using a re-encryption key without decrypting the encrypted data and transmitting resultant re-encrypted data to a decryption apparatus, the decryption apparatus executing a verification process on the re-encrypted data using a public key of the re-encryption apparatus, and executing a decryption process on the re-encrypted data using a private key corresponding to a public key of the decryption apparatus to obtain the plain data, the re-encrypted data verification program being executed by a processor in the decryption apparatus comprising a storage device storing the public key of the re-encryption key generation apparatus and the private key of the decryption apparatus, the re-encrypted data verification program being stored in a non-transitory computer-readable storage medium, the re-encrypted data verification program, when executed by the re-encryption system, causes the re-encryption system to perform the steps of:

a first program code of the re-encrypted data verification program allowing the processor to execute a process of holding at least one program instruction including a verification formula, the verification formula holding true when being calculated by substituting into the verification formula, a part of the re-encrypted data used for the re-encryption system and the public key used for the encryption process executed on the encrypted data before the re-encryption process is executed on the re-encrypted data;

a second program code of the re-encrypted data verification program allowing the processor to execute a process of performing a calculation based on the verification formula by substituting into the verification formula, the part of the re-encrypted data received from the re-encryption apparatus and the public key of the re-encryption key generation apparatus read from the storage device, to determine whether or not the verification formula holds true; and

a third program code of the re-encrypted data verification program allowing the processor to execute a process of outputting detection success indicating that the public key used for the encryption process executed on the plain data is the public key of the re-encryption key generation apparatus when a result of the determination indicates that the verification formula holds true.

2. The at least one non-transitory computer readable medium including the re-encrypted data verification program according to claim 1 , wherein, when the private key and public key of the re-encryption key generation apparatus are represented by x i and X i (where, when bilinear map groups satisfying a prime order p>2 λ are represented by G and G T and a first generator is represented by gεG, based on a security parameter λ, public parameters (p, λ, G, G T , g, u, v, Sig)),

the plain data is represented by m εG T ,

the encrypted data is represented by C i =(C 1 , C 2 , C 3 , C 4 , σ) (where, when a signature key and a verification key in a one-time signature are represented by ssk and svk, a multiplicative group for a prime number p is represented by Z p *, a first random number is represented by rεZ p *, a pairing function is represented by e(,), a second generator and a third generator are represented by u, vεG, respectively, and a signature generation function of the one-time signature is represented by Ŝ, for

C 1 =svk,

C 2 =X i r ,

C 3 =e ( g,g ) r ·m ,

C 4 =( u svk ·v ) r ,

σ=Ŝ(ssk, C 3 , C 4 )), and

when the private key and public key of the decryption apparatus are represented by x j and X j (where: X i =g X i , X j =g X j ),

the re-encryption key is represented by:

R ij =X j 1/x i =g x j /x i , and

the re-encrypted data is represented by C j =(C 1 , C 2′ , C 2″ , C 2′″ , C 2V , C 3 , C 4 , σ) (where a second random number is represented by tεZ p *), for

C

2

′

=

X

i

t

,

⁢

C

2

″

=

R

ij

1

/

t

=

g

(

x

j

/

x

i

)

t

-

1

,

⁢

C

2

″′

=

C

2

t

=

X

i

rt

,

⁢

C

2

⁢

V

=

g

t

,

and

the verification formula is represented by:

e ( C′ 2 ,g )= e ( C 2V ,X i ).

3. A re-encryption apparatus using a re-encrypted data verification program, the re-encryption apparatus comprising:

a verification program storage device which stores the re-encrypted data verification program; and

a verification program distribution device which distributes the re-encrypted data verification program in the verification program storage device to a decryption apparatus upon receiving a distribution request for the re-encrypted data verification program from the decryption apparatus, wherein

the re-encrypted data verification program includes

a first program code allowing a processor in a decryption apparatus to execute a process of holding a program code including a verification formula, the verification formula holding true when being calculated by substituting into the verification formula, a part of re-encrypted data used for the decryption apparatus and a public key used for an encryption process executed on encrypted data before an re-encryption process is executed on the re-encrypted data using a re-encryption key;

a second program code allowing the processor to execute a process of performing a calculation based on the verification formula by substituting into the verification formula, the part of the re-encrypted data received from the re-encryption apparatus and a public key of an re-encryption key generation apparatus, to determine whether or not the verification formula holds true; and

a third program code allowing the processor to execute a process of outputting detection success indicating that the public key used for the encryption process executed on plain data is the public key of the re-encryption key generation apparatus when a result of the determination indicates that the verification formula holds true.

4. The re-encryption apparatus according to claim 3 ,

wherein, when a private key and the public key of the re-encryption key generation apparatus are represented by x i and X i (where, when bilinear map groups satisfying a prime order p>2 λ are represented by G and G T and a first generator is represented by gεG, based on a security parameter λ, public parameters (p, λ, G, G T , g, u, v, Sig)),

the plain data is represented by mεG T ,

the encrypted data is represented by C i =(C 1 ,C 2 , C 3 ,C 4 , σ) (where, when a signature key and a verification key in a one-time signature are represented by ssk and svk, a multiplicative group for a prime number p is represented by Z p *, a first random number is represented by rεZ p *, a pairing function is represented by e(,), a second generator and a third generator are represented by u, vεG, respectively, and a signature generation function of the one-time signature is represented by Ŝ, for

C 1 =svk,

C 2 =X i r ,

C 3 =e ( g,g ) r ·m,

C 4 =( u svk ·v ) r ,

σ= Ŝ ( ssk, C 3 , C 4 )), and

when a private key and public key of the decryption apparatus are represented by x j and X j (where: X i =g x i , X j =g x j ),

the re-encryption key is represented by:

R ij =X j 1/x i =g x j /x i , and

the re-encrypted data is represented by C j =(C 1 , C 2′ , C 2″ , C 2′″ , C 2V , C 3 , C 4 , σ) (where a second random number is represented by tεZ p *), for

C

2

′

=

⁢

x

i

t

,

⁢

C

2

″

=

⁢

R

ij

1

/

t

=

g

⁡

(

x

j

/

x

i

)

t

-

1

,

⁢

C

2

′″

=

⁢

C

2

t

=

X

i

rt

,

⁢

C

2

⁢

⁢

V

=

⁢

g

t

,

and

the verification formula is represented by:

e (C′ 2 ,g )= e ( C 2V ,X i ).

5. A re-encryption system comprising an encryption apparatus, a re-encryption key generation apparatus, a re-encryption apparatus, and a decryption apparatus, wherein

the encryption apparatus is comprised of:

a first storage device which stores a public key of the re-encryption key generation apparatus;

an encryption device which executes an encryption process on plain data using the public key of the re-encryption key generation apparatus read from the first storage device, to obtain encrypted data; and

a first device which transmits the resultant encrypted data to the re-encryption apparatus,

the re-encryption key generation apparatus comprising:

a second storage device which stores a private key corresponding to the public key of the re-encryption key generation apparatus and a public key corresponding to a private key of the decryption apparatus;

a second device which generates a re-encryption key using the private key of the re-encryption key generation apparatus and the public key of the decryption apparatus both read from the second storage device; and

a third device which transmits the generated re-encryption key to the re-encryption apparatus,

the re-encryption apparatus comprising:

a third storage device which stores the re-encryption key received from the re-encryption key generation apparatus;

a re-encryption device which, upon receiving the encrypted data from the encryption apparatus, executes a re-encryption process on the encrypted data using the re-encryption key read from the third storage device without decrypting the encrypted data, to obtain re-encrypted data; and

a fourth device which transmits the resultant re-encrypted data to the decryption apparatus, and

the decryption apparatus comprising:

a fourth storage device which stores the public key of the re-encryption key generation apparatus and the private key of the decryption apparatus;

a decryption device which, upon receiving the re-encrypted data from the re-encryption apparatus, executes a decryption process on the re-encrypted data based on the private key of the decryption apparatus read from the fourth storage device, to obtain the plain data;

a holding device which holds a verification formula that holds true when the verification formula is calculated by substituting, into the verification formula, a part of the re-encrypted data used for the re-encryption system and the public key used for the encryption process executed on the encrypted data before the re-encryption process is executed on the re-encrypted data;

a determination device which performs a calculation based on the verification formula read from the holding device by substituting, into the verification formula, a part of the re-encrypted data received from the re-encryption apparatus and the public key of the re-encryption key generation apparatus read from the fourth storage device, to determine whether or not the verification formula holds true; and

an output device which outputs verification success indicating that the public key used for the encryption process executed on the plain data is the public key of the re-encryption key generation apparatus when a result of the determination indicates that the verification formula holds true.

6. The re-encryption system according to claim 5 , further comprising a key generation apparatus that generates a pair of a public key and a private key for each of the re-encryption and decryption apparatuses.