RE-ENCRYPTION DEVICE, RE-ENCRYPTION METHOD, COMPUTER READABLE MEDIUM, AND CRYPTOGRAPHIC SYSTEM

Abstract

An encryption device (50) generates a ciphertext. A master re-encryption key generation device (40) generates a master re-encryption key that cannot decrypt a ciphertext generated by the encryption device (50), but can generate a re-encryption key for changing an access range for a ciphertext generated by the encryption device (50). A re-encryption device (60) generates a re-encryption key for re-encrypting a target ciphertext generated by the encryption device (50), using the master re-encryption key, and re-encrypts the target ciphertext to generate a re-encrypted ciphertext, using the generated re-encryption key.

Claims

1. A re-encryption device comprising: processing circuitry to: generate a re-encryption key for re-encrypting a target ciphertext generated by an encryption device, using a master re-encryption key that cannot decrypt a ciphertext generated by the encryption device, but can generate a re-encryption key for changing an access range for a ciphertext generated by the encryption device, and re-encrypt the target ciphertext to generate a re-encrypted ciphertext, using the generated re-encryption key, wherein the master re-encryption key includes a key element k*.sub.r in which a parameter w{right arrow over ( )} is set, the parameter w{right arrow over ( )} corresponding to a parameter y{right arrow over ( )} set in a cipher element c.sub.1 included in the ciphertext generated by the encryption device, wherein the re-encryption key for re-encrypting the target ciphertext includes a key element k{tilde over ( )}*.sub.r in which a random number r is embedded in the key element k*.sub.r, a cipher element c{tilde over ( )}.sub.r in which a parameter x{right arrow over ( )}′ indicating a changed access range is set, and an element D{tilde over ( )} in which the random number r{tilde over ( )} is encrypted, and wherein the re-encrypted ciphertext includes an element K in which the cipher element c.sub.1 is decrypted with the key element k{tilde over ( )}*.sub.r, the cipher element c{tilde over ( )}.sub.r, and an element E in which the element D{tilde over ( )} is set.

2. The re-encryption device according to claim 1, wherein the processing circuitry generates the element K in which the cipher element c.sub.1 is decrypted with the key element k{tilde over ( )}*.sub.r and a random number r′ is embedded, and generates the element E in which the random number r′ is embedded in the element D{tilde over ( )}.

3. The re-encryption device according to claim 2, wherein the processing circuitry generates the cipher element c{tilde over ( )}.sub.r in which a random number ζ{tilde over ( )}.sub.r is embedded, and generates the element D{tilde over ( )} in which the random number ζ{tilde over ( )}.sub.r is embedded.

4. The re-encryption device according to claim 3, wherein the processing circuitry generates the re-encryption key including the key element k{tilde over ( )}*.sub.r, the cipher element c{tilde over ( )}.sub.r, and the element D{tilde over ( )} indicated in Formula 2, using the master re-encryption key indicated in Formula 1, and generates the re-encrypted ciphertext including the element K and the element E indicated in Formula 3 and including the cipher element c{tilde over ( )}.sub.r $\begin{array}{cc}{k}_r^{*}:={\left(r,{\delta }_r\stackrel{\_}{w},0^n,{\stackrel{\_}{\eta }}_r,0\right)}_{{\mathrm{��}}_1^{*}},c_r:={\left({ϛ}_r,0^n,0^n,0^n,{\phi }_r\right)}_{{\mathrm{��}}_0},D:=G\left(g_T^{{ϛ}_r}\right).Math.r\in {\mathrm{��}}_q\mathrm{where}{\stackrel{\_}{\eta }}_r\stackrel{U}{\leftarrow }{\mathrm{��}}_q^n,r,{ϛ}_r,{\phi }_r,{\delta }_r\stackrel{U}{\leftarrow }{\mathrm{��}}_q,G:\mathrm{encode}\mathrm{function}{\mathrm{��}}_T.fwdarw.{\mathrm{��}}_q,g_T\in {\mathrm{��}}_T,{\mathrm{��}}_0,{\mathrm{��}}_1^{*}:\mathrm{Base}& \left[\mathrm{Formula}1\right]\\ k_r^{~*}:=\tilde{r}{k}_r^{*}+{\left(0,0^n,0^n,{\stackrel{\_}{\eta }}^{\prime },0\right)}_{{\mathrm{��}}_1^{*}},c_r^{~}:=\left({\tilde{c}}_{r\mathrm{.0}},{\tilde{c}}_{r\mathrm{.1}}\right),{\tilde{c}}_{r\mathrm{.0}}:=c_r+{\left(0,{\tilde{\omega }}_{r\mathrm{.0}}{\stackrel{\_}{x}}^{\prime },0^n,0^n,{\tilde{\phi }}_{r\mathrm{.0}}\right)}_{{\mathrm{��}}_0},{\tilde{c}}_{r\mathrm{.1}}:={\left({\widetilde{ϛ}}_r,{\tilde{\omega }}_{r\mathrm{.1}}{\stackrel{\_}{x}}^{\prime },0^n,0^n,{\tilde{\phi }}_{r\mathrm{.1}}\right)}_{{\mathrm{��}}_0},D^{~}=D.Math.G\left(g_T^{{\widetilde{ϛ}}_r}\right).Math.\tilde{r}\mathrm{where}{\stackrel{\_}{\eta }}^{\prime }\stackrel{U}{\leftarrow }{\mathrm{��}}_q^n,r^{\prime },\tilde{r},{\widetilde{ϛ}}_r,{\tilde{\phi }}_{r\mathrm{.0}},{\tilde{\phi }}_{r\mathrm{.1}},{\tilde{\omega }}_{r\mathrm{.0}},{\tilde{\omega }}_{r\mathrm{.1}}\stackrel{U}{\leftarrow }{\mathrm{��}}_q& \left[\mathrm{Formula}2\right]\\ K:={e\left(c_1,{\tilde{k}}_r^{*}\right)}^{r^{\prime }},E:=\tilde{D}.Math.r^{\prime }\mathrm{where}{c}_1=ϛb_{1.0}+{\omega }_{1}c+{\phi }_1{b}_{1.3n+2},c:={\left(0,\omega \stackrel{\_}{y},0^n,0^n,\phi \right)}_{{\mathrm{��}}_1},ϛ,\omega ,{\omega }_1,\phi ,{\phi }_1\stackrel{U}{\leftarrow }{\mathrm{��}}_q,b_{1.0},b_{1.3n+2}:\mathrm{basis}\mathrm{vector}.& \left[\mathrm{Formula}3\right]\end{array}$

5. A re-encryption method comprising: generating a re-encryption key for re-encrypting a target ciphertext generated by an encryption device, using a master re-encryption key that cannot decrypt a ciphertext generated by the encryption device, but can generate a re-encryption key for changing an access range for a ciphertext generated by the encryption device; and re-encrypting the target ciphertext to generate a re-encrypted ciphertext, using the re-encryption key, wherein the master re-encryption key includes a key element k*.sub.r in which a parameter w{right arrow over ( )} is set, the parameter w{right arrow over ( )} corresponding to a parameter y{right arrow over ( )} set in a cipher element c.sub.1 included in the ciphertext generated by the encryption device, wherein the re-encryption key for re-encrypting the target ciphertext includes a key element k{tilde over ( )}*.sub.r in which a random number r{tilde over ( )} is embedded in the key element k*.sub.r, a cipher element c{tilde over ( )}.sub.r in which a parameter x{right arrow over ( )}′ indicating a changed access range is set, and an element D{tilde over ( )} in which the random number r{tilde over ( )} is encrypted, and wherein the re-encrypted ciphertext includes an element K in which the cipher element c.sub.1 is decrypted with the key element k{tilde over ( )}*.sub.r, the cipher element c{tilde over ( )}.sub.r, and an element E in which the element D{tilde over ( )} is set.

6. A non-transitory computer readable medium storing a re-encryption program that causes a computer to function as a re-encryption device to perform: a re-encryption key generation process of generating a re-encryption key for re-encrypting a target ciphertext generated by an encryption device, using a master re-encryption key that cannot decrypt a ciphertext generated by the encryption device, but can generate a re-encryption key for changing an access range for a ciphertext generated by the encryption device; and a re-encryption process of re-encrypting the target ciphertext to generate a re-encrypted ciphertext, using the re-encryption key generated by the re-encryption key generation process, wherein the master re-encryption key includes a key element k*.sub.r in which a parameter w{right arrow over ( )} is set, the parameter w{right arrow over ( )} corresponding to a parameter y{right arrow over ( )} set in a cipher element c.sub.1 included in the ciphertext generated by the encryption device, wherein the re-encryption key for re-encrypting the target ciphertext includes a key element k{tilde over ( )}*.sub.r in which a random number r is embedded in the key element k*.sub.r, a cipher element c{tilde over ( )}.sub.r in which a parameter x{right arrow over ( )}′ indicating a changed access range is set, and an element D{tilde over ( )} in which the random number r is encrypted, and wherein the re-encrypted ciphertext includes an element K in which the cipher element c.sub.1 is decrypted with the key element k{tilde over ( )}*.sub.r, the cipher element c{tilde over ( )}.sub.r, and an element E in which the element D{tilde over ( )} is set.

7. A cryptographic system comprising: an encryption device to generate a ciphertext; a master re-encryption key generation device to generate a master re-encryption key that cannot decrypt a ciphertext generated by the encryption device, but can generate a re-encryption key for changing an access range for a ciphertext generated by the encryption device, the master re-encryption key including a key element k*.sub.r in which a parameter w{right arrow over ( )} is set, the parameter w{right arrow over ( )} corresponding to a parameter y{right arrow over ( )} set in a cipher element c.sub.1 included in the ciphertext generated by the encryption device; a re-encryption device to generate a re-encryption key for re-encrypting a target ciphertext generated by the encryption device, using the master re-encryption key generated by the master re-encryption key generation device, the re-encryption key including a key element k{tilde over ( )}*.sub.r in which a random number r{tilde over ( )} is embedded in the key element k*.sub.r, a cipher element c{tilde over ( )}.sub.r in which a parameter x{right arrow over ( )}′ indicating a changed access range is set, and an element D{tilde over ( )} in which the random number r is encrypted, and re-encrypt the target ciphertext, using the generated re-encryption key, so as to generate a re-encrypted ciphertext including an element K in which the cipher element c.sub.1 is decrypted with the key element k{tilde over ( )}*.sub.r, the cipher element c{tilde over ( )}.sub.r, and an element E in which the element D{tilde over ( )} is set; and a decryption device to decrypt at least one of the ciphertext generated by the encryption device and the re-encrypted ciphertext generated by the re-encryption device.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0012] FIG. 1 is a configuration diagram of a cryptographic system 10 according to a first embodiment;

[0013] FIG. 2 is a configuration diagram of a common parameter generation device 20 according to the first embodiment;

[0014] FIG. 3 is a configuration diagram of a user secret key generation device 30 according to the first embodiment;

[0015] FIG. 4 is a configuration diagram of a master re-encryption key generation device 40 according to the first embodiment;

[0016] FIG. 5 is a configuration diagram of an encryption device 50 according to the first embodiment;

[0017] FIG. 6 is a configuration diagram of a re-encryption device 60 according to the first embodiment;

[0018] FIG. 7 is a configuration diagram of a decryption device 70 according to the first embodiment;

[0019] FIG. 8 is a flowchart illustrating operation of the common parameter generation device 20 according to the first embodiment;

[0020] FIG. 9 is a flowchart illustrating operation of the user secret key generation device 30 according to the first embodiment;

[0021] FIG. 10 is a flowchart illustrating operation of the master re-encryption key generation device 40 according to the first embodiment;

[0022] FIG. 11 is a flowchart illustrating operation of the encryption device 50 according to the first embodiment;

[0023] FIG. 12 is a flowchart illustrating operation of the re-encryption device 60 according to the first embodiment; and

[0024] FIG. 13 is a flowchart illustrating operation of the decryption device 70 according to the first embodiment.

DESCRIPTION OF EMBODIMENTS

First Embodiment

[0025] ***Description of Configurations***

[0026] Referring to FIG. 1, a configuration of a cryptographic system 10 according to a first embodiment will be described.

[0027] The cryptographic system 10 includes a common parameter generation device 20, user secret key generation devices 30, a master re-encryption key generation device 40, encryption devices 50, a re-encryption device 60, and a decryption device 70.

[0028] The common parameter generation device 20, the user secret key generation devices 30, the master re-encryption key generation device 40, and the encryption devices 50, the re-encryption device 60, and the decryption device 70 are connected via a transmission channel 80 such as the Internet or a local area network (LAN).

[0029] Referring to FIG. 2, a configuration of the common parameter generation device 20 according to the first embodiment will be described.

[0030] The common parameter generation device 20 is a computer such as a server.

[0031] The common parameter generation device 20 includes hardware of a processor 21, a memory 22, a storage 23, and a communication interface 24. The processor 21 is connected with the other hardware components via signal lines and controls these other hardware components.

[0032] The common parameter generation device 20 includes, as functional components, an acquisition unit 211, a common parameter generation unit 212, a basis generation unit 213, a master key generation unit 214, and a transmission unit 215. The functions of the functional components of the common parameter generation device 20 are realized by software.

[0033] The storage 23 stores programs that realize the functions of the functional components of the common parameter generation device 20. These programs are loaded into the memory 22 by the processor 21 and executed by the processor 21. This realizes the functions of the functional components of the common parameter generation device 20.

[0034] Referring to FIG. 3, a configuration of the user secret key generation device 30 according to the first embodiment will be described.

[0035] The user secret key generation device 30 is a computer such as a personal computer (PC).

[0036] The user secret key generation device 30 includes hardware of a processor 31, a memory 32, a storage 33, and a communication interface 34. The processor 31 is connected with the other hardware components via signal lines and controls these other hardware components.

[0037] The user secret key generation device 30 includes, as functional components, an acquisition unit 311, a user secret key generation unit 312, and a transmission unit 313. The functions of the functional components of the user secret key generation device 30 are realized by software.

[0038] The storage 33 stores programs that realize the functions of the functional components of the user secret key generation device 30. These programs are loaded into the memory 32 by the processor 31 and executed by the processor 31. This realizes the functions of the functional components of the user secret key generation device 30.

[0039] Referring to FIG. 4, a configuration of the master re-encryption key generation device 40 according to the first embodiment will be described.

[0040] The master re-encryption key generation device 40 is a computer such as a server.

[0041] The master re-encryption key generation device 40 includes hardware of a processor 41, a memory 42, a storage 43, and a communication interface 44. The processor 41 is connected with the other hardware components via signal lines and controls these other hardware components.

[0042] The master re-encryption key generation device 40 includes, as functional components, an acquisition unit 411, a master re-encryption key generation unit 412, and a transmission unit 413. The functions of the functional components of the master re-encryption key generation device 40 are realized by software.

[0043] The storage 43 stores programs that realize the functions of the functional components of the master re-encryption key generation device 40. These programs are loaded into the memory 42 by the processor 41 and executed by the processor 41. This realizes the functions of the functional components of the master re-encryption key generation device 40.

[0044] Referring to FIG. 5, a configuration of the encryption device 50 according to the first embodiment will be described.

[0045] The encryption device 50 is a computer such as a PC.

[0046] The encryption device 50 includes hardware of a processor 51, a memory 52, a storage 53, and a communication interface 54. The processor 51 is connected with the other hardware components via signal lines and controls these other hardware components.

[0047] The encryption device 50 includes, as functional components, an acquisition unit 511, an encryption unit 512, and a transmission unit 513. The functions of the functional components of the encryption device 50 are realized by software.

[0048] The storage 53 stores programs that realize the functions of the functional components of the encryption device 50. These programs are loaded into the memory 52 by the processor 51 and executed by the processor 51. This realizes the functions of the functional components of the encryption device 50.

[0049] Referring to FIG. 6, a configuration of the re-encryption device 60 according to the first embodiment will be described.

[0050] The re-encryption device 60 is a computer such as a server.

[0051] The re-encryption device 60 includes hardware of a processor 61, a memory 62, a storage 63, and a communication interface 64. The processor 61 is connected with the other hardware components via signal lines and controls these other hardware components.

[0052] The re-encryption device 60 includes, as functional components, an acquisition unit 611, a re-encryption key generation unit 612, a re-encryption unit 613, and a transmission unit 614. The functions of the functional components of the re-encryption device 60 are realized by software.

[0053] The storage 63 stores programs that realize the functions of the functional components of the re-encryption device 60. These programs are loaded into the memory 62 by the processor 61 and executed by the processor 61. This realizes the functions of the functional components of the re-encryption device 60.

[0054] Referring to FIG. 7, a configuration of the decryption device 70 according to the first embodiment will be described.

[0055] The decryption device 70 is a computer such as a server.

[0056] The decryption device 70 includes hardware such as a processor 71, a memory 72, a storage 73, and a communication interface 74. The processor 71 is connected with the other hardware components via signal lines and controls these other hardware components.

[0057] The decryption device 70 includes, as functional components, an acquisition unit 711, a determination unit 712, and a decryption unit 713. The functions of the functional components of the decryption device 70 are realized by software.

[0058] The storage 73 stores programs that realize the functions of the functional components of the decryption device 70. These programs are loaded into the memory 72 by the processor 71 and executed by the processor 71. This realizes the functions of the functional components of the decryption device 70.

[0059] Each of the processors 21, 31, 41, 51, 61, and 71 is an integrated circuit (IC) that performs operational processing. Specific examples of each of the processors 21, 31, 41, 51, 61, and 71 are a central processing unit (CPU), a digital signal processor (DSP), and a graphics processing unit (GPU).

[0060] Each of the memories 22, 32, 42, 52, 62, and 72 is a storage device to temporarily store data. Specific examples of each of the memories 22, 32, 42, 52, 62, and 72 are a static random access memory (SRAM) and a dynamic random access memory (DRAM).

[0061] Each of the storages 23, 33, 43, 53, 63, and 73 is a storage device to store data. A specific example of each of the storages 23, 33, 43, 53, 63, and 73 is a hard disk drive (HDD). Alternatively, each of the storages 23, 33, 43, 53, 63, and 73 may be a portable storage medium such as a Secure Digital (SD, registered trademark) memory card, CompactFlash (CF, registered trademark), a NAND flash, a flexible disk, an optical disc, a compact disc, a Blu-ray (registered trademark) disc, or a digital versatile disc (DVD).

[0062] Each of the communication interfaces 24, 34, 44, 54, 64, and 74 is an interface for communicating with external devices. Specific examples of each of the communication interfaces 24, 34, 44, 54, 64, and 74 is an Ethernet (registered trademark) port, a Universal Serial Bus (USB) port, and a High-Definition Multimedia Interface (HDMI) port.

[0063] FIG. 2 illustrates only one processor 21. However, the common parameter generation device 20 may include a plurality of processors as an alternative to the processor 21. Similarly, the user secret key generation device 30 may include a plurality of processors as an alternative to the processor 31. The master re-encryption key generation device 40 may include a plurality of processors as an alternative to the processor 41. The encryption device 50 may include a plurality of processors as an alternative to the processor 51. The re-encryption device 60 may include a plurality of processors as an alternative to the processor 61. The decryption device 70 may include a plurality of processors as an alternative to the processor 71.

[0064] The plurality of processors share execution of the programs that realize the functions of the respective functional components. Each of the processors is, like the processors 21, 31, 41, 51, 61, and 71, an IC that performs operational processing.

[0065] ***Description of Operation***

Referring to FIGS. 8 to 13, operation of the cryptographic system 10 according to the first embodiment will be described.

[0066] **Notations**

[0067] Notations to be used in the description of the operation of the cryptographic system 10 will be described.

[0068] When A is a random variable or distribution, Formula 101 denotes that y is randomly selected from A according to the distribution of A. That is, y is a random number in Formula 101.

[00001]$\begin{array}{cc}y\stackrel{R}{\leftarrow }A& \left[\mathrm{Formula}101\right]\end{array}$

[0069] When A is a set, Formula 102 denotes that y is uniformly selected from A. That is, y is a uniform random number in Formula 102.

[00002]$\begin{array}{cc}y\stackrel{U}{\leftarrow }A& \left[\mathrm{Formula}102\right]\end{array}$

[0070] Formula 103 denotes that y is a set defined by z, or y is a set substituted by z.

y:=z  [Formula 103]

[0071] When a is a constant, Formula 104 denotes that a machine (algorithm) A outputs a on input x.

A(x).fwdarw.a  [Formula 104]

for example,

A(x).fwdarw.1

[0072] Formula 105, that is F.sub.q, denotes a finite field of order q.

.sub.q[Formula 105]

[0073] A vector representation denotes a vector representation in the finite field F.sub.q. That is, it is as indicated in Formula 106. Note that n written as a superscript in the finite field F.sub.q indicates the number of elements in the vector.

{right arrow over (x)} denotes

(x.sub.1, . . . ,x.sub.n)∈.sub.q.sup.n.  [Formula 106]

[0074] Formula 107 denotes the inner-product, indicated in Formula 109, of two vectors x{right arrow over ( )} and v{right arrow over ( )} indicated in Formula 108.

{right arrow over (x)}.Math.{right arrow over (v)}  [Formula 107]

{right arrow over (x)}=(x.sub.1, . . . ,x.sub.n),

{right arrow over (v)}=(v.sub.1, . . . ,v.sub.n),  [Formula 108]

Σ.sub.i=1.sup.nx.sub.iv.sub.i  [Formula 109]

[0075] Note that X.sup.T denotes the transpose of a matrix X.

[0076] For a basis B and a basis B* indicated in Formula 110, Formula 111 is established.

:=(b.sub.1, . . . ,b.sub.N),

:=(b.sub.1, . . . ,b.sub.N),  [Formula 110]

(x.sub.1, . . . ,x.sub.N:=Σ.sub.i=1.sup.Nx.sub.ib.sub.i,

(y.sub.1, . . . ,y.sub.N:=Σ.sub.i=1.sup.Ny.sub.ib.sub.i,  [Formula 111]

[0077] **Dual Pairing Vector Spaces**

[0078] The cryptographic system 10 realizes a proxy re-encryption scheme using dual pairing vector spaces.

[0079] First, symmetric bilinear pairing groups will be described.

[0080] Symmetric bilinear pairing groups (q, G, G.sub.T, g, e) are a tuple of a prime q, a cyclic additive group G of order q, a cyclic multiplicative group G.sub.T of order q, g≠0∈G, and a polynomial-time computable nondegenerate bilinear pairing e:G×G.fwdarw.G.sub.T. The nondegenerate bilinear pairing signifies e(sg, tg)=e(f, g).sup.st, and e(g,g)≠1.

[0081] In the following description, let G.sub.bpg be an algorithm that takes as input 1.sup.λ, and outputs values of a parameter param.sub.G:=(q, G, G.sub.T, g, e) of bilinear pairing groups with a security parameter λ.

[0082] Next, dual pairing vector spaces will be described.

[0083] Dual pairing vector spaces (q, V, G.sub.T, A, e) can be constructed by a direct product of the symmetric bilinear pairing groups (param.sub.G:=(q, G, G.sub.T, g, e)). The dual pairing vector spaces (q, V, G.sub.T, A, e) are a tuple of a prime q, an N-dimensional vector space V over F.sub.q indicated in Formula 112, a cyclic group G.sub.T of order q, and a canonical basis A:=(a.sub.1, . . . a.sub.N) of the space V, and have the following operations (1) and (2). Note that a, is as indicated in Formula 113.

[00003]$\begin{array}{cc}\mathrm{��}:=\stackrel{\stackrel{N}{︷}}{\mathrm{��}\times \mathrm{.Math.}\times \mathrm{��}}& \left[\mathrm{Formula}112\right]\\ a_i:=\left(\stackrel{\stackrel{i-1}{︷}}{0,\mathrm{.Math.},0},g,\stackrel{\stackrel{N-i}{︷}}{0,\mathrm{.Math.},0}\right)& \left[\mathrm{Formula}113\right]\end{array}$

[0084] Operation (1): Nondegenerate Bilinear Pairing

[0085] A pairing on the space V is defined by Formula 114.

e(x,y):=Π.sub.i=1.sup.Ne(G.sub.i,H.sub.i)∈.sub.T[Formula 114]

[0086] where

[0087] (G.sub.1, . . . , G.sub.N):=x∈,

[0088] (H.sub.1, . . . , H.sub.N):=y∈,

[0089] This is nondegenerate bilinear, that is, e(sx, ty)=e(x, y).sup.st and if e(x, y)=1 for all y∈V, then x=0. For all i and j, e(a.sub.i, a.sub.j)=e(g, g).sup.ôi,j, where δ.sub.i,j=1 if i=j, and δ.sub.i,j=0 if i≠j, and e(g, g)≠1∈G.sub.T.

[0090] Operation (2): Distortion Maps

[0091] Linear transformations φ.sub.i,j on the space V indicated in Formula 115 can achieve Formula 116.

[00004]$\begin{array}{cc}\mathrm{if}{\varphi }_{i,j}\left(a_j\right)=a_i\mathrm{and}k\ne j,\mathrm{then}{\varphi }_{i,j}\left(a_k\right)=0.& \left[\mathrm{Formula}115\right]\\ {\varphi }_{i,j}\left(x\right):=\left(\stackrel{\stackrel{i-1}{︷}}{0,\mathrm{.Math.},0},g_j,\stackrel{\stackrel{N-i}{︷}}{0,\mathrm{.Math.},0}\right)\mathrm{where}\left(g_1,{\mathrm{.Math.g}}_N\right):=x.& \left[\mathrm{Formula}116\right]\end{array}$

[0092] The linear transformations φi,j will be called distortion maps.

[0093] In the following description, let G.sub.dpvs be an algorithm that takes as input 1.sup.λ (λ∈natural numbers), N∈natural numbers, and the values of the parameter param.sub.G:=(q, G, G.sub.T, g, e) of bilinear pairing groups, and outputs values of a parameter param.sub.V:=(q, V, G.sub.T, A, e) of dual pairing vector spaces of the N-dimensional vector space V with the security parameter λ.

[0094] A case in which dual pairing vector spaces are constructed with the symmetric bilinear pairing groups described above will be described here. Dual pairing vector spaces can also be constructed with asymmetric bilinear pairing groups. The following description can be readily applied to a case in which dual pairing vector spaces are constructed with asymmetric bilinear pairing groups.

[0095] **Operation of Common Parameter Generation Device 20**

[0096] Referring to FIG. 8, operation of the common parameter generation device 20 according to the first embodiment will be described.

[0097] A procedure for the operation of the common parameter generation device 20 according to the first embodiment is equivalent to a common parameter generation method according to the first embodiment. A program that realizes the operation of the common parameter generation device 20 according to the first embodiment is equivalent to a common parameter generation program according to the first embodiment.

[0098] The common parameter generation device 20 generates a public key pk and a master secret key msk to be used in the cryptographic system 10. The common parameter generation device 20 transmits the public key pk to the user secret key generation device 30, the master re-encryption key generation device 40, and each of the encryption devices 50 via the transmission channel 80. The common parameter generation device 20 transmits the master secret key msk in secrecy to the user secret key generation device 30 and the master re-encryption key generation device 40 via the transmission channel 80. To transmit in secrecy means to transmit after encryption by an existing encryption scheme, for example, so as to be concealed from third parties. The public key pk and the master secret key msk may be transmitted by a method such as postal mail, instead of being transmitted via the transmission channel 80.

[0099] (Step S11: Acquisition Process)

[0100] The acquisition unit 211 acquires a security parameter λ indicating a key length.

[0101] Specifically, the acquisition unit 211 accepts the security parameter λ that is input by an administrator of the cryptographic system 10. The acquisition unit 211 writes the security parameter λ in the memory 22.

[0102] (Step S12: Common Parameter Generation Process)

[0103] The common parameter generation unit 212 generates a parameter param.sub.V:=(q, V, G.sub.T, A, e) of dual pairing vector spaces by the algorithm G.sub.dpvs described above, taking as input the security parameter λ acquired in step S11. Specifically, the common parameter generation unit 212 generates the parameter param.sub.V, as indicated in Formula 117.

[00005]$\begin{array}{cc}{\mathrm{param}}_{\mathrm{��}}:=\left(q,\mathrm{��},{\mathrm{��}}_T,\mathrm{��},e\right)\stackrel{R}{\leftarrow }{G}_{\mathrm{dpvs}}\left(1^{\lambda },3n+2\right)& \left[\mathrm{Formula}117\right]\end{array}$

[0104] The common parameter generation unit 212 generates an element g.sub.T, as indicated in Formula 118.

[00006]$\begin{array}{cc}\psi \stackrel{.Math.}{\leftarrow }{\mathrm{��}}_q^{\times },g_T:={e\left(g,g\right)}^{\psi }& \left[\mathrm{Formula}118\right]\end{array}$

[0105] Then, the common parameter generation unit 212 generates a common parameter param in which the parameter param.sub.V and the element g.sub.T are set. The common parameter generation unit 212 writes the common parameter param in the memory 22.

[0106] (Step S13: Basis Generation Process)

[0107] The basis generation unit 213 generates a basis B{circumflex over ( )}.sub.u and a basis B{circumflex over ( )}*.sub.u for each integer u of u=0, 1, using the parameter param.sub.V generated in step S12. Specifically, the basis generation unit 213 generates the basis B{circumflex over ( )}.sub.u and the basis B{circumflex over ( )}*.sub.u for each integer u of u=0, 1, as indicated in Formula 119.

[00007]$\begin{array}{cc}{X}_u:=\left({\chi }_{u,i,j}\right)\stackrel{U}{\leftarrow }\mathrm{GL}\left(3n+2,{\mathrm{��}}_q\right)\left(v_{u,i,j}\right):=\psi .Math.{\left(X_u^T\right)}^{-1},b_{u,i}:={.Math.}_{j=1}^{3n+2}{\chi }_{u,i,j}{a}_j,{\mathrm{��}}_u:=\left(b_{u\mathrm{.0}},\mathrm{.Math.},b_{u\mathrm{.3}n+1}\right),b_{u,i}^{*}{.Math.}_{j=1}^{3n+2}{v}_{u,i,j}{a}_j,{\mathrm{��}}_u^{*}:=\left(b_{u\mathrm{.0}}^{*},\mathrm{.Math.},b_{u\mathrm{.3}n+1}^{*}\right),{\widehat{\mathrm{��}}}_u:=\left(b_{u\mathrm{.0}},\mathrm{.Math.},b_{u.u+2},b_{u\mathrm{.3}n+1}\right),{\widehat{\mathrm{��}}}_u^{*}:=\left(b_{u\mathrm{.0}}^{*},\mathrm{.Math.},b_{u.u+2}^{*},b_{u\mathrm{.3}n+1}^{*}\right)& \left[\mathrm{Formula}119\right]\end{array}$

[0108] The basis generation unit 213 generates an element c in which a parameter y{right arrow over ( )}:=(y.sub.1, . . . y.sub.n) is set, using the basis B{circumflex over ( )}.sub.u, as indicated in Formula 120.

[00008]$\begin{array}{cc}\stackrel{\_}{y}:=\left(y_1,\mathrm{.Math.},y_n\right)\stackrel{U}{\leftarrow }{\mathrm{��}}_q^n,\omega ,\phi \stackrel{U}{\leftarrow }{\mathrm{��}}_q,c:={\left(0,\omega \stackrel{\_}{y},0^n,0^n,\phi \right)}_{{\mathrm{��}}_i}& \left[\mathrm{Formula}120\right]\end{array}$

[0109] The basis generation unit 213 generates a parameter w{right arrow over ( )}:=(w.sub.1, . . . w.sub.n), as indicated in Formula 121.

[00009]$\begin{array}{cc}\stackrel{\_}{w}:=\left(w_1,\mathrm{.Math.},w_n\right)\stackrel{U}{\leftarrow }{\mathrm{��}}_q^n,\mathrm{such}\mathrm{that}\stackrel{\_}{y}.Math.\stackrel{\_}{w}=0& \left[\mathrm{Formula}121\right]\end{array}$

[0110] The basis generation unit 213 generates an encode function G indicated in Formula 122.

[00010]$\begin{array}{cc}G:{\mathrm{��}}_T.fwdarw.{\mathrm{��}}_q& \left[\mathrm{Formula}122\right]\end{array}$

[0111] The basis generation unit 213 writes the basis B{circumflex over ( )}.sub.u, the basis B{circumflex over ( )}*.sub.u, the element c, the parameter w{right arrow over ( )}, and the encode function G in the memory 22.

[0112] (Step S14: Public Key Generation Process)

[0113] The master key generation unit 214 generates a public key pk in which the security parameter λ, the common parameter param, the basis B{circumflex over ( )}.sub.0, the basis B{circumflex over ( )}*.sub.0, a basis vector b.sub.1.0, a basis vector b.sub.1.3n+2, the element c, and the encode function G are set. That is, pk:=(λ, param, B{circumflex over ( )}.sub.0, B{circumflex over ( )}*.sub.0, b.sub.1.0, b.sub.1.3n+2, c, G).

[0114] (Step S15: Master Secret Key Generation Process)

[0115] The master key generation unit 214 generates a master secret key msk in which a basis vector b*.sub.0.0, a basis vector b*.sub.0.1, the basis B{circumflex over ( )}*.sub.1, and the parameter w{right arrow over ( )} are set. That is, msk:=(b*.sub.0.0, b*.sub.0.1, B{circumflex over ( )}*.sub.1, w{right arrow over ( )}).

[0116] (Step S16: Transmission Process)

[0117] The transmission unit 215 transmits the public key pk to the user secret key generation device 30, the master re-encryption key generation device 40, and each of the encryption devices 50 via the transmission channel 80. The transmission unit 215 transmits the master secret key msk in secrecy to the user secret key generation device 30 and the master re-encryption key generation device 40 via the transmission channel 80.

[0118] **Operation of User Secret Key Generation Device 30**

[0119] Referring to FIG. 9, operation of the user secret key generation device 30 according to the first embodiment will be described.

[0120] A procedure for the operation of the user secret key generation device 30 according to the first embodiment is equivalent to a user secret key generation method according to the first embodiment. A program that realizes the operation of the user secret key generation device 30 according to the first embodiment is equivalent to a user secret key generation program according to the first embodiment.

[0121] The user secret key generation device 30 generates a user secret key dk.sub.v, based on the public key pk and the master secret key msk. The user secret key generation device 30 transmits the user secret key dk.sub.v in secrecy to the re-encryption device 60 and the decryption device 70 via the transmission channel 80.

[0122] The user secret key dk.sub.v may be transmitted by a method such as postal mail, instead of being transmitted via the transmission channel 80.

[0123] (Step S21: Acquisition Process)

[0124] The acquisition unit 311 acquires the public key pk and the master secret key msk that are transmitted by the common parameter generation device 20. The acquisition unit 311 writes the public key pk and the master secret key msk in the memory 32.

[0125] The acquisition unit 311 acquires a parameter v{right arrow over ( )}:=(v.sub.1, . . . , v.sub.n). Specifically, the acquisition unit 311 accepts the parameter v{right arrow over ( )} that is input by an administrator of the user secret key generation device 30. The acquisition unit 311 writes the parameter v{right arrow over ( )} in the memory 32. The parameter v{right arrow over ( )} indicates attributes or the like of a user who uses the user secret key dk.sub.v.

[0126] (Step S22: User Secret Key Generation Process)

[0127] The user secret key generation unit 312 generates random numbers, as indicated in Formula 123.

[00011]$\begin{array}{cc}\overline{\eta }\stackrel{U}{\leftarrow }{\mathrm{��}}_q^n,\delta \stackrel{U}{\leftarrow }{\mathrm{��}}_q& \left[\mathrm{Formula}123\right]\end{array}$

[0128] The user secret key generation unit 312 generates a key element k*, as indicated in Formula 124.

k*:=(1,δ{right arrow over (v)},0.sup.n,{right arrow over (η)},  [Formula 124]

[0129] The user secret key generation unit 312 writes the key element k* in the memory 32.

[0130] (Step S23: Transmission Process)

[0131] The transmission unit 313 transmits the user secret key dk.sub.v in which the parameter v{right arrow over ( )} and the key element k* are set to the decryption device 70 in secrecy via the transmission channel 80.

[0132] **Operation of Master Re-encryption Key Generation Device 40**

[0133] Referring to FIG. 10, operation of the master re-encryption key generation device 40 according to the first embodiment will be described.

[0134] A procedure for the operation of the master re-encryption key generation device 40 according to the first embodiment is equivalent to a master re-encryption key generation method according to the first embodiment. A program that realizes the operation of the master re-encryption key generation device 40 according to the first embodiment is equivalent to a master re-encryption key generation program according to the first embodiment.

[0135] The master re-encryption key generation device 40 generates a master re-encryption key mrk, based on the public key pk and the master secret key msk. The master re-encryption key generation device 40 transmits the master re-encryption key mrk to the re-encryption device 60 in secrecy via the transmission channel 80.

[0136] The master re-encryption key mrk may be transmitted by a method such as postal mail, instead of being transmitted via the transmission channel 80.

[0137] (Step S31: Acquisition Process)

[0138] The acquisition unit 411 acquires the public key pk and the master secret key msk that are transmitted by the common parameter generation device 20. The acquisition unit 311 writes the public key pk and the master secret key msk in the memory 32.

[0139] (Step S32: Master Re-Encryption Key Generation Process)

[0140] The master re-encryption key generation unit 412 generates random numbers, as indicated in Formula 125.

[00012]$\begin{array}{cc}{\overline{\eta }}_r\stackrel{U}{\leftarrow }{\mathrm{��}}_q^n,r,{ϛ}_r,{\phi }_r,{\delta }_r\stackrel{U}{\leftarrow }{\mathrm{��}}_q& \left[\mathrm{Formula}125\right]\end{array}$

[0141] The master re-encryption key generation unit 412 generates a key element k*.sub.r, a cipher element c.sub.r, and an element D, as indicated in Formula 126. The parameter w{right arrow over ( )} is set in the key element k*.sub.r, as indicated in Formula 126. The parameter w{right arrow over ( )} corresponds to a parameter y{right arrow over ( )} set in a cipher element c.sub.1 included in a ciphertext generated by the encryption device 50 to be described later.

k*.sub.r:=(r,δ.sub.r{right arrow over (w)},0.sup.n,{right arrow over (n)}.sub.r,,

c.sub.r:=(.sub.r,0.sup.n,0.sup.n,0.sup.n,φ.sub.r,

D:=G(g.sub.T.sup.r).Math.r∈.sub.q  [Formula 126]

[0142] The master re-encryption key generation unit 412 writes the key element k*.sub.r, the cipher element c.sub.r, and the element D in the memory 42.

[0143] (Step S33: Transmission Process)

[0144] The transmission unit 413 transmits the master re-encryption key mrk in which the key element k*.sub.r, the cipher element c.sub.r, the element D, and the basis B{circumflex over ( )}*.sub.1 are set to the re-encryption device 60 in secrecy via the transmission channel 80.

[0145] **Operation of Encryption Device 50**

[0146] Referring to FIG. 11, operation of the encryption device 50 according to the first embodiment will be described.

[0147] A procedure for the operation of the encryption device 50 according to the first embodiment is equivalent to an encryption method according to the first embodiment. A program that realizes the operation of the encryption device 50 according to the first embodiment is equivalent to an encryption program according to the first embodiment.

[0148] The encryption device 50 generates a ciphertext oct.sub.x in which an access range x is set and a message m is encrypted, based on the public key pk. The encryption device 50 transmits the ciphertext oct.sub.x to the re-encryption device 60 and the decryption device 70 via the transmission channel 80.

[0149] The ciphertext oct.sub.x may be transmitted by a method such as postal mail, instead of being transmitted via the transmission channel 80. The ciphertext oct.sub.x may be transmitted to only one of the re-encryption device 60 and the decryption device 70 as necessary.

[0150] (Step S41: Acquisition Process)

[0151] The acquisition unit 511 acquires the public key pk transmitted by the common parameter generation device 20. The acquisition unit 511 writes the public key pk in the memory 52.

[0152] The acquisition unit 511 acquires a parameter x{right arrow over ( )}:=(x.sub.1, . . . , x.sub.n) and the message m. Specifically, the acquisition unit 511 acquires the parameter x{right arrow over ( )} and the message m that are input by an administrator of the encryption device 50. The acquisition unit 511 writes the parameter x{right arrow over ( )} and the message m in the memory 52. The parameter x{right arrow over ( )} represents attributes or the like indicating the access range for the ciphertext oct.sub.x.

[0153] (Step S42: Encryption Process)

[0154] The encryption unit 512 generates random numbers, as indicated in Formula 127.

[00013]$\begin{array}{cc}ϛ,{\omega }_0,{\omega }_1,{\phi }_0,{\phi }_1\stackrel{U}{\leftarrow }{\mathrm{��}}_q& \left[\mathrm{Formula}127\right]\end{array}$

[0155] The encryption unit 512 generates a cipher element c.sub.0, a cipher element c.sub.1, and a cipher element C, as indicated in Formula 128.

c.sub.0:=(,ω.sub.0{right arrow over (x)},0.sup.n,0.sup.n,φ.sub.0).sub.,

c.sub.1:=b.sub.1.0+ω.sub.1c+φ.sub.1b.sub.1.3n+2,

C:=m.Math.g.sub.T^{[Formula 128]}

[0156] (Step S43: Transmission Process)

[0157] The transmission unit 513 transmits the ciphertext oct.sub.x in which the parameter x{right arrow over ( )}, the cipher element c.sub.0, the cipher element c.sub.1, and the cipher element C are set to the re-encryption device 60 and the decryption device 70.

[0158] **Operation of Re-encryption Device 60**

[0159] Referring to FIG. 12, operation of the re-encryption device 60 according to the first embodiment will be described.

[0160] A procedure for the operation of the re-encryption device 60 according to the first embodiment is equivalent to a re-encryption method according to the first embodiment. A program that realizes the operation of the re-encryption device 60 according to the first embodiment is equivalent to a re-encryption program according to the first embodiment.

[0161] The re-encryption device 60 generates a re-encrypted ciphertext rct.sub.x′, based on the public key pk and the master re-encryption key mrk. The re-encryption device 60 transmits the re-encrypted ciphertext rct.sub.x′ to the decryption device 70 via the transmission channel 80.

[0162] The re-encrypted ciphertext rct.sub.x′ may be transmitted by a method such as postal mail, instead of being transmitted via the transmission channel 80.

[0163] (Step S51: Acquisition Process)

[0164] The acquisition unit 611 acquires the public key pk transmitted by the common parameter generation device 20 and the master re-encryption key mrk transmitted by the master re-encryption key generation device 40. The acquisition unit 611 writes the public key pk and the master re-encryption key mrk in the memory 62.

[0165] The acquisition unit 611 acquires the ciphertext oct.sub.x, which is a target ciphertext to be re-encrypted, transmitted by the encryption device 50. The acquisition unit 611 writes the target ciphertext oct.sub.x in the memory 62.

[0166] The acquisition unit 611 acquires a parameter x{right arrow over ( )}′:=(x′.sub.1, . . . , x′.sub.n). Specifically, the acquisition unit 611 accepts the parameter x{right arrow over ( )}′ that is input by an administrator of the re-encryption device 60. The acquisition unit 611 writes the parameter x{right arrow over ( )}′ in the memory 62. The parameter x{right arrow over ( )}′ represents attributes or the like indicating the access range for the re-encrypted ciphertext rct.sub.x′. That is, the parameter x{right arrow over ( )}′ indicates the changed access range.

[0167] (Step S52: Re-Encryption Key Generation Process)

[0168] The re-encryption key generation unit 612 generates random numbers, as indicated in Formula 129.

[00014]$\begin{array}{cc}\stackrel{\_}{\eta }\stackrel{U}{\leftarrow }{\mathrm{��}}_q^n,r^{\prime },\tilde{r},{\widetilde{ϛ}}_r,{\tilde{\phi }}_{r\mathrm{.0}},{\tilde{\phi }}_{r\mathrm{.1}},{\tilde{\omega }}_{r\mathrm{.0}},{\tilde{\omega }}_{r\mathrm{.1}}\stackrel{U}{\leftarrow }{\mathrm{��}}_q& \left[\mathrm{Formula}129\right]\end{array}$

[0169] The re-encryption key generation unit 612 generates a key element k{tilde over ( )}*.sub.r, cipher elements c{tilde over ( )}.sub.r (c{tilde over ( )}.sub.r.0 and c{tilde over ( )}.sub.r.1), and an element D{tilde over ( )}, as indicated in Formula 130.

{tilde over (k)}*.sub.r:={tilde over (r)}k*.sub.r+(0,0.sup.n,0.sup.n,{right arrow over (η)}′,

{tilde over (c)}.sub.r.0:=c.sub.r+(0,ω.sub.r.0{right arrow over (x)}′,0.sup.n,0.sup.n,{tilde over (φ)}.sub.r.,

{tilde over (c)}.sub.r.1:=(.sub.r,{tilde over (ω)}.sub.r.1{right arrow over (x)}′,0.sup.n,0.sup.n,φ.sub.r.1,

{tilde over (D)}:=D.Math..Math.{tilde over (r)}  [Formula 130]

[0170] In the key element k{tilde over ( )}*.sub.r, a random number r{tilde over ( )} is embedded in the key element k*.sub.r, as indicated in Formula 130. In the cipher elements c{tilde over ( )}.sub.r, the parameter x{right arrow over ( )}′ indicating the changed access range is set and a random number ζ{tilde over ( )}.sub.r is embedded. In the element D{tilde over ( )}, the random number ζ{tilde over ( )}.sub.r is embedded to encrypt the random number r{tilde over ( )}.

[0171] The re-encryption key generation unit 612 writes the key element k{tilde over ( )}*.sub.r, the cipher elements c{tilde over ( )}.sub.r (c{tilde over ( )}.sub.r.0 and c{tilde over ( )}.sub.r.1), and the element D in the memory 62.

[0172] (Step S53: Re-Encryption Process)

[0173] The re-encryption unit 613 generates an element K and an element E, as indicated in Formula 131.

K:=e(c.sub.1,{tilde over (k)}*.sub.r)r′, E:={tilde over (D)}.Math.r′

[0174] As indicated in Formula 131, the element K is generated by computing a pairing operation between the cipher element c.sub.1 and a decryption key k{tilde over ( )}.sub.r so as to decrypt the cipher element c.sub.1 with the decryption key k{tilde over ( )}*.sub.r. In the element K, a random number r′ is embedded. In the element E, the random number r′ is embedded in the element D.

[0175] (Step S54: Transmission Process)

[0176] The transmission unit 614 transmits the re-encrypted ciphertext rct.sub.x′ in which the parameter x{right arrow over ( )}′, the cipher elements c{tilde over ( )}.sub.r (c{tilde over ( )}.sub.r.0 and c{tilde over ( )}.sub.r.1), the element E, the element K, and the cipher element C are set to the decryption device 70 via the transmission channel 80.

[0177] **Operation of Decryption Device 70**

[0178] Referring to FIG. 13, operation of the decryption device 70 according to the first embodiment will be described.

[0179] A procedure for the operation of the decryption device 70 according to the first embodiment is equivalent to a decryption method according to the first embodiment. A program that realizes the operation of the decryption device 70 according to the first embodiment is equivalent to a decryption program according to the first embodiment.

[0180] The decryption device 70 decrypts the ciphertext oct.sub.x generated by the encryption device 50 and the re-encrypted ciphertext rct.sub.x′ generated by the re-encryption device 60.

[0181] (Step S61: Acquisition Process)

[0182] The acquisition unit 711 acquires the user secret key dk.sub.v transmitted by the user secret key generation device 30. The acquisition unit 711 writes the user secret key dk.sub.v in the memory 72.

[0183] The acquisition unit 711 acquires a ciphertext ct, which is one of the ciphertext oct.sub.x transmitted by the encryption device 50 and the re-encrypted ciphertext rct.sub.x′ transmitted by the re-encryption device 60. The acquisition unit 711 writes the ciphertext ct in the memory 72.

[0184] (Step S62: Determination Process)

[0185] The determination unit 712 determines whether the ciphertext ct acquired in step S61 is the ciphertext oct.sub.x or the re-encrypted ciphertext rct.sub.x′. Specifically, the determination unit 712 determines whether the ciphertext ct is the ciphertext oct.sub.x or the re-encrypted ciphertext rct.sub.x′, based on the number of elements of the ciphertext ct.

[0186] If the ciphertext ct is the ciphertext oct.sub.x, the determination unit 712 advances the process to step S63. If the ciphertext ct is the re-encrypted ciphertext rct.sub.x′, the determination unit 712 advances the process to step S64.

[0187] (Step S63: First Decryption Process)

[0188] The decryption unit 713 decrypts the ciphertext ct (=ciphertext oct.sub.x) to generate a message m′, as indicated in Formula 132.

m′:=C/e(c.sub.0,k*)  [Formula 132]

[0189] Note that if the parameter x{right arrow over ( )} set in the ciphertext ct and the parameter v{right arrow over ( )} set in the user secret key dk.sub.v correspond to each other, the ciphertext ct is decrypted correctly, and the message m′ matches the message m. That the parameter x{right arrow over ( )} and the parameter v{right arrow over ( )} correspond to each other means that x{right arrow over ( )}.Math.v{right arrow over ( )}=0 holds.

[0190] (Step S64: Second Decryption Process) The decryption unit 713 decrypts the ciphertext ct (=re-encrypted ciphertext rct.sub.x′) to generate a message m′, as indicated in Formula 133.

[00015]$\begin{array}{cc}R:=\frac{E}{\left(G\left(e\left({\tilde{c}}_{r\mathrm{.0}},k^{\prime *}\right)\right).Math.G\left(e\left({\tilde{c}}_{r\mathrm{.1}},k^{\prime *}\right)\right)\right)},m^{\prime }:=C/K^{1/R}& \left[\mathrm{Formula}133\right]\end{array}$

[0191] Note that if the parameter x{right arrow over ( )}′ set in the ciphertext ct and the parameter v{right arrow over ( )} set in the user secret key dk.sub.v correspond to each other, the ciphertext ct is decrypted correctly and the message m′ matches the message m. That the parameter x{right arrow over ( )}′ and the parameter v{right arrow over ( )} correspond to each other means that x{right arrow over ( )}′.Math.v{right arrow over ( )}=0 holds.

[0192] (Step S65: Output Process)

[0193] The decryption unit 713 outputs the message m′ generated in step S63 or step S64 via the communication interface 64.

[0194] Note that the element E indicated in Formula 131 is as indicated in Formula 134.

[00016]$\begin{array}{cc}E:=\tilde{D}.Math.r^{\prime }=D.Math.G\left(g_T^{{\widetilde{ϛ}}_r}\right).Math.\tilde{r}.Math.r^{\prime }=G\left(g_T^{{ϛ}_r}\right).Math.G\left(g_T^{{\widetilde{ϛ}}_r}\right).Math.\tilde{r}.Math.r^{\prime }.Math.r=G\left(g_T^{\tilde{r}{r}^{\prime }r{ϛ}_r{\widetilde{ϛ}}_r}\right)& \left[\mathrm{Formula}134\right]\end{array}$

[0195] If x{right arrow over ( )}′.Math.v{right arrow over ( )}=0, the two pairing operations indicated in Formula 133 are as indicated in Formula 135.

e({tilde over (c)}.sub.r.0,k′*)=g.sub.T.sup.r,

e({tilde over (c)}.sub.r.1,k′*)=g.sub.T.sup.r,

[0196] where

[0197] {tilde over (c)}.sub.r.0=(.sub.r,{tilde over (ω)}.sub.r.0{right arrow over (x)}′,0.sup.n,0.sup.n,φ.sub.r+{tilde over (φ)}.sub.r.0,

[0198] {tilde over (c)}.sub.r.1=(.sub.r,{tilde over (ω)}.sub.r.1{right arrow over (x)}′,0.sup.n,0.sup.n,{tilde over (φ)}.sub.r.1,

[0199] k′*:=(1,δ{right arrow over (v)}′,0.sup.n,η,0)

[0200] Therefore, the element R indicated in Formula 133 is as indicated in Formula 136.

[00017]$\begin{array}{cc}R:=\frac{E}{\left(G\left(e\left({\tilde{c}}_{r\mathrm{.0}},k^{\prime *}\right)\right).Math.G\left(e\left({\tilde{c}}_{r.1},k^{\prime *}\right)\right)\right)}=\frac{G\left(g_T^{\tilde{r}{r}^{\prime }r{ϛ}_r{\widetilde{ϛ}}_r}\right)}{G\left(g_T^{{ϛ}_r}.Math.g_T^{{\widetilde{ϛ}}_r}\right)}=G\left(g_T^{\tilde{r}{r}^{\prime }r}\right)& \left[\mathrm{Formula}136\right]\end{array}$

[0201] The element K indicated in Formula 131 is as indicated in Formula 137.

K:=e(c.sub.1,{tilde over (k)}*.sub.r).sup.r′=g.sub.T.sup.{tilde over (r)}r′r^{[Formula 137]}

[0202] where

[0203] c.sub.1:=(,ω.sub.1ω{right arrow over (y)},0.sup.n,0.sup.nω.sub.1φ+φ.sub.1.sub.1

[0204] {tilde over (k)}.sub.r*:=({tilde over (r)}r,{tilde over (r)}δ.sub.r{right arrow over (w)},0.sup.n,{tilde over (r)}{right arrow over (η)}.sub.r+{right arrow over (η)}′,0

[0205] Therefore, the message m′ indicated in Formula 133 is as indicated in Formula 138.

m′:C/K.sup.1/R=(m.Math.g.sub.T)/(g.sub.T.sup.{tilde over (r)}r′r.sup.)1/G(g.sup.T.sup.{tilde over (r)}r′r)=(m.Math.g.sub.T)/g.sub.T=m

[0206] Note that the parameter x{right arrow over ( )} is set in the cipher element c.sub.0 of the ciphertext oct.sub.x generated by the encryption device 50. The master re-encryption key mrk does not include a key element in which the parameter v{right arrow over ( )} corresponding to the parameter x{right arrow over ( )} is set. Therefore, the master re-encryption key mrk cannot decrypt any ciphertext oct.sub.x generated by the encryption device 50.

[0207] The element c, in which the parameter y{right arrow over ( )} is set, is embedded in the cipher element c.sub.1 of the ciphertext oct.sub.x generated by the encryption device 50. The master re-encryption key mrk includes the key element k*.sub.r, in which the parameter w{right arrow over ( )} corresponding to the parameter y{right arrow over ( )} is set. Therefore, the master re-encryption key mrk can generate a re-encryption key for changing the access range for any ciphertext oct.sub.x generated by the encryption device 50.

[0208] ***Effects of First Embodiment***

[0209] As described above, in the cryptographic system 10 according to the first embodiment, re-encryption is performed using a master re-encryption key that cannot decrypt any ciphertext generated by the encryption device, but can generate a re-encryption key for changing an access range for any ciphertext generated by the encryption device.

[0210] Since a re-encryption key for changing an access range for any ciphertext can be generated with the master re-encryption key, a secret key of a user and a master public key are not required for generating a re-encryption key. Therefore, the possibility of leakage of the secret key of the user and the master public key can be reduced, resulting in enhanced security. In addition, no ciphertext can be decrypted with the master re-encryption key, so that unauthorized decryption using the master re-encryption key will not be performed, resulting in enhanced security.

[0211] ***Other Configurations***

[0212] <First Variation>

[0213] In the first embodiment, the functional components are realized by software. However, as a first variation, the functional components may be realized by hardware. With regard to this first variation, differences from the first embodiment will be described.

[0214] When the functions are realized by hardware, the common parameter generation device 20 includes an electronic circuit in place of the processor 21, the memory 22, and the storage 23. The electronic circuit is a dedicated circuit that realizes the functions of the functional components of the common parameter generation device 20, the memory 22, and the storage 23.

[0215] When the functions are realized by hardware, the user secret key generation device 30 includes an electronic circuit in place of the processor 31, the memory 32, and the storage 33. The electronic circuit is a dedicated circuit that realizes the functions of the functional components of the user secret key generation device 30, the memory 32, and the storage 33.

[0216] When the functions are realized by hardware, the master re-encryption key generation device 40 includes an electronic circuit in place of the processor 41, the memory 42, and the storage 43. The electronic circuit is a dedicated circuit that realizes the functions of the functional components of the master re-encryption key generation device 40, the memory 42, and the storage 43.

[0217] When the functions are realized by hardware, the encryption device 50 includes an electronic circuit in place of the processor 51, the memory 52, and the storage 53. The electronic circuit is a dedicated circuit that realizes the functions of the functional components of the encryption device 50, the memory 52, and the storage 53.

[0218] When the functions are realized by hardware, the re-encryption device 60 includes an electronic circuit in place of the processor 61, the memory 62, and the storage 63. The electronic circuit is a dedicated circuit that realizes the functions of the functional components of the re-encryption device 60, the memory 62, and the storage 63.

[0219] When the functions are realized by hardware, the decryption device 70 includes an electronic circuit in place of the processor 71, the memory 72, and the storage 73. The electronic circuit is a dedicated circuit that realizes the functions of the functional components of the decryption device 70, the memory 72, and the storage 73.

[0220] The electronic circuit is assumed to be a single circuit, a composite circuit, a programmed processor, a parallel-programmed processor, a logic IC, a gate array (GA), an application specific integrated circuit (ASIC), or a field-programmable gate array (FPGA).

[0221] The functions of the functional components of the common parameter generation device 20 may be realized by one electronic circuit, or the functions of the functional components of the common parameter generation device 20 may be distributed among and realized by a plurality of electronic circuits. Similarly, with regard to each of the user secret key generation device 30, the master re-encryption key generation device 40, the encryption device 50, the re-encryption device 60, and the decryption device 70, the functions of the functional components may be realized by one electronic circuit, or the functions of the functional components may be distributed among and realized by a plurality of electronic circuits.

[0222] <Second Variation>

[0223] As a second variation, some of the functions may be realized by hardware, and the rest of the functions may be realized by software. That is, some of the functions of the functional components may be realized by hardware, and the rest of the functions may be realized by software.

[0224] Each of the processors 21, 31, 41, 51, 61, 71, the memories 22, 32, 42, 52, 62, 72, the storages 23, 33, 43, 53, 63, 73, and the electronic circuit is referred to as processing circuitry. That is, the functions of the functional components are realized by the processing circuitry.

REFERENCE SIGNS LIST

[0225] 10: cryptographic system, 20: common parameter generation device, 21: processor, 22: memory, 23: storage, 24: communication interface, 211: acquisition unit, 212: common parameter generation unit, 213: basis generation unit, 214: master key generation unit, 215: transmission unit, 30: user secret key generation device, 31: processor, 32: memory, 33: storage, 34: communication interface, 311: acquisition unit, 312: user secret key generation unit, 313: transmission unit, 40: master re-encryption key generation device, 41: processor, 42: memory, 43: storage, 44: communication interface, 411: acquisition unit, 412: master re-encryption key generation unit, 413: transmission unit, 50: encryption device, 51: processor, 52: memory, 53: storage, 54: communication interface, 511: acquisition unit, 512: encryption unit, 513: transmission unit, 60: re-encryption device, 61: processor, 62: memory, 63: storage, 64: communication interface, 611: acquisition unit, 612: re-encryption key generation unit, 613: re-encryption unit, 614: transmission unit, 70: decryption device, 71: processor, 72: memory, 73: storage, 74: communication interface, 711: acquisition unit, 712: determination unit, 713: decryption unit, 80: transmission channel