# Patent

## Title
Cryptographic system, cryptographic method, and computer readable medium

## Abstract

It is an object to provide predicate encryption that can conceal both attribute information being set in a ciphertext and predicate information being set in a decryption key even in a public key setting. An encryption device 200 generates a ciphertext ctx in which attribute information x is set as a basis vector of a basis D. A conversion device 300 converts with conversion information W the basis D of the ciphertext ctx generated by the encryption device 200 to a basis B so as to generate a ciphertext CTx. A decryption device 400 decrypts the ciphertext CTx generated by the conversion device 300 with a token tkv in which predicate information v is set as a coefficient of a basis vector of a basis B* corresponding to the basis B.

## Background
TECHNICAL FIELD
The present invention relates to predicate encryption that can conceal both attribute information being set in a ciphertext and predicate information being set in a decryption key.
BACKGROUND ART
Non-Patent Literature 1 discusses inner-product predicate encryption that can conceal both attribute information being set in a ciphertext and predicate information being set in a decryption key in a secret key setting in which both an encryption-side key and a decryption-side key are kept secret.
CITATION LIST
Non-Patent Literature
Non-Patent Literature 1: Emily Shen, Elaine Shi, and Brent Waters. Predicate privacy in encryption systems. In Omer Reingold, editor, TCC 2009, volume 5444 of LNCS, pages 457.473. Springer, 2009.
Non-Patent Literature 2: Allison B. Lewko, Tatsuaki Okamoto, Amit Sahai, Katsuyuki Takashima, and Brent Waters. Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 62.91. Springer, 2010. Full version is available at http://eprint.iacr.org/2010/110.
Non-Patent Literature 3: Okamoto, T., Takashima, K.: Achieving Short Ciphertexts or Short Secret-Keys for Adaptively Secure General Inner-Product Encryption. CANS 2011, LNCS, vol. 7092, pp. 138-159 Springer Heidelberg (2011).
Non-Patent Literature 4: Okamoto, T Takashima, K.: Fully Secure Unbounded Inner-Product and Attribute-Based Encryption. ePrint http://eprint.iacr.org/2012/671
SUMMARY OF INVENTION
Technical Problem
There has been no implementation of predicate encryption that can conceal both attribute information being set in a ciphertext and predicate information being set in a decryption key in a public key setting in which an encryption-side key is made public.
It is an object of the present invention to provide predicate encryption that can conceal both attribute information being set in a ciphertext and predicate information being set in a decryption key even in the public key setting.
Solution to Problem
A cryptographic system according to the present invention includes
an encryption device to generate a ciphertext ctx in which attribute information x is set as a coefficient of a basis vector of a basis D;
a conversion device to convert with conversion information W the basis D of the ciphertext ctx generated by the encryption device to a basis B so as to generate a ciphertext CTx; and
a decryption device to decrypt the ciphertext CTx generated by the conversion device with a token tkv in which predicate information v is set as a coefficient of a basis vector of a basis B* corresponding to the basis B.
Advantageous Effects of Invention
By employing conversion information W and a conversion device, a cryptographic system according to the present invention can implement predicate encryption that can conceal both attribute information being set in a ciphertext and predicate information being set in a decryption key even in the public key setting.



BRIEF DESCRIPTION OF DRAWINGS
FIG. 1 is a configuration diagram of a cryptographic system 10 according to Embodiment 1;
FIG. 2 is a functional block diagram illustrating the function of a key generation device 100 according to Embodiment 1;
FIG. 3 is a functional block diagram illustrating the function of an encryption device 200 according to Embodiment 1;
FIG. 4 is a functional block diagram illustrating the function of a conversion device 300 according to Embodiment 1;
FIG. 5 is a functional block diagram illustrating the function of a decryption device 400 according to Embodiment 1;
FIG. 6 is a flowchart illustrating the process of a Setup algorithm according to Embodiment 1;
FIG. 7 is a flowchart illustrating the process of a TokenGen algorithm according to Embodiment 1;
FIG. 8 is a flowchart illustrating the process of an Enc algorithm according to Embodiment 1;
FIG. 9 is a flowchart illustrating the process of a Conv algorithm according to Embodiment 1;
FIG. 10 is a flowchart illustrating the process of a Query algorithm according to Embodiment 1;
FIG. 11 is a flowchart illustrating the process of a TokenGen algorithm according to Embodiment 3;
FIG. 12 is a configuration diagram of a secure search system 500 according to Embodiment 5;
FIG. 13 is a configuration diagram of a secure search system 500 having a configuration different from that of FIG. 12; and
FIG. 14 is a diagram illustrating an example of the hardware configuration of the key generation device 100, the encryption device 200, the conversion device 300, and the decryption device 400 presented in the above embodiments.



DESCRIPTION OF EMBODIMENTS
Notations to be used in the following description will be described.
When A is a random variable or distribution, Formula 101 denotes that y is randomly selected from A according to the distribution of A. That is, y is a random number in Formula 101.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      101
    
    ]
  




  
    y
    ⁢
    
      ⟵
      R
    
    ⁢
    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.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      102
    
    ]
  




  
    y
    ⁢
    
      ⟵
      U
    
    ⁢
    A
  



Formula 103 denotes that y is defined, defined, or substituted by z.

y:=z  [Formula 103]

When a is a fixed value, Formula 104 denotes that a machine (algorithm) A outputs a on input x.

A(x)→a  [Formula 104]

For example,

A(x)→1

Formula 105, namely Fq, denotes a finite field of order q.

q  [Formula 105]

A vector symbol denotes a vector representation over the finite field Fq, as indicated in Formula 106.

{right arrow over (x)} denotes

(x1, . . . ,xn)εqn  [Formula 106]

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

{right arrow over (x)}·{right arrow over (ν)}  [Formula 107]

{right arrow over (x)}=(x1, . . . ,xn),

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

Σi=1nxiνi  [Formula 109]

Note that XT denotes the transpose of a matrix X.
For a basis B and a basis B* indicated in Formula 110, Formula 111 is defined.

:=(b1, . . . ,bN),

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

:=Σi=1Nxibi,

:=Σi=1Nyib*i  [Formula 111]

In the following description, when “δi,j” is represented as a superscript, this δi,j denotes δi,j.
When “→” denoting a vector is attached to a subscript or superscript, it is meant that this “→” is attached as a superscript to the subscript or superscript.
In the following description, cryptographic processes include a key generation process, an encryption process, a conversion process, and a decryption process (query process).
Embodiment 1
Basic concepts for an inner-product predicate encryption scheme will be described first, and then an inner-product predicate encryption scheme will be described in which both attribute information being set in a ciphertext and predicate information being set in a decryption key can be concealed even in a public key setting.
First, the background to the concealment of both the attribute information being set in the ciphertext and the predicate information being set in the decryption key will be described.
Second, a space having a rich mathematical structure called “dual pairing vector spaces (DPVS)” which is a space for implementing the inner-product predicate encryption scheme will be described.
Third, a key technique for constructing the inner-product predicate encryption scheme according to Embodiment 1 will be described.
Fourth, the inner-product predicate encryption scheme according to Embodiment 1 will be described.
<1. Background>
There is a practice in which, for example, a hospital or the like accumulates the DNA information of patients in a database, and a pharmaceutical company or the like searches the database using a search query to investigate whether there is specific regularity in the DNA information of patients having a certain disease.
The DNA information of patients is private information. For pharmaceutical companies and the like, search queries need to be kept secret in the light of development strategies for pharmaceutical products.
In predicate encryption and the like, a ciphertext is generated by setting the DNA information or the like of a patient as attribute information, and a search query is generated by setting a search condition as predicate information.
However, in the conventional public key setting, there is a risk that a search condition cannot be concealed even if the DNA information of a patient can be concealed. This is because the public key setting allows a ciphertext to be freely generated based on a public key, so that it may be possible to execute a search query on the generated ciphertext and deduce a search condition which is set in the search query.
The inner-product predicate encryption scheme discussed in Non-Patent Literature 1 can conceal both the DNA information of a patient and a search condition in the secret key setting.
However, in the secret key setting, a secret key is required to generate a ciphertext, which is highly inconvenient from a practical point of view. Thus, there has been a demand for a scheme which can conceal both the DNA information of a patient and a search condition in the public key setting.
<2. Dual Pairing Vector Spaces>
The inner-product predicate encryption scheme to be described hereinafter is implemented in dual pairing vector spaces.
First, symmetric bilinear pairing groups will be described.
Symmetric bilinear pairing groups (q, G, GT, g, e) are a tuple of a prime q, a cyclic additive group G of order q, a cyclic multiplicative group GT of order q, g≠0εG, and a polynomial-time computable nondegenerate bilinear pairing e: G×G→GT. The nondegenerate bilinear pairing signifies e(sg, tg)=e(g, g)st, and e(g, g)≠1.
In the following description, let Gbpg be an algorithm that takes as input 1λ and outputs values of a parameter paramG:=(q, G, GT, g, e) of bilinear pairing groups with a security parameter λ.
Dual pairing vector spaces will now be described.
Dual pairing vector spaces (q, V, GT, A, e) can be constructed by a direct product of the symmetric bilinear pairing groups (paramG:=(q, G, GT, g, e)). The dual pairing vector spaces (q, V, GT, A, e) are a tuple of a prime q, an N-dimensional vector space V over Fq indicated in Formula 112, a cyclic group GT of order q, and a canonical basis A:=(a1, . . . , aN) of the space V, and have the following operations (1) and (2), where ai is as indicated in Formula 113.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      112
    
    ]
  




  
    
      
        
          V
          :=
          
            
              
                G
                ×
                ⋯
                ×
                G
              
              
                {
                N
              
            
            ⁢
            
              

            
            [
            
              Formula
              ⁢
              
                
              
              ⁢
              113
            
            ]
          
        
      
    
    
      
        
          
            a
            i
          
          :=
          
            (
            
              
                
                  0
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  0
                
                
                  {
                  
                    i
                    -
                    1
                  
                
              
              ,
              g
              ,
              
                
                  0
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  0
                
                
                  {
                  
                    N
                    -
                    i
                  
                
              
            
            )
          
        
      
    
  



Operation (1): Nondegenerate Bilinear Pairing
A pairing in the space V is defined by Formula 114.

e(x,y):=Πi=1Ne(Gi,Hi)εT  [Formula 114]

where

(G1, . . . ,GN):=xε, 

(H1, . . . ,HN):=yε

This is nondegenerate bilinear, that is, e(sx, ty)=e(x, y)st and if e(x, y)=1 for all yεV then x=0. For all i and j, e(ai, aj)=e(g, g)δi,j, where δi,j=1 if i=j, and δi,j=0 if i≠j, and e(g, g)≠1εGT.
Operation (2): Distortion Maps
Linear transformations φi,j on the space V indicated in Formula 115 can achieve Formula 116.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      115
    
    ]
  




  
    
      
        
          
            
              If
              ⁢
              
                
              
              ⁢
              
                
                  φ
                  
                    i
                    ,
                    j
                  
                
                ⁡
                
                  (
                  
                    a
                    j
                  
                  )
                
              
            
            =
            
              
                a
                i
              
              ⁢
              
                
              
              ⁢
              and
            
          
          ⁢
          
            
          
          ⁢
          
            

          
          ⁢
          
            k
            ≠
            j
          
          ,
          
            
          
          ⁢
          
            
              then
              ⁢
              
                
              
              ⁢
              
                
                  φ
                  
                    i
                    ,
                    j
                  
                
                ⁡
                
                  (
                  
                    a
                    k
                  
                  )
                
              
            
            =
            
              0.
              ⁢
              
                

              
              [
              
                Formula
                ⁢
                
                  
                
                ⁢
                116
              
              ]
            
          
        
      
    
    
      
        
          
            
              
                φ
                
                  i
                  ,
                  j
                
              
              ⁡
              
                (
                x
                )
              
            
            :=
            
              (
              
                
                  
                    0
                    ,
                    
                      ...
                      ⁢
                      
                        
                      
                      ⁢
                      0
                    
                  
                  
                    {
                    
                      i
                      -
                      1
                    
                  
                
                ,
                
                  g
                  j
                
                ,
                
                  
                    0
                    ,
                    ...
                    ⁢
                    
                      
                    
                    ,
                    0
                  
                  
                    {
                    
                      N
                      -
                      i
                    
                  
                
              
              )
            
          
          ⁢
          
            
          
          ⁢
          
            

          
          ⁢
          
            
              where
              ⁢
              
                
              
              ⁢
              
                (
                
                  
                    g
                    1
                  
                  ,
                  
                    ...
                    ⁢
                    
                      
                    
                    ⁢
                    
                      g
                      N
                    
                  
                
                )
              
            
            ⁢
            
              
            
            :=
            x
          
        
      
    
  



The linear transformations φi,j will be called distortion maps.
In the following description, let Gdpvs be an algorithm that takes as input 1λ (λεnatural number), Nεnatural number, and values of a parameter paramG:=(q, G, GT, g, e) of bilinear pairing groups, and outputs values of a parameter paramV:=(q, V, GT, A, e) of dual pairing vector spaces with a security parameter λ and an N-dimensional space V.
Description will be directed herein to a case where the dual pairing vector spaces are constructed using the above-described symmetric bilinear pairing groups. The dual pairing vector spaces can also be constructed using asymmetric bilinear pairing groups. The following description can easily be adapted to a case where the dual pairing vector spaces are constructed using asymmetric bilinear pairing groups.
<3. Key Technique>
To achieve the concealment of both attribute information and predicate information, a new trapdoor (conversion key W to be described later) is employed between a public key and a secret key (alternatively, between a ciphertext and a token).
First, random dual bases B and B* on dual pairing vector spaces are generated. Then, using the conversion key W which is a random matrix, a subbasis B^ of the basis B is linearly transformed to generate a new basis D^ (:=B^·W). The basis D^ is uniformly and independently distributed from the basis B. Then, the basis D^ is output as the public key, and a subbasis B*^ of the basis B* is output as the secret key. The basis D^ and the basis B*^ are independent from each other if W is not considered.
An original ciphertext generated by an encrypting party and a token for search inherit this independence property from the key pair.
Using the trapdoor W (conversion key W), an intermediary different from the encrypting party converts the original ciphertext to a searchable ciphertext which is related to the token through the dual orthonormal property of the bases B and B*. Then, the converted ciphertext is searched for with the token.
<4. Inner-Product Predicate Encryption Scheme>
A scheme for inner-product predicate encryption with ciphertext conversion (Inner Product Encryption with Ciphertext Conversion, IPE-CC) will be described.
In the IPE-CC scheme, attribute information of inner-product predicates is represented as an attribute vector {right arrow over (x)}εFqn\{{right arrow over (0)}}, and predicate information (fv→) is represented as a predicate vector {right arrow over (v)}, where fv→({right arrow over (x)})=1 only if {right arrow over (v)}·{right arrow over (x)}=0.
The IPE-CC scheme includes five probabilistic polynomial-time algorithms: Setup, TokenGen, Enc, Conv, and Query.
(Setup)
A Setup algorithm takes as input a security parameter 1λ, and outputs a public key pk, a conversion key ck, and a secret key sk (master secret key).
(TokenGen)
A TokenGen algorithm takes as input the public key pk, the secret key sk, and a predicate vector {right arrow over (v)}, and outputs a token tkv (decryption key).
(Enc)
An Enc algorithm takes as input the public key pk and an attribute vector {right arrow over (x)}, and outputs a ciphertext ctx.
(Conv)
A Conv algorithm takes as input the public key pk, the conversion key ck, and the ciphertext ctx, and outputs a converted ciphertext CTx.
(Query)
A Query algorithm takes as input the public key pk, the token tkv, and the converted ciphertext CTx, and outputs 0 or 1 indicating a value of a predicate fv→ concerning the predicate vector {right arrow over (v)} which is evaluated based on the attribute vector {right arrow over (x)}.
A cryptographic system 10 that executes the algorithms of the IPE-CC scheme will be described.
FIG. 1 is a configuration diagram of the cryptographic system 10 according to Embodiment 1.
The cryptographic system 10 includes a key generation device 100, an encryption device 200, a conversion device 300, and a decryption device 400.
The key generation device 100 executes the Setup algorithm taking as input a security parameter λ, and thus generates a public key pk, a conversion key ck, and a secret key sk. Then, the key generation device 100 publishes the public key pk, and transmits the conversion key ck to the conversion device 300 in secrecy. The key generation device 100 also executes the TokenGen algorithm taking as input the public key pk, the secret key sk, and a predicate vector {right arrow over (v)}, and thus generates a token tkv, and transmits the token tkv to the decryption device 400 in secrecy.
The encryption device 200 executes the Enc algorithm taking as input the public key pk and an attribute vector {right arrow over (x)}, and thus generates a ciphertext ctx.
The conversion device 300 executes the Conv algorithm taking as input the public key pk, the conversion key ck, and the ciphertext ctx, and thus generates a ciphertext CTx.
The decryption device 400 executes the Query algorithm taking as input the public key pk, the token tkv, and the ciphertext CTx, and outputs 0 or 1.
FIG. 2 is a functional block diagram illustrating the function of the key generation device 100 according to Embodiment 1. FIG. 3 is a functional block diagram illustrating the function of the encryption device 200 according to Embodiment 1. FIG. 4 is a functional block diagram illustrating the function of the conversion device 300 according to Embodiment 1. FIG. 5 is a functional block diagram illustrating the function of the decryption device 400 according to Embodiment 1.
FIG. 6 and FIG. 7 are flowcharts illustrating the operation of the key generation device 100 according to Embodiment 1. FIG. 6 is a flowchart illustrating the process of the Setup algorithm according to Embodiment 1, and FIG. 7 is a flowchart illustrating the process of the TokenGen algorithm according to Embodiment 1. FIG. 8 is a flowchart illustrating the operation of the encryption device 200 according to Embodiment 1 and illustrating the process of the Enc algorithm according to Embodiment 1. FIG. 9 is a flowchart illustrating the operation of the conversion device 300 according to Embodiment 1 and illustrating the process of the Conv algorithm according to Embodiment 1. FIG. 10 is a flowchart illustrating the operation of the decryption device 400 according to Embodiment 1 and illustrating the process of the Query algorithm according to Embodiment 1.
The function and operation of the key generation device 100 will be described.
As illustrated in FIG. 2, the key generation device 100 includes a master key generation part 110, a master key storage part 120, an information input part 130, a token generation part 140, and a token transmission part 150.
With reference to FIG. 6, the process of the Setup algorithm will be described.
(S101: Orthonormal Basis Generation Step)
Using a processing device, the master key generation part 110 computes Formula 117, and thus generates a parameter paramV, a basis B, and a basis B*.




  
    
      
        [
        
          Formula
          ⁢
          
            
          
          ⁢
          117
        
        ]
      
    
    
      
        
      
    
  
  
    
      
        input
        ⁢
        
          
        
        ⁢
        
          1
          λ
        
      
    
    
      
        (
        1
        )
      
    
  
  
    
      
        N
        :=
        
          n
          +
          u
          +
          w
          +
          z
        
      
    
    
      
        (
        2
        )
      
    
  
  
    
      
        
          
            param
            G
          
          :=
          
            
              (
              
                q
                ,
                G
                ,
                
                  G
                  T
                
                ,
                g
                ,
                e
              
              )
            
            ⁢
            
              ⟵
              R
            
            ⁢
            
              
                G
                bpg
              
              ⁡
              
                (
                
                  1
                  λ
                
                )
              
            
          
        
        ,
        
          

        
        ⁢
        
          
            param
            
              V
              ′
            
          
          :=
          
            
              (
              
                q
                ,
                V
                ,
                
                  
                    G
                    
                      T
                      ,
                    
                  
                  ⁢
                  A
                
                ,
                e
              
              )
            
            ⁢
            
              ⟵
              R
            
            ⁢
            
              
                G
                dpvs
              
              ⁡
              
                (
                
                  
                    1
                    λ
                  
                  ,
                  N
                  ,
                  
                    param
                    G
                  
                
                )
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  
  
    
      
        ψ
        ⁢
        
          ⟵
          ⋃
        
        ⁢
        
          F
          q
          x
        
      
    
    
      
        (
        4
        )
      
    
  
  
    
      
        X
        :=
        
          
            (
            
              χ
              
                i
                ,
                j
              
            
            )
          
          ⁢
          
            ⟵
            ⋃
          
          ⁢
          
            GL
            ⁡
            
              (
              
                N
                ,
                
                  F
                  q
                
              
              )
            
          
        
      
    
    
      
        (
        5
        )
      
    
  
  
    
      
        
          (
          
            θ
            
              i
              ,
              j
            
          
          )
        
        :=
        
          ψ
          ·
          
            
              (
              
                X
                T
              
              )
            
            
              -
              1
            
          
        
      
    
    
      
        (
        6
        )
      
    
  
  
    
      
        
          
            b
            i
          
          :=
          
            
              ∑
              
                j
                =
                1
              
              N
            
            ⁢
            
              
            
            ⁢
            
              
                χ
                
                  i
                  ,
                  j
                
              
              ⁢
              
                a
                j
              
            
          
        
        ,
        
          
            
              B
              *
            
            ⁢
            
              :
            
          
          =
          
            (
            
              
                b
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                b
                N
              
            
            )
          
        
      
    
    
      
        (
        7
        )
      
    
  
  
    
      
        
          
            b
            i
            *
          
          :=
          
            
              ∑
              
                j
                =
                1
              
              N
            
            ⁢
            
              
                θ
                
                  i
                  ,
                  j
                
              
              ⁢
              
                a
                j
              
            
          
        
        ,
        
          
            
              B
              *
            
            ⁢
            
              :
            
          
          =
          
            (
            
              
                b
                1
                *
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                b
                N
                *
              
            
            )
          
        
      
    
    
      
        (
        8
        )
      
    
  
  
    
      
        
          
            g
            T
          
          :=
          
            e
            ⁢
            
              
                (
                
                  g
                  ,
                  g
                
                )
              
              ψ
            
          
        
        ,
        
          
        
        ⁢
        
          
            param
            V
          
          =
          
            (
            
              
                param
                
                  V
                  ′
                
              
              ,
              
                g
                T
              
            
            )
          
        
      
    
    
      
        (
        9
        )
      
    
  




That is, the master key generation part 110 executes the following process (1) through (9).
(1) Using an input device, the master key generation part 110 takes as input a security parameter λ.
(2) Using the processing device, the master key generation part 110 sets n+u+w+z in N. Note that n is an integer of 1 or more, and u, w, and z are integers of 0 or more.
(3) Using the processing device, the master key generation part 110 executes the algorithm Gbpg taking as input the security parameter λ inputted in (1), and thus generates a parameter paramG of bilinear pairing groups. Then, using the processing device, the master key generation part 110 executes the algorithm Gdpvs taking as input the security parameter λ inputted in (1), N set in (2), and the parameter paramG, and thus generates values of a parameter paramV′:=(q, V, GT, A, e) of dual pairing vector spaces.
(4) Using the processing device, the master key generation part 110 generates a random number ψ.
(5) Using the processing device, the master key generation part 110 takes as input N set in (2) and Fq, and randomly generates a linear transformation X:=(χi,j). Note that GL stands for general linear. In other words, GL is a general linear group, a set of square matrices with non-zero determinants, and a group under multiplication.
(6) Using the processing device and based on the random number ψ generated in (4) and the linear transformation X generated in (5), the master key generation part 110 generates (νi,j):=ψ·(XT)−1.
(7) Using the processing device and based on the linear transformation X generated in (5), the master key generation part 110 generates a basis B from the canonical basis A generated in (3).
(8) Using the processing device and based on νi,j generated in (6), the master key generation part 110 generates a basis B* from the canonical basis A generated in (3).
(9) Using the processing device, the master key generation part 110 sets e(g, g)ψ in gT. The master key generation part 110 also sets paramV′ generated in (3) and gT in paramV.
(S102: Conversion Key Generation Step)
Using the processing device, the master key generation part 110 generates conversion information W, as indicated in Formula 118. The master key generation part 110 designates the conversion information W as a conversion key ck.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      118
    
    ]
  




  
    W
    ⁢
    
      ⟵
      ⋃
    
    ⁢
    
      GL
      ⁡
      
        (
        
          N
          ,
          
            F
            q
          
        
        )
      
    
  



(S103: Public Key Generation Step)
Using the processing device, the master key generation part 110 converts the basis B generated in S101 with the conversion key W, as indicated in Formula 119, and thus generates a basis D. Then, using the processing device, the master key generation part 110 generates a subbasis D^ of the basis D, as indicated in Formula 119.

di:=biW for i=1, . . . ,n+u+w+z, 

:=(d1, . . . ,dn+u+w+z),

:=(d1, . . . ,dn,dn+u+w+1 . . . ,dn+u+w+z)  [Formula 119]

The master key generation part 110 designates a combination of the subbasis D^, the security parameter λ inputted in S101, and paramV generated in S101 as a public key pk.
(S104: Secret Key Generation Step)
Using the processing device, the master key generation part 110 generates a subbasis B*^ of the basis B* generated in S101, as indicated in Formula 120.

*:=(b*1, . . . ,b*n,b*n+u+1, . . . ,b*n+u+w)  [Formula 120]

The master key generation part 110 designates the subbasis B*^ as a secret key sk.
(S105: Key Storage Step)
The master key storage part 120 stores the conversion key ck generated in S102, the public key pk generated in S103, and the secret key sk generated in S104 in a storage device.
In brief, in S101 through S104, the key generation device 100 generates the conversion key ck, the public key pk, and the secret key sk by executing the Setup algorithm indicated in Formula 121. In S105, the key generation device 100 stores the conversion key ck, the public key pk, and the secret key sk in the storage device.
The public key pk is published, for example, via a network, and is made available for the encryption device 200, the conversion device 300, and the decryption device 400. The conversion key ck is transmitted to the conversion device 300 in secrecy by a communication device and via the network, for example.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      121
    
    ]
  




  
    Setup
    ⁢
    
      
    
    ⁢
    
      (
      
        1
        λ
      
      )
    
    ⁢
    
      :
    
  




  
    
      
        (
        
          
            param
            V
          
          ,
          
            B
            :=
            
              (
              
                
                  b
                  1
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  b
                  
                    n
                    +
                    u
                    +
                    w
                    +
                    z
                  
                
              
              )
            
          
          ,
          
            

          
          ⁢
          
            
              B
              *
            
            :=
            
              (
              
                
                  b
                  1
                  *
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  b
                  
                    n
                    +
                    u
                    +
                    w
                    +
                    z
                  
                  *
                
              
              )
            
          
        
        )
      
      ⁢
      
        ⟵
        R
      
      ⁢
      
        
          G
          ob
          IPE
        
        ⁡
        
          (
          
            1
            λ
          
          )
        
      
    
    ,
    
      

    
    ⁢
    
      W
      ⁢
      
        ⟵
        ⋃
      
      ⁢
      
        GL
        ⁡
        
          (
          
            N
            ,
            
              F
              q
            
          
          )
        
      
    
    ,
    
      

    
    ⁢
    
      
        d
        i
      
      :=
      
        
          
            b
            i
          
          ⁢
          W
          ⁢
          
            
          
          ⁢
          for
          ⁢
          
            
          
          ⁢
          i
        
        =
        1
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      n
      +
      u
      +
      w
      +
      z
    
    ,
    
      

    
    ⁢
    
      D
      :=
      
        (
        
          
            d
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            
              n
              +
              u
              +
              w
              +
              z
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        D
        ^
      
      :=
      
        (
        
          
            d
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            n
          
          ,
          
            
              d
              
                n
                +
                u
                +
                w
                +
                1
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            d
            
              n
              +
              u
              +
              w
              +
              z
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        
          B
          ^
        
        *
      
      :=
      
        (
        
          
            b
            1
            *
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            n
            *
          
          ,
          
            b
            
              n
              +
              u
              +
              1
            
            *
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            
              n
              +
              u
              +
              w
            
            *
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        pk
      
      :=
      
        (
        
          
            1
            λ
          
          ,
          
            param
            V
          
          ,
          
            D
            ^
          
        
        )
      
    
    ,
    
      ck
      :=
      W
    
    ,
    
      sk
      :=
      
        
          
            
              B
              ^
            
            *
          
          .
          
            

          
          ⁢
          
            
              G
              ob
              IPE
            
            ⁡
            
              (
              
                1
                λ
              
              )
            
          
        
        ⁢
        
          :
        
      
    
  




  
    
      N
      :=
      
        n
        +
        u
        +
        w
        +
        z
      
    
    ,
    
      

    
    ⁢
    
      
        param
        G
      
      :=
      
        
          (
          
            q
            ,
            G
            ,
            
              G
              T
            
            ,
            g
            ,
            e
          
          )
        
        ⁢
        
          ⟵
          R
        
        ⁢
        
          
            G
            bpg
          
          ⁡
          
            (
            
              1
              λ
            
            )
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        param
        
          V
          ′
        
      
      :=
      
        
          (
          
            q
            ,
            V
            ,
            
              G
              T
            
            ,
            A
            ,
            e
          
          )
        
        ⁢
        
          ⟵
          R
        
        ⁢
        
          
            G
            dpvs
          
          ⁡
          
            (
            
              
                1
                λ
              
              ,
              N
            
            )
          
        
      
    
    ,
    
      

    
    ⁢
    
      ψ
      ⁢
      
        ⟵
        ⋃
      
      ⁢
      
        F
        q
        x
      
    
    ,
    
      
        g
        T
      
      :=
      
        
          e
          ⁡
          
            (
            
              g
              ,
              g
            
            )
          
        
        ψ
      
    
    ,
    
      

    
    ⁢
    
      X
      :=
      
        
          (
          
            χ
            
              i
              ,
              j
            
          
          )
        
        ⁢
        
          ⟵
          ⋃
        
        ⁢
        
          GL
          ⁡
          
            (
            
              N
              ,
              
                F
                q
              
            
            )
          
        
      
    
    ,
    
      
        (
        
          θ
          
            i
            ,
            j
          
        
        )
      
      ⁢
      
        :
      
      ⁢
      
        ψ
        ·
        
          
            (
            
              X
              T
            
            )
          
          
            -
            1
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        param
        V
      
      :=
      
        (
        
          
            param
            
              V
              ′
            
          
          ,
          
            g
            T
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        b
        i
      
      :=
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
            χ
            
              i
              ,
              j
            
          
          ⁢
          
            a
            j
          
        
      
    
    ,
    
      B
      :=
      
        (
        
          
            b
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            N
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        b
        i
        *
      
      :=
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
        
        ⁢
        
          
            θ
            
              i
              ,
              j
            
          
          ⁢
          
            a
            j
          
        
      
    
    ,
    
      
        B
        *
      
      :=
      
        (
        
          
            b
            1
            *
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            N
            *
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      return
      ⁢
      
        
      
      ⁢
      
        
          (
          
            
              param
              V
            
            ,
            B
            ,
            
              B
              *
            
          
          )
        
        .
      
    
  



With reference to FIG. 7, the process of the TokenGen algorithm will be described.
(S201: Information Input Step)
Using the input device, the information input part 130 takes as input a predicate vector {right arrow over (v)}. In the predicate vector {right arrow over (v)}, attribute information of a user of a token tkv, a search keyword, and so on are set as elements, for example.
(S202: Random Number Generation Step)
Using the processing device, the token generation part 140 generates random numbers, as indicated in Formula 122.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      122
    
    ]
  




  
    
      σ
      ⁢
      
        ⟵
        ⋃
      
      ⁢
      
        F
        q
      
    
    ,
    
      

    
    ⁢
    
      
        η
        →
      
      :=
      
        
          (
          
            
              η
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              η
              w
            
          
          )
        
        ⁢
        
          ⟵
          ⋃
        
        ⁢
        
          F
          q
          w
        
      
    
  



(S203: Token Element Generation Step)
Using the processing device, the token generation part 140 generates an element k* of the token tkv, as indicated in Formula 123.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      123
    
    ]
  




  
    
      k
      *
    
    :=
    
      
        (
        
          
            
              σ
              ⁢
              
                
              
              ⁢
              
                v
                →
              
            
            
              {
              n
            
          
          ,
          
            
              0
              u
            
            
              {
              u
            
          
          ,
          
            
              η
              →
            
            
              {
              w
            
          
          ,
          
            
              0
              z
            
            
              {
              z
            
          
          ,
        
        )
      
      
        B
        *
      
    
  



For the basis B and the basis B* indicated in Formula 110, Formula 111 is defined. Thus, Formula 123 means that σv1, . . . , σvn are respectively set as the coefficient of basis vectors b*1, . . . , b*n of the basis B*, 0 is set as the coefficient of each of basis vectors b*n+1, . . . , b*n+u of the basis B*, η1, . . . , ηw are respectively set as the coefficient of basis vectors b*n+u+1, . . . , b*n+u+w of the basis B*, and 0 is set as the coefficient of each of basis vectors b*n+u+w+1, . . . , b*n+u+w+z of the basis B*.
(S204: Token Transmission Step)
Using the communication device and via the network, for example, the token transmission part 150 transmits the token tkv having the element k* generated in S203 to the decryption device 400 in secrecy. As a matter of course, the token tkv may be transmitted to the decryption device 400 by another method.
In brief, in S201 through S203, the key generation device 100 generates the token tkv by executing the TokenGen algorithm indicated in Formula 124. In S204, the key generation device 100 transmits the token tkv to the decryption device 400.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      124
    
    ]
  




  
    
      TokenGen
      ⁡
      
        (
        
          pk
          ,
          sk
          ,
          
            
              v
              →
            
            ∈
            
              
                F
                q
                n
              
              ⁢
              \
              ⁢
              
                {
                
                  0
                  →
                
                }
              
            
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    
      σ
      ⁢
      
        ⟵
        ⋃
      
      ⁢
      
        F
        q
      
    
    ,
    
      
        η
        →
      
      :=
      
        
          (
          
            
              η
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              η
              w
            
          
          )
        
        ⁢
        
          ⟵
          ⋃
        
        ⁢
        
          F
          q
          w
        
      
    
    ,
    
      

    
    ⁢
    
      
        k
        *
      
      :=
      
        
          (
          
            
              
                σ
                ⁢
                
                  
                
                ⁢
                
                  v
                  →
                
              
              
                {
                n
              
            
            ,
            
              
                0
                u
              
              
                {
                u
              
            
            ,
            
              
                η
                →
              
              
                {
                w
              
            
            ,
            
              
                0
                z
              
              
                {
                z
              
            
            ,
          
          )
        
        
          B
          *
        
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        
          tk
          v
        
      
      :=
      
        
          k
          *
        
        .
      
    
  



The function and operation of the encryption device 200 will be described.
As illustrated in FIG. 3, the encryption device 200 includes a public key acquisition part 210, an information input part 220, a ciphertext generation part 230, and a data transmission part 240.
With reference to FIG. 8, the process of the Enc algorithm will be described.
(S301: Public Key Acquisition Step)
Using the communication device and via the network, for example, the public key acquisition part 210 obtains the public key pk generated by the key generation device 100.
(S302: Information Input Step)
Using the input device, the information input part 220 takes as input an attribute vector {right arrow over (x)}εFq. In the attribute vector {right arrow over (x)}, attribute information of a user who is allowed to search and a search tag are set as elements, for example.
(S303: Random Number Generation Step)
Using the processing device, the ciphertext generation part 230 generates random numbers as indicated in Formula 125.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      125
    
    ]
  




  
    
      τ
      ⁢
      
        ⟵
        ⋃
      
      ⁢
      
        F
        q
      
    
    ,
    
      
    
    ⁢
    
      
        ξ
        →
      
      :=
      
        
          (
          
            
              ξ
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              ξ
              z
            
          
          )
        
        ⁢
        
          ⟵
          ⋃
        
        ⁢
        
          F
          q
          z
        
      
    
  



(S304: Cipher Element Generation Step)
Using the processing device, the ciphertext generation part 230 generates an element f of a ciphertext ctx, as indicated in Formula 126.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      126
    
    ]
  




  
    f
    :=
    
      
        (
        
          
            
              τ
              ⁢
              
                
              
              ⁢
              
                x
                →
              
            
            
              {
              n
            
          
          ,
          
            
              0
              u
            
            
              {
              u
            
          
          ,
          
            
              0
              w
            
            
              {
              w
            
          
          ,
          
            
              ξ
              →
            
            
              {
              z
            
          
        
        )
      
      D
    
  



(S305: Data Transmission Step)
Using the communication device and via the network, for example, the data transmission part 240 transmits the ciphertext ctx including the element f generated in S304 to the conversion device 300. As a matter of course, the ciphertext ctx may be transmitted to the conversion device 300 by another method.
In brief, in S301 through S304, the encryption device 200 generates the ciphertext ctx by executing the Enc algorithm indicated in Formula 127. In S305, the encryption device 200 transmits the ciphertext ctx to the conversion device 300.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      127
    
    ]
  




  
    
      Enc
      ⁡
      
        (
        
          pk
          ,
          
            
              x
              →
            
            ∈
            
              F
              q
              n
            
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    
      τ
      ⁢
      
        ⟵
        ⋃
      
      ⁢
      
        F
        q
      
    
    ,
    
      
    
    ⁢
    
      
        ξ
        →
      
      :=
      
        
          (
          
            
              ξ
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              ξ
              z
            
          
          )
        
        ⁢
        
          ⟵
          ⋃
        
        ⁢
        
          F
          q
          z
        
      
    
    ,
    
      

    
    ⁢
    
      f
      :=
      
        
          (
          
            
              
                τ
                ⁢
                
                  
                
                ⁢
                
                  x
                  →
                
              
              
                {
                n
              
            
            ,
            
              
                0
                u
              
              
                {
                u
              
            
            ,
            
              
                0
                w
              
              
                {
                w
              
            
            ,
            
              
                ξ
                →
              
              
                {
                z
              
            
          
          )
        
        D
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        
          ct
          x
        
      
      :=
      
        f
        .
      
    
  



The function and operation of the conversion device 300 will be described.
As illustrated in FIG. 4, the conversion device 300 includes a conversion key acquisition part 310, a ciphertext acquisition part 320, a ciphertext conversion part 330, and a data transmission part 340.
With reference to FIG. 9, the process of the Conv algorithm will be described.
(S401: Conversion Key Acquisition Step)
Using the communication device and via the network, for example, the conversion key acquisition part 310 obtains the conversion key ck:=W transmitted by the key generation device 100. The conversion key acquisition part 310 also obtains the public key pk generated by the key generation device 100.
(S402: Ciphertext Acquisition Step)
Using the communication device and via the network, for example, the ciphertext acquisition part 320 receives the ciphertext ctx:=f transmitted by the encryption device 200.
(S403: Random Number Generation Step)
Using the processing device, the ciphertext conversion part 330 generates random numbers as indicated in Formula 128.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      128
    
    ]
  




  
    
      ρ
      ⁢
      
        ⟵
        ⋃
      
      ⁢
      
        F
        q
      
    
    ,
    
      

    
    ⁢
    
      
        y
        ⁢
        
          ⟵
          ⋃
        
        ⁢
        span
      
      ⁢
      
        〈
        
          
            d
            
              n
              +
              u
              +
              w
              +
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            
              n
              +
              u
              +
              w
              +
              z
            
          
        
        〉
      
    
  



(S404: Ciphertext Conversion Step)
Using the processing device, the ciphertext conversion part 330 converts the ciphertext ctx, as indicated in Formula 129, and thus generates an element c.

c:=(ρf+y)W−1  [Formula 129]

(S405: Data Transmission Step)
Using the communication device and via the network, for example, the data transmission part 340 transmits a ciphertext CTx including the element c generated in S404 to the decryption device 400. As a matter of course, the ciphertext CTx may be transmitted to the decryption device 400 by another method.
In brief, in S401 through S404, the conversion device 300 generates the ciphertext CTx by executing the Conv algorithm indicated in Formula 130. In S405, the conversion device 300 transmits the generated ciphertext CTx to the decryption device 400.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      130
    
    ]
  




  
    
      Conv
      ⁡
      
        (
        
          pk
          ,
          
            ck
            :=
            W
          
          ,
          
            
              ct
              x
            
            :=
            f
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    
      ρ
      ⁢
      
        ⟵
        ⋃
      
      ⁢
      
        F
        q
      
    
    ,
    
      
        y
        ⁢
        
          ⟵
          ⋃
        
        ⁢
        span
      
      ⁢
      
        〈
        
          
            d
            
              n
              +
              u
              +
              w
              +
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            
              n
              +
              u
              +
              w
              +
              z
            
          
        
        〉
      
    
    ,
    
      

    
    ⁢
    
      c
      :=
      
        
          (
          
            
              ρ
              ⁢
              
                
              
              ⁢
              f
            
            +
            y
          
          )
        
        ⁢
        
          W
          
            -
            1
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        
          CT
          x
        
      
      :=
      
        c
        .
      
    
  



The function and operation of the decryption device 400 will be described.
As illustrated in FIG. 5, the decryption device 400 includes a token acquisition part 410, a ciphertext acquisition part 420, and a decryption part 430.
With reference to FIG. 10, the process of the Dec algorithm will be described.
(S501: Token Acquisition Step)
Using the communication device and via the network, for example, the token acquisition part 410 obtains the token tkv:=k* transmitted by the key generation device 100. The token acquisition part 410 also obtains the public key pk generated by the key generation device 100.
(S502: Ciphertext Acquisition Step)
Using the communication device and via the network, for example, the ciphertext acquisition part 420 receives the ciphertext CTx:=c transmitted by the conversion device 300.
(S503: Decryption Step)
Using the processing device, the decryption part 430 outputs 1 indicating that decryption has been successful if a result of computing a pairing operation e(c, k*) is 1, and outputs 0 indicating that decryption has failed if the result is not 1.
In brief, in S501 through S503, the decryption device 400 executes the Query algorithm indicated in Formula 131, and thus determines whether or not decryption has been successful.

Query(pk,tkν:=k*,CTX:=c):  [Formula 131]

if e(c,k*)=1, output 1,
otherwise, output 0.
Note that D·W−1:=d1W−1, . . . , dn+u+w+zW−1) is equal to B:=(b1, . . . , bn+u+w+z). Thus, c:=(ρf+y)W−1=(ω{right arrow over (x)},0u,0w,{right arrow over (η)})D·W−1=(ω{right arrow over (x)},0u,0w,{right arrow over (η)})D·W-1=(ω{right arrow over (x)},0u,0w, {right arrow over (η)})B, where the subscript W−1 means W−1. ωεFq and {right arrow over (η)}εFnq are uniformly and independently distributed. Thus, if {right arrow over (v)}·{right arrow over (x)}=0, then e(c, k*)=gTωσv→·x→=1.
In the conventional IPE, a ciphertext can be freely generated using the public key pk. Thus, there is a risk that information on the predicate vector {right arrow over (v)} which is set in the token tkv may be leaked by executing the Query algorithm on a large number of ciphertexts.
In the IPE-CC scheme according to Embodiment 1, the conversion device 300 converts the basis of the ciphertext ctx using the conversion key ck to generate the ciphertext CTx, and the decryption device 400 executes the Query algorithm on the converted ciphertext CTx. Therefore, the Query algorithm cannot be executed on a large number of ciphertexts without help from the conversion device 300. With this arrangement, the leakage of the information on the predicate vector {right arrow over (v)} which is set in the token tkv can be prevented.
It has been described in the above that a combination of the basis D^, the security parameter λ, and paramV is published as the public key pk.
However, the basis D^, the security parameter λ, and paramV may be transmitted to the encryption device 200 in secrecy as another secret key which is paired with the secret key sk, instead of being used as the public key. In this case, inner-product predicate encryption which can conceal both the attribute information and the predicate information in the secret key setting can be implemented.
It has been described in the above that u, w, and z are integers of 0 or more. It may be arranged that u=3n, w=n, and z=n, for example.
In the above, the method for determining whether or not the ciphertext ctx satisfies the condition which is set in the token tkv has been described. With this method, a secure search system can be constructed in which the ciphertext ctx can be searched for while remaining encrypted.
However, as discussed in Non-Patent Literature 2 and so on, by embedding a message m in a ciphertext ctx, a narrowly-defined cryptographic system can be constructed in which the message m embedded in the ciphertext ctx is retrieved with the token tkv.
Embodiment 2
Embodiment 2 describes an IPE-CC scheme in which efficiency is improved by employing a sparse matrix for generating orthonormal bases B and B*.
In Embodiment 2, what is the same as in Embodiment 1 will not be described, and differences from Embodiment 1 will be mainly described.
The configurations of the key generation device 100, the encryption device 200, the conversion device 300, and the decryption device 400 according to Embodiment 2 are respectively the same as the configurations of these devices illustrated in FIG. 2 to FIG. 5.
The flows of the Setup algorithm, the TokenGen algorithm, the Enc algorithm, the Conv algorithm, and the Query algorithm according to Embodiment 2 are respectively the same as the flows of these algorithms illustrated in FIG. 6 to FIG. 10.
A sparse matrix employed in Embodiment 2 will be described, and a linear transformation X constructed using the sparse matrix and an adjoint matrix ψ(X−1)T of the linear transformation X will be described.
It is assumed that N:=6n, that H(n, Fq) is as indicated in Formula 132, and that L(6, n, Fq) is as indicated in Formula 133.




  
    
      
        
          
        
        ⁢
        
          
            [
            
              Formula
              ⁢
              
                
              
              ⁢
              132
            
            ]
          
          ⁢
          
            

          
          ⁢
          
            
              H
              ⁡
              
                (
                
                  n
                  ,
                  
                    F
                    q
                  
                
                )
              
            
            :=
            
              
                {
                
                  
                    (
                    
                      
                        
                          
                            μ
                            1
                            ′′
                          
                        
                        
                          
                            μ
                            2
                            ′′
                          
                        
                        
                          ⋯
                        
                        
                          
                            μ
                            
                              n
                              -
                              1
                            
                            ′′
                          
                        
                        
                          
                            μ
                            ′′
                          
                        
                      
                      
                        
                          
                            
                          
                        
                        
                          μ
                        
                        
                          
                            
                          
                        
                        
                          
                            
                          
                        
                        
                          
                            μ
                            2
                            ′
                          
                        
                      
                      
                        
                          
                            
                          
                        
                        
                          
                            
                          
                        
                        
                          
                            ⋱
                            ⁢
                            
                              
                            
                          
                        
                        
                          
                            
                          
                        
                        
                          ⋮
                        
                      
                      
                        
                          
                            
                          
                        
                        
                          
                            
                          
                        
                        
                          
                            
                          
                        
                        
                          μ
                        
                        
                          
                            μ
                            
                              n
                              -
                              1
                            
                            ′
                          
                        
                      
                      
                        
                          
                            
                          
                        
                        
                          
                            
                          
                        
                        
                          
                            
                          
                        
                        
                          
                            
                          
                        
                        
                          
                            μ
                            n
                            ′
                          
                        
                      
                    
                    )
                  
                  ⁢
                  
                    
                  
                  |
                  
                    
                      
                        
                          μ
                          ,
                          
                            μ
                            2
                            ′
                          
                          ,
                          ...
                          ⁢
                          
                            
                          
                          ,
                          
                            μ
                            n
                            ′
                          
                          ,
                        
                      
                    
                    
                      
                        
                          
                            μ
                            1
                            ′′
                          
                          ,
                          ...
                          ⁢
                          
                            
                          
                          ,
                          
                            μ
                            
                              n
                              -
                              1
                            
                            ′′
                          
                          ,
                          
                            
                              μ
                              ′′′
                            
                            ∈
                            
                              F
                              q
                            
                          
                        
                      
                    
                    
                      
                        
                          a
                          ⁢
                          
                            
                          
                          ⁢
                          
                            blan
                            ⁢
                            k
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            eleme
                            ⁢
                            nt
                          
                          ⁢
                          
                            
                          
                          ⁢
                          in
                          ⁢
                          
                            
                          
                          ⁢
                          the
                          ⁢
                          
                            
                          
                          ⁢
                          matrix
                        
                      
                    
                    
                      
                        
                          
                            
                              denote
                              ⁢
                              s
                            
                            ⁢
                            
                              
                            
                            ⁢
                            0
                          
                          ∈
                          
                            F
                            q
                          
                        
                      
                    
                  
                
                }
              
              ⁢
              
                

              
              ⁢
              
                
              
              [
              
                Formula
                ⁢
                
                  
                
                ⁢
                133
              
              ]
            
          
        
      
    
  
  
    
      
        
          L
          ⁡
          
            (
            
              6
              ,
              n
              ,
              
                F
                q
              
            
            )
          
        
        :=
        
          
            {
            
              X
              :=
              
                
                  (
                  
                    
                      
                        
                          X
                          
                            1
                            ,
                            1
                          
                        
                      
                      
                        ⋯
                      
                      
                        
                          X
                          
                            1
                            ,
                            6
                          
                        
                      
                    
                    
                      
                        ⋮
                      
                      
                        
                          
                        
                      
                      
                        ⋮
                      
                    
                    
                      
                        
                          X
                          
                            6
                            ,
                            1
                          
                        
                      
                      
                        ⋯
                      
                      
                        
                          X
                          
                            6
                            ,
                            6
                          
                        
                      
                    
                  
                  )
                
                |
                
                  
                    
                      
                        
                          X
                          
                            i
                            ,
                            j
                          
                        
                        ∈
                        
                          H
                          ⁡
                          
                            (
                            
                              n
                              ,
                              
                                F
                                q
                              
                            
                            )
                          
                        
                      
                    
                  
                  
                    
                      
                        
                          for
                          ⁢
                          
                            
                          
                          ⁢
                          i
                        
                        ,
                        
                          j
                          =
                          1
                        
                        ,
                        ...
                        ⁢
                        
                          
                        
                        ,
                        6
                      
                    
                  
                
              
            
            }
          
          ⋂
          
            GL
            ⁡
            
              (
              
                N
                ,
                
                  F
                  q
                
              
              )
            
          
        
      
    
  




Note that L(6, n, Fq) is a subset of GL(N, Fq).
The adjoint matrix ψ(X−1)T of the linear transformation XεL(6, n, Fq) is represented in a sparse form indicated in Formula 134.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      134
    
    ]
  




  
    
      
        ψ
        ⁡
        
          (
          
            X
            
              -
              1
            
          
          )
        
      
      T
    
    :=
    
      (
      
        
          
            
              Y
              
                1
                ,
                1
              
            
          
          
            ...
          
          
            
              Y
              
                1
                ,
                6
              
            
          
        
        
          
            ⋮
          
          
            
              
            
          
          
            ⋮
          
        
        
          
            
              Y
              
                6
                ,
                1
              
            
          
          
            ...
          
          
            
              Y
              
                6
                ,
                6
              
            
          
        
      
      )
    
  




  
    
      
        where
        ⁢
        
          
        
        ⁢
        
          Y
          
            i
            ,
            j
          
        
      
      :=
      
        
          (
          
            
              
                
                  v
                  
                    i
                    ,
                    j
                    ,
                    1
                  
                  ′′
                
              
              
                
                  
                
              
              
                
                  
                
              
              
                
                  
                
              
              
                
                  
                
              
            
            
              
                
                  v
                  
                    i
                    ,
                    
                      j
                      ⁢
                      
                        
                      
                      ⁢
                      2
                    
                  
                  ′′
                
              
              
                
                  v
                  
                    i
                    ,
                    j
                  
                
              
              
                
                  
                
              
              
                
                  
                
              
              
                
                  
                
              
            
            
              
                ⋮
              
              
                
                  
                
              
              
                ⋱
              
              
                
                  
                
              
              
                
                  
                
              
            
            
              
                
                  v
                  
                    i
                    ,
                    j
                    ,
                    
                      n
                      -
                      1
                    
                  
                  ′′
                
              
              
                
                  
                
              
              
                
                  
                
              
              
                
                  v
                  
                    i
                    ,
                    j
                  
                
              
              
                
                  
                
              
            
            
              
                
                  v
                  
                    i
                    ,
                    j
                  
                  ′′′
                
              
              
                
                  v
                  
                    i
                    ,
                    j
                    ,
                    2
                  
                  ′
                
              
              
                ...
              
              
                
                  
                
              
              
                
                  v
                  
                    i
                    ,
                    j
                    ,
                    n
                  
                  ′
                
              
            
          
          )
        
        ⁢
        
          
        
        ⁢
        i
      
    
    ,
    
      j
      =
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    6
  



Here, a blank element in matrices X and (X−1)T denotes a constant value 0εFq. The constant value 0 signifies that the value is fixed to 0.
That is, the matrix XεL(6, n, Fq) is represented by 72n non-zero elements {ui,j, u′i,j,2, . . . , u′i,j,n, u′′i,j,1, . . . , u′′i,j,n−1, u′′′i,j}i,j=1, . . . , 6, and the adjoint matrix ψ(X−1)T is represented by 72n non-zero elements {vi,j, v′i,j,2, . . . , v′i,j,n,v′′i,j,1, . . . , v′′i,j,n−1, v′′′i,j}i,j=1, . . . , 6. Note that a non-zero element is a uniform random number which may be 0.
The IPE-CC scheme according to Embodiment 2 will be described.
Here, it is assumed that x1≠0 and v1≠0 for an attribute vector {right arrow over (x)}:=(x1, . . . , fxn) and a predicate vector {right arrow over (v)}:=(v1, . . . , vn) which are inputted.
With reference to FIG. 6, the process of the Setup algorithm will be described.
(S101: Orthonormal Basis Generation Step)
Using the processing device, the master key generation part 110 computes Formula 135, and thus generates a parameter paramV, a basis B, and a basis B*.




  
    
      
        
          
        
        ⁢
        
          [
          
            Formula
            ⁢
            
              
            
            ⁢
            135
          
          ]
        
      
    
    
      
        
      
    
  
  
    
      
        
          
        
        ⁢
        
          input
          ⁢
          
            
          
          ⁢
          
            1
            λ
          
        
      
    
    
      
        (
        1
        )
      
    
  
  
    
      
        
          
        
        ⁢
        
          N
          :=
          
            6
            ⁢
            n
          
        
      
    
    
      
        (
        2
        )
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            
              param
              G
            
            :=
            
              
                
                  (
                  
                    q
                    ,
                    G
                    ,
                    
                      G
                      T
                    
                    ,
                    g
                    ,
                    e
                  
                  )
                
                ⁢
                
                  ⟵
                  R
                
                ⁢
                
                  G
                  bpg
                
              
              ⁢
              
                (
                
                  1
                  λ
                
                )
              
            
          
          ,
          
            

          
          ⁢
          
            
          
          ⁢
          
            
              param
              
                V
                ′
              
            
            :=
            
              
                (
                
                  q
                  ,
                  V
                  ,
                  
                    G
                    T
                  
                  ,
                  A
                  ,
                  e
                
                )
              
              ⁢
              
                ⟵
                R
              
              ⁢
              
                
                  G
                  dpvs
                
                ⁡
                
                  (
                  
                    
                      1
                      λ
                    
                    ,
                    N
                    ,
                    
                      param
                      G
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  
  
    
      
        
          
        
        ⁢
        
          ψ
          ⁢
          
            ⟵
            U
          
          ⁢
          
            F
            q
            ×
          
        
      
    
    
      
        (
        4
        )
      
    
  
  
    
      
        
          
        
        ⁢
        
          X
          ⁢
          
            ⟵
            U
          
          ⁢
          
            L
            ⁡
            
              (
              
                6
                ,
                n
                ,
                
                  F
                  q
                
              
              )
            
          
        
      
    
    
      
        (
        5
        )
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            (
            
              θ
              
                i
                ,
                j
              
            
            )
          
          :=
          
            ψ
            ·
            
              
                (
                
                  X
                  
                    -
                    1
                  
                
                )
              
              T
            
          
        
      
    
    
      
        (
        6
        )
      
    
  
  
    
      
        {
        
          
            
              B
              
                i
                ,
                j
              
            
            :=
            
              
                μ
                
                  i
                  ,
                  j
                
              
              ⁢
              g
            
          
          ,
          
            
              B
              
                i
                ,
                j
                ,
                2
              
              ′
            
            :=
            
              
                μ
                
                  i
                  ,
                  j
                  ,
                  2
                
                ′
              
              ⁢
              g
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              B
              
                i
                ,
                j
                ,
                n
              
              ′
            
            :=
            
              
                μ
                
                  i
                  ,
                  j
                  ,
                  n
                
                ′
              
              ⁢
              g
            
          
          ,
          
            
               
              
                
                  
                    B
                    
                      i
                      ,
                      j
                      ,
                      1
                    
                    ′′
                  
                  :=
                  
                    
                      μ
                      
                        i
                        ,
                        j
                        ,
                        1
                      
                      ′′
                    
                    ⁢
                    g
                  
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  
                    B
                    
                      i
                      ,
                      j
                      ,
                      
                        n
                        -
                        1
                      
                    
                    ′′
                  
                  :=
                  
                    
                      μ
                      
                        i
                        ,
                        j
                        ,
                        
                          n
                          -
                          1
                        
                      
                      ′′
                    
                    ⁢
                    g
                  
                
                ,
                
                  
                    B
                    
                      i
                      ,
                      j
                    
                    ′′′
                  
                  :=
                  
                    
                      μ
                      
                        i
                        ,
                        j
                      
                      ′′′
                    
                    ⁢
                    g
                  
                
              
              }
            
            
              i
              ,
              
                j
                =
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              6
            
          
        
      
    
    
      
        (
        7
        )
      
    
  
  
    
      
        {
        
          
            
              B
              
                i
                ,
                j
              
              *
            
            :=
            
              
                v
                
                  i
                  ,
                  j
                
              
              ⁢
              g
            
          
          ,
          
            
              B
              
                i
                ,
                j
                ,
                2
              
              
                ′
                *
              
            
            :=
            
              
                v
                
                  i
                  ,
                  j
                  ,
                  2
                
                ′
              
              ⁢
              g
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              B
              
                i
                ,
                j
                ,
                n
              
              
                ′
                *
              
            
            :=
            
              
                v
                
                  i
                  ,
                  j
                  ,
                  n
                
                ′
              
              ⁢
              g
            
          
          ,
          
            
               
              
                
                  
                    B
                    
                      i
                      ,
                      j
                      ,
                      1
                    
                    ′′
                  
                  :=
                  
                    
                      v
                      
                        i
                        ,
                        j
                        ,
                        1
                      
                      ′′
                    
                    ⁢
                    g
                  
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  
                    B
                    
                      i
                      ,
                      j
                      ,
                      
                        n
                        -
                        1
                      
                    
                    
                      ′′
                      *
                    
                  
                  :=
                  
                    
                      v
                      
                        i
                        ,
                        j
                        ,
                        
                          n
                          -
                          1
                        
                      
                      ′′
                    
                    ⁢
                    g
                  
                
                ,
                
                  
                    B
                    
                      i
                      ,
                      j
                    
                    
                      ′′′
                      *
                    
                  
                  :=
                  
                    
                      v
                      
                        i
                        ,
                        j
                      
                      ′′′
                    
                    :=
                    g
                  
                
              
              }
            
            
              i
              ,
              
                j
                =
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              6
            
          
        
      
    
    
      
        (
        8
        )
      
    
  
  
    
      
        
          
        
        ⁢
        
          
            param
            V
          
          :=
          
            (
            
              
                param
                
                  V
                  ′
                
              
              ,
              
                g
                T
              
            
            )
          
        
      
    
    
      
        (
        9
        )
      
    
  




That is, the master key generation part 110 executes the following process (1) through (9).
(1), (3), (4), and (9) are the same as those in Embodiment 1, and thus will not be described.
(2) Using the processing device, the master key generation part 110 sets 6n in N. Note that n is an integer of 1 or more.
(5) Using the processing device, the master key generation part 110 takes as input n of N:=6n set in (2) and Fq, and randomly generates a linear transformation X:=(χi,j).
(6) Using the processing device, the master key generation part 110 generates (νi,j):=ψ·(X−1)T based on the random number ψ generated in (4) and the linear transformation X generated in (5).
In the following, {ui,j, u′i,j,2, . . . , u′i,j,n, u′′i,j,1, . . . , u′′i,j,n−1, u′′′i,j}i,j=1, . . . , 6 denotes non-zero elements in the linear transformation X. {vi,j, v′i,j,2, . . . , v′i,j,n, v′′i,j,1, . . . , v′′i,j,n−1, v′′′i,j}i,j=1, . . . , 6 denotes non-zero elements in the adjoint matrix ψ·(X−1)T.
(7) Using the processing device, the master key generation part 110 generates a basis B based on the linear transformation X generated in (5).
(8) Using the processing device, the master key generation part 110 generates a basis B* based on the adjoint matrix ψ·(X−1)T generated in (6).
Here, Formula 136 holds, and note that the basis B:=(b1, . . . , b6n) and the basis B*:=(b*1, . . . , b*6n). Note that a blank element in the matrix denotes the constant element 0εG, and that the bases B and B* are orthonormal bases. That is, for 1≦i≠j≦6n, e(bi, b*i)=gT and e(bi, b*j)=1.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      136
    
    ]
  




  
    
      
        (
        
          
            
              
                b
                
                  
                    
                      (
                      
                        i
                        -
                        1
                      
                      )
                    
                    ⁢
                    n
                  
                  +
                  1
                
              
            
          
          
            
              ⋮
            
          
          
            
              ⋮
            
          
          
            
              
                b
                
                  i
                  ⁢
                  
                    
                  
                  ⁢
                  n
                
              
            
          
        
        )
      
      :=
      
        (
        
          
            
              
                B
                
                  i
                  ,
                  1
                  ,
                  1
                
                ′′
              
            
            
              
                B
                
                  i
                  ,
                  1
                  ,
                  2
                
                ′′
              
            
            
              ...
            
            
              
                B
                
                  i
                  ,
                  
                    
                      1
                      ⁢
                      n
                    
                    -
                    1
                  
                
                ′′
              
            
            
              
                B
                
                  i
                  ,
                  1
                
                ′′′
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  1
                
                ′′
              
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  2
                
                ′′
              
            
            
              ...
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  
                    n
                    -
                    1
                  
                
                ′′
              
            
            
              
                B
                
                  i
                  ,
                  6
                
                ′′′
              
            
          
          
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  1
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  1
                  ,
                  2
                
                ′
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  2
                
                ′
              
            
          
          
            
              
                
              
            
            
              
                
              
            
            
              ⋱
            
            
              
                
              
            
            
              ⋮
            
            
              ...
            
            
              
                
              
            
            
              
                
              
            
            
              ⋱
            
            
              
                
              
            
            
              ⋮
            
          
          
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  1
                
              
            
            
              
                B
                
                  i
                  ,
                  1
                  ,
                  
                    n
                    -
                    1
                  
                
                ′
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  
                    n
                    -
                    1
                  
                
                ′
              
            
          
          
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  1
                  ,
                  n
                
                ′
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  n
                
                ′
              
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        (
        
          
            
              
                b
                
                  
                    
                      (
                      
                        i
                        -
                        1
                      
                      )
                    
                    ⁢
                    n
                  
                  +
                  1
                
                *
              
            
          
          
            
              ⋮
            
          
          
            
              ⋮
            
          
          
            
              
                b
                
                  i
                  ⁢
                  
                    
                  
                  ⁢
                  n
                
                *
              
            
          
        
        )
      
      :=
      
        (
        
          
            
              
                B
                
                  i
                  ,
                  1
                  ,
                  1
                
                
                  ′′
                  *
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  1
                
                
                  ′′
                  *
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
          
          
            
              
                B
                
                  i
                  ,
                  1
                  ,
                  2
                
                
                  ′′
                  *
                
              
            
            
              
                B
                
                  i
                  ,
                  1
                
                *
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  2
                
                
                  ′′
                  *
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                
                *
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                
              
            
          
          
            
              ⋮
            
            
              
                
              
            
            
              ⋱
            
            
              
                
              
            
            
              
                
              
            
            
              ...
            
            
              ⋮
            
            
              
                
              
            
            
              ⋱
            
            
              
                
              
            
            
              
                
              
            
          
          
            
              
                B
                
                  i
                  ,
                  
                    
                      1
                      ⁢
                      n
                    
                    -
                    1
                  
                
                
                  ′′
                  *
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  1
                
                *
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  
                    
                      6
                      ⁢
                      n
                    
                    -
                    1
                  
                
                
                  ′′
                  *
                
              
            
            
              
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                
                *
              
            
            
              
                
              
            
          
          
            
              
                B
                
                  i
                  ,
                  1
                
                
                  ′′′
                  *
                
              
            
            
              
                B
                
                  i
                  ,
                  1
                  ,
                  2
                
                
                  ′
                  *
                
              
            
            
              ...
            
            
              
                B
                
                  i
                  ,
                  1
                  ,
                  
                    n
                    -
                    1
                  
                
                
                  ′
                  *
                
              
            
            
              
                B
                
                  i
                  ,
                  1
                  ,
                  n
                
                
                  ′
                  *
                
              
            
            
              
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                
                
                  ′′′
                  *
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  2
                
                
                  ′
                  *
                
              
            
            
              ...
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  
                    n
                    -
                    1
                  
                
                
                  ′
                  *
                
              
            
            
              
                B
                
                  i
                  ,
                  6
                  ,
                  n
                
                
                  ′
                  *
                
              
            
          
        
        )
      
    
  



(S102: Conversion Key Generation Step)
Using the processing device, the master key generation part 110 generates conversion information W, as indicated in Formula 137. The master key generation part 110 designates the conversion information W as a conversion key ck.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      137
    
    ]
  




  
    W
    ⁢
    
      ⟵
      U
    
    ⁢
    
      L
      ⁡
      
        (
        
          6
          ,
          n
          ,
          
            F
            q
          
        
        )
      
    
  



(S103: Public Key Generation Step)
Using the processing device, the master key generation part 110 converts the basis B generated in S101 with the conversion information W, as indicated in Formula 138, and thus generates a basis D:=(d1, . . . , d6n). Then, using the processing device, the master key generation part 110 generates a subbasis D^ of the basis D, as indicated in Formula 138. Here, like the basis B indicated in Formula 136, the basis D is constructed with {Di,j, D′i,j,2, . . . , D′i,j,n, D′′i,j,1, . . . , D′′i,j,n−1, D′′′i,j}i,j=1, . . . , 6.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      138
    
    ]
  




  
    
      D
      :=
      
        
          (
          
            
              
                
                  d
                  1
                
              
            
            
              
                ⋮
              
            
            
              
                
                  d
                  
                    6
                    ⁢
                    n
                  
                
              
            
          
          )
        
        :=
        
          
            (
            
              
                
                  
                    b
                    1
                  
                
              
              
                
                  ⋮
                
              
              
                
                  
                    b
                    
                      6
                      ⁢
                      n
                    
                  
                
              
            
            )
          
          ·
          W
        
      
    
    ,
    
      

    
    ⁢
    
      using
      ⁢
      
        
      
      ⁢
      
        
          {
          
            
              D
              
                i
                ,
                j
              
            
            ,
            
              D
              
                i
                ,
                j
                ,
                2
              
              ′
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              D
              
                i
                ,
                j
                ,
                n
              
              ′
            
            ,
            
              D
              
                i
                ,
                j
                ,
                1
              
              ′′
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              D
              
                i
                ,
                j
                ,
                
                  n
                  -
                  1
                
              
              ′′
            
            ,
            
              D
              
                i
                ,
                j
              
              ′′′
            
          
          }
        
        
          i
          ,
          
            j
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          6
        
      
    
    ,
    
      

    
    ⁢
    
      
        D
        ^
      
      :=
      
        
          {
          
            
              D
              
                i
                ,
                j
              
            
            ,
            
              D
              
                i
                ,
                j
                ,
                2
              
              ′
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              D
              
                i
                ,
                j
                ,
                n
              
              ′
            
            ,
            
              D
              
                i
                ,
                j
                ,
                1
              
              ′′
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              D
              
                i
                ,
                j
                ,
                
                  n
                  -
                  1
                
              
              ′′
            
            ,
            
              D
              
                i
                ,
                j
              
              ′′′
            
          
          }
        
        
          
            i
            =
            1
          
          ,
          
            6
            ;
            
              j
              =
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          6
        
      
    
  



The master key generation part 110 designates a combination of the generated subbasis D^, the security parameter λ inputted in S101, and paramv generated in S101 as a public key pk.
(S104: Secret Key Generation Step)
Using the processing device, the master key generation part 110 generates a subbasis B*^ of the basis B* generated in S101, as indicated in Formula 139.

:={B*i,j,B′*i,j,2, . . . ,B′*i,j,n,B′′*i,j,1, . . . ,B′′*i,j,n−1,B′′′*i,j}i=1,5;j=1, . . . ,6  [Formula 139]

The master key generation part 110 designates the generated subbasis B*^ as a secret key sk.
(S105: Key Storage Step)
The master key storage part 120 stores the conversion key ck generated in S102, the public key pk generated in S103, and the secret key sk generated in S104 in the storage device.
In brief, in S101 through S104, the key generation device 100 generates the conversion key ck, the public key pk, and the secret key sk by executing the Setup algorithm indicated in Formula 140. Note that a GZIPE,SKob algorithm is as indicated in Formula 141. In S105, the key generation device 100 stores the conversion key ck, the public key pk, and the secret key sk that have been generated in the storage device.



  
    
      
    
    ⁢
    
      [
      
        Formula
        ⁢
        
          
        
        ⁢
        140
      
      ]
    
  




  
    
      
    
    ⁢
    
      Setup
      ⁢
      
        
      
      ⁢
      
        (
        
          
            1
            λ
          
          ,
          n
        
        )
      
      ⁢
      
        :
      
    
  




  
    
      
        (
        
          
            param
            V
          
          ,
          
            
              {
              
                
                  B
                  
                    i
                    ,
                    j
                  
                
                ,
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    2
                  
                  ′
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    n
                  
                  ′
                
                ,
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    1
                  
                  ′′
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    
                      n
                      -
                      1
                    
                  
                  ′′
                
                ,
                
                  B
                  
                    i
                    ,
                    j
                  
                  ′′′
                
              
              }
            
            
              i
              ,
              
                j
                =
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              6
            
          
          ,
          
            
              {
              
                
                  B
                  
                    i
                    ,
                    j
                  
                  *
                
                ,
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    2
                  
                  
                    ′
                    *
                  
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    n
                  
                  
                    ′
                    *
                  
                
                ,
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    1
                  
                  
                    ′′
                    *
                  
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    
                      n
                      -
                      1
                    
                  
                  
                    ′′
                    *
                  
                
                ,
                
                  B
                  
                    i
                    ,
                    j
                  
                  
                    ′′′
                    *
                  
                
              
              }
            
            
              i
              ,
              
                j
                =
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              6
            
          
        
        )
      
      ⁢
      
        

      
      ⁢
      
        
      
      ⁢
      
        ⟵
        R
      
      ⁢
      
        
          G
          ob
          
            ZIPE
            ,
            SK
          
        
        ⁡
        
          (
          
            
              1
              λ
            
            ,
            6
            ,
            n
          
          )
        
      
    
    ,
    
      

    
    ⁢
    
      
    
    ⁢
    
      W
      ⁢
      
        ⟵
        U
      
      ⁢
      
        L
        ⁡
        
          (
          
            6
            ,
            n
            ,
            
              F
              q
            
          
          )
        
      
    
    ,
    
      
        (
        
          
            
              
                d
                1
              
            
          
          
            
              ⋮
            
          
          
            
              
                d
                
                  6
                  ⁢
                  n
                
              
            
          
        
        )
      
      :=
      
        
          (
          
            
              
                
                  b
                  1
                
              
            
            
              
                ⋮
              
            
            
              
                
                  b
                  
                    6
                    ⁢
                    n
                  
                
              
            
          
          )
        
        ·
        W
      
    
    ,
    
      

    
    ⁢
    
      
    
    ⁢
    
      using
      ⁢
      
        
      
      ⁢
      
        
          {
          
            
              D
              
                i
                ,
                j
              
            
            ,
            
              D
              
                i
                ,
                j
                ,
                2
              
              ′
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              D
              
                i
                ,
                j
                ,
                n
              
              ′
            
            ,
            
              D
              
                i
                ,
                j
                ,
                1
              
              ′′
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              D
              
                i
                ,
                j
                ,
                
                  n
                  -
                  1
                
              
              ′′
            
            ,
            
              D
              
                i
                ,
                j
              
              ′′′
            
          
          }
        
        
          i
          ,
          
            j
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          6
        
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        p
        ⁢
        
          
        
        ⁢
        k
      
      :=
      
        (
        
          
            1
            λ
          
          ,
          
            param
            V
          
          ,
          
            
              {
              
                
                  D
                  
                    i
                    ,
                    j
                  
                
                ,
                
                  D
                  
                    i
                    ,
                    j
                    ,
                    2
                  
                  ′
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  D
                  
                    i
                    ,
                    j
                    ,
                    n
                  
                  ′
                
                ,
                
                  D
                  
                    i
                    ,
                    j
                    ,
                    1
                  
                  ′′
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  D
                  
                    i
                    ,
                    j
                    ,
                    
                      n
                      -
                      1
                    
                  
                  ′′
                
                ,
                
                  D
                  
                    i
                    ,
                    j
                  
                  ′′′
                
              
              }
            
            
              
                i
                =
                1
              
              ,
              
                6
                ;
                
                  j
                  =
                  1
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              6
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
    
    ⁢
    
      ck
      :=
      W
    
    ,
    
      

    
    ⁢
    
      sk
      :=
      
        
          
            {
            
              
                B
                
                  i
                  ,
                  j
                
                *
              
              ,
              
                B
                
                  i
                  ,
                  j
                  ,
                  2
                
                
                  ′
                  *
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                B
                
                  i
                  ,
                  j
                  ,
                  n
                
                
                  ′
                  *
                
              
              ,
              
                B
                
                  i
                  ,
                  j
                  ,
                  1
                
                
                  ′′
                  *
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                B
                
                  i
                  ,
                  j
                  ,
                  
                    n
                    -
                    1
                  
                
                
                  ′′
                  *
                
              
              ,
              
                B
                
                  i
                  ,
                  j
                
                
                  ′′′
                  *
                
              
            
            }
          
          
            
              i
              =
              1
            
            ,
            
              5
              ;
              
                j
                =
                1
              
            
            ,
            ...
            ⁢
            
              
            
            ,
            6
          
        
        .
        
          

        
        ⁢
        
          
        
        ⁢
        
          [
          
            Formula
            ⁢
            
              
            
            ⁢
            141
          
          ]
        
      
    
  




  
    
      
    
    ⁢
    
      
        
          G
          ob
          
            ZIPE
            ,
            SK
          
        
        ⁡
        
          (
          
            
              1
              λ
            
            ,
            6
            ,
            n
          
          )
        
      
      ⁢
      
        :
      
    
  




  
    
      
    
    ⁢
    
      
        
          param
          G
        
        :=
        
          
            
              (
              
                q
                ,
                G
                ,
                
                  G
                  T
                
                ,
                g
                ,
                e
              
              )
            
            ⁢
            
              ⟵
              R
            
            ⁢
            
              G
              bpg
            
          
          ⁢
          
            (
            
              1
              λ
            
            )
          
        
      
      ,
      
        

      
      ⁢
      
        
      
      ⁢
      
        N
        :=
        
          6
          ⁢
          n
        
      
      ,
      
        ψ
        ⁢
        
          ⟵
          U
        
        ⁢
        
          F
          q
          ×
        
      
      ,
      
        
          g
          T
        
        :=
        
          
            e
            ⁡
            
              (
              
                g
                ,
                g
              
              )
            
          
          ψ
        
      
      ,
      
        

      
      ⁢
      
        
      
      ⁢
      
        
          param
          
            V
            ′
          
        
        :=
        
          
            (
            
              q
              ,
              V
              ,
              
                G
                T
              
              ,
              A
              ,
              e
            
            )
          
          :=
          
            
              G
              dpvs
            
            ⁢
            
              (
              
                
                  1
                  λ
                
                ,
                N
                ,
                
                  param
                  G
                
              
              )
            
          
        
      
      ,
      
        

      
      ⁢
      
        
      
      ⁢
      
        
          param
          V
        
        :=
        
          (
          
            
              param
              
                V
                ′
              
            
            ,
            
              g
              T
            
          
          )
        
      
      ,
      
        X
        ⁢
        
          ⟵
          U
        
        ⁢
        
          L
          ⁡
          
            (
            
              6
              ,
              n
              ,
              
                F
                q
              
            
            )
          
        
      
      ,
      hereafter
      ,
      
        

      
      ⁢
      
        
      
      ⁢
      
        
          {
          
            
              μ
              
                i
                ,
                j
              
            
            ,
            
              μ
              
                i
                ,
                j
                ,
                2
              
              ′
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              μ
              
                i
                ,
                j
                ,
                n
              
              ′
            
            ,
            
              μ
              
                i
                ,
                j
                ,
                1
              
              ′′
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              μ
              
                i
                ,
                j
                ,
                
                  n
                  -
                  1
                
              
              ′′
            
            ,
            
              μ
              
                i
                ,
                j
              
              ′′′
            
          
          }
        
        
          i
          ,
          
            j
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          6
        
      
    
  




  
    
      
    
    ⁢
    
      
        denotes
        ⁢
        
          
        
        ⁢
        non
        ⁢
        
          -
        
        ⁢
        zero
        ⁢
        
          
        
        ⁢
        entries
        ⁢
        
          
        
        ⁢
        of
        ⁢
        
          
        
        ⁢
        X
      
      ,
      
        

      
      ⁢
      
        
      
      ⁢
      
        and
        ⁢
        
          
        
        ⁢
        
          
            {
            
              
                v
                
                  i
                  ,
                  j
                
              
              ,
              
                v
                
                  i
                  ,
                  j
                  ,
                  2
                
                ′
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                v
                
                  i
                  ,
                  j
                  ,
                  n
                
                ′
              
              ,
              
                v
                
                  i
                  ,
                  j
                  ,
                  1
                
                ′′
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                v
                
                  i
                  ,
                  j
                  ,
                  
                    n
                    -
                    1
                  
                
                ′′
              
              ,
              
                v
                
                  i
                  ,
                  j
                
                ′′′
              
            
            }
          
          
            i
            ,
            
              j
              =
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            6
          
        
      
    
  




  
    
      
    
    ⁢
    
      
        denotes
        ⁢
        
          
        
        ⁢
        non
        ⁢
        
          -
        
        ⁢
        zero
        ⁢
        
          
        
        ⁢
        entries
        ⁢
        
          
        
        ⁢
        of
        ⁢
        
          
        
        ⁢
        
          
            ψ
            ⁡
            
              (
              
                X
                
                  -
                  1
                
              
              )
            
          
          T
        
      
      ,
      
        

      
      ⁢
      
        {
        
          
            
              B
              
                i
                ,
                j
              
            
            :=
            
              
                μ
                
                  i
                  ,
                  j
                
              
              ⁢
              g
            
          
          ,
          
            
              B
              
                i
                ,
                j
                ,
                2
              
              ′
            
            :=
            
              
                μ
                
                  i
                  ,
                  j
                  ,
                  2
                
                ′
              
              ⁢
              g
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
              B
              
                i
                ,
                j
                ,
                n
              
              ′
            
            :=
            
              
                μ
                
                  i
                  ,
                  j
                  ,
                  n
                
                ′
              
              ⁢
              g
            
          
          ,
          
            
              B
              
                i
                ,
                j
                ,
                1
              
              ′′
            
            :=
            
              
                μ
                
                  i
                  ,
                  j
                  ,
                  1
                
                ′′
              
              ⁢
              g
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            
               
              
                
                  
                    B
                    
                      i
                      ,
                      j
                      ,
                      
                        n
                        -
                        1
                      
                    
                    ′′
                  
                  :=
                  
                    
                      μ
                      
                        i
                        ,
                        j
                        ,
                        
                          n
                          -
                          1
                        
                      
                      ′′
                    
                    ⁢
                    g
                  
                
                ,
                
                  
                    B
                    
                      i
                      ,
                      j
                    
                    ′′′
                  
                  :=
                  
                    
                      μ
                      
                        i
                        ,
                        j
                      
                      ′′′
                    
                    ⁢
                    g
                  
                
              
              }
            
            
              i
              ,
              
                j
                =
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              6
            
          
          ,
          
            

          
          ⁢
          
            {
            
              
                
                  B
                  
                    i
                    ,
                    j
                  
                  *
                
                :=
                
                  
                    v
                    
                      i
                      ,
                      j
                    
                  
                  ⁢
                  g
                
              
              ,
              
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    2
                  
                  
                    ′
                    *
                  
                
                :=
                
                  
                    v
                    
                      i
                      ,
                      j
                      ,
                      2
                    
                    ′
                  
                  ⁢
                  g
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    n
                  
                  
                    ′
                    *
                  
                
                :=
                
                  
                    v
                    
                      i
                      ,
                      j
                      ,
                      n
                    
                    ′
                  
                  ⁢
                  g
                
              
              ,
              
                
                  B
                  
                    i
                    ,
                    j
                    ,
                    1
                  
                  
                    ′′
                    *
                  
                
                :=
                
                  
                    v
                    
                      i
                      ,
                      j
                      ,
                      1
                    
                    ′′
                  
                  ⁢
                  g
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                
                   
                  
                    
                      
                        B
                        
                          i
                          ,
                          j
                          ,
                          
                            n
                            -
                            1
                          
                        
                        
                          ′′
                          *
                        
                      
                      :=
                      
                        
                          v
                          
                            i
                            ,
                            j
                            ,
                            
                              n
                              -
                              1
                            
                          
                          ′′
                        
                        ⁢
                        g
                      
                    
                    ,
                    
                      
                        B
                        
                          i
                          ,
                          j
                        
                        
                          ′′′
                          *
                        
                      
                      :=
                      
                        
                          v
                          
                            i
                            ,
                            j
                          
                          ′′′
                        
                        ⁢
                        g
                      
                    
                  
                  }
                
                
                  i
                  ,
                  
                    j
                    =
                    1
                  
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  6
                
              
              ,
              
                

              
              ⁢
              
                
                  return
                  (
                  
                    
                      param
                      V
                    
                    ,
                    
                      
                        {
                        
                          
                            B
                            
                              i
                              ,
                              j
                            
                          
                          ,
                          
                            B
                            
                              i
                              ,
                              j
                              ,
                              2
                            
                            ′
                          
                          ,
                          ...
                          ⁢
                          
                            
                          
                          ,
                          
                            B
                            
                              i
                              ,
                              j
                              ,
                              n
                            
                            ′
                          
                          ,
                          
                            B
                            
                              i
                              ,
                              j
                              ,
                              1
                            
                            ′′
                          
                          ,
                          ...
                          ⁢
                          
                            
                          
                          ,
                          
                            B
                            
                              i
                              ,
                              j
                              ,
                              
                                n
                                -
                                1
                              
                            
                            ′′
                          
                          ,
                          
                            B
                            
                              i
                              ,
                              j
                            
                            ′′′
                          
                        
                        }
                      
                      
                        i
                        ,
                        
                          j
                          =
                          1
                        
                        ,
                        ...
                        ⁢
                        
                          
                        
                        ,
                        6
                      
                    
                    ,
                    
                      
                        {
                        
                          
                            B
                            
                              i
                              ,
                              j
                            
                            *
                          
                          ,
                          
                            B
                            
                              i
                              ,
                              j
                              ,
                              2
                            
                            
                              ′
                              *
                            
                          
                          ,
                          ...
                          ⁢
                          
                            
                          
                          ,
                          
                            B
                            
                              i
                              ,
                              j
                              ,
                              n
                            
                            
                              ′
                              *
                            
                          
                          ,
                          
                            B
                            
                              i
                              ,
                              j
                              ,
                              1
                            
                            
                              ′′
                              *
                            
                          
                          ,
                          ...
                          ⁢
                          
                            
                          
                          ,
                          
                            B
                            
                              i
                              ,
                              j
                              ,
                              
                                n
                                -
                                1
                              
                            
                            
                              ′′
                              *
                            
                          
                          ,
                          
                            B
                            
                              i
                              ,
                              j
                            
                            
                              ′′′
                              *
                            
                          
                        
                        }
                      
                      
                        i
                        ,
                        
                          j
                          =
                          1
                        
                        ,
                        ...
                        ⁢
                        
                          
                        
                        ,
                        6
                      
                    
                  
                  )
                
                .
              
            
          
        
      
    
  



With reference to FIG. 7, the process of the TokenGen algorithm will be described.
S201 is the same as that in Embodiment 1, and thus will not be described.
(S202: Random Number Generation Step)
Using the processing device, the token generation part 140 generates random numbers, as indicated in Formula 142.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      142
    
    ]
  




  
    σ
    ,
    
      η
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        η
        n
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
  



(S203: Token Element Generation Step)
Using the processing device, the token generation part 140 generates an element k* of a token tkv, as indicated in Formula 143.

for j=1, . . . ,6,

K*j,1:=ΣL=1n−1(σνLB′′*1,j,L+ηLB′′*5,j,L)+σνnB′′′*1,j+ηnB′′′*5,j,

K*j,L:=σ(νLB*1,j+νnB′*1,j,L)+ηLB*5,j+ηLB′*5,j,L for L=2, . . . ,n−1,

K*j,n:=σνnB′*1,j,n+ηnB′*5,j,n,

k*:=(K*1,1, . . . ,K*1,n, . . . ,K*6,1, . . . ,K*6,n)ε6n  [Formula 143]

(S204: Token Transmission Step)
Using the communication device and via the network, for example, the token transmission part 150 transmits the token tkv having the element k* generated in S203 to the decryption device 400 in secrecy. As a matter of course, the token tkv may be transmitted to the decryption device 400 by another method.
In brief, in S201 through S203, the key generation device 100 generates the token tkv by executing the TokenGen algorithm indicated in Formula 144. In S204, the key generation device 100 transmits the generated token tkv to the decryption device 400.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      144
    
    ]
  




  
    
      TokenGen
      ⁡
      
        (
        
          
            p
            ⁢
            
              
            
            ⁢
            k
          
          ,
          sk
          ,
          
            
              v
              →
            
            ∈
            
              
                F
                q
                n
              
              ⁢
              \
              ⁢
              
                {
                
                  0
                  →
                
                }
              
            
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    σ
    ,
    
      η
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        η
        k
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      

    
    ⁢
    
      
        for
        ⁢
        
          
        
        ⁢
        j
      
      =
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    6
  




  
    
      
        K
        
          j
          ,
          1
        
        *
      
      :=
      
        
          
            ∑
            
              L
              =
              1
            
            
              n
              -
              1
            
          
          ⁢
          
            (
            
              
                σ
                ⁢
                
                  
                
                ⁢
                
                  v
                  L
                
                ⁢
                
                  B
                  
                    1
                    ,
                    j
                    ,
                    L
                  
                  
                    ′′
                    *
                  
                
              
              +
              
                
                  η
                  L
                
                ⁢
                
                  B
                  
                    5
                    ,
                    j
                    ,
                    L
                  
                  
                    ′′
                    *
                  
                
              
            
            )
          
        
        +
        
          σ
          ⁢
          
            
          
          ⁢
          
            v
            n
          
          ⁢
          
            B
            
              1
              ,
              j
            
            
              ′′′
              *
            
          
        
        +
        
          
            η
            n
          
          ⁢
          
            B
            
              5
              ,
              j
            
            
              ′′′
              *
            
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        K
        
          j
          ,
          L
        
        *
      
      :=
      
        
          σ
          ⁡
          
            (
            
              
                
                  v
                  L
                
                ⁢
                
                  B
                  
                    1
                    ,
                    j
                  
                  *
                
              
              +
              
                
                  v
                  n
                
                ⁢
                
                  B
                  
                    1
                    ,
                    j
                    ,
                    L
                  
                  
                    ′
                    *
                  
                
              
            
            )
          
        
        +
        
          
            η
            L
          
          ⁢
          
            B
            
              5
              ,
              j
            
            *
          
        
        +
        
          
            η
            L
          
          ⁢
          
            B
            
              5
              ,
              j
              ,
              L
            
            
              ′
              *
            
          
        
      
    
  




  
    
      
        for
        ⁢
        
          
        
        ⁢
        L
      
      =
      2
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      n
      -
      1
    
    ,
    
      

    
    ⁢
    
      
        K
        
          j
          ,
          n
        
        *
      
      :=
      
        
          σ
          ⁢
          
            
          
          ⁢
          
            v
            n
          
          ⁢
          
            B
            
              1
              ,
              j
              ,
              n
            
            
              ′
              *
            
          
        
        +
        
          
            η
            n
          
          ⁢
          
            B
            
              5
              ,
              j
              ,
              n
            
            
              ′
              *
            
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        k
        *
      
      :=
      
        
          (
          
            
              K
              
                1
                ,
                1
              
              *
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              K
              
                1
                ,
                n
              
              *
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              K
              
                6
                ,
                1
              
              *
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              K
              
                6
                ,
                n
              
              *
            
          
          )
        
        ∈
        
          G
          
            6
            ⁢
            n
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        
          tk
          v
        
      
      :=
      
        
          k
          *
        
        .
      
    
  



With reference to FIG. 8, the process of the Enc algorithm will be described.
S301 and S302 are the same as those in Embodiment 1, and thus will not be described.
(S303: Random Number Generation Step)
Using the processing device, the ciphertext generation part 230 generates random numbers, as indicated in Formula 145.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      145
    
    ]
  




  
    ω
    ,
    
      φ
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        φ
        n
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
  



(S304: Cipher Element Generation Step)
Using the processing device, the ciphertext generation part 230 generates an element f of a ciphertext ctx, as indicated in Formula 146.

for j=1, . . . ,6,

Fj,1:=ωx1D′′1,j,1+σ1D′′6,j,1,

Fj,L:=ω(x1D′′1,j,L+xLD1,j)+φ1D′′6,j,L+φLD6,j for L=2, . . . ,n−1,

Fj,n:=ωx1D′′′1,j+φ1D′′′6,j+ΣL=2n(ωxLD′′1,j,L+φLD′′6,j,L),

f:=(F1,1, . . . ,F1,n, . . . ,F6,1, . . . ,F6,n)ε6n 

(S305: Data Transmission Step)
Using the communication device and via the network, for example, the data transmission part 240 transmits the ciphertext ctx including the element f generated in S304 to the conversion device 300. As a matter of course, the ciphertext ctx may be transmitted to the conversion device 300 by another method.
In brief, in S301 through S304, the encryption device 200 generates the ciphertext ctx by executing the Enc algorithm indicated in Formula 147. In S305, the encryption device 200 transmits the generated ciphertext ctx to the conversion device 300.



  
    
      
        
          
            [
            
              Formula
              ⁢
              
                
              
              ⁢
              147
            
            ]
          
          ⁢
          
            

          
          ⁢
          
            Enc
            ⁢
            
              (
              
                
                  p
                  ⁢
                  
                    
                  
                  ⁢
                  k
                
                ,
                
                  
                    x
                    →
                  
                  ∈
                  
                    F
                    q
                    n
                  
                
              
            
          
        
        }
      
      )
    
    ⁢
    
      :
    
  




  
    ω
    ,
    
      φ
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        φ
        n
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      

    
    ⁢
    
      
        for
        ⁢
        
          
        
        ⁢
        j
      
      =
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    6
    ,
    
      

    
    ⁢
    
      
        F
        
          j
          ,
          1
        
      
      :=
      
        
          ω
          ⁢
          
            
          
          ⁢
          
            x
            1
          
          ⁢
          
            D
            
              1
              ,
              j
              ,
              1
            
            ′′
          
        
        +
        
          
            φ
            1
          
          ⁢
          
            D
            
              6
              ,
              j
              ,
              1
            
            ′′
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        F
        
          j
          ,
          L
        
      
      :=
      
        
          ω
          ⁡
          
            (
            
              
                
                  x
                  1
                
                ⁢
                
                  D
                  
                    1
                    ,
                    j
                    ,
                    L
                  
                  ′′
                
              
              +
              
                
                  x
                  L
                
                ⁢
                
                  D
                  
                    1
                    ,
                    j
                  
                
              
            
            )
          
        
        +
        
          
            φ
            1
          
          ⁢
          
            D
            
              6
              ,
              j
              ,
              L
            
            ′′
          
        
        +
        
          
            φ
            L
          
          ⁢
          
            D
            
              6
              ,
              j
            
          
        
      
    
  




  
    
      
        for
        ⁢
        
          
        
        ⁢
        L
      
      =
      2
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      n
      -
      1
    
    ,
    
      

    
    ⁢
    
      
        F
        
          j
          ,
          n
        
      
      :=
      
        
          ω
          ⁢
          
            
          
          ⁢
          
            x
            1
          
          ⁢
          
            D
            
              1
              ,
              j
            
            ′′′
          
        
        +
        
          
            φ
            1
          
          ⁢
          
            D
            
              6
              ,
              j
            
            ′′′
          
        
        +
        
          
            ∑
            
              L
              =
              2
            
            n
          
          ⁢
          
            (
            
              
                ω
                ⁢
                
                  
                
                ⁢
                
                  x
                  L
                
                ⁢
                
                  D
                  
                    1
                    ,
                    j
                    ,
                    L
                  
                  ′′
                
              
              +
              
                
                  φ
                  L
                
                ⁢
                
                  D
                  
                    6
                    ,
                    j
                    ,
                    L
                  
                  ′′
                
              
            
            )
          
        
      
    
    ,
    
      

    
    ⁢
    
      f
      :=
      
        
          (
          
            
              F
              
                1
                ,
                1
              
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              F
              
                1
                ,
                n
              
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              F
              
                6
                ,
                1
              
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              F
              
                6
                ,
                n
              
            
          
          )
        
        ∈
        
          G
          
            6
            ⁢
            n
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        
          ct
          x
        
      
      :=
      
        f
        .
      
    
  



The Conv algorithm and the Query algorithm are the same as those in Embodiment 1, and thus will not be described. However, in S403 of the Conv algorithm, the random number y is generated as indicated in Formula 148.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      149
    
    ]
  




  
    
      y
      ⁢
      
        ⟵
        U
      
      ⁢
      span
    
    ⁢
    
      〈
      
        
          d
          
            
              5
              ⁢
              n
            
            +
            1
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          d
          
            6
            ⁢
            n
          
        
      
      〉
    
  



Note that {Di,j, D′i,j,2, . . . , D′i,j,n, D′′i,j,1, . . . , D′′i,j,n−1, D′′′i,j}i=1,6;i,j=1, . . . , 6 which is a part of the output of the Setup algorithm is identified with the basis D^:=(d1, . . . , dn, d5n+1, . . . , d6n). The basis D:=(d1, . . . , d6n) is identified with {Di,j, D′i,j,2, . . . , D′i,j,n, D′′i,j,1, . . . , D′′i,j,n−1, D′′′i,j}i,j=1, . . . , 6.
{B*i,j, B′*i,j,2, . . . , B′*i,j,n, B′′*i,j,1, . . . , B′′*i,j,n−1, B′′′*i,j}i=1,5;i,j=1, . . . , 6 is identified with the basis B*^ :=(B*1, . . . , B*n, B*4n+1, . . . , B*5n). The basis B*:=(d*1, . . . , d*6n) is identified with {B*i,j, B′*i,j,2, . . . , B′*i,j,n, B′′*i,j,1, . . . , B′′*i,j,n−1,B′′′*i,j}i,j=1, . . . , 6.
Then, c and k* in the Query algorithm can be represented as indicated in Formula 149.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      149
    
    ]
  




  
    
      c
      :=
      
        
          (
          
            
              
                ω
                ⁢
                
                  
                
                ⁢
                
                  x
                  →
                
              
              
                {
                n
              
            
            ,
            
              
                0
                
                  3
                  ⁢
                  n
                
              
              
                {
                
                  3
                  ⁢
                  n
                
              
            
            ,
            
              
                0
                n
              
              
                {
                n
              
            
            ,
            
              
                φ
                →
              
              
                {
                n
              
            
          
          )
        
        B
      
    
    ,
    
      

    
    ⁢
    
      
        where
        ⁢
        
          
        
        ⁢
        
          φ
          →
        
      
      :=
      
        
          (
          
            
              φ
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              φ
              n
            
          
          )
        
        ∈
        
          F
          q
          n
        
      
    
    ,
    
      

    
    ⁢
    
      
        k
        *
      
      :=
      
        
          (
          
            
              
                σ
                ⁢
                
                  
                
                ⁢
                
                  v
                  →
                
              
              
                {
                n
              
            
            ,
            
              
                0
                
                  3
                  ⁢
                  n
                
              
              
                {
                
                  3
                  ⁢
                  n
                
              
            
            ,
            
              
                η
                →
              
              
                {
                n
              
            
            ,
            
              
                0
                n
              
              
                {
                n
              
            
          
          )
        
        
          B
          *
        
      
    
    ,
    
      

    
    ⁢
    
      
        where
        ⁢
        
          
        
        ⁢
        
          η
          →
        
      
      :=
      
        
          (
          
            
              η
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              η
              n
            
          
          )
        
        ∈
        
          F
          q
          n
        
      
    
  



As described above, in the cryptographic system 10 according to Embodiment 2, a sparse matrix is employed for generating the orthonormal bases B and B*. With this arrangement, it is possible while maintaining security to reduce the size of the public parameter and the size of the master secret key and reduce the time required for the process to generate a secret key to be given to a user and the time required for the encryption process.
It has been described in the above that the orthonormal bases B and B* are generated using the sparse matrix indicated in Formula 132. However, the sparse matrix to be employed for generating the orthonormal bases B and B* is not limited to this. For example, a plurality of μ in Formula 132 may be respectively different values. In Formula 132, all entries in the n-th column are random numbers other than the constant value 0. Alternatively, all entries in at least another column, instead of the n-th column, may be random numbers other than the constant value 0. Likewise, in Formula 132, all entries in the first row are random numbers other than the constant value 0. Alternatively, all entries in at least another row, instead of the first row, may be random numbers other than the constant value 0.
More generally, it is required for the sparse matrix that at least one value other than the constant value 0 is included in each row and each column. Further, when the sparse matrix is an n-row and n-column matrix, it is desirable that at least n pieces of different values are included as values other than the constant value 0. Further, it is desirable for the sparse matrix that all entries in at least one column are values other than the constant value 0. Further, it is desirable for the sparse matrix that all entries in at least one row are values other than the constant value 0. Further, it is desirable for the sparse matrix that diagonal entries and all entries in at least one column and at least one row are values other than the constant value 0. Further, it is desirable for the sparse matrix that the values of diagonal entries are the same except for a column where all entries are values other than the constant value 0.
Even when such a sparse matrix is used, the size of the public parameter and the size of the secret key are reduced compared to when a regular matrix is used. The processing times for generating a user key and for the encryption process are also reduced.
However, depending on the format of the linear transformation X, it may not be possible to reduce the number of pairing operations.
In the above description, the method for determining whether or not the ciphertext ctx satisfies the condition which is set in the token tkv has been described. With this method, it is possible to construct a secure search system in which the ciphertext et can be searched for while remaining encrypted.
However, as discussed in Non-Patent Literature 2, by embedding a message m in a ciphertext ctx, it is possible to construct a narrowly-defined cryptographic system in which the message m embedded in the ciphertext ctx is retrieved with the token tkv.
Embodiment 3
Embodiment 3 describes an IPE-CC scheme which allows addition of an attribute category without reissuing a public parameter.
In Embodiment 3, what is the same as in Embodiment 1 will not be described, and differences from Embodiment 1 will be mainly described.
An attribute category is, for example, a classification of an attribute of each user, such as belonging organization, belonging department, position, age, and gender, or a classification of an attribute of a search condition.
Generally, attribute categories used for access control and search conditions are determined in advance at the design stage of a system. However, there may be a case where the operational rules of the system are changed at a later stage, necessitating addition of an attribute category used for access control and search conditions.
For example, suppose that a cryptographic system is constructed on the assumption that the system is to be used only within Company A. In this case, it is assumed that the attribute categories to be used for access control are belonging department, position, and individual ID, and the like. However, suppose that the operational rules are changed at a later stage so that the cryptographic system is used not only in Company A but also in an associated company of Company A. In this case, belonging company needs to be newly set as an attribute category to be used for access control.
In the IPE-CC scheme according to Embodiment 1, the basis vectors of the basis B and the basis B* are required for each attribute category. To add an attribute category, it is necessary to generate a new basis B and a new basis B* with increased dimensions. Because the basis B is included in the public parameter, the public parameter needs to be reissued and newly distributed to users. For this reason, an attribute category cannot be easily added at a later stage, and an operational mode that has not been taken into consideration at the design stage of the system cannot be flexibly adopted.
The configurations of the key generation device 100, the encryption device 200, the conversion device 300, and the decryption device 400 according to Embodiment 3 are respectively the same as the configurations of these devices illustrated in FIG. 2 to FIG. 5.
The flows of the Setup algorithm, the Enc algorithm, the Conv algorithm, and the Query algorithm according to Embodiment 3 are respectively the same as the flows of these algorithms illustrated in FIG. 6 and FIG. 8 to FIG. 10.
FIG. 11 is a flowchart illustrating the process of the TokenGen algorithm according to Embodiment 3.
With reference to FIG. 6, the process of the Setup algorithm will be described.
(S101: Orthonormal Basis Generation Step)
Using the processing device, the master key generation part 110 computes Formula 150, and thus generates a parameter paramv, a basis B, and a basis B*.




  
    
      
        [
        
          Formula
          ⁢
          
            
          
          ⁢
          150
        
        ]
      
    
    
      
        
      
    
  
  
    
      
        input
        ⁢
        
          
        
        ⁢
        
          1
          λ
        
      
    
    
      
        (
        1
        )
      
    
  
  
    
      
        
          
            N
            0
          
          :=
          
            1
            +
            
              u
              0
            
            +
            
              w
              0
            
            +
            
              z
              0
            
          
        
        ,
        
          
            N
            1
          
          :=
          
            4
            +
            u
            +
            w
            +
            z
          
        
      
    
    
      
        (
        2
        )
      
    
  
  
    
      
        
          param
          G
        
        :=
        
          
            (
            
              q
              ,
              G
              ,
              
                G
                T
              
              ,
              g
              ,
              e
            
            )
          
          ⁢
          
            ⟵
            R
          
          ⁢
          
            
              G
              bpg
            
            ⁡
            
              (
              
                1
                λ
              
              )
            
          
        
      
    
    
      
        (
        3
        )
      
    
  
  
    
      
        ψ
        ⁢
        
          ⟵
          U
        
        ⁢
        
          F
          q
          ×
        
      
    
    
      
        (
        4
        )
      
    
  




For each t=0, 1, the following process (5) through (9) is executed.





  
    
      
        
          param
          
            V
            t
          
        
        :=
        
          
            (
            
              q
              ,
              
                V
                t
              
              ,
              
                G
                T
              
              ,
              
                A
                t
              
              ,
              e
            
            )
          
          :=
          
            
              G
              dpvs
            
            ⁡
            
              (
              
                
                  1
                  λ
                
                ,
                
                  N
                  t
                
                ,
                
                  param
                  G
                
              
              )
            
          
        
      
    
    
      
        (
        5
        )
      
    
  
  
    
      
        
          X
          t
        
        :=
        
          
            
              (
              
                χ
                
                  t
                  ,
                  i
                  ,
                  j
                
              
              )
            
            
              i
              ,
              
                j
                =
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                N
                t
              
            
          
          ⁢
          
            ⟵
            U
          
          ⁢
          
            GL
            ⁡
            
              (
              
                
                  N
                  t
                
                ,
                
                  F
                  q
                
              
              )
            
          
        
      
    
    
      
        (
        6
        )
      
    
  
  
    
      
        
          X
          t
          *
        
        :=
        
          
            
              (
              
                θ
                
                  t
                  ,
                  i
                  ,
                  j
                
              
              )
            
            
              i
              ,
              
                j
                =
                1
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                N
                t
              
            
          
          :=
          
            ψ
            ·
            
              
                (
                
                  X
                  t
                  T
                
                )
              
              
                -
                1
              
            
          
        
      
    
    
      
        (
        7
        )
      
    
  
  
    
      
        
          
            b
            
              t
              ,
              i
            
          
          :=
          
            
              
                (
                
                  
                    χ
                    →
                  
                  
                    t
                    ,
                    i
                  
                
                )
              
              
                A
                t
              
            
            =
            
              
                
                  ∑
                  
                    j
                    =
                    1
                  
                  
                    N
                    t
                  
                
                ⁢
                
                  
                    χ
                    
                      t
                      ,
                      i
                      ,
                      j
                    
                  
                  ⁢
                  
                    a
                    
                      t
                      ,
                      j
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  for
                  ⁢
                  
                    
                  
                  ⁢
                  i
                
              
              =
              1
            
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          N
          t
        
        ,
        
          

        
        ⁢
        
          
            B
            t
          
          :=
          
            (
            
              
                b
                
                  t
                  ,
                  1
                
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                b
                
                  t
                  ,
                  
                    N
                    t
                  
                
              
            
            )
          
        
      
    
    
      
        (
        8
        )
      
    
  
  
    
      
        
          
            b
            
              t
              ,
              i
            
            *
          
          :=
          
            
              
                (
                
                  
                    θ
                    →
                  
                  
                    t
                    ,
                    i
                  
                
                )
              
              
                A
                t
              
            
            =
            
              
                
                  ∑
                  
                    j
                    =
                    1
                  
                  
                    N
                    t
                  
                
                ⁢
                
                  
                    θ
                    
                      t
                      ,
                      i
                      ,
                      j
                    
                  
                  ⁢
                  
                    a
                    
                      t
                      ,
                      j
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  for
                  ⁢
                  
                    
                  
                  ⁢
                  t
                
              
              =
              1
            
          
        
        ,
        ...
        ⁢
        
          
        
        ,
        
          N
          t
        
        ,
        
          

        
        ⁢
        
          
            B
            t
            *
          
          :=
          
            (
            
              
                b
                
                  t
                  ,
                  1
                
                *
              
              ,
              ...
              ⁢
              
                
              
              ,
              
                b
                
                  t
                  ,
                  
                    N
                    t
                  
                
                *
              
            
            )
          
        
      
    
    
      
        (
        9
        )
      
    
  
  
    
      
        
          
            g
            T
          
          :=
          
            
              e
              ⁡
              
                (
                
                  g
                  ,
                  g
                
                )
              
            
            ψ
          
        
        ,
        
          

        
        ⁢
        
          param
          :=
          
            (
            
              
                
                  {
                  
                    param
                    
                      V
                      t
                    
                  
                  }
                
                
                  
                    t
                    =
                    0
                  
                  ,
                  1
                
              
              ,
              
                g
                T
              
            
            )
          
        
      
    
    
      
        (
        10
        )
      
    
  




That is, the master key generation part 110 executes the following process (1) through (10).
(1) is the same as that in Embodiment 1, and thus will not be described.
(2) Using the processing device, the master key generation part 110 sets 1+u0+w0+z0 in N0, and sets 4+u+w+z in N1. Note that u0, w0, z0, u, w, and z are integers of 0 or more.
(3) Using the processing device, the master key generation part 110 executes the algorithm Gbpg taking as input the security parameter λ inputted in (1), and thus generates a parameter paramG of bilinear pairing groups.
(4) Using the processing device, the master key generation part 110 generates a random number ψ.
Then, the master key generation part 110 executes the following process (5) through (9) for each t=0, 1.
(5) Using the processing device, the master key generation part 110 executes the algorithm Gdpvs taking as input the security parameter λ inputted in (1), Nt set in (2), and the values of paramG:=(q, G, GT, g, e) generated in (3), and thus generates values of a parameter paramVt:=(q, Vt, GT, At, e) of dual pairing vector spaces.
(6) Using the processing device, the master key generation part 110 takes as input Nt set in (2) and Fq, and randomly generates a linear transformation Xt:=(χt,i,j)i,j. Note that (χt,i,j)i,j denotes a matrix concerning the suffixes i and j of the matrix χt,i,j, where i, j=1, . . . , Nt.
(7) Using the processing device, the master key generation part 110 generates a linear transformation X*t:=(νt,i,j)i,j:=ψ·(XtT)−1 based on the random number and the linear transformation Xt. Like (χt,i,j)i,j, (νt,i,j)i,j denotes a matrix concerning the suffixes i and j of the matrix νt,i,j, where i, j=1, . . . , Nt.
(8) Using the processing device, the master key generation part 110 generates a basis Bt from the canonical basis At generated in (5), based on the linear transformation Xt generated in (6). Note that {right arrow over (x)}t,i denotes the i-th row of the linear transformation Xt.
(9) Using the processing device and based on (νt,i,j)i,j generated in (7), the master key generation part 110 generates a basis B*t from the canonical basis At generated in (5). Note that {right arrow over (v)}t,i denotes the i-th row of the linear transformation X*t.
(10) Using the processing device, the master key generation part 110 sets e(g, g)ψ in gT. The master key generation part 110 also sets {paramVt}t=0,1 generated in (5) and gT in param.
In the following description, for simplicity, the basis B1 and the basis B*1 will be described as the basis B and the basis B*.
(S102: Conversion Key Generation Step)
Using the processing device, the master key generation part 110 generates conversion information W0 and W, as indicated in Formula 151. The master key generation part 110 designates the conversion information W0 and W as a conversion key ck.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      151
    
    ]
  




  
    
      
        W
        0
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        GL
        ⁡
        
          (
          
            
              N
              0
            
            ,
            
              F
              q
            
          
          )
        
      
    
    ,
    
      

    
    ⁢
    
      W
      ⁢
      
        ⟵
        U
      
      ⁢
      
        GL
        ⁡
        
          (
          
            
              N
              1
            
            ,
            
              F
              q
            
          
          )
        
      
    
  



(S103: Public Key Generation Step)
Using the processing device, the master key generation part 110 converts the basis B0 and the basis B which have been generated in S101 with the conversion information W0 and W, as indicated in Formula 152, and thus generates a basis D0 and a basis D. Then, using the processing device, the master key generation part 110 generates a subbasis D^0 of the basis D0 and a subbasis D^ of the basis D, as indicated in Formula 152.

d0,i:=b0,iW0 for i=1, . . . ,1+u0+w0+z0,

D0:=(d0,1, . . . ,d0,1+u0+w0+z0),

{circumflex over (D)}0:=(d0,1,d0,1+u0+w0+1 . . . ,d1+u0+w0+z0),

di:=biW for i=1, . . . ,4+u+w+z, 

D:=(d1, . . . ,d4+u+w+z),

{circumflex over (D)}:=(d1, . . . ,d4+u+w+1 . . . ,d4+u+w+z)  [Formula 152]

The master key generation part 110 designates a combination of the subbasis D^0, the subbasis D^, the security parameter λ inputted in S101, and paramV generated in S101 as a public key pk.
(S104: Secret Key Generation Step)
Using the processing device, the master key generation part 110 generates a subbasis B^0 of the basis B*0 and a subbasis B*^ of the basis B*, as indicated in Formula 153, the bases B*0 and B* having been generated in S101.

*0:=(b*0,1,b*0,1+u0+1, . . . ,b*0,1+u0+w0),

*:=(b*1, . . . ,b*4,b*4+u+1, . . . ,b*4+u+w)  [Formula 153]

The master key generation part 110 designates the subbasis B*^ 0 and the subbasis B*^ that have been generated as a secret key sk.
(S105: Key Storage Step)
The master key storage part 120 stores the conversion key ck generated in S102, the public key pk generated in S103, and the secret key sk generated in S104 in the storage device.
In brief, in S101 through S104, the key generation device 100 generates the conversion key ck, the public key pk, and the secret key sk by executing the Setup algorithm indicated in Formula 154. Note that a GIPEob algorithm is as indicated in Formula 155. In S105, the key generation device 100 stores the conversion key ck, the public key pk, and the secret key sk that have been generated in the storage device.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      154
    
    ]
  




  
    
      Setup
      ⁡
      
        (
        
          1
          λ
        
        )
      
    
    ⁢
    
      :
    
  




  
    
      (
      
        param
        ,
        
          (
          
            
              B
              0
            
            ,
            
              B
              0
              *
            
          
          )
        
        ,
        
          (
          
            B
            ,
            
              B
              *
            
          
          )
        
      
      )
    
    ⁢
    
      ⟵
      R
    
    ⁢
    
      
                ob
        IPE
      
      ⁡
      
        (
        
          1
          λ
        
        )
      
    
  




  
    
      
        d
        
          0
          ,
          i
        
      
      :=
      
        
          
            b
            
              0
              ,
              i
            
          
          ⁢
          
            W
            0
          
          ⁢
          
            
          
          ⁢
          for
          ⁢
          
            
          
          ⁢
          i
        
        =
        1
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      1
      +
      
        u
        0
      
      +
      
        w
        0
      
      +
      
        z
        0
      
    
    ,
    
      

    
    ⁢
    
      
        D
        0
      
      :=
      
        (
        
          
            d
            
              0
              ,
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            
              0
              ,
              
                1
                +
                
                  u
                  0
                
                +
                
                  w
                  0
                
                +
                
                  z
                  0
                
              
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        
          D
          ^
        
        0
      
      :=
      
        (
        
          
            d
            
              0
              ,
              1
            
          
          ,
          
            
              d
              
                0
                ,
                
                  1
                  +
                  
                    u
                    0
                  
                  +
                  
                    w
                    0
                  
                  +
                  1
                
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            d
            
              1
              +
              
                u
                0
              
              +
              
                w
                0
              
              +
              
                z
                0
              
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        d
        i
      
      :=
      
        
          
            b
            i
          
          ⁢
          W
          ⁢
          
            
          
          ⁢
          for
          ⁢
          
            
          
          ⁢
          i
        
        =
        1
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      4
      +
      u
      +
      w
      +
      z
    
    ,
    
      

    
    ⁢
    
      D
      :=
      
        (
        
          
            d
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            
              4
              +
              u
              +
              w
              +
              z
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        D
        ^
      
      :=
      
        (
        
          
            d
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            4
          
          ,
          
            
              d
              
                4
                +
                u
                +
                w
                +
                1
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            d
            
              4
              +
              u
              +
              w
              +
              z
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        
          B
          ^
        
        0
        *
      
      :=
      
        (
        
          
            b
            
              0
              ,
              1
            
            *
          
          ,
          
            
              b
              
                0
                ,
                
                  1
                  +
                  
                    u
                    0
                  
                  +
                  1
                
                ,
                ...
                ⁢
                
                  
                
                ,
              
              *
            
            ⁢
            
              b
              
                0
                ,
                
                  1
                  +
                  
                    u
                    0
                  
                  +
                  
                    w
                    0
                  
                
              
              *
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        
          B
          ^
        
        *
      
      :=
      
        (
        
          
            b
            1
            *
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            4
            *
          
          ,
          
            b
            
              4
              +
              u
              +
              1
            
            *
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            
              4
              +
              u
              +
              w
            
            *
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        p
        ⁢
        
          
        
        ⁢
        k
      
      :=
      
        (
        
          
            1
            λ
          
          ,
          param
          ,
          
            
              D
              ^
            
            0
          
          ,
          
            D
            ^
          
        
        )
      
    
    ,
    
      sk
      :=
      
        
          (
          
            
              
                B
                ^
              
              0
              *
            
            ,
            
              
                B
                ^
              
              *
            
          
          )
        
        .
        
          

        
        ⁢
        
          [
          
            Formula
            ⁢
            
              
            
            ⁢
            155
          
          ]
        
      
    
  




  
        ⁢
    
      :
    
  




  
    
      
        N
        0
      
      :=
      
        1
        +
        
          u
          0
        
        +
        
          w
          0
        
        +
        
          z
          0
        
      
    
    ,
    
      
        N
        1
      
      :=
      
        4
        +
        u
        +
        w
        +
        z
      
    
    ,
    
      

    
    ⁢
    
      
        param
        G
      
      :=
      
        
          
            (
            
              q
              ,
              G
              ,
              
                G
                T
              
              ,
              g
              ,
              e
            
            )
          
          ⁢
          
            ⟵
            R
          
          ⁢
          
                        bpg
          
        
        ⁢
        
          (
          
            1
            λ
          
          )
        
      
    
    ,
    
      ψ
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
        x
      
    
    ,
    
      

    
    ⁢
    
      
        for
        ⁢
        
          
        
        ⁢
        t
      
      =
      0
    
    ,
    1
    ,
    
      

    
    ⁢
    
      
        param
        
          V
          t
        
      
      :=
      
        
          (
          
            q
            ,
            
              V
              t
            
            ,
            
              G
              T
            
            ,
            
              A
              t
            
            ,
            e
          
          )
        
        :=
        
          
                        dpvs
          
          ⁢
          
            (
            
              
                1
                λ
              
              ,
              
                N
                t
              
              ,
              
                param
                G
              
            
            )
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        X
        t
      
      :=
      
        
          
            (
            
              χ
              
                t
                ,
                i
                ,
                j
              
            
            )
          
          
            i
            ,
            
              j
              =
              1
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              N
              t
            
          
        
        ⁢
        
          ⟵
          U
        
        ⁢
        
          GL
          ⁡
          
            (
            
              
                N
                t
              
              ,
              
                F
                q
              
            
            )
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        
          
            X
            t
            *
          
          ⁡
          
            (
            
              θ
              
                t
                ,
                i
                ,
                j
              
            
            )
          
        
        
          i
          ,
          
            j
            =
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            N
            t
          
        
      
      :=
      
        ψ
        ·
        
          
            (
            
              X
              t
              T
            
            )
          
          
            -
            1
          
        
      
    
    ,
    hereafter
    ,
    
      
        χ
        →
      
      
        t
        ,
        i
      
    
  




  
    and
    ⁢
    
      
    
    ⁢
    
      
        θ
        →
      
      
        t
        ,
        i
      
    
    ⁢
    
      
    
    ⁢
    denote
    ⁢
    
      
    
    ⁢
    the
    ⁢
    
      
    
    ⁢
    i
    ⁢
    
      -
    
    ⁢
    th
    ⁢
    
      
    
    ⁢
    rows
    ⁢
    
      
    
    ⁢
    of
    ⁢
    
      
    
    ⁢
    
      X
      t
    
    ⁢
    
      
    
    ⁢
    and
    ⁢
    
      
    
    ⁢
    
      X
      t
      *
    
  




  
    
      
        for
        ⁢
        
          
        
        ⁢
        i
      
      =
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      N
      t
    
    ,
    respectively
    ,
    
      

    
    ⁢
    
      
        b
        
          t
          ,
          i
        
      
      :=
      
        
          
            (
            
              
                χ
                →
              
              
                t
                ,
                i
              
            
            )
          
          
            A
            t
          
        
        =
        
          
            ∑
            
              j
              =
              1
            
            
              N
              t
            
          
          ⁢
          
            
              χ
              
                t
                ,
                i
                ,
                j
              
            
            ⁢
            
              a
              
                t
                ,
                j
              
            
          
        
      
    
  




  
    
      
        for
        ⁢
        
          
        
        ⁢
        i
      
      =
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      N
      t
    
    ,
    
      
        B
        t
      
      :=
      
        (
        
          
            b
            
              t
              ,
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            
              t
              ,
              
                N
                t
              
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        b
        
          t
          ,
          i
        
        *
      
      :=
      
        
          
            (
            
              
                θ
                →
              
              
                t
                ,
                i
              
            
            )
          
          
            A
            t
          
        
        =
        
          
            ∑
            
              j
              =
              1
            
            
              N
              t
            
          
          ⁢
          
            
              θ
              
                t
                ,
                i
                ,
                j
              
            
            ⁢
            
              a
              
                t
                ,
                j
              
            
          
        
      
    
  




  
    
      
        for
        ⁢
        
          
        
        ⁢
        i
      
      =
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      N
      t
    
    ,
    
      
        B
        t
        *
      
      :=
      
        (
        
          
            b
            
              t
              ,
              1
            
            *
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            
              t
              ,
              
                N
                t
              
            
            *
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        g
        T
      
      :=
      
        
          e
          ⁡
          
            (
            
              g
              ,
              g
            
            )
          
        
        ψ
      
    
    ,
    
      param
      :=
      
        (
        
          
            
              {
              
                param
                
                  V
                  t
                
              
              }
            
            
              
                t
                =
                0
              
              ,
              1
            
          
          ,
          
            g
            T
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      return
      ⁢
      
        
      
      ⁢
      
        
          (
          
            param
            ,
            
              
                {
                
                  
                    B
                    t
                  
                  ,
                  
                    B
                    t
                    *
                  
                
                }
              
              
                
                  t
                  =
                  0
                
                ,
                1
              
            
          
          )
        
        .
      
    
  



With reference to FIG. 11, the process of the TokenGen algorithm will be described.
(S601: Information Input Step)
Using the input device, the information input part 130 takes as input a predicate vector {right arrow over (v)}:={(t, vt)|tεIv→}. That is, the predicate vector {right arrow over (v)} is a vector having as elements an index t and predicate information vt regarding the index t included in a set Iv→. As the predicate information vt, attribute information of a user of a token tkv, a search keyword, and so on are set, for example.
(S602: Secret Information Generation Step)
Using the processing device, the token generation part 140 generates secret information st and s0, as indicated in Formula 156.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      156
    
    ]
  




  
    
      
        
          
            s
            t
          
          ⁢
          
            ⟵
            U
          
          ⁢
          
            F
            q
          
        
        ⁢
        
          
        
        ⁢
        for
        ⁢
        
          
        
        ⁢
        
          (
          
            t
            ,
            
              v
              t
            
          
          )
        
      
      ∈
      
        v
        →
      
    
    ,
    
      

    
    ⁢
    
      
        s
        0
      
      :=
      
        
          ∑
          
            
              (
              
                t
                ,
                
                  v
                  t
                
              
              )
            
            ∈
            
              v
              →
            
          
        
        ⁢
        
          s
          t
        
      
    
  



(S603: Random Number Generation Step)
Using the processing device, the token generation part 140 generates random numbers, as indicated in Formula 157.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      157
    
    ]
  




  
    
      
        
          η
          →
        
        0
      
      :=
      
        
          (
          
            
              η
              
                0
                ,
                1
              
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              η
              
                0
                ,
                
                  w
                  0
                
              
            
          
          )
        
        ⁢
        
          ⟵
          U
        
        ⁢
        
          F
          q
          
            w
            0
          
        
      
    
    ,
    
      

    
    ⁢
    
      δ
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      

    
    ⁢
    
      
        
          
            μ
            t
          
          ⁢
          
            ⟵
            U
          
          ⁢
          
            F
            q
          
        
        ⁢
        
          
        
        ⁢
        for
        ⁢
        
          
        
        ⁢
        
          (
          
            t
            ,
            
              v
              t
            
          
          )
        
      
      ∈
      
        v
        →
      
    
    ,
    
      

    
    ⁢
    
      
        
          η
          →
        
        t
      
      :=
      
        
          
            
              (
              
                
                  η
                  
                    t
                    ,
                    1
                  
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  η
                  
                    t
                    ,
                    w
                  
                
              
              )
            
            ⁢
            
              ⟵
              U
            
            ⁢
            
              F
              q
              w
            
          
          ⁢
          
            
          
          ⁢
          for
          ⁢
          
            
          
          ⁢
          
            (
            
              t
              ,
              
                v
                t
              
            
            )
          
        
        ∈
        
          v
          →
        
      
    
  



(S604: Token Element Generation Step)
Using the processing device, the token generation part 140 generates an element k*0 of the token tkv, as indicated in Formula 158.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      158
    
    ]
  




  
    
      k
      0
      *
    
    :=
    
      
        (
        
          
            -
            
              s
              0
            
          
          ,
          
            
              
                0
                
                  u
                  0
                
              
              {
            
            
              u
              0
            
          
          ,
          
            
              
                
                  η
                  →
                
                0
              
              {
            
            
              W
              0
            
          
          ,
          
            
              
                0
                
                  z
                  0
                
              
              {
            
            
              Z
              0
            
          
          ,
        
        )
      
      
        B
        0
        *
      
    
  



Using the processing device, the token generation part 140 also generates an element k*t of the token tkv for the index t included in the set Iv→, as indicated in Formula 159.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      159
    
    ]
  




  
    
      k
      t
      *
    
    :=
    
      
        (
        
          
            
              
                
                  
                    μ
                    t
                  
                  ⁡
                  
                    (
                    
                      
                        
                          t
                        
                        
                          
                            
                              -
                              1
                            
                            ,
                          
                        
                      
                    
                    )
                  
                
                ,
                
                  δ
                  ⁢
                  
                    
                  
                  ⁢
                  
                    v
                    t
                  
                
                ,
                
                  s
                  t
                
              
              
                {
                4
              
            
            ⁢
            
              
            
            ⁢
            
              
                
                  0
                  u
                
                {
              
              u
            
          
          ,
          
            
              
                
                  η
                  →
                
                t
              
              {
            
            w
          
          ,
          
            
              
                0
                z
              
              {
            
            z
          
        
        )
      
      
        B
        *
      
    
  



(S605: Token Distribution Step)
Using the communication device and via the network, for example, the token transmission part 150 distributes the token tkv having the elements k*0 and k*t generated in S604 to the decryption device 400 in secrecy. As a matter of course, the token tkv may be distributed to the decryption device 400 by another method.
In brief, in S601 through S604, the key generation device 100 generates the token tkv by executing the TokenGen algorithm indicated in Formula 160. In S605, the key generation device 100 distributes the generated token tkv to the decryption device 400.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      160
    
    ]
  




  
    
      TokenGen
      ⁡
      
        (
        
          
            p
            ⁢
            
              
            
            ⁢
            k
          
          ,
          sk
          ,
          
            
              v
              →
            
            :=
            
              {
              
                
                  (
                  
                    t
                    ,
                    
                      v
                      t
                    
                  
                  )
                
                |
                
                  t
                  ∈
                  
                    I
                    
                      v
                      →
                    
                  
                
              
              }
            
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    δ
    ,
    
      
        
          
            s
            t
          
          ⁢
          
            ⟵
            U
          
          ⁢
          
            F
            q
          
        
        ⁢
        
          
        
        ⁢
        for
        ⁢
        
          
        
        ⁢
        
          (
          
            t
            ,
            
              v
              t
            
          
          )
        
      
      ∈
      
        v
        →
      
    
  




  
    
      
        
          η
          →
        
        0
      
      :=
      
        
          (
          
            
              η
              
                0
                ,
                1
              
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              η
              
                0
                ,
                
                  w
                  0
                
              
            
          
          )
        
        ⁢
        
          ⟵
          U
        
        ⁢
        
          F
          q
          
            w
            0
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        s
        0
      
      :=
      
        
          ∑
          
            
              (
              
                t
                ,
                
                  v
                  t
                
              
              )
            
            ∈
            
              v
              →
            
          
        
        ⁢
        
          s
          t
        
      
    
    ,
    
      

    
    ⁢
    
      
        k
        0
        *
      
      :=
      
        
          (
          
            
              -
              
                s
                0
              
            
            ,
            
              
                
                  0
                  
                    u
                    0
                  
                
                {
              
              
                u
                0
              
            
            ,
            
              
                
                  
                    η
                    →
                  
                  0
                
                {
              
              
                W
                0
              
            
            ,
            
              
                
                  0
                  
                    z
                    0
                  
                
                {
              
              
                Z
                0
              
            
            ,
          
          )
        
        
          B
          0
          *
        
      
    
    ,
    
      

    
    ⁢
    
      
        for
        ⁢
        
          
        
        ⁢
        
          (
          
            t
            ,
            
              v
              t
            
          
          )
        
      
      ∈
      
        v
        →
      
    
    ,
    
      

    
    ⁢
    
      
        μ
        t
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      

    
    ⁢
    
      
        
          η
          →
        
        t
      
      :=
      
        
          (
          
            
              η
              
                t
                ,
                1
              
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              η
              
                t
                ,
                w
              
            
          
          )
        
        ⁢
        
          ⟵
          U
        
        ⁢
        
          F
          q
          w
        
      
    
    ,
    
      

    
    ⁢
    
      
        k
        t
        *
      
      :=
      
        
          (
          
            
              
                
                  
                    
                      μ
                      t
                    
                    ⁡
                    
                      (
                      
                        
                          
                            
                              t
                              ,
                            
                          
                          
                            
                              
                                -
                                1
                              
                              ,
                            
                          
                        
                      
                      )
                    
                  
                  ,
                  
                    δ
                    ⁢
                    
                      
                    
                    ⁢
                    
                      v
                      t
                    
                  
                  ,
                  
                    s
                    t
                  
                
                
                  {
                  4
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    0
                    u
                  
                  {
                
                u
              
            
            ,
            
              
                
                  
                    η
                    →
                  
                  t
                
                {
              
              w
            
            ,
            
              
                
                  0
                  z
                
                {
              
              z
            
          
          )
        
        
          B
          *
        
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        
          sk
          v
        
      
      :=
      
        
          (
          
            
              k
              0
              *
            
            ,
            
              
                {
                
                  k
                  t
                  *
                
                }
              
              
                
                  (
                  
                    t
                    ,
                    
                      v
                      t
                    
                  
                  )
                
                ∈
                
                  v
                  →
                
              
            
          
          )
        
        .
      
    
  



With reference to FIG. 8, the process of the Enc algorithm will be described.
S301 is the same as that in Embodiment 1, and thus will not be described.
(S302: Information Input Step)
Using the input device, the information input part 220 takes as input an attribute vector {right arrow over (x)}:={(t, xt)|tεIx→}. That is, the attribute vector {right arrow over (x)} is a vector having as elements an index t and attribute information xt regarding the index t included in a set Ix→. In the attribute vector {right arrow over (x)}, attribute information of a user who is allowed to search and a search tag are set, for example.
(S303: Random Number Generation Step)
Using the processing device, the ciphertext generation part 230 generates random numbers, as indicated in Formula 161.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      161
    
    ]
  




  
    ω
    ,
    
      
        ω
        ~
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      

    
    ⁢
    
      
        
          φ
          →
        
        0
      
      :=
      
        
          (
          
            
              φ
              
                0
                ,
                1
              
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              φ
              
                0
                ,
                
                  z
                  0
                
              
            
          
          )
        
        ⁢
        
          ⟵
          U
        
        ⁢
        
          F
          q
          
            z
            0
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        
          
            σ
            t
          
          ⁢
          
            ⟵
            U
          
          ⁢
          
            F
            q
          
        
        ⁢
        
          
        
        ⁢
        for
        ⁢
        
          
        
        ⁢
        
          (
          
            t
            ,
            
              x
              t
            
          
          )
        
      
      ∈
      
        x
        →
      
    
    ,
    
      

    
    ⁢
    
      
        
          φ
          →
        
        t
      
      =
      
        
          
            
              (
              
                
                  φ
                  
                    t
                    ,
                    1
                  
                
                ,
                ...
                ⁢
                
                  
                
                ,
                
                  φ
                  
                    t
                    ,
                    z
                  
                
              
              )
            
            ⁢
            
              ⟵
              U
            
            ⁢
            
              F
              q
              z
            
          
          ⁢
          
            
          
          ⁢
          for
          ⁢
          
            
          
          ⁢
          
            (
            
              t
              ,
              
                x
                t
              
            
            )
          
        
        ∈
        
          x
          →
        
      
    
  



(S304: Cipher Element Generation Step)
Using the processing device, the ciphertext generation part 230 generates an element f0 of a ciphertext ctx, as indicated in Formula 162.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      162
    
    ]
  




  
    
      f
      0
    
    :=
    
      
        (
        
          
            ω
            ~
          
          ,
          
            
              
                0
                
                  u
                  0
                
              
              {
            
            
              u
              0
            
          
          ,
          
            
              
                0
                
                  w
                  0
                
              
              {
            
            
              w
              0
            
          
          ,
          
            
              
                
                  φ
                  →
                
                0
              
              {
            
            
              z
              0
            
          
          ,
        
        )
      
      
        B
        0
      
    
  



Using the processing device, the ciphertext generation part 230 also generates an element ft of the ciphertext ctx for the index t included in the set Ix→, as indicated in Formula 163.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      163
    
    ]
  




  
    
      
        f
        t
      
      =
      
        
          (
          
            
              
                
                  
                    
                      σ
                      t
                    
                    ⁡
                    
                      (
                      
                        1
                        ,
                        t
                      
                      )
                    
                  
                  ,
                  
                    ω
                    ⁢
                    
                      
                    
                    ⁢
                    
                      x
                      t
                    
                  
                  ,
                  
                    ω
                    ~
                  
                
                
                  {
                  4
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    0
                    u
                  
                  {
                
                u
              
            
            ,
            
              
                
                  0
                  w
                
                {
              
              w
            
            ,
            
              
                
                  
                    φ
                    →
                  
                  t
                
                {
              
              z
            
          
          )
        
        B
      
    
    ,
  



(S305: Data Transmission Step)
Using the communication device and via the network, for example, the data transmission part 240 transmits the ciphertext ctx having the elements f0 and ft generated in S304 to the conversion device 300. As a matter of course, the ciphertext ctx may be transmitted to the conversion device 300 by another method.
In brief, in S301 through S304, the encryption device 200 generates the ciphertext ctx by executing the Enc algorithm indicated in Formula 164. In S305, the encryption device 200 transmits the generated ciphertext ctx to the conversion device 300.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      164
    
    ]
  




  
    
      Enc
      ⁡
      
        (
        
          
            p
            ⁢
            
              
            
            ⁢
            k
          
          ,
          
            
              x
              →
            
            :=
            
              {
              
                
                  (
                  
                    t
                    ,
                    
                      x
                      t
                    
                  
                  )
                
                |
                
                  t
                  ∈
                  
                    I
                    
                      x
                      →
                    
                  
                
              
              }
            
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    ω
    ,
    
      ω
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      
        
          φ
          →
        
        0
      
      :=
      
        
          (
          
            
              φ
              
                0
                ,
                1
              
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              φ
              
                0
                ,
                
                  z
                  0
                
              
            
          
          )
        
        ⁢
        
          ⟵
          U
        
        ⁢
        
          F
          q
          
            z
            0
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        f
        0
      
      :=
      
        
          (
          
            
              ω
              ~
            
            ⁢
            
              
            
            ,
            
              
                
                  0
                  
                    u
                    0
                  
                
                {
              
              
                u
                0
              
            
            ,
            
              
                
                  0
                  
                    w
                    0
                  
                
                {
              
              
                w
                0
              
            
            ,
            
              
                
                  
                    φ
                    →
                  
                  0
                
                {
              
              
                z
                0
              
            
          
          )
        
        
          B
          0
        
      
    
    ,
    
      

    
    ⁢
    
      
        for
        ⁢
        
          
        
        ⁢
        
          (
          
            t
            ,
            
              x
              t
            
          
          )
        
      
      ∈
      
        x
        →
      
    
    ,
    
      

    
    ⁢
    
      
        σ
        t
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      
        
          φ
          →
        
        t
      
      :=
      
        
          (
          
            
              φ
              
                t
                ,
                1
              
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              φ
              
                t
                ,
                z
              
            
          
          )
        
        ⁢
        
          ⟵
          U
        
        ⁢
        
          F
          q
          z
        
      
    
    ,
    
      

    
    ⁢
    
      
        f
        t
      
      =
      
        
          (
          
            
              
                
                  
                    
                      σ
                      t
                    
                    ⁡
                    
                      (
                      
                        1
                        ,
                        t
                      
                      )
                    
                  
                  ,
                  
                    ω
                    ⁢
                    
                      
                    
                    ⁢
                    
                      x
                      t
                    
                  
                  ,
                  
                    ω
                    ~
                  
                
                
                  {
                  4
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    0
                    u
                  
                  {
                
                u
              
            
            ,
            
              
                
                  0
                  w
                
                {
              
              w
            
            ,
            
              
                
                  
                    φ
                    →
                  
                  t
                
                {
              
              z
            
          
          )
        
        B
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        
          ct
          x
        
      
      :=
      
        
          (
          
            
              f
              0
            
            ⁢
            
              
                {
                
                  f
                  t
                
                }
              
              
                
                  (
                  
                    t
                    ,
                    
                      x
                      t
                    
                  
                  )
                
                ∈
                
                  x
                  →
                
              
            
          
          )
        
        .
      
    
  



With reference to FIG. 9, the process of the Conv algorithm will be described.
(S401: Conversion Key Acquisition Step)
Using the communication device and via the network, for example, the conversion key acquisition part 310 obtains the conversion key ck:=(W0, W) transmitted by the key generation device 100. The conversion key acquisition part 310 also obtains the public key pk generated by the key generation device 100.
(S402: Ciphertext Acquisition Step)
Using the communication device and via the network, for example, the ciphertext acquisition part 320 receives the ciphertext ctx:=(f0, f) transmitted by the encryption device 200.
(S403: Random Number Generation Step)
Using the processing device, the ciphertext conversion part 330 generates random numbers, as indicated in Formula 165.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      165
    
    ]
  




  
    
      
        ρ
        0
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      

    
    ⁢
    
      
        
          y
          0
        
        ⁢
        
          ⟵
          U
        
        ⁢
        span
      
      ⁢
      
        〈
        
          
            d
            
              1
              +
              
                u
                0
              
              +
              
                w
                0
              
              +
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            
              1
              +
              
                u
                0
              
              +
              
                w
                0
              
              +
              
                z
                0
              
            
          
        
        〉
      
    
    ,
    
      

    
    ⁢
    
      ρ
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      

    
    ⁢
    
      
        y
        ⁢
        
          ⟵
          U
        
        ⁢
        span
      
      ⁢
      
        〈
        
          
            d
            
              4
              +
              u
              +
              w
              +
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            
              4
              +
              u
              +
              w
              +
              z
            
          
        
        〉
      
    
  



(S404: Ciphertext Conversion Step)
Using the processing device, the ciphertext conversion part 330 coverts the ciphertext ctx, as indicated in Formula 166, and thus generates an element c0 and an element ct.

c0:=(ρ0f0+y0)W0−1,

ct:=(ρf+y)W−1  [Formula 166]

(S405: Data Transmission Step)
Using the communication device and via the network, for example, the data transmission part 340 transmits the ciphertext CTx including the element c0 and the element ct generated in S404 to the decryption device 400. As a matter of course, the ciphertext CTx may be transmitted to the decryption device 400 by another method.
In brief, in S401 through S404, the conversion device 300 generates the ciphertext CTx by executing the Conv algorithm indicated in Formula 167. In S405, the conversion device 300 transmits the generated ciphertext CTx to the decryption device 400.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      167
    
    ]
  




  
    
      Conv
      ⁡
      
        (
        
          
            p
            ⁢
            
              
            
            ⁢
            k
          
          ,
          
            ck
            :=
            W
          
          ,
          
            
              ct
              x
            
            :=
            f
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    
      
        ρ
        0
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      
        
          y
          0
        
        ⁢
        
          ⟵
          U
        
        ⁢
        span
      
      ⁢
      
        〈
        
          
            d
            
              1
              +
              
                u
                0
              
              +
              
                w
                0
              
              +
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            
              1
              +
              
                u
                0
              
              +
              
                w
                0
              
              +
              
                z
                0
              
            
          
        
        〉
      
    
    ,
    
      

    
    ⁢
    
      ρ
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      
        y
        ⁢
        
          ⟵
          U
        
        ⁢
        span
      
      ⁢
      
        〈
        
          
            d
            
              n
              +
              u
              +
              w
              +
              1
            
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            
              n
              +
              u
              +
              w
              +
              z
            
          
        
        〉
      
    
    ,
    
      

    
    ⁢
    
      
        c
        0
      
      :=
      
        
          (
          
            
              
                ρ
                0
              
              ⁢
              
                f
                0
              
            
            +
            
              y
              0
            
          
          )
        
        ⁢
        
          W
          0
          
            -
            1
          
        
      
    
    ,
    
      
        c
        t
      
      :=
      
        
          (
          
            
              ρ
              ⁢
              
                
              
              ⁢
              f
            
            +
            y
          
          )
        
        ⁢
        
          W
          
            -
            1
          
        
      
    
  




  
    
      return
      ⁢
      
        
      
      ⁢
      
        CT
        x
      
    
    :=
    
      
        (
        
          
            c
            0
          
          ,
          c
        
        )
      
      .
    
  



With reference to FIG. 10, the process of the Query algorithm will be described.
(S501: Token Acquisition Step)
Using the communication device and via the network, for example, the token acquisition part 410 obtains the token tkv:=(k*0, k*t) transmitted by the key generation device 100. The token acquisition part 410 also obtains the public key pk generated by the key generation device 100.
(S502: Ciphertext Acquisition Step)
Using the communication device and via the network, for example, the ciphertext acquisition part 420 receives the ciphertext CTx:=(c0, ct) transmitted by the conversion device 300.
(S503: Decryption Step)
Using the processing device, the decryption part 430 outputs 1 indicating that decryption has been successful if the set Iv→ is a subset of the set Ix→ and a result of computing a pairing operation e(c0, k*0)·ΠtεIv→e(ct, k*t) is 1, and outputs 0 indicating that decryption has failed if the result is not 1.
In brief, in S501 through S503, the decryption device 400 executes the Query algorithm indicated in Formula 168, and thus determines whether or not decryption has been successful.

Query(pk,tkν:=(k*0,k*t),CTx:=(c0,ct)):

if I{right arrow over (ν)}⊂I{right arrow over (x)} and e(c0,k*0)·ΠtεI{right arrow over (ν—)}e(ct,k*t)=1,output 1,

otherwise, output 0.  [Formula 168]

As described above, in the inner-product predicate encryption scheme according to Embodiment 3, if the set Iv→ is a subset of Ix→ and the sum of vtxt for the index t included in the set Iv→ is 0, the ciphertext ctx can be decrypted with the token tkv even when the dimensions of the attribute vector {right arrow over (x)} and the predicate vector {right arrow over (v)} are not the same.
In the inner-product predicate encryption scheme according to Embodiment 3, μtt and −μt are respectively set as the coefficient of the basis vectors b*1 and b*2 (basis vector b*index) for the element k*t of the decryption key skv. In the cryptographic system 10, σt and σtt are respectively set as the coefficient of the basis vectors b1 and b2 (basis vector bindex) for the element ct of the ciphertext ctx.
Because of these arrangements, when a pairing operation is performed on the element k*t and the element ct for the corresponding index t, an inner-product of 0 is obtained for portions constituted by the basis vectors b*1 and b*2 and the basis vectors b1 and b2, which are thus canceled out. That is, when a pairing operation is performed on the element k*t and the element ct for the corresponding index t, the index parts that are set as the coefficients of the basis vectors (portions constituted by the basis vectors b*1 and b*2 and the basis vectors b1 and b2) are canceled out, and a result of the pairing operation for the remaining portions can be obtained.
In the inner-product predicate encryption scheme according to Embodiment 3, the index parts are provided, so that the bases that are used for every attribute category can be constructed as the common bases (basis B and basis B*). As a result, only the basis B and the basis B* need to be included in a public parameter, eliminating the need for reissuing the public parameter when an attribute category is to be added at a later stage.
For the index parts, it is required that 0 be obtained as a result of an inner-product operation of the index parts. Therefore, although the 2-dimensional index parts, namely the basis vectors b*1 and b*2 and the basis vectors b1 and b2, are employed in the above description, the index parts are not limited to 2-dimensional and may be 3-dimensional or higher-dimensional. The values assigned to the index parts are not limited to those described above, and a different assignment arrangement may be employed.
In the above, the IPE-CC scheme corresponding to Type 1 of Non-Patent Literature 4 has been described in which decryption is possible if the set Iv→ is a subset of set Ix→.
However, by applying the above-described algorithms in a similar manner, it is possible to construct an IPE-CC scheme corresponding to Type 2 of Non-Patent Literature 4 (IPE-CC scheme in which decryption is possible if the set Ix→ is a subset of the set Iv→) and an IPE-CC scheme corresponding to Type 0 of Non-Patent Literature 4 (IPE-CC scheme in which decryption is possible if the set Iv→ is a subset of the set Ix→ and the set Ix→ is a subset of the Iv→).
In the above, the method for determining whether or not the ciphertext ctx satisfies the condition which is set in the token tkv has been described. With this method, a secure search system can be constructed in which the ciphertext ctx can be searched for while remaining encrypted.
However, as described in Non-Patent Literature 2 and so on, by embedding a message m in a ciphertext ctx, a narrowly-defined cryptographic system can be constructed in which the message m embedded in the ciphertext ctx is retrieved with the token tkv.
Embodiment 4
Embodiment 4 briefly describes that an IPE-CC scheme having a delegation system is constructed by applying the construction of Non-Patent Literature 2 to the IPE-CC scheme described in the above embodiments.
An example in which the IPE-CC scheme described in Embodiment 1 is provided with a delegation system will be presented herein. Formula 169 through Formula 173 indicate the Setup algorithm, the TokenGen algorithm, and the Enc algorithm, the Query algorithm, and the Delegate algorithm when the IPE-CC scheme described in Embodiment 1 is provided with the delegation system. The Conv algorithm is the same as that in Embodiment 1, and thus will not be described.
For simplicity, an IPE-CC scheme with a two-layer delegation system will be described herein. However, by applying the scheme presented herein, an IPE-CC scheme having a d-layer (d is an integer of 3 or more) delegation system can be easily implemented.



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      169
    
    ]
  




  
    
      Setup
      ⁡
      
        (
        
          
            1
            λ
          
          ,
          
            (
            
              
                n
                1
              
              ,
              
                n
                2
              
            
            )
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    
      n
      :=
      
        
          n
          1
        
        +
        
          n
          2
        
      
    
    ,
    
      

    
    ⁢
    
      
        
          (
          
            
              param
              V
            
            ,
            
              B
              :=
              
                (
                
                  
                    b
                    1
                  
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  
                    b
                    
                      n
                      +
                      u
                      +
                      w
                      +
                      z
                    
                  
                
                )
              
            
            ,
            
              

            
            ⁢
            
              
                B
                *
              
              :=
              
                (
                
                  
                    b
                    1
                    *
                  
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  
                    b
                    
                      n
                      +
                      u
                      +
                      w
                      +
                      z
                    
                    *
                  
                
                )
              
            
          
          )
        
        ⁢
        
          ⟵
          R
        
        ⁢
        
                    ob
          IPE
        
      
      ⁢
      
        (
        
          
            1
            λ
          
          ,
          n
        
        )
      
    
    ,
    
      

    
    ⁢
    
      W
      ⁢
      
        ⟵
        U
      
      ⁢
      
        GL
        ⁡
        
          (
          
            N
            ,
            
              F
              q
            
          
          )
        
      
    
    ,
    
      

    
    ⁢
    
      
        d
        i
      
      :=
      
        
          
            b
            i
          
          ⁢
          W
          ⁢
          
            
          
          ⁢
          for
          ⁢
          
            
          
          ⁢
          i
        
        =
        1
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      n
      +
      u
      +
      w
      +
      z
    
    ,
    
      

    
    ⁢
    
      D
      :=
      
        (
        
          
            d
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            
              n
              +
              u
              +
              w
              +
              z
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        D
        ^
      
      :=
      
        (
        
          
            d
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            n
          
          ,
          
            
              d
              
                n
                +
                u
                +
                w
                +
                1
              
            
            ⁢
            ...
          
          ⁢
          
            
          
          ,
          
            d
            
              n
              +
              u
              +
              w
              +
              z
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        
          B
          ^
        
        *
      
      :=
      
        (
        
          
            b
            1
            *
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            n
            *
          
          ,
          
            b
            
              n
              +
              u
              +
              1
            
            *
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            
              n
              +
              u
              +
              w
            
            *
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        p
        ⁢
        
          
        
        ⁢
        k
      
      :=
      
        (
        
          
            1
            λ
          
          ,
          
            param
            V
          
          ,
          
            D
            ^
          
        
        )
      
    
    ,
    
      ck
      :=
      W
    
    ,
    
      sk
      :=
      
        
          
            
              
                
                  B
                  ^
                
                *
              
              .
              
                

              
              ⁢
              
                                ob
                IPE
              
            
            ⁢
            
              (
              
                
                  1
                  λ
                
                ,
                n
              
              )
            
          
          :
          
            

          
          ⁢
          N
        
        :=
        
          n
          +
          u
          +
          w
          +
          z
        
      
    
    ,
    
      

    
    ⁢
    
      
        param
        G
      
      :=
      
        
          
            (
            
              q
              ,
              G
              ,
              
                G
                T
              
              ,
              g
              ,
              e
            
            )
          
          ⁢
          
            ⟵
            R
          
          ⁢
          
                        bpg
          
        
        ⁢
        
          (
          
            1
            λ
          
          )
        
      
    
    ,
    
      

    
    ⁢
    
      
        param
        
          V
          ′
        
      
      :=
      
        
          
            (
            
              q
              ,
              V
              ,
              
                G
                T
              
              ,
              A
              ,
              e
            
            )
          
          ⁢
          
            ⟵
            R
          
          ⁢
          
                        dpvs
          
        
        ⁢
        
          (
          
            
              1
              λ
            
            ,
            N
          
          )
        
      
    
    ,
    
      

    
    ⁢
    
      ψ
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
        x
      
    
    ,
    
      
        g
        T
      
      :=
      
        
          e
          ⁡
          
            (
            
              g
              ,
              g
            
            )
          
        
        ψ
      
    
    ,
    
      

    
    ⁢
    
      X
      :=
      
        
          (
          
            χ
            
              i
              ,
              j
            
          
          )
        
        ⁢
        
          ⟵
          U
        
        ⁢
        
          GL
          ⁡
          
            (
            
              N
              ,
              
                F
                q
              
            
            )
          
        
      
    
    ,
    
      
        (
        
          θ
          
            i
            ,
            j
          
        
        )
      
      :=
      
        ψ
        ·
        
          
            (
            
              X
              T
            
            )
          
          
            -
            1
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        param
        V
      
      :=
      
        (
        
          
            param
            
              V
              ′
            
          
          ,
          
            g
            T
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        b
        i
      
      :=
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
            χ
            
              i
              ,
              j
            
          
          ⁢
          
            a
            j
          
        
      
    
    ,
    
      B
      :=
      
        (
        
          
            b
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            N
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        b
        i
        *
      
      :=
      
        
          ∑
          
            j
            =
            1
          
          N
        
        ⁢
        
          
            θ
            
              i
              ,
              j
            
          
          ⁢
          
            a
            j
          
        
      
    
    ,
    
      
        B
        *
      
      :=
      
        (
        
          
            b
            1
            *
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            N
            *
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      return
      ⁢
      
        
      
      ⁢
      
        
          (
          
            
              param
              V
            
            ,
            B
            ,
            
              B
              *
            
          
          )
        
        .
        
          

        
        ⁢
        
          [
          
            Formula
            ⁢
            
              
            
            ⁢
            170
          
          ]
        
      
    
  




  
    
      TokenGen
      ⁡
      
        (
        
          
            p
            ⁢
            
              
            
            ⁢
            k
          
          ,
          sk
          ,
          
            
              
                v
                →
              
              1
            
            ∈
            
              
                F
                q
                
                  n
                  1
                
              
              ⁢
              \
              ⁢
              
                {
                
                  0
                  →
                
                }
              
            
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    δ
    ,
    
      φ
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      
        η
        →
      
      0
    
    ,
    
      
        η
        →
      
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        
          η
          →
        
        
          n
          2
        
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
        w
      
    
    ,
    
      

    
    ⁢
    
      
        k
        0
        *
      
      :=
      
        
          (
          
            
              
                
                  σ
                  ⁢
                  
                    
                  
                  ⁢
                  
                    v
                    1
                  
                
                ,
                
                  0
                  
                    n
                    2
                  
                
              
              
                {
                n
              
            
            ,
            
              
                
                  0
                  u
                
                {
              
              u
            
            ,
            
              
                
                  
                    η
                    →
                  
                  0
                
                {
              
              w
            
            ,
            
              
                
                  0
                  z
                
                {
              
              z
            
          
          )
        
        
          B
          *
        
      
    
    ,
    
      

    
    ⁢
    
      
        k
        i
        *
      
      :=
      
        
          (
          
            
              
                
                  σ
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      v
                      →
                    
                    1
                  
                
                ,
                
                  φ
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      e
                      →
                    
                    i
                  
                
              
              
                {
                n
              
            
            ,
            
              
                
                  0
                  u
                
                {
              
              u
            
            ,
            
              
                
                  
                    η
                    →
                  
                  i
                
                {
              
              w
            
            ,
            
              
                
                  0
                  z
                
                {
              
              z
            
          
          )
        
        
          B
          *
        
      
    
    ,
    
      
        for
        ⁢
        
          
        
        ⁢
        i
      
      =
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      n
      2
    
    ,
    
      

    
    ⁢
    
      
        where
        ⁢
        
          
        
        ⁢
        
          
            e
            →
          
          i
        
      
      :=
      
        (
        
          
            0
            
              i
              -
              1
            
          
          ,
          1
          ,
          
            0
            
              
                n
                2
              
              -
              i
            
          
        
        )
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        
          tk
          
            v
            1
          
        
      
      :=
      
        
          (
          
            
              k
              0
              *
            
            ,
            
              k
              1
              *
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              k
              
                n
                2
              
              *
            
          
          )
        
        .
        
          

        
        ⁢
        
          [
          
            Formula
            ⁢
            
              
            
            ⁢
            171
          
          ]
        
      
    
  




  
    
      Enc
      ⁡
      
        (
        
          
            p
            ⁢
            
              
            
            ⁢
            k
          
          ,
          
            
              
                x
                →
              
              1
            
            ∈
            
              
                F
                q
                
                  n
                  1
                
              
              ⁢
              \
              ⁢
              
                {
                
                  0
                  →
                
                }
              
            
          
          ,
          
            
              
                x
                →
              
              2
            
            ∈
            
              F
              q
              
                n
                2
              
            
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    
      τ
      1
    
    ,
    
      
        τ
        2
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      
        ξ
        →
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
        z
      
    
    ,
    
      

    
    ⁢
    
      
        if
        ⁢
        
          
        
        ⁢
        
          
            x
            →
          
          2
        
      
      =
      
        0
        →
      
    
    ,
    
      
        
          x
          →
        
        2
        ′
      
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
        
          n
          2
        
      
    
    ,
    
      
        else
        ⁢
        
          
        
        ⁢
        
          
            x
            →
          
          2
          ′
        
      
      :=
      
        
          x
          →
        
        2
        ′
      
    
    ,
    
      

    
    ⁢
    
      f
      :=
      
        
          (
          
            
              
                
                  
                    τ
                    1
                  
                  ⁢
                  
                    
                      x
                      →
                    
                    1
                  
                
                ,
                
                  
                    τ
                    2
                  
                  ⁢
                  
                    
                      x
                      →
                    
                    2
                    ′
                  
                
              
              
                {
                n
              
            
            ,
            
              
                
                  0
                  u
                
                {
              
              u
            
            ,
            
              
                
                  0
                  w
                
                {
              
              w
            
            ,
            
              
                
                  ξ
                  →
                
                {
              
              z
            
          
          )
        
        D
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        
          ct
          x
        
      
      :=
      
        f
        .
        
          

        
        ⁢
        
          [
          
            Formula
            ⁢
            
              
            
            ⁢
            172
          
          ]
        
      
    
  




  
    
      Query
      ⁡
      
        (
        
          
            p
            ⁢
            
              
            
            ⁢
            k
          
          ,
          
            tk
            :=
            
              
                tk
                
                  v
                  1
                
              
              ⁢
              
                
              
              ⁢
              or
              ⁢
              
                
              
              ⁢
              
                tk
                
                  (
                  
                    
                      v
                      1
                    
                    ,
                    
                      v
                      2
                    
                  
                  )
                
              
            
          
          ,
          
            
              CT
              x
            
            :=
            c
          
        
        )
      
    
    ⁢
    
      :
    
  




  
    
      
        if
        ⁢
        
          
        
        ⁢
        tk
      
      =
      
        
          tk
          
            v
            1
          
        
        =
        
          (
          
            
              k
              0
              *
            
            ,
            
              k
              1
              *
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              k
              
                
                  n
                  2
                
                -
                
                  n
                  1
                
              
              *
            
          
          )
        
      
    
    ,
    
      

    
    ⁢
    
      
        if
        ⁢
        
          
        
        ⁢
        
          e
          ⁡
          
            (
            
              c
              ,
              
                k
                0
                *
              
            
            )
          
        
      
      =
      1
    
    ,
    
      output
      ⁢
      
        
      
      ⁢
      1
    
    ,
    otherwise
    ,
    
      
        output
        ⁢
        
          
        
        ⁢
        0
        ⁢
        
          

        
        ⁢
        if
        ⁢
        
          
        
        ⁢
        tk
      
      =
      
        
          tk
          
            (
            
              
                v
                1
              
              ,
              
                v
                2
              
            
            )
          
        
        =
        
          
            k
            ~
          
          *
        
      
    
    ,
    
      

    
    ⁢
    
      
        if
        ⁢
        
          
        
        ⁢
        
          e
          ⁡
          
            (
            
              c
              ,
              
                k
                *
              
            
            )
          
        
      
      =
      1
    
    ,
    
      output
      ⁢
      
        
      
      ⁢
      1
    
    ,
    otherwise
    ,
    
      output
      ⁢
      
        
      
      ⁢
      
        0.
        ⁢
        
          

        
        [
        
          Formula
          ⁢
          
            
          
          ⁢
          173
        
        ]
      
    
  




  
    
      
        Delegate
        ⁡
        
          (
          
            
              p
              ⁢
              
                
              
              ⁢
              k
            
            ,
            
              
                tk
                
                  v
                  1
                
              
              :=
              
                (
                
                  
                    k
                    0
                    *
                  
                  ,
                  
                    k
                    1
                    *
                  
                  ,
                  ...
                  ⁢
                  
                    
                  
                  ,
                  
                    k
                    
                      n
                      2
                    
                    *
                  
                
                )
              
            
            ,
            
              

            
            ⁢
            
              
                
                  v
                  →
                
                2
              
              :=
              
                
                  (
                  
                    
                      v
                      
                        2
                        ,
                        1
                      
                    
                    ,
                    ...
                    ⁢
                    
                      
                    
                    ,
                    
                      v
                      
                        2
                        ,
                        
                          n
                          2
                        
                      
                    
                  
                  )
                
                ∈
                
                  
                    F
                    q
                    
                      n
                      2
                    
                  
                  ⁢
                  \
                  ⁢
                  
                    {
                    
                      0
                      →
                    
                    }
                  
                
              
            
          
          )
        
      
      :
      
        

      
      ⁢
      ξ
    
    ,
    
      δ
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      
        
          η
          →
        
        ′
      
      :=
      
        
          (
          
            
              
                η
                →
              
              1
              ′
            
            ,
            ...
            ⁢
            
              
            
            ,
            
              
                η
                →
              
              n
              ′
            
          
          )
        
        ⁢
        
          ⟵
          U
        
        ⁢
        
          F
          q
          n
        
      
    
    ,
    
      

    
    ⁢
    
      
        
          k
          ~
        
        *
      
      :=
      
        
          ξ
          ⁢
          
            
          
          ⁢
          
            k
            0
            *
          
        
        +
        
          δ
          ⁡
          
            (
            
              
                ∑
                
                  i
                  =
                  1
                
                
                  n
                  2
                
              
              ⁢
              
                
                  v
                  
                    2
                    ,
                    i
                  
                
                ⁢
                
                  k
                  i
                  *
                
              
            
            )
          
        
        +
        
          
            ∑
            
              i
              =
              1
            
            n
          
          ⁢
          
            
              
                η
                →
              
              i
              ′
            
            ⁢
            
              b
              
                
                  4
                  ⁢
                  n
                
                +
                i
              
              *
            
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        return
        ⁢
        
          
        
        ⁢
        
          tk
          
            (
            
              
                
                  v
                  →
                
                1
              
              ,
              
                
                  v
                  →
                
                2
              
            
            )
          
        
      
      =
      
        
          tk
          
            (
            
              
                
                  v
                  →
                
                1
              
              ⋀
              
                
                  v
                  →
                
                2
              
            
            )
          
        
        :=
        
          
            
              k
              ~
            
            *
          
          .
        
      
    
  



Embodiment 5
Embodiment 5 describes a secure search system 500 which is an application of the cryptographic system 10 described in the above embodiments to a medical information DB (database).
FIG. 12 is a configuration diagram of the secure search system 500 according to Embodiment 5.
The secure search system 500 includes a PKG 510, a plurality of hospitals 520, a helper 530, a plurality of pharmaceutical companies 540, and a medical information DB 550.
Using the key generation device 100, the PKG executes the Setup algorithm, and thus generates a public key pk:=D^, a secret key sk:=B*^ , and a conversion key ck:=W.
Using the encryption device 200, each hospital 520 executes the Enc algorithm, and thus generates a ciphertext ctx in which the DNA information of a patient or the like is encrypted. Then, each hospital 520 registers the generated ciphertext ctx in the medical information DB 550.
Using the conversion device 300, the helper 530 executes the Conv algorithm, and thus converts the ciphertext ctx registered in the medical information DB 550 to generate a ciphertext CTx. The helper 530 registers the generated ciphertext CTx in the medical information DB 550.
Each pharmaceutical company 540, who conducts a search, transmits a predicate vector {right arrow over (v)} in which its own attribute information is set to the PKG 510 from a terminal such as a PC (Personal Computer). Then, using the key generation device 100, the PKG 510 executes the TokenGen algorithm, and thus generates a token tkv based on the transmitted predicate vector {right arrow over (v)}. Then, the PKG 510 transmits the generated token tkv to the pharmaceutical company who has transmitted the predicate vector {right arrow over (v)}.
After receiving the token tkv, the pharmaceutical company 540 transmits a token tkv^ω in which a search condition ({right arrow over (ω)}) is set in the received token tkv to the medical information DB 550 from the terminal to request a search based on the token tkv. As a method for setting the search condition ({right arrow over (ω)}) in the token tkv, there is a method in which the delegation described in Embodiment 4 is adapted.
Upon receiving the request for the search, the medical information DB 550 executes the Query algorithm on each registered ciphertext CTx and the transmitted token tkv using the decryption device 400, and transmits a result to the pharmaceutical company 540 who has requested the search. The result to be transmitted may include an identifier or the like of the ciphertext CTx that has been decrypted by the Query algorithm.
FIG. 13 is a configuration diagram of a secure search system 500 having a different configuration from that of FIG. 12.
The secure search system 500 illustrated in FIG. 13 differs from the secure search system 500 illustrated in FIG. 12 in that the helper 530 is positioned between the pharmaceutical company 540 and the medical information DB 550.
In the secure search system 500 illustrated in FIG. 12, the helper 530 generates a ciphertext CTx and registers the ciphertext CTx in the medical information DB 550. After receiving a request for a search, the medical information DB 550 executes the Query algorithm and returns a result to the pharmaceutical company 540.
In the secure search system 500 illustrated in FIG. 13, when the helper 530 receives a request for a search, the helper 530 executes the Conv algorithm, and thus converts each ciphertext ctx registered in the medical information DB 550 to generate a ciphertext CTx. Then, using the decryption device 400, the helper 530 executes the Query algorithm on each ciphertext CTx that has been generated and the transmitted token tkv, and transmits a result to the pharmaceutical company 540 who has requested the search.
In the above description, the hospital 520 and the pharmaceutical company 540 are examples, and may be replaced by other establishments.
Embodiment 6
In the above embodiments, the methods for implementing the cryptographic processes in dual vector spaces have been described. In Embodiment 6, a method for implementing the cryptographic processes in dual modules will be described.
That is, in the above embodiments, the cryptographic processes are implemented in cyclic groups of prime order q. However, when a ring R is expressed using a composite number M as indicated in Formula 174, the cryptographic processes described in the above embodiments can be adapted to a module having the ring R as a coefficient.

:=/M  [Formula 174]

where

: integer, and

M: composite number.

By changing Fq to R in the algorithms described in the above embodiments, the cryptographic processes in dual additive groups can be implemented.
FIG. 14 is a diagram illustrating an example of the hardware configuration of the key generation device 100, the encryption device 200, the conversion device 300, and the decryption device 400 presented in the above embodiments.
Each of the key generation device 100, the encryption device 200, the conversion device 300, and the decryption device 400 is a computer, and each component of the key generation device 100, the encryption device 200, the conversion device 300, and the decryption device 400 can be implemented by a program.
As the hardware configuration of the key generation device 100, the encryption device 200, the conversion device 300, and the decryption device 400, an arithmetic device 901, an external memory device 902, a main memory device 903, a communication device 904, and an input/output device 905 are connected to a bus.
The arithmetic device 901 is a CPU (Central Processing Unit) or the like that executes programs. The external memory device 902 is, for example, a ROM (Read Only Memory), a flash memory, a hard disk device, and the like. The main memory device 903 is a RAM (Random Access Memory) and the like. The communication device 904 is a network card and the like. The input/output device 905 is, for example, a mouse, a keyboard, a display device, and the like.
The programs are normally stored in the external memory device 902, and are loaded into the main memory device 903 to be sequentially read and executed by the arithmetic device 901.
The programs realize the functions described as the master key generation part 110, the master key storage part 120, the information input part 130, the token generation part 140, the token transmission part 150, the public key acquisition part 210, the information input part 220, the ciphertext generation part 230, the data transmission part 240, the conversion key acquisition part 310, the ciphertext acquisition part 320, the ciphertext conversion part 330, the data transmission part 340, the token acquisition part 410, the ciphertext acquisition part 420, and the decryption part 430.
Further, the external memory device 902 stores an operating system (OS). At least a part of the OS is loaded into the main memory device 903. The arithmetic device 901 executes the programs while executing the OS.
Information, data, signal values, and variable values indicating results of processes described as “compute”, “receive”, “transmit” and so on in the description of Embodiments 1 to 6 are stored as files in the main memory device 903.
The configuration of FIG. 14 is an example of the hardware configuration of the key generation device 100, the encryption device 200, the conversion device 300, and the decryption device 400. The hardware configuration of the key generation device 100, the encryption device 200, the conversion device 300, and the decryption device 400 is not limited to and may be different from the configuration described in FIG. 14.
REFERENCE SIGNS LIST
10: cryptographic system, 100: key generation device, 110: master key generation part, 120: master key storage part, 130: information input part, 140 token generation part, 150: token transmission part, 200: encryption device, 210 public key acquisition part, 220: information input part, 230: ciphertext generation part, 240: data transmission part, 300: conversion device, 310: conversion key acquisition part, 320: ciphertext acquisition part, 330: ciphertext conversion part, 340: data transmission part, 400: decryption device, 410: token acquisition part, 420: ciphertext acquisition part, 430: decryption part, 901: arithmetic device, 902: external memory device, 903: main memory device, 904: communication device, 905: input/output device

## Claims

1. A cryptographic system for concealment of both attribute information and predicate information in a search query, the system comprising:
an encryption device that generates a ciphertext ctx in which attribute information x is set as a coefficient of a basis vector of a basis D;
a conversion device that converts, using conversion information W, the basis D of the ciphertext ctx generated by the encryption device to a basis B so as to generate a ciphertext CTx; and
a decryption device that decrypts the ciphertext CTx generated by the conversion device with a token tkv in which predicate information v is set as a coefficient of a basis vector of a basis B* corresponding to the basis B, determines whether or not the ciphertext condition which is set in the token tkv based on the decryption of the ciphertext CTx, and outputs result of the query based on the determination.

2. The cryptographic system according to claim 1, wherein the decryption device decrypts the ciphertext CTx by performing a pairing operation on the ciphertext CTx and the token tkv and thereby computing an inner-product of the attribute information x and the predicate information v.

3. The cryptographic system according to claim 2,
wherein the encryption device generates the ciphertext ctx including an element f indicated in Formula 1
wherein the conversion device generates a ciphertext CTx including an element c indicated in Formula 2, and
wherein the decryption device decrypts the ciphertext CTx by performing a pairing operation indicated in Formula 3




  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      1
    
    ]
  




  
    
      f
      :=
      
        
          (
          
            
              
                τ
                ⁢
                
                  
                
                ⁢
                
                  x
                  →
                
              
              {
            
            n
          
          )
        
        ⁢
        D
        ⁢
        
          

        
        ⁢
        where
        ⁢
        
          

        
        ⁢
        
          τ
          ⁢
          
            ⟵
            U
          
          ⁢
          
            F
            q
          
        
      
    
    ,
    
      

    
    ⁢
    
      
        x
        →
      
      :=
      
        x
        1
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      x
      n
    
    ,
    and
  




  
    
      x
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        
          
            x
            n
          
          ⁢
          
            
          
          ⁢
          is
          ⁢
          
            
          
          ⁢
          the
          ⁢
          
            
          
          ⁢
          attribute
          ⁢
          
            
          
          ⁢
          information
          ⁢
          
            
          
          ⁢
          x
        
        ;
      
      ⁢
      
        

      
      [
      
        Formula
        ⁢
        
          
        
        ⁢
        2
      
      ]
    
  




  
    c
    :=
    
      ρ
      ⁢
      
        
      
      ⁢
      
        f
        ·
        
          W
          
            -
            1
          
        
      
    
  




  where




  
    
      ρ
      ⁢
      
        ⟵
        U
      
      ⁢
      
        F
        q
      
    
    ,
    
      

    
    ⁢
    
      
        d
        i
      
      :=
      
        
          
            b
            i
          
          ⁢
          W
          ⁢
          
            
          
          ⁢
          for
          ⁢
          
            
          
          ⁢
          i
        
        =
        1
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    n
    ,
    
      

    
    ⁢
    
      D
      :=
      
        (
        
          
            d
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            d
            n
          
        
        )
      
    
    ,
    and
  




  
    B
    :=
    
      
        (
        
          
            b
            1
          
          ,
          ...
          ⁢
          
            
          
          ,
          
            b
            n
          
        
        )
      
      ⁢
      
        

      
      [
      
        Formula
        ⁢
        
          
        
        ⁢
        3
      
      ]
    
  




  
    e
    ⁡
    
      (
      
        c
        ,
        
          k
          *
        
      
      )
    
  




  where




  
    
      
        k
        *
      
      :=
      
        
          (
          
            
              
                σ
                ⁢
                
                  v
                  →
                
              
              {
            
            n
          
          )
        
        ⁢
        
          B
          *
        
      
    
    ,
    
      

    
    ⁢
    
      
        v
        →
      
      :=
      
        v
        1
      
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      v
      n
    
    ,
    and
  




  
    
      v
      1
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        v
        n
      
      ⁢
      
        
      
      ⁢
      is
      ⁢
      
        
      
      ⁢
      the
      ⁢
      
        
      
      ⁢
      predicate
      ⁢
      
        
      
      ⁢
      information
      ⁢
      
        
      
      ⁢
      
        v
        .

4. The cryptographic system according to claim 1, wherein the basis B and the basis B* are orthonormal bases in dual pairing vector spaces.

5. The cryptographic system according to claim 1, wherein the basis B and the basis B* are bases that are generated by modifying a basis A which is predetermined using a sparse matrix having at least one value other than a constant value 0 in each row and in each column.

6. The cryptographic system according to claim 5, wherein the basis B and the basis B* are bases that are generated from the basis A, as indicated in Formula 5, using an N-row and N-column (N being an integer of n or more) linear transformation X whose values in a first row in a first column through in an n-th row in an n-th column are a sparse matrix indicated in Formula 4



  
    [
    
      Formula
      ⁢
      
        
      
      ⁢
      4
    
    ]
  




  
    (
    
      
        
          
            μ
            1
            ′′
          
        
        
          
            μ
            2
            ′′
          
        
        
          ⋯
        
        
          
            μ
            
              n
              -
              1
            
            ′′
          
        
        
          
            μ
            ′′′
          
        
      
      
        
          
            
          
        
        
          μ
        
        
          
            
          
        
        
          
            
          
        
        
          
            μ
            2
            ′
          
        
      
      
        
          
            
          
        
        
          
            
          
        
        
          ⋱
        
        
          
            
          
        
        
          ⋮
        
      
      
        
          
            
          
        
        
          
            
          
        
        
          
            
          
        
        
          
            
          
        
        
          
            μ
            
              n
              -
              1
            
            ′
          
        
      
      
        
          
            
          
        
        
          
            
          
        
        
          
            
          
        
        
          
            
          
        
        
          
            μ
            n
            ′
          
        
      
    
    )
  



where μ, μ′2, . . . , μ′n, μ′′1, . . . , μ′′n−1, and μ′′′ are predetermined values other than the constant value 0, and a blank element denotes the constant value 0,


bi:=Σj=1NXi,jaj for i=1, . . . ,N,B:=(b1, . . . ,bN),



∂i,j:=ψ·(X−1)T,



b*i:=Σi=jN∂i,jaj for i=1, . . . ,N,B*:=(b*1, . . . ,b*N)  [Formula 5]


where Xi,j denotes an entry in an i-th row in a j-th column in the linear transformation X, ψ is a predetermined value, and aj is a j-th basis vector of the basis A.

7. The cryptographic system according to claim 1,
wherein the encryption device generates the ciphertext ctx including, for each index t included in a set Ix, an element ct in which information Jt which is assigned to the index t in advance is set as a coefficient of a basis vector dindex of the basis D, and attribute information xt among the attribute information x is set as a coefficient of another basis vector of the basis D, and
wherein the decryption device decrypts the ciphertext CTx with the token tkv including, for each index t included in a set Iv, an element kt in which information J*t having an inner-product of 0 with the information Jt is set as a coefficient of a basis vector b*index of the basis B* corresponding to the basis vector dindex, and predicate information vt among the predicate information v is set as a coefficient of another basis vector of the basis B*.

8. The cryptographic system according to claim 1,
wherein the encryption device generates a ciphertext ctx in which genetic information is set as the attribute information x, and
wherein the decryption device decrypts the ciphertext CTx with the token tkv so as to search for a ciphertext CTx having genetic information satisfying a condition which is set in the token tkv.

9. A cryptographic method for concealment of both attribute information and predicate information in a query, the method comprising:
generating a ciphertext ctx in which attribute information x is set as a coefficient of a basis vector of a basis D, by an encryption device;
converting, using conversion information W, the basis D of the generated ciphertext ctx to a basis B so as to generate a ciphertext CTx, by a conversion device;
decrypting the generated ciphertext CTx, with a token tkv in which predicate information v is set as a coefficient of a basis vector of a basis B* corresponding to the basis B, by a decryption device;
determining whether or not the ciphertext ctx satisfies a condition which is set in the token tkv based on the decryption of the ciphertext CTx; and
outputting a result of the query based on the determination.

10. A non-transitory computer readable medium, having stored there on a cryptographic program that when executed causes a computer to
generate a ciphertext ctx in which attribute information x is set as a coefficient of a basis vector of a basis D;
convert, using conversion information W the basis D of the generated ciphertext ctx to a basis B so as to generate a ciphertext CTx;
decrypting the generated ciphertext CTx with a token tkv in which predicate information v is set as a coefficient of a basis vector of a basis B* corresponding to the basis B,
determining whether or not the ciphertext ctx satisfies a condition which is set in the token tkv based on the decryption of the ciphertext CTx; and
outputting a result of the query based on the determination.

11. The cryptographic system according to claim 1, wherein the cryptographic system implements an encryption scheme in a public key setting in which at least a part of basis vectors of the basis D is made public as a public key.

12. The cryptographic system according to claim 1, wherein the cryptographic system implements an encryption scheme in a secret key setting in which at least a part of basis vectors of the basis D is distributed to the encryption device as a secret key.