CYPHER SYSTEM, KEY GENERATION APPARATUS, ENCRYPTION APPARATUS, DECRYPTION APPARATUS, METHOD AND PROGRAM

Abstract

An encryption system includes one or more computers each including a memory and a processor configured to generating a public key and a master private key that are used in attribute-based encryption; using, as inputs, at least the public key and one of an attribute and a policy that is denoted by an arbitrary conditional expression related to the attribute, and generating at least cyphertext in which one of the attribute and the policy is embedded; using the public key, the master private key, and the other of the attribute and the policy as inputs, and generating a private key in which the other of the attribute and the policy is embedded; and using the public key, the cyphertext, and the private key as inputs, and decrypting the cyphertext.

Claims

1. An encryption system, comprising: one or more computers each including a memory and a processor configured to generating a public key and a master private key that are used in attribute-based encryption; using, as inputs, at least the public key and one of an attribute and a policy that is denoted by an arbitrary conditional expression related to the attribute, and generating at least cyphertext in which one of the attribute and the policy is embedded; using the public key, the master private key, and the other of the attribute and the policy as inputs, and generating a private key in which the other of the attribute and the policy is embedded; and using the public key, the cyphertext, and the private key as inputs, and decrypting the cyphertext.

2. A key generation apparatus, comprising: a memory and a processor configured to generating a public key and a master private key that are used in attribute-based encryption; and using, as inputs, the public key, the master private key, and one of an attribute and a policy that is denoted by an arbitrary conditional expression related to the attribute, and generating a private key in which one of the attribute and the policy is embedded.

3-4. (canceled)

5. A method executed by a computer including a memory and a processor, the method comprising: generating a public key and a master private key that are used in attribute-based encryption; an encryption procedure of using, as inputs, at least the public key and one of an attribute and a policy that is denoted by an arbitrary conditional expression related to the attribute, and generating at least cyphertext in which one of the attribute and the policy is embedded; using the public key, the master private key, and the other of the attribute and the policy as inputs, and generating a private key in which the other of the attribute and the policy is embedded; and using the public key, the cyphertext, and the private key as inputs, and decrypting the cyphertext.

6. A non-transitory computer-readable recording medium having computer-readable instructions stored thereon, which when executed, cause a computer including a memory and a processor to execute respective operations in the encryption system according to claim 1 or respective operations in the key generation apparatus according to claim 2.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0011] FIG. 1 is a diagram showing an example of an overall configuration of an encryption system according to the present embodiment.

[0012] FIG. 2 is a diagram showing an example of a hardware configuration of a key generation apparatus, an encryption apparatus, and a decryption apparatus according to the present embodiment.

DESCRIPTION OF EMBODIMENTS

[0013] The following describes an embodiment of the present invention (hereinafter also referred to as “the present embodiment”). The present embodiment will be described in relation to an encryption system 1 which can use an arbitrary conditional expression as a policy without increasing the size of cyphertext and a private key, and which implements attribute-based encryption that operates efficiently.

[0014] <Preparation>

[0015] First, the notation, concept, and the like necessary for the description of the present embodiment will be explained.

[0016] Notation

[0017] Denoting a prime number by p, a field Z/pZ is denoted by Z.sub.p. A set of all bit strings each having a finite length is denoted by {0,1}*. For example, denoting a natural number by n, a set of all bit strings having a length of n is denoted by {0,1}.sup.n.

[0018] For a natural number n, {1, . . . , n} is denoted by [n]. Denoting a set by S, selecting s uniformly from the set S is denoted by s←S. For matrices A.sub.1 and A.sub.2 having the same number of rows, a concatenation of A.sub.1 and A.sub.2 is denoted as follows.

(A.sub.1∥A.sub.2)  [Math 1]

A space spanned by all columns of the matrix A (i.e., a space having the column vectors constituting the matrix Z as the base) is denoted by span(A).

[0019] Let i∈{1,2,T}, a matrix on a cyclic group G.sub.i having an order p with respect to a matrix A:=(a.sub.j,l).sub.j,l on Z.sub.p that has the following element (j,l), is denoted by [A].sub.i.

[Math 2]
Note that this notation is similarly applied to vectors and scalars. Furthermore, ([A].sub.1,[A].sub.2) is denoted by [A].sub.1,2.

[0020] Regarding matrices A and B for which

B  [Math 3]

is defined, pairing is denoted as follows, albeit an overly-used notation.

e([A].sub.1,[B].sub.2)=[B].sup.T  [Math 4]

Note that the following denotes transposition.

  [Math 5]

[0021] Boolean Formula

[0022] A Boolean formula is an expression in which Boolean variables are connected by “AND”, “OR”, and “NOT”. A Boolean formula can easily be converted into a logic circuit with fan-in of 2 and fan-out of 1. A Boolean formula that does not include NOT is referred to as a monotone Boolean formula, whereas a Boolean formula that includes NOT is referred to as a non-monotone Boolean formula. In the present embodiment, it is assumed that a Boolean formula is represented as a logic circuit.

[0023] Attribute and Policy

[0024] In the present embodiment, a set of attributes is defined by the following expression (1).

[Math 6]

χ=×Φ.sub.i  (1)

Here, Φ.sub.i denotes a set composed of all injective functions φ: [i].fwdarw.{0,1}*.

[0025] Also, a set of policies is defined by the following expression (2).

[Math 7]

y=×.sub.i×Ψ.sub.i×  (2)

[0026] Here,

[Math 8]

[0027] F.sub.i is a set composed of all monotone Boolean formulae with an input length of i,
Ψ.sub.i is a set composed of all functions ψ:[i].fwdarw.{0,1}*, and
T.sub.i is a set composed of all functions t:[i].fwdarw.{0,1}.

[0028] In attribute-based encryption described in the present embodiment, each attribute is an element of a set defined by the aforementioned expression (1), and each policy is an element of a set defined by the aforementioned expression (2).

[0029] Furthermore, when an attribute

x=(x∈.sub.p.sup.m,ϕ)  [Math 9]

satisfies a policy

y=(y∈.sub.p.sup.n,f,ψ,t),  [Math 10]

it means that f(b)=1 holds for b defined by the following expression (3). That is to say, decryption can be performed only when f(b)=1.

[0030] For an attribute x and a policy y, b=(b.sub.1, . . . , b.sub.n)∈{0,1}.sup.n is defined by the following expression (3).

[00001]$\begin{array}{cc}\left[\mathrm{Math}11\right]& \\ b_i:=\{\begin{array}{cc}t\left(i\right)\odot \mathrm{true}\left(x_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}=y_i\right)& \psi \left(i\right).Math.\mathrm{Im}\left(\varphi \right)\\ 0& \psi \left(i\right)⊈\mathrm{Im}\left(\varphi \right)\end{array}& \left(3\right)\end{array}$

Here,

[0031]
⊙  [Math 12]

denotes exclusive NOR (XNOR), and true denotes a truth value. Furthermore, x.sub.j is the j.sup.th element of

x∈.sub.p.sup.m,  [Math 13]

and y.sub.i is the i.sup.th element of

y∈.sub.p.sup.m.  [Math 14]

[0032] Note that the aforementioned expression (1) and expression (2) are notations for the case of key-policy attribute-based encryption; in ciphertext-policy attribute-based encryption, the contents of definitions of a set of attributes and of a set of policies are reversed.

[0033] Linear Secret Sharing

[0034] In the present embodiment, a linear secret sharing scheme is used. The linear secret sharing scheme is a scheme in which a secret vector k is allocated and split into σ.sub.1, . . . , σ.sub.n in accordance with a certain function f{0,1}.sup.n.fwdarw.{0,1}. The original secret vector k can be restored by collecting, from among the split allocations, allocations corresponding to a portion having a bit 1 in a bit string b that satisfies f(b)=1. That is to say, there is a set S that can easily be calculated from f and b, and k can be restored by simply adding the allocations as follows.

k=Σ.sub.i∈Sσ.sub.i  [Math 15]

On the other hand, k cannot be restored by collecting allocations corresponding to a portion with a bit 1 in a bit string b that satisfies f(b)=0.

[0035] The linear secret sharing scheme is implemented by algorithms shown in the following (S1) to (S4). Here, the inputs into the linear secret sharing scheme are a monotone Boolean formula f:{0,1}.sup.n.fwdarw.{0,1}, and a secret vector

k∈.  [Math 16]

Hereinafter, an algorithm in this linear secret sharing scheme is also referred to as “Share”.

[0036] (S1) A vector σ.sub.out:=k is set to an output line of a monotone Boolean formula f represented by a logic circuit (i.e., an output line of this logic circuit).

[0037] (S2) Assuming that each AND gate in this logic circuit has input lines a and b and an output line c, a vector

u.sub.g←  [Math 17]

is selected with respect to each AND gate with the output line c for which a vector σ.sub.c is set, and then, a vector σ.sub.a:=σ.sub.c−u.sub.g and a vector σ.sub.b:=u.sub.g are respectively set to the input line a and the input line b.

[0038] (S3) Assuming that each OR gate in this logic circuit has input lines a and b and an output line c, and with respect to each OR gate with the output line c to which a vector σ.sub.n is set, vectors σ.sub.a:=σ.sub.c and σ.sub.b:=σ.sub.c are respectively set to the input line a and the input line b.

[0039] (S4) σ.sub.1, . . . , σ.sub.n that have been set to the input lines 1, . . . , n of the monotone Boolean formula f (i.e., the input lines 1, . . . , n of this logic circuit) are output as allocations for the secret vector k.

[0040] Note that an algorithm Share in this linear secret sharing is similarly applicable also to vectors of group elements.

Attribute-Based Encryption According to Present Embodiment

[0041] Key-policy attribute-based encryption according to the present embodiment and ciphertext-policy attribute-based encryption according to the present embodiment will be described as attribute-based encryption according to the present embodiment. The attribute-based encryption is composed of four algorithms (i.e., a setup algorithm Setup, an encryption algorithm Enc, a key generation algorithm KeyGen, and a decryption algorithm Dec). In the present embodiment, cyclic groups having bilinear mappings e:G.sub.1×G.sub.2.fwdarw.G.sub.T are used as cyclic groups G.sub.1, G.sub.2, and G.sub.T of an order p of a prime number. These cyclic groups and the bilinear mappings are collectively referred to as bilinear groups. Known bilinear groups may be used, or bilinear groups may be generated using the setup algorithm Setup.

[0042] Notations of Matrices

[0043] First, notations of matrices used in the description of each algorithm in attribute-based encryption, and in the description of each algorithm in later-described attribute-based KEM (Key Encapsulation Mechanism), will be described.

[0044] It is assumed that k is an arbitrary natural number, and

.sub.k  [Math 18]

is an appropriate set of matrices of (k+1)×k on Z.sub.p that have full rank. At this time, A*, a.sub.R, and a.sup.⊥ are defined with respect to

A∈.sub.k,  [Math 19]

as follows. That is, it is assumed that a.sub.R is a vector which is calculated definitely from the matrix A by a certain, determined method, and has

Ā:=(A∥a.sub.R)  [Math 20]

as the base. Furthermore, it is assumed that A* is a matrix composed of k columns from the left (i.e., columns from the first column to the k.sup.th column) of

().sup.−1,  [Math 21]

and a vector al is the rightmost column of

().sup.−1.  [Math 22]

For these A*, a.sub.R, and a.sup.⊥, the following relationship is satisfied.

A*=I.sub.k,a.sup.⊥=0,A*+=I.sub.k+1  [Math 23]

[0045] Here, I.sub.k is a unit matrix of k×k, and I.sub.k+1 is a unit matrix of (k+1)×(k+1).

[0046] Also, it is assumed that a matrix B, a vector b.sub.1, and a vector b.sub.2 are respectively a matrix composed of k columns from the left of the following matrix, a vector representing the (k+1).sup.th column of the following matrix, and a vector representing the rightmost column (i.e., the (k+2).sup.th column) of the following matrix.

B∈GL.sub.k+2(.sub.p)  [Math 24]

Here, GL.sub.k+2(Z.sub.p) is a set of all regular matrices of (k+2)×(k+2) on Z.sub.p (i.e., a general linear group having a size k+2 on Z.sub.p).

[0047] Similarly, it is assumed that a matrix B*, a vector b.sub.1*, and a vector b.sub.2* are respectively a matrix composed of k columns from the left of the following matrix, a vector representing the (k+1).sup.th column of the following matrix, and a vector representing the rightmost column of the following matrix.

().sup.−1  [Math 25]

[0048] Note that, for simplicity,

(b.sub.1∥b.sub.2)  [Math 26]

is also denoted by B.sub.12. This notation is similarly applied to other cases as well (e.g., the case of matrices or the like).

[0049] Key-Policy Attribute-Based Encryption According to Present Embodiment

[0050] The following describes the respective algorithms in key-policy attribute-based encryption according to the present embodiment. It is assumed that k is an arbitrary natural number, and

H:{0,1}*.fwdarw.G.sub.1.sup.(k+1)×k×G.sub.1.sup.(k+1)×k  [Math 27]

is a function. Furthermore, it is assumed that

F.sub.K:{0,1}*.fwdarw..sub.p.sup.k+1×.sub.p.sup.k+1  [Math 28]

is a family of functions with an index K, and

  [Math 29]

is an index space of K. At this time, the setup algorithm Setup, the encryption algorithm Enc, the key generation algorithm KeyGen, and the decryption algorithm Dec in key-policy attribute-based encryption according to the present embodiment are configured as follows.

[0051] Setup( ): The setup algorithm Setup outputs a public key pk and a master private key msk as follows.

A,B←.sub.k,k←.sub.p.sup.k+1,K←,

pk:(,[A].sub.2,[k].sub.T),msk:(A*,a.sup.⊥,B,k,K)  [Math30]

Here, G denotes bilinear groups, and G:=(p, G.sub.1, G.sub.2, G.sub.T, g.sub.1, g.sub.2, e). Also, g.sub.1 and g.sub.2 are generators of G.sub.1 and G.sub.2, respectively. As stated earlier, known bilinear groups G may be used, or bilinear groups G may be generated using the setup algorithm Setup.

[0052] Enc (pk, x, M): The encryption algorithm Enc takes a public key pk, an attribute

x=(x∈.sub.p.sup.m,ϕ),  [Math 31]

and a message MEG.sub.T as inputs, and outputs cyphertext ct.sub.x (cyphertext ct.sub.x with an attribute) as follows.

s←.sub.p.sup.k,([U.sub.ϕ(i),0].sub.1,[U.sub.ϕ)(i),1].sub.1):=H(ϕ(i)),

c.sub.1:=[As].sub.2,c.sub.2,i:=[(x.sub.iU.sub.ϕ(i),0+U.sub.ϕ(i),1)s].sub.1,

c.sub.3:=[sk].sub.TM for i∈[m],

ct.sub.x:=(x,c.sub.1,{c.sub.2,i}.sub.i∈[m],c.sub.3)  [Math 32]

KeyGen (pk, msk, y): The key generation algorithm KeyGen takes a public key pk, a master private key msk, and a policy

y=(y∈.sub.p.sup.n,f,Φ,t)  [Math 33]

as inputs, and outputs a private key sk.sub.y (a private key sk.sub.y with a policy) as follows.

[00002]$\begin{array}{cc}\left[\mathrm{Math}34\right]& \\ \begin{array}{c}{r}_1,.Math.,r_d\leftarrow {\mathbb{Z}}_p^k,k_1,.Math.,k_n\leftarrow \mathrm{Share}\left(f,k\right)\in {\mathbb{Z}}_p^{k+1},\\ {k_{1,j}:=[{\mathrm{Br}}_j.Math.}_2\mathrm{for}j\in \left[d\right],\\ \left({\left[U_{\psi \left(i\right),0}\right]}_1,{\left[U_{\psi \left(i\right),1}\right]}_1\right):=H\left(\psi \left(i\right)\right),\left(u_{\psi \left(i\right),0},u_{\psi \left(i\right),1}\right):=F_K\left(\psi \left(i\right)\right),\\ k_{2,i}:={\left[k_i+A^{*}\left(y_i{U}_{\psi \left(i\right),0}^{\top }+U_{\psi \left(i\right),1}^{\top }\right){\mathrm{Br}}_{\pi \left(i\right)}+a^{\perp }\left(y_i{u}_{\psi \left(i\right),0}^{\top }+u_{\psi \left(i\right),1}^{\top }\right){\mathrm{Br}}_{\pi \left(i\right)}\right]}_1\mathrm{if}t\left(i\right)=1,\\ k_{2,i}:=\left(k_{2,i,1},k_{2,i,2}\right):=\left(\begin{array}{c}{\left[-k_i+A^{*}{U}_{\psi \left(i\right),0}^{\top }{\mathrm{Br}}_{\pi \left(i\right)}+a^{\perp }{u}_{\psi \left(i\right),0}^{\top }{\mathrm{Br}}_{\pi \left(i\right)}\right]}_1,\\ {\left[y_i{k}_i+A^{*}{U}_{\psi \left(i\right),1}^{\top }{\mathrm{Br}}_{\pi \left(i\right)}+a^{\perp }{u}_{\psi \left(i\right),1}^{\top }{\mathrm{Br}}_{\pi \left(i\right)}\right]}_1\end{array}\right)\mathrm{if}t\left(i\right)=0\\ \mathrm{for}i\in \left[n\right]\\ {\mathrm{sk}}_y:=\left(y,{\left\{k_{1,j}\right\}}_{j\in \left[d\right]},{\left\{k_{2,i}\right\}}_{i\in \left[n\right]}\right)\end{array}& \end{array}$

Here, π:[n].fwdarw.{n|n is a natural number} is a function defined as π(i):=|{j|ω(j)=ψ(i), j≤i}|, and d is the maximum value of the number of appearances of the same attribute label in f (i.e., d:=max.sub.i∈[n]π(i)).

[0053] Dec (pk, ct.sub.x, sk.sub.y): The decryption algorithm Dec takes a public key pk, cyphertext ct.sub.x, and a private key sk.sub.y as inputs, calculates b from x and y by the aforementioned expression (3), and then, outputs ⊥ indicating a decryption failure when f(b)=0. On the other hand, when f(b)≠0, the decryption algorithm Dec calculates a set S.Math.{i|b.sub.i=1} that satisfies

k=Σ.sub.i∈Sk.sub.i  [Math 35]

and outputs M′ as follows.

[00003]$\begin{array}{cc}\left[\mathrm{Math}36\right]& \\ \begin{array}{c}{D}_{1,j}:=e\left(\underset{i\in S_1}{\underset{\pi \left(i\right)=j}{.Math.}}{k}_{2,i}+\underset{i\in S_0}{\underset{\pi \left(i\right)=j}{.Math.}}\frac{1}{y_i-x_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}}\left(x_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}{k}_{2,i,1}+k_{2,i,2}\right),c_1\right),\\ D_{2,j}:=e\left(\underset{i\in S_1}{\underset{\pi \left(i\right)=j}{.Math.}}{c}_{2,{\varphi }^{-1}\left(\psi \left(i\right)\right)}+\underset{i\in S_0}{\underset{\pi \left(i\right)=j}{.Math.}}\frac{1}{y_i-x_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}}{c}_{2,{\varphi }^{-1}\left(\psi \left(i\right)\right)},k_{1,j}\right)\mathrm{for}j\in \left[d\right],\\ M^{\prime }:=c_3/\underset{j\in \left[d\right]}{.Math.}\left(D_{1,j}/D_{2,j}\right)\end{array}& \end{array}$

Here, S.sub.1:=S∩{i|t(i)=1} and S.sub.0:=S∩{i|t(i)=0}.

[0054] Ciphertext-Policy Attribute-Based Encryption According to Present Embodiment

[0055] The following describes the respective algorithms in ciphertext-policy attribute-based encryption according to the present embodiment. It is assumed that k is an arbitrary natural number, GL.sub.k(Z.sub.p) is a general linear group with a size k on Z.sub.p, and

H:{0,1}*.fwdarw.G.sub.1.sup.(k+1)×k×G.sub.1.sup.(k+1)×k  [Math 37]

is a function. Also, it is assumed that

F.sub.K:{0,1}*.fwdarw..sub.p.sup.k+2×.sub.p.sup.k+2  [Math 38]

is a family of functions with an index K, and

  [Math 39]

is an index space of K. At this time, the setup algorithm Setup, the encryption algorithm Enc, the key generation algorithm KeyGen, and the decryption algorithm Dec in ciphertext-policy attribute-based encryption according to the present embodiment are configured as follows.

[0056] Setup( ): The setup algorithm Setup outputs a public key pk and a master private key msk as follows.

A←.sub.k,←GL.sub.k+2(.sub.p),W←.sub.p.sup.(k+1)×(k+2),

k←.sub.p.sup.k+2,K←,

pk:=(,[B].sub.2,[WB].sub.1,[k].sub.T),

msk:=(A,A,B*,B.sub.12*,k,K)  [Math 40]

Here, G denotes bilinear groups, and G:=(p, G.sub.1, G.sub.2, G.sub.T, g.sub.1, g.sub.2, e). As stated earlier, known bilinear groups G may be used, or bilinear groups G may be generated using the setup algorithm Setup.

[0057] Enc (pk, x, M): The encryption algorithm Enc takes a public key pk, a policy

x=(x∈.sub.p.sup.n,f,ψ,t),  [Math 41]

and a message MEG.sub.T as inputs, and outputs cyphertext ct.sub.x (cyphertext ct.sub.x with a policy) as follows.

r,r.sub.1, . . . ,r.sub.d←.sub.p.sup.k,[w.sub.1].sub.1, . . . ,[w.sub.n].sub.1←Share(f,[WBr].sub.1)∈.sub.p.sup.k+1,

c.sub.1:=[Br].sub.2,c.sub.2,j:=[Br.sub.j].sub.2 for j∈[d],c.sub.4:=[k].sub.TM,

([U.sub.ψ(i),0].sub.1,[U.sub.ψ(i),1].sub.1):=H(ψ(i)),

c.sub.3,i:=[w.sub.i+(x.sub.iU.sub.ψ(i),0+U.sub.ψ(i),1)r.sub.π(i)].sub.1 if t(i)=1,

c.sub.3,i:=(c.sub.3,i,1,c.sub.3,i,2):=([−w.sub.i+U.sub.ψ(i),0r.sub.π(i)].sub.1,[x.sub.iw.sub.1+U.sub.ψ(i),1r.sub.π(i)].sub.1 if t(i)=0

for i∈[n],

ct.sub.x:=(x,c.sub.1,{c.sub.2,j}.sub.j∈[d],{c.sub.3,i}.sub.i∈[n],c.sub.4)  [Math 42]

Here, π:[n].fwdarw.{n|n is a natural number} is a function defined as to π(i):=|{j|ψ(j)=ψ(i), j≤i}|, and d is the maximum value of the number of appearances of the same attribute label in f (i.e., d:=max.sub.i∈[x]π(i)).

[0058] KeyGen (pk, msk, y): The key generation algorithm KeyGen takes a public key pk, a master private key msk, and an attribute

y=(y∈.sub.p.sup.m,ϕ)  [Math 43]

as inputs, and outputs a private key sk.sub.y (a private key sk.sub.y with an attribute) as follows.

s←.sub.p.sup.k,([U.sub.ϕ(i),0].sub.1,[U.sub.ϕ(i),1].sub.1):=H(ϕ(i)),(V.sub.ϕ(i),0,V.sub.ϕ(i),1):=F.sub.K(ϕ(i))

k.sub.1:=[As].sub.2,k.sub.2:=[k+W.sup.T As].sub.1,

k.sub.3,i:=[B+As+B.sub.12*(y.sub.i .sub.+.sub.)As].sub.1 for i∈[m],

sk.sub.y:=(y,k.sub.1,k.sub.2,{k.sub.3,i}.sub.i∈[m])  [Math 44]

Dec (pk, ct.sub.x, sk.sub.y): The decryption algorithm Dec takes a public key pk, cyphertext ct.sub.x, and a private key sk.sub.y as inputs, calculates b from x and y by the aforementioned expression (3), and then outputs ⊥ indicating a decryption failure when f(b)=0. On the other hand, when f(b)≠0, the decryption algorithm Dec calculates a set S.Math.{i|b.sub.i=1} that satisfies.

WBr=Σ.sub.i∈Sw.sub.i  [Math 45]

and outputs M′ as follows.

[00004]$\begin{array}{cc}\left[\mathrm{Math}46\right]& \\ \begin{array}{c}{D}_{1,j}:=e\left(\underset{i\in S_1}{\underset{\pi \left(i\right)=j}{.Math.}}{c}_{3,i}+\underset{i\in S_0}{\underset{\pi \left(i\right)=j}{.Math.}}\frac{1}{x_i-y_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}}\left(y_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}{c}_{3,i,1}+c_{3,i,2}\right),k_1\right),\\ D_{2,j}:=e\left(\underset{i\in S_1}{\underset{\pi \left(i\right)=j}{.Math.}}{k}_{3,{\varphi }^{-1}\left(\psi \left(i\right)\right)}+\underset{i\in S_0}{\underset{\pi \left(i\right)=j}{.Math.}}\frac{1}{x_i-y_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}}{k}_{3,{\varphi }^{-1}\left(\psi \left(i\right)\right)},c_{2,j}\right)\mathrm{for}j\in \left[d\right],\\ M^{\prime }:=c_4/\left(e\left(k_2,c_1\right)/\underset{j\in \left[d\right]}{.Math.}\left(D_{1,j}/D_{2,j}\right)\right)\end{array}& \end{array}$

Here, S.sub.1:=S∩{i|t(i)=1}, S.sub.0:=S∩{i|t(i)=0}.

Attribute-Based KEM According to Present Embodiment

[0059] The aforementioned key-policy attribute-based encryption and ciphertext-policy attribute-based encryption according to the present embodiment are also applicable to a KEM method. In general, public key encryption techniques are slow in operation; thus, when large-volume data is encrypted, it is often the case that a private key used in common-key encryption is delivered safely using public key encryption, and the data is encrypted using common-key encryption. A method used to safely deliver a private key of common-key encryption (hereinafter also referred to as a “common key”) is called KEM.

[0060] In view of this, the following describes key-policy attribute-based KEM in which key-policy attribute-based encryption according to the present embodiment is applied to KEM, as well as cyphertext-policy attribute-based KEM in which ciphertext-policy attribute-based encryption according to the present embodiment is applied to KEM.

[0061] Key-Policy Attribute-Based KEM According to Present Embodiment

[0062] The following describes the respective algorithms in key-policy attribute-based KEM according to the present embodiment. It is assumed that a function H and a family of functions F.sub.K are similar to those of “key-policy attribute-based encryption according to the present embodiment” described earlier, and

H.sub.2:G.sub.T.fwdarw.  [Math 47]

is a function. Here,

  [Math 48]

is a private key space of common-key encryption. At this time, the setup algorithm Setup, the encryption algorithm Enc, the key generation algorithm KeyGen, and the decryption algorithm Dec in key-policy attribute-based KEM according to the present embodiment are configured as follows.

[0063] Setup( ): The setup algorithm Setup outputs a public key pk and a master private key msk as follows.

A,B←.sub.k,k←.sub.p.sup.k+1,K←K,

pk:=(,[A].sub.2,[k].sub.T),msk:=(A*,a.sup.⊥,B,k,K)  [Math 49]

Here, G denotes bilinear groups, and G:=(p, G.sub.1, G.sub.2, G.sub.T, g.sub.1, g.sub.2, e). As stated earlier, known bilinear groups G may be used, or bilinear groups G may be generated using the setup algorithm Setup.

[0064] Enc (pk, x): The encryption algorithm Enc takes a public key pk and an attribute

X=(x∈.sub.p.sup.m,ϕ)  [Math 50]

as inputs, and outputs cyphertext ct.sub.x (cyphertext ct.sub.x with an attribute) and a common key L as follows.

s←.sub.p.sup.k,([U.sub.ϕ(i),0].sub.1,[U.sub.ϕ(i),1].sub.1):=H(ϕ(i)),

c.sub.1:=[As].sub.2,c.sub.2,i:=[(x.sub.iU.sub.ϕ(i),0+U.sub.ϕ(i),1)s].sub.1,

L:=H.sub.2([k].sub.T) for i∈[m],

ct.sub.x:=(x,c.sub.1,{c.sub.2,i}.sub.i∈[m])  [Math 51]

KeyGen (pk, msk, y): The key generation algorithm KeyGen takes a public key pk, a master private key msk, and a policy

y=(y∈.sub.p.sup.n,f,ψ,t)  [Math 52]

as inputs, and outputs a private key sk.sub.y (a private key sk.sub.y with a policy) as follows.

[00005]$\begin{array}{cc}\left[\mathrm{Math}53\right]& \\ \begin{array}{c}{r}_1,.Math.,r_d\leftarrow {\mathbb{Z}}_p^k,k_1,.Math.,k_n\leftarrow \mathrm{Share}\left(f,k\right)\in {\mathbb{Z}}_p^{k+1},\\ k_{1,j}:={\left[{\mathrm{Br}}_j\right]}_2\mathrm{for}j\in \left[d\right],\\ \left({\left[U_{\psi \left(i\right),0}\right]}_1,{\left[U_{\psi \left(i\right),1}\right]}_1\right):=H\left(\psi \left(i\right)\right),\left(u_{\psi \left(i\right),0},u_{\psi \left(i\right),1}\right):=F_K\left(\psi \left(i\right)\right),\\ k_{2,i}:={\left[k_i+A^{*}\left(y_i{U}_{\psi \left(i\right),0}^{\top }+U_{\psi \left(i\right),1}^{\top }\right){\mathrm{Br}}_{\pi \left(i\right)}+a^{\perp }\left(y_i{u}_{\psi \left(i\right),0}^{\top }+u_{\psi \left(i\right),1}^{\top }\right){\mathrm{Br}}_{\pi \left(i\right)}\right]}_1\mathrm{if}t\left(i\right)=1,\\ k_{2,i}:=\left(k_{2,i,1},k_{2,i,2}\right):=\left(\begin{array}{c}{\left[-k_i+A^{*}{U}_{\psi \left(i\right),0}^{\top }{\mathrm{Br}}_{\pi \left(i\right)}+a^{\perp }{u}_{\psi \left(i\right),0}^{\top }{\mathrm{Br}}_{\pi \left(i\right)}\right]}_1,\\ {\left[y_i{k}_i+A^{*}{U}_{\psi \left(i\right),1}^{\top }{\mathrm{Br}}_{\pi \left(i\right)}+a^{\perp }{u}_{\psi \left(i\right),1}^{\top }{\mathrm{Br}}_{\pi \left(i\right)}\right]}_1\end{array}\right)\mathrm{if}t\left(i\right)=0\\ \mathrm{for}i\in \left[n\right]\\ {\mathrm{sk}}_y:=\left(y,{\left\{k_{1,j}\right\}}_{j\in \left[d\right]},{\left\{k_{2,i}\right\}}_{i\in \left[n\right]}\right)\end{array}& \end{array}$

Here, π:[n].fwdarw.{n|n is a natural number} is a function defined as π(i):=|{j|ω(j)=ψ(i), j≤i}|, and d is the maximum value of the number of appearances of the same attribute label in f (i.e., d:=max.sub.i∈[n]π(i)).

[0065] Dec (pk, ct.sub.x, sk.sub.y): The decryption algorithm Dec takes a public key pk, cyphertext ct.sub.x, and a private key sk.sub.y as inputs, calculates b from x and y by the aforementioned expression (3), and then outputs ⊥ indicating a decryption failure when f(b)=0. On the other hand, when f(b)≠0, the decryption algorithm Dec calculates a set S.Math.{i|b.sub.i=1} that satisfies

k=Σ.sub.i∈Sk.sub.i  [Math 54]

and outputs a common key L′ as follows.

[00006]$\begin{array}{cc}\left[\mathrm{Math}55\right]& \\ \begin{array}{c}{D}_{1,j}:=e\left(\underset{i\in S_1}{\underset{\pi \left(i\right)=j}{.Math.}}{k}_{2,i}+\underset{i\in S_0}{\underset{\pi \left(i\right)=j}{.Math.}}\frac{1}{y_i-x_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}}\left(x_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}{k}_{2,i,1}+k_{2,i,2}\right),c_1\right),\\ D_{2,j}:=e\left(\underset{i\in S_1}{\underset{\pi \left(i\right)=j}{.Math.}}{c}_{2,{\varphi }^{-1}\left(\psi \left(i\right)\right)}+\underset{i\in S_0}{\underset{\pi \left(i\right)=j}{.Math.}}\frac{1}{y_i-x_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}}{c}_{2,{\varphi }^{-1}\left(\psi \left(i\right)\right),}{k}_{1,j}\right)\mathrm{for}j\in \left[d\right],\\ L^{\prime }:=H_2\left(\underset{j\in \left[d\right]}{.Math.}\left(D_{1,j}/D_{2,j}\right)\right)\end{array}& \end{array}$

Here, S.sub.1:=S∩{i|t(i)=1}, S.sub.0:=S∩{i|t(i)=0}.

[0066] Cyphertext-Policy Attribute-Based KEM According to Present Embodiment

[0067] The following describes the respective algorithms in cyphertext-policy attribute-based KEM according to the present embodiment. It is assumed that a function H and a family of functions F.sub.K are similar to those of “ciphertext-policy attribute-based encryption according to the present embodiment” described earlier, and

H.sub.2:G.sub.T.fwdarw.  [Math 56]

is a function. Here,

  [Math 57]

is a private key space of common-key encryption. At this time, the setup algorithm Setup, the encryption algorithm Enc, the key generation algorithm KeyGen, and the decryption algorithm Dec in cyphertext-policy attribute-based KEM according to the present embodiment are configured as follows.

[0068] Setup( ): The setup algorithm Setup outputs a public key pk and a master private key msk as follows.

B←GL.sub.k+2(.sub.p), W←.sub.p.sup.(k+1)×(k+2),k←.sub.p.sup.k+2,K←K,

pk:=(G,[B].sub.2, [WB].sub.1,[k].sub.T),

msk:=(A,W.sup.T A,B*,B.sub.12*,k,K)  [Math 58]

Here, G denotes bilinear groups, and G:=(p, G.sub.1, G.sub.2, G.sub.T, g.sub.1, g.sub.2, e). As stated earlier, known bilinear groups G may be used, or bilinear groups G may be generated using the setup algorithm Setup.

[0069] Enc (pk, x): The encryption algorithm Enc takes a public key pk and a policy

x=(x∈.sub.p.sup.nf,ψ,t)  [Math 59]

as inputs, and outputs cyphertext ct.sub.x (cyphertext ct.sub.x with a policy) and a common key L as follows.

r,r.sub.1, . . . ,r.sub.d←.sub.p.sup.k,[w.sub.1].sub.1, . . . ,[w.sub.n].sub.1←Share(f,[WBr].sub.1)∈.sub.p.sup.k+1,

c.sub.1:=[Br].sub.2,c.sub.2,j:=[Br.sub.j].sub.2 for j∈[d],L:=H.sub.2([k].sub.T),

([U.sub.ψ(i),0].sub.1,[U.sub.ψ(i),1].sub.1):=H(ψ(i)),

c.sub.3,i:=[w.sub.i+(x.sub.iU.sub.ψ(i),0+U.sub.ψ(i),1)r.sub.π(i)].sub.1 if t(i)=1,

c.sub.3,i:=(c.sub.3,i,1,c.sub.3,i,2):=([−w.sub.i+U.sub.ψ(i),0r.sub.π(i)].sub.1,[x.sub.iw.sub.i+U.sub.ψ(i),1r.sub.π(i)].sub.1) if t(i)=0

for i∈[n],

ct.sub.x:=(x,c.sub.1,{c.sub.2,j}.sub.j∈[d],{c.sub.3,i}.sub.i∈[n])  [Math 60]

[0070] Here, π:[n].fwdarw.{n|n is a natural number} is a function defined as π(i):=|{j|ψ(j)=ψ(i), j≤i}|, and d is the maximum value of the number of appearances of the same attribute label in f (i.e., d:=max.sub.i∈[n]π(i)).

[0071] KeyGen (pk, msk, y): The key generation algorithm KeyGen takes a public key pk, a master private key msk, and an attribute

y=(y∈.sub.p.sup.m,ϕ)  [Math 61]

as inputs, and outputs a private key sk.sub.y (a private key sk.sub.y with an attribute) as follows.

s←.sub.p.sup.k,([U.sub.ϕ(i),0].sub.1,[U.sub.ϕ(i),1].sub.1):=H(ϕ(i)),(V.sub.ϕ(i),0,V.sub.ϕ(i),1):=F.sub.K(ϕ(i))

k.sub.1:=[As].sub.2,k.sub.2:=[k+W.sup.T As].sub.1,

k.sub.3,i:=[B*(y.sub.i.sub.+.sub.)As+B.sub.12*(y.sub.i .sub.(i), .sub.for i∈[m],

sk.sub.y:=(y,k.sub.1,k.sub.2,{k.sub.3,i}.sub.i∈[m]).  [Math 62]

Dec (pk, ct.sub.x, sk.sub.y): The decryption algorithm Dec takes a public key pk, cyphertext ct.sub.x, and a private key sk.sub.y as inputs, calculates b from x and y by the aforementioned expression (3), and then outputs ⊥ indicating a decryption failure when f(b)=0. On the other hand, when f(b)≠0, the decryption algorithm Dec calculates a set S.Math.{i|b.sub.i=1} that satisfies

WBr=Σ.sub.i∈Sw.sub.i  [Math 63]

and outputs a common key L′ as follows.

[00007]$\begin{array}{cc}\left[\mathrm{Math}64\right]& \\ \begin{array}{c}{D}_{1,j}:=e\left(\underset{i\in S_1}{\underset{\pi \left(i\right)=j}{.Math.}}{c}_{3,i}+\underset{i\in S_0}{\underset{\pi \left(i\right)=j}{.Math.}}\frac{1}{x_i-y_{{\varphi }^{-1}\left(\phi \left(i\right)\right)}}\left(y_{{\varphi }^{-1}\left(\phi \left(i\right)\right)}{c}_{3,i,1}+c_{3,i,2}\right),k_1\right),\\ D_{2,j}:=e\left(\underset{i\in S_1}{\underset{\pi \left(i\right)=j}{.Math.}}{k}_{3,{\varphi }^{-1}\left(\psi \left(i\right)\right)}+\underset{i\in S_0}{\underset{\pi \left(i\right)=j}{.Math.}}\frac{1}{x_i-y_{{\varphi }^{-1}\left(\psi \left(i\right)\right)}}{k}_{3,{\varphi }^{-1}\left(\psi \left(i\right)\right)},c_{2,j}\right)\mathrm{for}j\in \left[d\right],\\ L^{\prime }:=H_2\left(e\left(k_2,c_1\right)/\underset{j\in \left[d\right]}{.Math.}\left(D_{1,j}/D_{2,j}\right)\right)\end{array}& \end{array}$

Here, S.sub.1:=S∩{i|t(i)=1}, S.sub.0:=S∩{i|t(i)=0}.

[0072] <Overall Configuration of Encryption System 1>

[0073] Next, with reference to FIG. 1, an overall configuration of the encryption system 1 will be described that implements “key-policy attribute-based encryption according to the present embodiment”, “ciphertext-policy attribute-based encryption according to the present embodiment”, “key-policy attribute-based KEM according to the present embodiment”, and “cyphertext-policy attribute-based KEM according to the present embodiment”, which have been described above. FIG. 1 is a diagram showing an example of the overall configuration of the encryption system 1 according to the present embodiment.

[0074] As shown in FIG. 1, the encryption system 1 according to the present embodiment includes a key generation apparatus 10, an encryption apparatus 20, and a decryption apparatus 30. These apparatuses are connected to one another in a communication-enabled manner via, for example, a communication network N, such as the Internet. Note that although the example of FIG. 1 depicts a case where one encryption apparatus 20 and one decryption apparatus 30 exist, the number of these apparatuses may be more than one each. Furthermore, the number of the key generation apparatus 10 may be more than one as well.

[0075] The key generation apparatus 10 is a computer or a computer system that generate a key by executing the setup algorithm Setup and the key generation algorithm KeyGen. Here, the key generation apparatus 10 includes a setup processing unit 101, a key generation processing unit 102, and a storage unit 103. Note that the setup processing unit 101 and the key generation processing unit 102 are implemented by processing that one or more programs installed in the key generation apparatus 10 causes a processor and the like to execute. Furthermore, the storage unit 103 can be implemented using, for example, various types of memories, such as an auxiliary storage device.

[0076] The setup processing unit 101 executes the setup algorithm Setup. The key generation processing unit 102 executes the key generation algorithm KeyGen. The storage unit 103 stores various types of data (e.g., a public key pk, a master private key msk, and the like output by the setup algorithm Setup).

[0077] The encryption apparatus 20 is a computer or a computer system that generates cyphertext by executing the encryption algorithm Enc. Here, the encryption apparatus 20 includes an encryption processing unit 201 and a storage unit 202. The encryption processing unit 201 is implemented by processing that one or more programs installed in the encryption apparatus 20 causes a processor and the like to execute. Furthermore, the storage unit 202 can be implemented using, for example, various types of memories, such as an auxiliary storage device.

[0078] The encryption processing unit 201 executes the encryption algorithm Enc. The storage unit 202 stores various types of data (e.g., data input to the encryption algorithm Enc and the like).

[0079] The decryption apparatus 30 is a computer or a computer system that decrypts cyphertext by executing the decryption algorithm Dec. Here, the decryption apparatus 30 includes a decryption processing unit 301 and a storage unit 302. The decryption processing unit 301 is implemented by processing that one or more programs installed in the decryption apparatus 30 causes a processor and the like to execute. Furthermore, the storage unit 302 can be implemented using, for example, various types of memories, such as an auxiliary storage device.

[0080] The decryption processing unit 301 executes the decryption algorithm Dec. The storage unit 302 stores various types of data (e.g., data input to the decryption algorithm Dec, data output from the decryption algorithm Dec, and the like).

[0081] Note that the configuration of the encryption system 1 shown in FIG. 1 is an example, and another configuration may be used. For example, the encryption apparatus 20 and the decryption apparatus 30 may be implemented in the same apparatus. In this case, this apparatus includes, for example, the encryption processing unit 201, the decryption processing unit 301, and a storage unit.

[0082] <Flow of Processing Executed by Encryption System 1>

[0083] The following describes a flow of processing executed by the encryption system 1 according to the present embodiment.

[0084] Key-Policy Attribute-Based Encryption According to Present Embodiment

[0085] When the encryption system 1 according to the present embodiment implements “key-policy attribute-based encryption according to the present embodiment”, the following Step 1-1 to Step 1-4 are executed.

[0086] (Step 1-1) The setup processing unit 101 of the key generation apparatus 10 executes the setup algorithm Setup of key-policy attribute-based encryption according to the present embodiment. As a result, a public key pk and a master private key msk are generated and output. These public key pk and master private key msk are stored in the storage unit 103. Also, the public key pk is made public.

[0087] (Step 1-2) The encryption processing unit 201 of the encryption apparatus 20 takes the public key pk, an attribute x, and a message M as inputs, and executes the encryption algorithm Enc of key-policy attribute-based encryption according to the present embodiment. As a result, cyphertext ct.sub.x with an attribute is output. The cyphertext ct.sub.x with the attribute is transmitted to the decryption apparatus 30 via, for example, the communication network N. The cyphertext ct.sub.x with the attribute may be stored in the storage unit 202.

[0088] (Step 1-3) The key generation processing unit 102 of the key generation apparatus 10 takes the public key pk, the master private key msk, and a policy y as inputs, and executes the key generation algorithm KeyGen of key-policy attribute-based encryption according to the present embodiment. As a result, a private key sk.sub.y with a policy is generated. The private key sk.sub.y with the policy is transmitted to the decryption apparatus 30 via, for example, the communication network N.

[0089] (Step 1-4) The decryption processing unit 301 of the decryption apparatus 30 takes the public key pk, the cyphertext ct.sub.x with the attribute, and the private key sk.sub.y with the policy as inputs, and executes the decryption algorithm Dec of key-policy attribute-based encryption according to the present embodiment. As a result, ⊥ indicating a decryption failure or a message M′ is output. This output result is stored in, for example, the storage unit 302.

[0090] Ciphertext-Policy Attribute-Based Encryption According to Present Embodiment

[0091] When the encryption system 1 according to the present embodiment implements “ciphertext-policy attribute-based encryption according to the present embodiment”, the following Step 2-1 to Step 2-4 are executed.

[0092] (Step 2-1) The setup processing unit 101 of the key generation apparatus 10 executes the setup algorithm Setup of ciphertext-policy attribute-based encryption according to the present embodiment. As a result, a public key pk and a master private key msk are generated and output. These public key pk and master private key msk are stored in the storage unit 103. Also, the public key pk is made public.

[0093] (Step 2-2) The encryption processing unit 201 of the encryption apparatus 20 takes the public key pk, a policy x, and a message M as inputs, and executes the encryption algorithm Enc of ciphertext-policy attribute-based encryption according to the present embodiment. As a result, cyphertext ct.sub.x with a policy is output. The cyphertext ct.sub.x with the policy is transmitted to the decryption apparatus 30 via, for example, the communication network N. The cyphertext ct.sub.x with the policy may be stored in the storage unit 202.

[0094] (Step 2-3) The key generation processing unit 102 of the key generation apparatus 10 takes the public key pk, the master private key msk, and an attribute y as inputs, and executes the key generation algorithm KeyGen of ciphertext-policy attribute-based encryption according to the present embodiment. As a result, a private key sk.sub.y with an attribute is generated. The private key sk.sub.y with the attribute is transmitted to the decryption apparatus 30 via, for example, the communication network N.

[0095] (Step 2-4) The decryption processing unit 301 of the decryption apparatus 30 takes the public key pk, the cyphertext ct.sub.x with the policy, and the private key sk.sub.y with the attribute as inputs, and executes the decryption algorithm Dec of ciphertext-policy attribute-based encryption according to the present embodiment. As a result, ⊥ indicating a decryption failure or a message M′ is output. This output result is stored in, for example, the storage unit 302.

[0096] Key-Policy Attribute-Based KEM According to Present Embodiment

[0097] When the encryption system 1 according to the present embodiment implements “key-policy attribute-based KEM according to the present embodiment”, the following Step 3-1 to Step 3-4 are executed.

[0098] (Step 3-1) The setup processing unit 101 of the key generation apparatus 10 executes the setup algorithm Setup of key-policy attribute-based KEM according to the present embodiment. As a result, a public key pk and a master private key msk are generated and output. These public key pk and master private key msk are stored in the storage unit 103. Also, the public key pk is made public.

[0099] (Step 3-2) The encryption processing unit 201 of the encryption apparatus 20 takes the public key pk and an attribute x as inputs, and executes the encryption algorithm Enc of key-policy attribute-based KEM according to the present embodiment. As a result, cyphertext ct.sub.x with an attribute and a common key L are output. The cyphertext ct.sub.x with the attribute is transmitted to the decryption apparatus 30 via, for example, the communication network N. The cyphertext ct.sub.x with the attribute may be stored in the storage unit 202. Also, the common key L is stored in the storage unit 202.

[0100] (Step 3-3) The key generation processing unit 102 of the key generation apparatus 10 takes the public key pk, the master private key msk, and a policy y as inputs, and executes the key generation algorithm KeyGen of key-policy attribute-based KEM according to the present embodiment. As a result, a private key sk.sub.y with a policy is generated. The private key sk.sub.y with the policy is transmitted to the decryption apparatus 30 via, for example, the communication network N.

[0101] (Step 3-4) The decryption processing unit 301 of the decryption apparatus 30 takes the public key pk, the cyphertext ct.sub.x with the attribute, and the private key sk.sub.y with the policy as inputs, and executes the decryption algorithm Dec of key-policy attribute-based KEM according to the present embodiment. As a result, ⊥ indicating a decryption failure or a common key K′ is output. This output result is stored in, for example, the storage unit 302.

[0102] Cyphertext-Policy Attribute-Based KEM According to Present Embodiment

[0103] When the encryption system 1 according to the present embodiment implements “cyphertext-policy attribute-based KEM according to the present embodiment”, the following Step 4-1 to Step 4-4 are executed.

[0104] (Step 4-1) The setup processing unit 101 of the key generation apparatus 10 executes the setup algorithm Setup of cyphertext-policy attribute-based KEM according to the present embodiment. As a result, a public key pk and a master private key msk are generated and output. These public key pk and master private key msk are stored in the storage unit 103. Also, the public key pk is made public.

[0105] (Step 4-2) The encryption processing unit 201 of the encryption apparatus 20 takes the public key pk and a policy x as inputs, and executes the encryption algorithm Enc of cyphertext-policy attribute-based KEM according to the present embodiment. As a result, cyphertext ct.sub.x with a policy and a common key L are output. The cyphertext ct.sub.x with the policy is transmitted to the decryption apparatus 30 via, for example, the communication network N. The cyphertext ct.sub.x with the policy may be stored in the storage unit 202. Also, the common key L is stored in the storage unit 202.

[0106] (Step 4-3) The key generation processing unit 102 of the key generation apparatus 10 takes the public key pk, the master private key msk, and an attribute y as inputs, and executes the key generation algorithm KeyGen of ciphertext-policy attribute-based KEM according to the present embodiment. As a result, a private key sk.sub.y with an attribute is generated. The private key sk.sub.y with the attribute is transmitted to the decryption apparatus 30 via, for example, the communication network N.

[0107] (Step 4-4) The decryption processing unit 301 of the decryption apparatus 30 takes the public key pk, the cyphertext ct.sub.x with the policy, and the private key sk.sub.y with the attribute as inputs, and executes the decryption algorithm Dec of ciphertext-policy attribute-based KEM according to the present embodiment. As a result, ⊥ indicating a decryption failure or a common key L′ is output. This output result is stored in, for example, the storage unit 302.

[0108] <Hardware Configuration of Key Generation Apparatus 10, Encryption Apparatus 20, and Decryption Apparatus 30>

[0109] Next, with reference to FIG. 2, a hardware configuration of the key generation apparatus 10, the encryption apparatus 20, and the decryption apparatus 30 included in the encryption system 1 according to the present embodiment, will be described. FIG. 2 is a diagram showing an example of the hardware configuration of the key generation apparatus 10, the encryption apparatus 20, and the decryption apparatus 30 according to the present embodiment. Note that as the key generation apparatus 10, the encryption apparatus 20, and the decryption apparatus 30 according to the present embodiment can be implemented by similar hardware configurations, the following mainly describes the hardware configuration of the key generation apparatus 10.

[0110] As shown in FIG. 2, the key generation apparatus 10 according to the present embodiment includes an input device 501, a display device 502, a RAM (Random Access Memory) 503, a ROM (Read Only Memory) 504, a processor 505, an external I/F 506, a communication I/F 507, and an auxiliary storage device 508. These items of hardware are connected to one another in a communication-enabled manner via a bus 509.

[0111] The input device 501 is, for example, a keyboard, a mouse, a touchscreen, and the like. The display device 502 is, for example, a display and the like. Note that the key generation apparatus 10, the encryption apparatus 20, and the decryption apparatus 30 may not include at least one of the input device 501 and the display device 502.

[0112] The RAM 503 is a volatile semiconductor memory that temporarily holds programs and data. The ROM 504 is a nonvolatile semiconductor memory that can hold programs and data even when the power is OFF. The processor 505 is, for example, a CPU (Central Processing Unit) and the like, and is a computation device that reads programs and data from the ROM 504, the auxiliary storage device 508, and the like into the RAM 503 and executes processing.

[0113] The external I/F 506 is an interface with an external apparatus. Examples of the external device include a recording medium 506a, such as a CD (Compact Disc), a DVD (Digital Versatile Disk), an SD memory card (Secure Digital memory card), a USB (Universal Serial Bus) memory card, and the like.

[0114] The communication I/F 507 is an interface for connecting to a communication network and communicating with another apparatus. The auxiliary storage device 508 is, for example, a nonvolatile storage device, such as an HDD (Hard Disk Drive) and an SSD (Solid State Drive).

[0115] The key generation apparatus 10, the encryption apparatus 20, and the decryption apparatus 30 according to the present embodiment have the hardware configuration shown in FIG. 2, and thus can implement various types of processing by executing each of the aforementioned algorithms. Note that although FIG. 2 shows a case in which the key generation apparatus 10, the encryption apparatus 20, and the decryption apparatus 30 according to the present embodiment are implemented by one apparatus (computer), no limitation is intended by this. The key generation apparatus 10, the encryption apparatus 20, and the decryption apparatus 30 according to the present embodiment may be implemented by a plurality of apparatuses (computers). Furthermore, one apparatus (computer) may include a plurality of processors 505 and a plurality of memories (e.g., RAMs 503, ROMs 504, and auxiliary storage devices 508).

SUMMARY

[0116] As described above, the encryption system 1 according to the present embodiment can implement “key-policy attribute-based encryption according to the present embodiment”, “ciphertext-policy attribute-based encryption according to the present embodiment”, “key-policy attribute-based KEM according to the present embodiment”, and “cyphertext-policy attribute-based KEM according to the present embodiment”. These encryption methods and KEM methods are based on techniques configuring a method called FAME, which is efficient but has low expressiveness compared to the OT method. See, for example, a document “S. Agrawal and M. Chase. FAME: Fast attribute-based message encryption. In ACM CCS, 2017.” for the details of FAME.

[0117] While FAME is an efficient configuration, FAME cannot use NOT in a conditional expression that expresses a policy. In contrast, the encryption methods according to the present embodiment (and the KEM methods that use the application of these encryption methods) are designed so as to allow NOT in a conditional expression and multiple appearances of attribute labels while retaining the characteristics where efficient operations are performed with reference to the structure of FAME. In this way, the encryption system 1 according to the present embodiment can implement attribute-based encryption (and KEM that uses this attribute-based encryption) which can use an arbitrary conditional expression as a policy without increasing the sizes of cyphertext and a private key, and which is efficient.

[0118] More specifically, in attribute-based encryption implemented by the encryption system 1 according to the present embodiment (and KEM that uses this attribute-based encryption), first of all, the number of group elements of the cyphertext and the private key is smaller compared to the OT method, and thus, the number of exponentiation calculations, which are relatively heavy calculations upon encryption and key generation, can be significantly reduced. Therefore, the calculation time for encryption and key generation can be reduced.

[0119] Furthermore, second, the number of pairing calculations, which are heavy calculations necessary upon decryption, is significantly reduced as well, and thus, decryption is also performed at a higher speed compared to the OT method. Especially, although the number of pairing calculations depends on a policy to be used, decryption can be performed at a speed that is faster by a factor equivalent to the number of variables of this policy or greater. For example, in a case where decryption processing is performed using cyphertext or a private key with a policy composed of 20 variables, speeding up of 20 times or greater can be achieved.

[0120] Furthermore, attribute-based encryption implemented by the encryption system 1 according to the present embodiment (and KEM that uses this attribute-based encryption) can use an arbitrary conditional expression as a policy without increasing the sizes of cyphertext and the key. That is to say, attribute labels may appear any number of times in a conditional expression.

[0121] The present invention is not limited to the foregoing embodiment that has been specifically disclosed, and a variety of modifications and changes can be made thereto without departing from the description of claims.

REFERENCE SIGNS LIST

[0122] 1 Encryption system [0123] 10 Key generation apparatus [0124] 20 Encryption apparatus [0125] 30 Decryption apparatus [0126] 101 Setup processing unit [0127] 102 Key generation processing unit [0128] 103 Storage unit [0129] 201 Encryption processing unit [0130] 202 Storage unit [0131] 301 Decryption processing unit [0132] 302 Storage unit