1
DESCRIPTION
Title of Invention:
DECRYPTION CONDITION ADDITION DEVICE, CRYPTOGRAPHIC SYSTEM, 5 AND DECRYPTION CONDITION ADDITION PROGRAM
Technical Field
[0001] The present invention relates to a technique for restricting a decryption
condition set in a ciphertext without decrypting the ciphertext. 10 Background Art
[0002] Functional encryption and attribute-based encryption are public key encryption
schemes according to which a set of users authorized to decrypt a ciphertext can be set
in the ciphertext with a logical expression composed of OR, AND, and NOT. That is,
functional encryption and attribute-based encryption are public key encryption schemes 15 according to which a deciyption condition of a ciphertext can be set in the ciphertext
with a logical expression composed of OR, AND, and NOT. Patent Literature 1
describes a functional encryption scheme.
[0003] There is a technique called proxy re-encryption according to which a
decryption condition set in a ciphertext can be changed using a re-encryption key 20 without decrypting the ciphertext. Non-Patent Literature 1 describes a proxy
re-encryption scheme in functional encryption. Non-Patent Literature 2 describes a
proxy re-encryption scheme in attribute-based encryption.
Citation List
Patent Literature 25 [0004] Patent Literature 1: WO 2011/135895 A

2
Non-Patent Literature
[0005] Non-Patent Literature 1: Yutaka Kawai and Katuyuki Takashima,
Fully-Anonymous Functional Proxy-Re-Encryption. Cryptology ePrint Archive: Report
2013/318
5 Non-Patent Literature 2: Junzuo Lai and Robert H. Deng and Yanjiang Yang
and Jian Weng. "Adaptable Ciphertext-Policy Attribute-Based Encryption"
Summary of Invention
Technical Problem
[0006] In the proxy re-encryption schemes described in Non-Patent Literature 1 and 10 Non-Patent Literature 2, a re-encryption key is always required to change the decryption
condition of the ciphertext.
In order to generate a re-encryption key, a user secret key or a master secret
key, which is a key that needs to be held in secrecy, is required. In the proxy
re-encryption schemes described in Non-Patent Literature 1 and Non-Patent Literature 15 2, the user secret key or the master secret key is accessed each time a re-encryption key
is generated, resulting in an increase in the number of accesses to the user secret key or
the master secret key.
It is an object of the present invention to allow a decryption condition of an
original ciphertext to be restricted without using a re-encryption key. 20 Solution to Problem
[0007] A decryption condition addition device according to the present invention
includes:
an original ciphertext acquisition part to acquire an original ciphertext in which
a secret distribution matrix is set as information specifying a decryption condition;
25 a condition acquisition part to acquire a restriction condition to restrict the

3
decryption condition of the original ciphertext acquired by the original ciphertext acquisition part; and
an updated ciphertext generation part to generate an updated ciphertext for which the decryption condition of the original ciphertext is restricted by adding a row 5 and a column which are related to the restriction condition acquired by the condition acquisition part to the secret distribution matrix set in the original ciphertext, Advantageous Effects of Invention
[0008] In the present invention, a decryption condition of an original ciphertext is restricted by adding a row and a column to a secret distribution matrix set in the 10 ciphertext. No re-encryption key is required in order to add the row and the column to the secret distribution matrix. Therefore, it is not necessary to use a re-encryption key to restrict the decryption condition of the original ciphertext. Brief Description of Drawings
[0009] Fig. 1 is an explanatory drawing of an access structure S used in functional 15 encryption;
Fig. 2 is an explanatory drawing of a submatrix M§;
Fig. 3 is an explanatory drawing of a secret value so of secret distribution;
Fig. 4 is an explanatory drawing of distributed values Si,..., SL of secret
distribution;
20 Fig. 5 is an explanatory drawing of an example of restricting a decryption
condition of a ciphertext;
Fig. 6 is a configuration diagram of a cryptographic system 10 according to a first embodiment;
Fig. 7 is a configuration diagram of a key generation device 100 according to 25 the first embodiment;

4
Fig. 8 is a configuration diagram of an encryption device 200 according to the first embodiment;
Fig. 9 is a configuration diagram of a decryption condition addition device 300
according to the first embodiment;
5 Fig. 10 is a configuration diagram of a decryption device 400 according to the
first embodiment;
Fig. 11 is a flowchart of a Setup algorithm according to the first embodiment;
Fig. 12 is a flowchart of a KG algorithm according to the first embodiment;
Fig. 13 is a flowchart of an Enc algorithm according to the first embodiment;
10 Fig. 14 is a flowchart of an ApdAND algorithm according to the first
embodiment;
Fig. 15 is an explanatory drawing of an additional access structure S+;
Fig. 16 is a flowchart of a Dec algorithm according to the first embodiment;
and
15 Fig. 17 is a diagram illustrating an example of a hardware configuration of
each device of the key generation device 100, the encryption device 200, the decryption condition addition device 300, and the decryption device 400 described in the first embodiment.
Description of Embodiments 20 [0010] First Embodiment
In a first embodiment, an example of applying a technique for restricting a deciyption condition of a ciphertext to ciphertext-policy functional encryption will be described. Restricting the decryption condition of the ciphertext means reducing the number of keys that can decrypt the ciphertext. 25 [0011] ***Description of Notations***

5
Notations to be used in the following description will be described.
When A is a random value 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. 5 [Formula 101]
y< A
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. 10 [Formula 102]
y< A
Formula 103 denotes that z is set to y, y is defined by z, or y is substituted b]
[Formula 103] 15 y~Z
When a is a fixed value, Formula 104 denotes that a machine (algorithm) A outputs a on input x. [Formula 104] 20 A{x) -> a For example,
A(x) -> 1

6
Formula 105 denotes a field of order q. [Formula 105]
F*
5 Formula 106 denotes a vector representation in a finite field Fq.
[Formula 106] X denotes
(xh...,xn)e¥l
10 Formula 107 denotes the inner-product, indicated in Formula 109, of two
vectors x~~* and v~* indicated in Formula 108. [Formula 107]
x-v

15 [Formula 108]
X — (X] ,..., Xn ) ,
v = (vi,...,v?z)
[Formula 109]
20 YLXiVi
Note that X denotes the transpose of a matrix X.
For a basis B and a basis B indicated in Formula 110, Formula 311 is

7
established. [Formula 110]
M:=(by,...,bN\ B*:=(6T,...^)
5 [Formula 111]
OI,---5*AT)B :=zli=ixibi>
(«v,W)B,:=I/=iM*
Note that e-^ denotes a normal basis vector indicated in Formula 112. [Formula 112]
j-\ n-j
io e/:(0---0 ,1, 0--0)eF» for/ = lv..,n
[0012] ***Description of Overview***
The basics of ciphertext-policy functional encryption will be described, and then an overview of the technique for restricting the decryption condition of the 15 ciphertext will be described.
[0013] The basics of ciphertext-policy functional encryption will be described.
Fig. 1 is an explanatory drawing of an access structure S used in functional encryption.
In functional encryption, a combination of an L-row and r-column secret 20 distnbution matrix M and a label p given to each row of the secret distribution matrix M is used as an access structure S. The label p given to each row is related to one literal

8
of positive literals {pj,..., pn} and negative literals {-ipi, ■-., ->pn} which are given by a set of variables {pi,..., pn}.
[0014] For an input sequence 5 = 5; e {0, 1} (i = 1,..., n), a submatrix M§ of the secret distribution matrix M is defined. The submatrix M5 consists of those rows of the 5 secret distribution matrix M the labels p of which are related to a value "1" by the input sequence 5. That is, the submatrix Ms consists of the rows of the secret distribution matrix M which are related to pi such that 5; = 1 and the rows of the secret distribution matrix M which are related to —«pi such that 8, = 0. [0015] Fig. 2 is an explanatory drawing of the submatrix Mg.
10 In Fig. 2, note that n = 7, L= 6, and r = 5. That is, the set of variables is {pi,
..., p?}, and the matrix Mhas six rows and five columns. In Fig. 2, assume that the labels p are related such that pi is related to -ip2, p2 to pi, p3 to p4, p4 to —ips, ps to —ip3, and p6 to p5.
Assume that in the input sequence 5, 8i = 1, S2 = 0, 83 = 1, 84 = 0, 65 = 0, S6 =
15 1, and 87 = 1. hi this case, the submatrix M5 consists of the rows of the secret distribution matrix M which are related to literals (p;, p3, p6, p?, -ip2, —ip4s ""Ps) surrounded by broken lines. That is, the submatrix M5 consists of the first row (Mi), second row (M2), and fourth row (M4) of the secret distribution matrix M. [0016] When [p(j) - Pi] A [8; - 1] or [p(j) - -.Pi] A [8, = 0], then map YG) = 1;
20 otherwise map y(j) = 0. In this case, it can be represented as M8 := (Mj)y(j)=i- Note that Mj is row j of the matrix M.
[0017] In functional encryption, each variable p of the set of variables in the access structure S is defined by a tuple (t, v-^) of an identifier t and a vector v~Y When an attribute set F which is a tuple (t, x""t) of the identifier t and a vector x~\ is given to the
25 access structure S, the map y(i) is defined such that when [p(i) = (t, v~*i)] A [(t, x_>,) e F]

9
A [v^i-x^t = 0] or [p(i) = -, (t, v~*i)] A [(t, x"*t) e T] A [v^-x^t ^ 0], then y(j) = 1; otherwise y(j) = 0.
That is, in junctional encryption, the map y(i) is computed based on the inner-product of the vector v^j and the vector x~\. Then, as described above, which 5 row of the secret distribution matrix M is included in the submatrix M§ is decided by the map 7(i).
[0018] The access structure S accepts the attribute set T only if 1~* is obtained as a result of linear combination of the rows of the submatrix Mg. Note that 1~* is a row vector in which every element is 1.
10 For example, in the example of Fig 2, the access structure S accepts the
attribute set T only if 1~* is obtained as a result of linear combination of the rows of the submatrix Ms consisting of the first, second, and fourth rows of the secret distribution matrix M. That is, the access structure S accepts the attribute set F if there exist coefficients cti, ci2, and a4 with which ai(Mi) + ot2 (M2) + 04(^4) = 1"*.
15 In other words, when the set of the row numbers of the secret distribution
matrix included in the submatrix Ms is defined as I, the access structure S accepts the attribute set T if there exists a coefficient 04 with which Sie!aiMi = 1"". [0019] hi ciphettext-policy functional encryption, a key element k t in which a vector x~*t is set is generated for the identifier t included in the attribute set T representing the
20 attribute of the user. Then, a user secret key skp which includes the key element k t for each identifier t included in the attribute set T and t = 0 is generated.
The identifier t is related to an attribute category and an attribute in the attribute category related to the identifier t is set in the vector x~V The attribute category is a classification of attributes, such as belonging department, gender, and age.
25 For example, when the identifier t is related to the belonging department, a value

10
indicating the belonging department of the user of the user secret key skr is set in the vector x~\-
[0020] In ciphertext-policy functional encryption, a distributed value s; of secret distribution is assigned to row i in the secret distribution matrix M of the access 5 structure S for each integer i - 1,..., L. Then, a cipher element c; in which the
assigned distributed value s; and a vector v~*j are set is generated for each row i of the secret distribution matrix M. A cipher element c0 in which a secret value So computed from the set of the distributed value S; satisfying a condition is also generated. A cipher element Cd+i in which a message m is encrypted using a session key K is also
10 generated. Then, an original ciphertext cts which includes the cipher element c; for each integer i = 0,... L, d+1 and the access structure S is generated. [0021] In ciphertext-policy functional encryption, a pairing operation is performed on the key element k t for the identifier t included in the attribute set T and the cipher element q identified by the label p(i) having the identifier t. By performing the pairing
15 operation, the inner-product of the vector v^i and the vector x~~\ is computed, and the map y(i) is computed. Then, which row of the secret distribution matrix M is included in the submatrix M5 is decided.
Then, if the access structure S accepts the attribute set F, the set of the distributed value Sj satisfying the condition is extracted and the secret value so is
20 computed. The session key K is generated from the key element k'o, the cipher
element c0) and the secret value so- The message m is computed with the session key K.
[0022] Fig. 3 is an explanatory drawing of the secret value so of secret distribution. The secret value so is a sum of elements of a product of a row vector having 1
25 in all of r elements and a column vector f having r elements f), ..., fr. Note that each

11
element of the column vector f is a uniform random number.
[0023] Fig. 4 is an explanatory drawing of the distributed values Si,..., SL of secret
distribution.
The distributed values s1; ..., sL are a product of the secret distribution matrix M 5 and the column vector f. A column vector s is a vector whose elements are the
distributed values Si,..., SL.
[0024] As described above, if the access structure S accepts the attribute set F, there
exists the coefficient a; with which ZjeiaiMj = 1~\ The coefficient a, can be computed
in polynomial time in the size of the secret distribution matrix M. Then, when the 10 coefficient aj is used, ^gic^s; = So is obtained according to the definitions of the secret
value So and the distributed values Si,..., sL.
[0025] An overview of the technique for restricting the decryption condition of the
ciphertext will be described.
As described above, the original ciphertext cts includes the cipher element c0 in 15 which the secret value so is set, the cipher element Cj for each integer i = 1,..., Lin
which the distributed value s; and the vector v~*j are set, the cipher element Cd+i in which
the message m is encrypted, and the access structure S.
Then, the decryption condition of the original ciphertext cts is specified by the
secret distribution matrix M included in the access structure S and the cipher element Cj 20 which is set for each row of the secret distribution matrix M.
[0026] In the first embodiment, the decryption condition of the original ciphertext cts
is restricted by adding a row and a column to the secret distribution matrix M included
in the original ciphertext cts and adding a cipher element CJ related to the added row.
[0027] Fig. 5 is an explanatory drawing of an example of restricting the decryption 25 condition of the ciphertext.

12
In the original ciphertext cts, (department = administration department) AND (section = personnel section) is set as the decryption condition.
In this case, the secret distribution matrix M has two rows and two columns, and the first row is related to the department and the second row is related to the section. 5 Then, the label p(l) of the first row is related to a positive tuple (department := t], administration department :- v~'i), and the label p(2) of the second row is related to a positive tuple (section :- t2, personnel section := v-^).
The distributed value si and administration department := v~*i are set in the cipher element ci related to the first row of the secret distribution matrix M, and the 10 distributed value s2 and personnel section := v*-^ are set in the cipher element c2 related to the second row.
[0028] Assume here, for example, that the user secret key skr of the user with ID =1001 needs to be invalidated. In this case, ID = 1001 may be removed from the decryption condition. This can be realized by adding NOT (ID = 1001) as an AND 15 condition to the decryption condition of the original ciphertext cts.
That is, the decryption condition may be set as (department = administration department) AND (section = personnel section) AND (NOT (ID = 1001)). [0029] Therefore, in an updated ciphertext cts1 which is the updated original ciphertext cts, the third row and the third column are added to the secret distribution matrix M, and 20 the third row is related to the user ID. Then, the label p(3) of the third row is related to a negative tuple (ID :=t3, 1001 := v"*3).
The distributed value s3 and 1001 :=v~*3 in negative form are set in the cipher element c3 related to the third row of the secret distribution matrix M.
With this arrangement, the decryption condition can be set as (department = 25 administration department) AND (section = personnel section) AND (NOT (3D =

13
1001)).
[0030] ***Description of Configuration***
Fig. 6 is a configuration diagram of a cryptographic system 10 according to the
first embodiment.
5 The cryptographic system 10 has a key generation device 100, an encryption
device 200, a decryption condition addition device 300, and a decryption device 400. [0031] The key generation device 100 executes a Setup algorithm taking as input an attribute format n~* and a security parameter X, and thereby generates a public key pk and a master secret key msk. The key generation device 100 also executes a KG
10 algorithm taking as input the public key pk, the master secret key msk, and a user attribute set F, and thereby generates a user secret key skp.
Then, the key generation device 100 publishes the public key pk. The key generation device 100 outputs the user secret key skr- to the decryption device 400 in secrecy.
15 [0032] The encryption device 200 executes an Enc algoritlim taking as input the public key pk, an access structure S, and a message m, and thereby generates an original ciphertext cts in which the message m is encrypted and a secret distribution matrix M is set as information specifying a decryption condition. The encryption device 200 outputs the original ciphertext cts to the decryption condition addition device 300.
20 [0033] The decryption condition addition device 300 executes an ApdAND algorithm taking as input the public key pk, the original ciphertext cts, and an additional access structure S , and thereby generates an updated ciphertext etsp for which the decryption condition of the original ciphertext cts is restricted. If the updated ciphertext cts- has been generated, the decryption condition addition device 300 outputs the updated
25 ciphertcxt ct$' to the decryption device 400. If the updated ciphertext cts* has not been

14
generated, the decryption condition addition device 300 outputs the original ciphertext cts to the decryption device 400.
Specifically, the decryption condition addition device 300 acquires the additional access structure S+ which is a restriction condition to restrict the decryption 5 condition of the original ciphertext cts generated by the encryption device 200, and adds a row and a column which are related to the restriction condition to the secret distribution matrix M being set in the original ciphertext cts, and thereby generates the updated ciphertext cts* for which the decryption condition of the original ciphertext cts is restricted.
10 [0034] The decryption device 400 executes a Dec algorithm taking as input the public key pk, the user secret key skr, and the original ciphertext cts generated by the encryption device 200 or the updated ciphertext ctS' generated by the decryption condition addition device 300, and thereby decrypts the original ciphertext cts generated by the encryption device 200 or the updated ciphertext cts1 generated by the decryption
15 condition addition device 300. The decryption device 400 outputs the message m or a symbol X indicating a decryption failure.
[0035] Fig. 7 is a configuration diagram of the key generation device 100 according to the first embodiment.
The key generation device 100 has an information acquisition part 110, a
20 master key generation part 120, a user secret key generation part 130, and a key output part 140.
[0036] The information acquisition part 110 acquires an attribute format n~\ a security parameter X, and an attribute set F which are input by an administrator of the cryptographic system 10. The master key generation part 120 generates a master
25 secret key msk and a public key pk based on the attribute format n~* and the security

15
parameter X acquired by the information acquisition part 110. The user secret key generation part 130 generates a user secret key skr based on the attribute set T acquired by the information acquisition part 110 and the master secret key msk and the public key pk generated by the master key generation part 120. The key output part 140 5 outputs the public key pk to a server for publication or the like so as to publish the public key pk, and outputs in secrecy the user secret key skr to the decryption device 400 used by the user. Outputting in secrecy means, for example, transmitting after encrypting by an existing encryption scheme. [0037] Fig. 8 is a configuration diagram of the encryption device 200 according to the
10 first embodiment.
The encryption device 200 has an information acquisition part 210, a ciphertext generation part 220, and a ciphertext output part 230.
[0038] The information acquisition part 210 acquires the public key pk generated by the key generation device 100 as well as an access structure S and a message m which
15 are input by the user of the encryption device 200. The ciphertext generation part 220 generates an original ciphertext cts in which the message m is encrypted based on the public key pk, the access structure S, and the message m acquired by the information acquisition part 210. The ciphertext output part 230 outputs the original ciphertext cts generated by the ciphertext generation part 220 to the decryption condition addition
20 device 300.
[0039] Fig. 9 is a configuration diagram of the decryption condition addition device 300 according to the first embodiment.
The decryption condition addition device 300 has an information acquisition part 310, an updated ciphertext generation part 320, a ciphertext storage part 330, and a
25 ciphertext output part 340.

16
[0040] The information acquisition part 310 has a public key acquisition part 311, an original ciphertext acquisition part 312, and a condition acquisition part 313.
The public key acquisition part 311 acquires the public key pk generated by the key generation device 100. The original ciphertext acquisition part 312 acquires the 5 original ciphertext cts generated by the encryption device 200. The condition acquisition part 313 acquires an additional access structure S+ which is a restriction condition to restrict the decryption condition of the original ciphertext cts. [0041] The updated ciphertext generation part 320 generate an updated ciphertext cts> by restricting the decryption condition of the original ciphertext cts acquired by the
10 original ciphertext acquisition part 312 with the additional access structure S+ acquired by the condition acquisition part 313, based on the public key pk acquired by the public key acquisition part 311.
The updated ciphertext generation part 320 has an access structure updating part 321, a distributed value generation part 322, an additional cipher element
15 generation part 323, and a cipher element updating part 324.
[0042] The ciphertext storage part 330 is a storage device to store the original ciphertext cts acquired by the original ciphertext acquisition part 312. If the updated ciphertext generation part 320 has generated the updated ciphertext cts- from the original ciphertext cts, the ciphertext storage part 330 deletes the original ciphertext cts and
20 stores the updated ciphertext cts-.
[0043] If requested by the decryption device 400, the ciphertext output part 340 outputs the original ciphertext cts or the updated ciphertext cts> stored in the ciphertext storage part 330 to the decryption device 400. [0044] Fig. 10 is a configuration diagram of the decryption device 400 according to
25 the first embodiment.

17
The decryption device 400 has an information acquisition part 410, a ciphertext determination part 420, a decryption part 430, and a result output part 440. [0045] The information acquisition part 410 acquires the public key pk and the user secret key skp generated by the key generation device 100 and either one of the original 5 ciphertext cts generated by the encryption device 200 and the updated ciphertext cts-generated by the decryption condition addition device 300. The ciphertext determination part 420 determines whether or not the ciphertext acquired by the information acquisition part 410 can be decrypted with the user secret key skp If the ciphertext determination part 420 has determined, based on the public key pk, that 10 decryption is possible, the decryption part 430 decrypts the ciphertext acquired by the information acquisition part 410 with the user secret key skr-. If the ciphertext determination part 420 has determined that decryption is possible, the result output part 440 outputs a result of decryption by the decryption part 430. If the ciphertext determination part 420 has determined that decryption is not possible, the result output 15 part 440 outputs a symbol J_ indicating a decryption failure. [0046] ***Description of Operation***
Fig. 11 is a flowchart of the Setup algorithm according to the first embodiment.
The Setup algorithm is executed by the key generation device 100.
[0047] (S101: Information Acquisition Process)
20 The information acquisition part 110 acquires an attribute format n-*: = (d;
ni , ..., nj)ijry,-(X})-K

N.
bt,i :==E ik Xtj,jatj^t :=(^,b".A,JV,)>

N,
param„:={paramV(}f=0)itt)rf,
return param,7,gr,{B^n^0,...,fy),5)> Mt:=(bt>l,...>bt>nt9btiNt)fort = l,...9d
5
The master key generation part 120 generates a public key pk by putting together the subbasis BA0, the subbasis BAt, the security parameter X input in S101, and paramn generated in SI01.
[0050] (S104: Master Secret Key Generation Process)
10 The master key generation part 120 generates a subbasis BA 0 of the basis B o
generated in S102 and a subbasis BA t for each integer t - 1,..., d, as indicated in Formula 115. [Formula 115]
^O^ (^0,1^0,2^0,4),
B* := (^lv--,^v^+b--.,bl3nt)fort = l,...,d
15
The master key generation part 120 generates a master secret key msk constituted by the subbasis BA 0 and the subbasis BA t. [0051] (SI05: Key Output Process)
The key output part 140 outputs the public key pk generated in SI03 to the 20 server for publication or the like so as to publish the public key pk.
[0052] Fig. 12 is a flowchart of the KG algorithm according to the first embodiment.

20
The KG algorithm is executed by the key generation device 100. [0053] (S201: Information Acquisition Process)
The information acquisition part 110 acquires a user attribute set F which is input by the administrator or the like of the cryptographic system 10 with an input 5 device.
The attribute set T is a tuple (t, x~\) of an identifier t and a vector x"'t. The
identifier t is related to an attribute category, and an attribute in the attribute category
related to the identifier t is set in the vector x~\.
[0054] (S202: Random Number Generation Process)
10 The user secret key generation part 130 generates random numbers, as
indicated in Formula 116. [Formula 116]
9t<^—W* for (t,xt)er
15 [0055] (S203: Key Element Generation Step)
The user secret key generation part 130 generates a key element k 0 and a key element k t for each identifier t included in the attribute set T, based on the attribute set T acquired in S201 and the random numbers generated in S202, as indicated in Formula 117.

21
[Formula 117]
^:=(l,£,0,^o,O)Bj5
k*:^(S5ct, 0nt, 0"' > °"' > % )B( > if>(0^,vf),
nt nt nt 1
q:=( stvu 0nt, 0"/, 77£ )B/J
cd+\:=m-Sr
As indicated in Formula 120, the secret value s0 is set in the cipher element CQ. 5 The distributed value Sj and a vector v-"; are set in the cipher element Ci for each integer i — 1,..., L. How a value is set in the cipher element c, varies depending on whether the label p(i) is related to positive (t, v~*j) or related to negative -i (t, v~*;). In the cipher element Cd+], the message m is encrypted with the session key K. [0062] (S305: Ciphertext Output Process)
10 The ciphertext output part 230 outputs an original ciphertext cts which includes
the access structure S acquired in S301 and the cipher clement Cj for each integer i = 0, ..., L, d+1 generated in S304 to the decryption condition addition device 300. [0063] Fig. 14 is a flowchart of the ApdAND algorithm according to the first embodiment.
15 The ApdAND algorithm is executed by the decryption condition addition
device 300.

24
[0064] (S401: Public Key Acquisition Process)
The public key acquisition part 311 acquires the public key pk generated by the key generation device 100.
[0065] (S402: Original Ciphertext Acquisition Process)
5 The original ciphertext acquisition part 312 acquires the original ciphertext cts
generated by the encryption device 200. As described above, in the original ciphertext cts, the access structure S which includes the secret distribution matrix M and the label p is set as the information specifying the decryption condition. In the original ciphertext ctS) the cipher element a indicating an attribute is also set for each row of the secret 10 distribution matrix M, as the information specifying the decryption condition, in
addition to the access structure S which includes the secret distribution matrix M and the label p.
The acquired original ciphertext cts is stored in the ciphertext storage part 330.
[0066] (S403: Condition Acquisition Process)
15 The condition acquisition part 313 acquires an additional access structure S+
which is a restriction condition to restrict the decryption condition of the original ciphertext cts acquired by the original ciphertext acquisition part 312.
The additional access structure S+ includes an additional matrix M+ in which values are set only in elements of the row and column to be added to the secret 20 distribution matrix M included in the access structure S and includes the label p(L+i) given to the added row. [0067] Fig. 15 is an explanatory drawing of the additional access structure S+.
Fig. 15 illustrates a case where rows L+l to L+p and columns r+1 to r+p are
added.
25 In the additional matrix M"', an element at row L+i and column r+i for each

25
integer i - 1,..., p is 1 and other elements are 0.
For each integer i = 1,..., p, the label p(L+i) is given to row L+i. The label p(L+i) is related to one of literals ((t, v~*i,+i), (f, V~*L+0, -, -> (t, v~*L+i), and -i (f, v~*L+i)» ■■■)- That 1S> eacn label P(L+i) is related to a tuple of the identifier t indicating 5 an attribute category and the vector v~\+i representing an attribute in the attribute category indicated by the identifier t.
[0068] A case will be described here, where the updated ciphertext generation part 320 adds one row and one column for one restriction condition, and then arranges the elements of the added row such that elements other than an element at the added column
10 are 0, and arranges the elements of the added column such that elements other than an element at the added row are 0. Specifically, as illustrated in Fig. 15, a case will be described, where when adding rows L+l to L+p and columns r+1 to r+p, where L, r, and p are positive integers, the updated ciphertext generation part 320 arranges the elements of the added row and column such that the element at row L+i and column r+i for each
15 integer i = 1, ..., p is 1 and other elements are 0.
However, the number of rows to be added and the number of columns to be added are set according to the design of the access structure, and may be other than one for one restriction condition. Similarly, the values assigned to the elements of the added row and column are to be set according to the design of the access structure, and
20 may be decided arbitrarily according to the design of the access structure.
[0069] In the additional matrix M+ in the additional access structure S+, only the number p of rows and columns to be added may be set, and the values of the elements of the added row and column may not need to be set. This is because 1 is set in the element at row L+i and column r+i for each integer i = 1,..., p and 0 is set in other
25 elements, so that it is sufficient that the number p of rows and columns to be added be

26
known.
[0070] (S404: Access Structure Updating Process)
The access structure updating part 321 adds row L+i and column r+i for each
integer i = 1, ..., p, indicated in the additional matrix M+ of the additional access .
5 structure S+ acquired in S403, to the secret distribution matrix M of the access structure
S included in the original ciphertext cts acquired in S402, and thereby generates a secret
distribution matrix M'. The access structure updating part 321 also gives the label
p(L+i) of the additional access structure S+ to the added row L+i for each integer i =
1, ..., p of the secret distribution matrix M10 In this way, the access structure updating part 321 updates the access structure
S := (M, p) to the access structure S1 := (M\ p'). [0071 ] (S405: Distributed Value Generation Process)
The distributed value generation part 322 generates a distributed value s; for each integer i = L+l,..., L+p, as indicated in Formula 121. 15 [Formula 121]
R
st< F^ fori-L + l,...,L + p
[0072] (S406: Additional Cipher Element Generation Process)
The additional cipher element generation part 323 generates an additional 20 cipher element c, for each integer i = L+l, ..., L+p, based on the public key pk acquired in S401 and the distributed value sL+i generated in S405, as indicated in Formula 122.

27
[Formula 122]
fori = L + \,...,L + p,
if p(i) = (t,Vi), 0i,7?i
«, "/ "/
1

ci
,-:=( *v„ 0% 0% % )B

[0073] (S407: Cipher Element Updating Process)
The cipher element updating part 324 updates the cipher element Co included in the original ciphertext cts acquired in S402, based on the public key pk acquired in S401 and the distributed value SL+i of the additional access structure S+ acquired in S403, as indicated in Formula 123. [Formula 123]
c0 := c0 + (0, -£ f^j ^.,0,0,
As indicated in Formula 123, by updating the cipher element Co, the secret value so is updated with the added distributed value SL+J-
The distributed value sL+i for each integer i = 1, ..., p is added to the secret value so here. However, the method for updating the secret value so depends on the stmcture of the secret distribution matrix M'. Since it is arranged here that the element at row L+i and column r+i for each integer i = 1, ..., p is 1 and other elements are 0 in

28
the additional matrix M , consistency is achieved by adding the distributed value SL+i for
each integer i = 1,..., p to the secret value so-
[0074] (S408: Ciphertext Updating Process)
The ciphertext storage part 330 stores an updated ciphertext cty which includes 5 the access structure S' updated in S404, the cipher element c; for each integer i = 1,..., L
included in the original ciphertext cts acquired in S402, the additional cipher element
cL+i for each integer i — 1,..., p generated in S406, and the cipher element c0 updated in
S407, by overwriting the original ciphertext cts.
[0075] If requested by the decryption device 400, the ciphertext output part 340 10 outputs the original ciphertext cts or the updated ciphertext cts1 stored by the ciphertext
storage part 330 to the decryption device 400.
[0076] The process from S404 to S408 will be collectively referred to as an updated
ciphertext generation process.
In the updated ciphertext generation process, the updated ciphertext generation 15 part 320 adds each row and column related to each restriction condition acquired by the
condition acquisition process to the secret distribution matrix M set in the original
ciphertext cts acquired by the original ciphertext acquisition process. Then, the
updated ciphertext generation part 320 additionally sets, for each added row, the cipher
element c, which is related to an attribute category and in which an attribute in the 20 attribute category is set, and thereby generates the updated ciphertext cts' for which the
decryption condition of the original ciphertext cts is restricted.
[0077] Fig. 16 is a flowchart of the Dec algorithm according to the first embodiment. The Dec algorithm is executed by the decryption device 400.
[0078] (S501: Information Acquisition Process)
25 The information acquisition part 410 acquires the public key pk and the user

29
secret key skr generated by the key generation device 100.
The information acquisition part 410 outputs a request to the decryption condition addition device 300, and acquires a ciphertext cts^ from the decryption condition addition device 300. The ciphertext cts* is the original ciphertext cts or the 5 updated ciphertext cts'. It is assumed here that the ciphertext cts* includes an access structure SA and a cipher element Cj for each integer i - 1,..., L', d+1. [0079] (S502: Ciphertext Determination Process)
The ciphertext determination part 420 determines whether or not the access structure SA included in the ciphertext cts* acquired in S501 accepts the attribute set F 10 included in the user secret key skr acquired in S501.
If the ciphertext determination part 420 determines acceptance, the ciphertext determination part 420 advances the process to S503. If the ciphertext detennination part 420 determines non-acceptance, the ciphertext determination part 420 advances the process to S506. 15 [0080] (S503: Interpolation Coefficient Computation Process)
The decryption part 430 computes a set I of row numbers and a complementary coefficient {ot,}iei such as indicated in Formula 124. [Formula 124]
where A/z- is the z'-th row of M,
and/cz {i e {l,...,L}\[p(i) ~ (t,Vj) A(t,xt) GF AVZ- -xt = 0]
v[p(i) = -{t^i) A (t9xt) e T A vrxt* 0]}
20
[0081] (S504: Session Key Computation Process)

30
The decryption part 430 computes Formula 125 based on the ciphertext ctSA and the user secret key skr acquired in S501 and the set I and the complementary coefficient {aj}iei computed in S503, and thereby computes a session key K. [Formula 125]
K:=e(c0,k*). fl (7,v.)
5 • Yl e(chkf)aM-Xt)
[0082] (S505: Message Computation Process)
The decryption part 430 divides the cipher element Q+I included in the ciphertext cts* by the session key K computed in S504, and thereby computes the 10 message m.
[0083] (S506: Result Output Process)
If acceptance is determined in S502, the result output part 440 outputs the message m computed in S505. If non-acceptance is determined in S502, the result output part 440 outputs a symbol X indicating a decryption failure. 15 [0084] ***Description of Effects***
As described above, in the cryptographic system 10 according to the first
embodiment, the decryption condition can be restricted by adding information to the
access structure S included in the original ciphertext cts and also adding the cipher
element c,.
20 Adding information to the access structure S and adding the cipher element Cj
can be implemented with only the ciphertext cts and the public key pk, and a special ke such as a re-encryption key is not required. Therefore, it is not necessary to use a

31
re-encryption key to restrict the decryption condition of the original ciphertext cts. [0085] When a particular user secret key is invalidated, for example, the decryption condition needs to be restricted promptly. In the cryptographic system 10 according to the first embodiment, the decryption condition can be restricted without generating a 5 re-encryption key, so that the decryption condition can be restricted promptly.
[0086] In the above description, it has been described that the decryption condition of the original ciphertext cts is restricted in the ApdAND algorithm. In the ApdAND algorithm, however, it is also possible to further restrict the decryption condition of the updated ciphertext cts'. In this case, the updated ciphertext cts- may be acquired in
10 S402, in place of the original ciphertext cts.
[0087] In the above description, the example of applying the technique for restricting the decryption condition of the ciphertext to ciphertext-policy functional encryption has been described. Ciphertext-policy attribute-based encryption also uses a secret distribution matrix. Therefore, the technique for restricting the decryption condition of
15 the ciphertext by adding a row and a column to the secret distribution matrix, as
described above, can also be applied to ciphertext-policy attribute-based encryption. [0088] Fig. 17 is a diagram illustrating an example of a hardware configuration of each device of the key generation device 100, the encryption device 200, the decryption condition addition device 300, and the decryption device 400 described in the first
20 embodiment.
Each device is a computer. Each element of each device can be implemented by a program so as to constitute a data display program.
As the hardware configuration of each device, an arithmetic device 901, an external storage device 902, a main storage device 903, a communication device 904,
25 and an input/output device 905 are connected to a bus.

32
[0089] The arithmetic device 901 is a CPU (Central Processing Unit) and the like to execute programs. The external storage device 902 is, for example, a ROM (Read Only Memory), a flash memory, a hard disk device, and the like. The main storage device 903 is, for example, a RAM (Random Access Memory) and the like. The 5 communication device 904 is, for example, a communication board and the like. The input/output device 905 is, for example, a mouse, a keyboard, a display device, and the like.
[0090] The programs are normally stored in the external storage device 902, and are loaded into the main storage device 903 to be sequentially read and executed by the 10 arithmetic device 901.
The programs are those that implement the functions each described as the "... part".
Further, the external storage device 902 stores an operating system (OS), and at least part of the OS is loaded into the main storage device 903. The arithmetic device 15 901 executes the above programs while executing the OS.
Information and the like described as being acquired, generated, output, and so on by the "... part" in the description of the first embodiment are stored in the main storage device 903 as files. Reference Signs List 20 [0091] 10: ciypto graphic system; 100: key generation device; 110: information acquisition part; 120: master key generation part; 130: user secret key generation part; 140: key output part; 200: encryption device; 210: information acquisition part; 220: ciphertext generation part; 230: ciphertext output part; 300: decryption condition addition device; 310: information acquisition part; 31 i: public key 25 acquisition part; 312: original ciphertext acquisition part; 313: condition acquisition

33
part; 320: updated ciphertext generation part; 321: access structure updating part, 322: distributed value generation part; 323: additional cipher element generation part; 324: cipher element updating part; 330: ciphertext storage part; 340: ciphertext output part; 400: decryption device; 410: information acquisition part; 420: 5 ciphertext determination part; 430: decryption part; 440: result output part; A: canonical basis; B, B : basis; BA, B A: subbasis; msk: master secret key; pk: public key; F: attribute set; M: secret distribution matrix; p: label; S, S1: access structure; S+: additional access structure; m: message; skr: user secret key; cts: original ciphertext; cts1: updated ciphertext; t: identifier; k\: key element; c;: 10 cipher element; s: distributed value

34
CLAIMS
[Claim 1] A decryption condition addition device comprising:
an original ciphertext acquisition part to acquire an original ciphertext in which 5 a secret distribution matrix is set as information specifying a decryption condition;
a condition acquisition part to acquire a restriction condition to restrict the decryption condition of the original ciphertext acquired by the original ciphertext acquisition part; and
an updated ciphertext generation part to generate an updated ciphertext for 10 which the decryption condition of the original ciphertext is restricted by adding a row and a column which are related to the restriction condition acquired by the condition acquisition part to the secret distribution matrix set in the original ciphertext.
[Claim 2] The decryption condition addition device according to claim 1,
15 wherein the updated ciphertext generation part arranges elements of the added
row such that an element other than an element at the added column is 0, and arranges elements of the added column such that an element other than an element at the added row is 0.
20 [Claim 3] The decryption condition addition device according to claim 2,
wherein the updated ciphertext generation part adds one row and one column for one restriction condition.
[Claim 4] The decryption condition addition device according to claim 3,
25 wherein when the updated ciphertext generation part adds rows L+l to L+p

35
and columns r+1 to r+p to the secret distribution matrix with L rows and r columns, where L, r, and p are positive integers, the updated ciphertext generation part arranges elements of the added rows and columns such that an element at row L+i and column r+i for each integer i - 1, ..., p is 1 and other elements are 0. 5
[Claim 5] The decryption condition addition device according to any one of claims 1 to
4,
wherein in the original ciphertext, a cipher element indicating an attribute is set for each row of the secret distribution matrix as the information specifying the 10 decryption condition, in addition to the secret distribution matrix,
wherein the condition acquisition part acquires an attribute category and an attribute in the attribute category as the restriction condition, and
the updated ciphertext generation part generates the updated ciphertext by additionally setting a cipher element to the original ciphertext, the cipher element being 15 related to the attribute category acquired by the condition acquisition part, and the attribute in the attribute category being set in the cipher element.
[Claim 6] A crypto graphic system comprising:
an encryption device to generate an original ciphertext in which a secret 20 distribution matrix is set as information specifying a decryption condition;
a decryption condition addition device to acquire a restriction condition to restrict the decryption condition of the original ciphertext generated by the encryption device, and generate art updated ciphertext for which the decryption condition of the original ciphertext is restricted by adding a row and a column which are related to the 25 restriction condition to the secret distribution matrix set in the original ciphertext; and

36
a decryption device to decrypt the updated ciphertext generated by the decryption condition addition device.
[Claim 7] A decryption condition addition program for causing a computer to execute:
5 an original ciphertext acquisition process to acquire an original ciphertext in
which a secret distribution matrix is set as information specifying a decryption condition;
a condition acquisition process to acquire a restriction condition to restrict the decryption condition of the original ciphertext acquired by the original ciphertext 10 acquisition process; and
an updated ciphertext generation process to generate an updated ciphertext for which the decryption condition of the original ciphertext is restricted by adding a row and a column which are related to the restriction condition acquired by the condition acquisition process to the secret distribution matrix set in the original ciphertext. 15