Cryptographic system and computer readable medium
A cryptographic system ( 10 ) performs a cryptographic process using a basis. B and a basis B*. An encryption device ( 200 ) generates a ciphertext including a transmission-side vector being a vector in the basis B and being generated using one vector of a first vector consisting of coefficients y j of a polynomial having x i as roots and a second vector consisting of v 1 i being a power of v 1 . A decryption device ( 300 ) decrypts the ciphertext generated by the encryption device ( 200 ) with a decryption key including a reception-side vector being a vector in the basis B* and being generated using the other vector of the first vector and the second vector.
1. A cryptographic system to perform a cryptographic process using a basis B and a basis B*, the cryptographic system comprising:
processing circuitry to:
generate a transmission-side vector being a vector in the basis B and being generated using one vector of a first vector consisting of coefficients y j (j=1, . . . , n) of a polynomial having attribute information x i (i=1, . . . , n′, n′ being an integer from 1 to n−1, n being an integer of 2 or greater) as roots and a second vector consisting of v 1 i (i=0, . . . , n−1) being a power of predicate information v 1 ;
perform a pairing operation on the transmission-side vector and a reception-side vector being a vector in the basis B* and being generated using another vector of the first vector and the second vector; and
generate at least one of a ciphertext, decryption key and signature output of reduced size containing the transmission-side vector or reception-side vector to reduce processing time of an encryption or decryption process.
2. The cryptographic system according to claim 1 , wherein
the basis B and the basis B* are bases which are generated by transforming a basis A by using a sparse matrix having at least one value other than a constant value 0 in each row and each column.
3. A cryptographic system to perform a cryptographic process using a basis B and a basis B*, the cryptographic system comprising:
processing circuitry to:
generate a transmission-side vector being a vector in the basis B and being generated using one vector of a first vector consisting of coefficients y j (j=1, . . . , n) of a polynomial having attribute information x i (i=1, . . . , n′, n′ being an integer from 1 to n−1, n being an integer of 2 or greater) as roots and a second vector consisting of v 1 i (i=0, . . . , n−1) being a power of predicate information v 1 ;
perform a pairing operation on the transmission-side vector and a reception-side vector being a vector in the basis B* and being generated using another vector of the first vector and the second vector; and
generate at least one of a ciphertext, decryption key, and signature output of reduced size containing the transmission-side vector or reception-side vector to reduce processing time of an encryption or decryption process, wherein
the first vector is a vector indicated in Formula 1, and
the second vector is a vector indicated in Formula 2
{right arrow over ( y )}:=( y 1 , . . . ,y n ) such that Σ j=0 n-1 y n-j z j =z n-1-n′ ·( z−x j ) [Formula 1]
{right arrow over (v)} 1 :=( v 1 n-1n , . . . ,v 1 ,1) [Formula 2]
4. The cryptographic system according to claim 3 , wherein
the processing circuitry generates at least one of a ciphertext ct Γ including a transmission-side vector c 1 indicated in Formula 3, and
decrypts the ciphertext ct Γ by using a decryption key sk S including a reception-side vector k* i indicated in Formula 4
c
1
=
(
ω
y
->
,
︷
n
…
)
𝔹
1
where
ω
⟵
U
𝔽
q
[
Formula
3
]
for
i
=
1
,
…
,
L
,
if
ρ
(
i
)
=
v
i
,
k
i
*
:=
(
s
i
e
->
1
+
θ
i
v
->
i
,
︷
n
…
)
𝔹
1
*
,
if
ρ
(
i
)
=
⫬
v
i
,
k
i
*
:=
(
s
i
v
->
i
,
︷
n
t
…
)
𝔹
1
*
where
f
->
⟵
U
𝔽
q
r
,
s
->
T
:=
(
s
1
,
…
,
s
L
)
T
:=
M
·
f
->
T
,
s
0
:=
1
->
·
f
->
T
,
θ
i
⟵
U
𝔽
q
,
v
->
i
:=
(
v
i
n
-
1
,
…
,
v
i
,
1
)
.
[
Formula
4
]
5. The cryptographic system according to claim 3 , wherein
the processing circuitry generates at least one of a ciphertext ct S including a transmission-side vector c i indicated in Formula 5, and
decrypts the ciphertext ct S by using a decryption key sk Γ including a reception-side vector k* 1 indicated in Formula 6
for
i
=
1
,
…
,
L
,
if
ρ
(
i
)
=
v
i
,
c
i
:=
(
s
i
e
->
1
+
θ
i
v
->
i
,
︷
n
…
)
𝔹
1
,
if
ρ
(
i
)
=
⫬
v
i
,
c
i
:=
(
s
i
v
->
i
,
︷
n
t
…
)
𝔹
1
where
f
->
⟵
U
𝔽
q
r
,
s
->
T
:=
(
s
1
,
…
,
s
L
)
T
:=
M
·
f
->
T
,
s
0
:=
1
->
·
f
->
T
,
θ
i
⟵
U
𝔽
q
,
v
->
i
:=
(
v
i
n
-
1
,
…
,
v
i
,
1
)
[
Formula
5
]
k
1
*
=
(
ω
y
->
,
︷
n
…
)
𝔹
1
*
where
ω
⟵
U
𝔽
q
.
[
Formula
6
]
6. The cryptographic system according to claim 3 , wherein
the processing circuitry generates at least one of a ciphertext ct Γ including a transmission-side vector c 1.t indicated in Formula 7, and
decrypts the ciphertext ct Γ by using a decryption key sk S including a reception-side vector k* i.t indicated in Formula 8
c
1
,
t
=
(
ω
y
->
t
,
︷
n
t
…
)
𝔹
1
,
t
where
ω
⟵
U
𝔽
q
,
y
->
t
:=
(
y
1
,
t
,
…
,
y
n
t
,
t
)
such
that
∑
j
=
0
n
t
-
1
y
n
t
-
j
,
t
z
j
=
z
n
t
-
1
-
n
t
′
·
∏
j
=
1
n
t
′
(
z
-
x
j
,
t
)
[
Formula
7
]
for
i
=
1
,
…
,
L
,
if
ρ
(
i
)
=
(
t
,
v
i
)
,
k
i
*
:=
(
s
i
e
->
1
,
t
+
θ
i
v
->
i
,
︷
n
t
…
)
𝔹
1
,
t
*
,
if
ρ
(
i
)
=
⫬
(
t
,
v
i
)
,
k
i
*
:=
(
s
i
v
->
i
,
︷
n
t
…
)
𝔹
1
,
t
*
where
f
->
⟵
U
𝔽
q
r
,
s
->
T
:=
(
s
1
,
…
,
s
L
)
T
:=
M
·
f
->
T
,
s
0
:=
1
->
·
f
->
T
,
θ
i
⟵
U
𝔽
q
,
v
->
i
:=
(
v
i
n
t
-
1
,
…
,
v
i
,
1
)
.
[
Formula
8
]
7. The cryptographic system according to claim 3 , wherein
the processing circuitry generates at least one of a ciphertext ct S including a transmission-side vector c i.t indicated in Formula 9, and
decrypts the ciphertext ct S by using a decryption key sk Γ including a reception-side vector k* 1.t indicated in Formula 10
for
i
=
1
,
…
,
L
,
if
ρ
(
i
)
=
(
t
,
v
i
)
,
c
i
:=
(
s
i
e
->
1
,
t
+
θ
i
v
->
i
,
︷
n
t
…
)
𝔹
1
,
t
,
if
ρ
(
i
)
=
⫬
(
t
,
v
i
)
,
c
i
:=
(
s
i
v
->
i
,
︷
n
t
…
)
𝔹
1
,
t
where
f
->
⟵
U
𝔽
q
r
,
s
->
T
:=
(
s
1
,
…
,
s
L
)
T
:=
M
·
f
->
T
,
s
0
:=
1
->
·
f
->
T
,
θ
i
,
t
⟵
U
𝔽
q
,
v
->
i
:=
(
v
i
n
t
-
1
,
…
,
v
i
,
1
)
[
Formula
9
]
k
1
,
t
*
=
(
ω
y
t
->
,
︷
n
t
…
)
𝔹
1
,
t
*
where
ω
⟵
U
𝔽
q
,
y
->
t
:=
(
y
1
,
t
,
…
,
y
n
t
,
t
)
such
that
∑
j
=
0
n
t
-
1
y
n
t
-
j
,
t
z
j
=
z
n
t
-
1
-
n
t
′
·
∏
j
=
1
n
t
′
(
z
-
x
j
,
t
)
.
[
Formula
10
]
8. The cryptographic system according to claim 3 , wherein
the processing circuitry generates a signature Sig including a transmission-side vector s* i indicated in Formula 11, and
verifies the signature Sig by using a verification key vk including a reception-side vector c i indicated in Formula 12
s
i
*
:=
γ
i
·
ξ
k
1
*
+
∑
t
=
1
n
u
i
,
t
·
b
1
,
t
*
,
for
i
=
1
,
…
,
L
where
k
1
*
=
(
ω
y
->
,
︷
n
…
)
𝔹
1
*
,
ξ
⟵
U
𝔽
q
,
γ
i
,
u
->
i
:=
(
u
i
,
1
,
…
,
u
i
,
n
)
are
defined
as
if
i
∈
I
⩓
ρ
(
i
)
=
v
->
i
,
γ
i
:=
α
i
,
u
->
i
⟵
U
{
u
->
i
|
u
->
i
·
v
->
i
=
0
⩓
u
i
,
1
=
β
i
}
,
if
i
∈
I
⩓
ρ
(
i
)
=
⫬
v
->
i
,
γ
i
:=
α
i
v
->
i
·
y
->
,
u
->
i
⟵
U
{
u
->
i
|
u
->
i
·
v
->
i
=
β
i
}
,
if
i
∉
I
⩓
ρ
(
i
)
=
v
->
i
,
γ
i
:=
0
,
u
->
i
⟵
U
{
u
->
i
|
u
->
i
·
v
->
i
=
0
⩓
u
i
,
1
=
β
i
}
,
if
i
∉
I
⩓
ρ
(
i
)
=
⫬
v
->
i
,
γ
i
:=
0
,
u
->
i
⟵
U
{
u
->
i
|
u
->
i
·
v
->
i
=
β
i
}
[
Formula
11
]
for
i
=
1
,
…
,
L
,
if
ρ
(
i
)
=
v
i
c
i
:=
(
s
i
e
->
1
+
θ
i
v
->
t
,
︷
n
…
)
𝔹
1
,
if
ρ
(
i
)
=
⫬
v
i
,
c
i
:=
(
s
i
v
->
t
,
︷
n
t
…
)
𝔹
1
where
f
->
⟵
U
𝔽
q
r
,
s
->
T
:=
(
s
1
,
…
,
s
L
)
T
:=
M
·
f
->
T
,
s
0
:=
1
->
·
f
->
T
,
θ
i
⟵
U
𝔽
q
,
v
->
i
:=
(
v
i
n
-
1
,
…
,
v
i
,
1
)
.
[
Formula
12
]
9. A non-transitory computer readable medium storing a cryptographic program for performing a cryptographic process using a basis B and a basis B*, the cryptographic program causing a computer to execute:
a transmission-side process of generating a transmission-side vector being a vector in the basis B and being generated using one vector of a first vector consisting of coefficients y j (j=1, n) of a polynomial having attribute information x i (i=1, . . . , n′, n′ being an integer from 1 to n−1, n being an integer of 2 or greater) as roots and a second vector consisting of v 1 i (i=0, . . . , n−1) being a power of predicate information v 1 ;
a reception-side process of performing a pairing operation on the transmission-side vector and a reception-side vector being a vector in the basis B* and being generated using another vector of the first vector and the second vector; and
wherein at least one of the transmission-side process and reception-side process generates at least one of a ciphertext, decryption key and signature output of reduced size containing the transmission-side vector or reception-side vector to reduce processing time of an encryption or decryption process.