# US 11,909,873 B2 · Decryption device, cryptographic system, and decryption method

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,909,873 B2
- Document ID: US11909873B2
- Status: Granted
- Kind: B2
- Application number: 17/207,087
- Filed: 2021-03-19
- Published: 2021-07-29
- Granted: 2024-02-20
- Earliest claimed: 2018-10-04
- Assignees: Mitsubishi Electric Corporation; Nippon Telegraph and Telephone Corporation
- Applicants: Mitsubishi Electric Corporation; Nippon Telegraph and Telephone Corporation
- Inventors: Katsuyuki Takashima; Tatsuaki Okamoto; Pratish Datta
- Web page: https://patentgrep.com/patent/US11909873B2

## CPC

- H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords}
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G09C 1/00: Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00)
- H04L 9/0825: {using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates}
- H04L 9/083: {involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]}
- H04L 9/0847: {involving identity based encryption [IBE] schemes}
- H04L 9/088: {Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms (network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068)}
- H04L 9/3073: {involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G09C: CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY

## Abstract

An encryption device (20) generates a ciphertext by setting, in the ciphertext, one of a predicate vector of arithmetic branching programs (ABP) and an attribute vector over a basis B of the basis B and a basis B*, which are dual bases in dual vector spaces. A key generation device (30) generates a decryption key by setting, in the decryption key, the other one of the predicate vector and the attribute vector over the basis B*. A decryption device (40) decrypts the ciphertext by performing a pairing operation on the ciphertext generated by the encryption device (20) and the decryption key generated by the key generation device (30).

## Claims

### Claim 1

A decryption device comprising:
processing circuitry to:
acquire a ciphertext in which one of a predicate vector of arithmetic branching programs (ABP) and an attribute vector is set over a basis B, wherein the basis B and a basis B* are dual bases in dual vector spaces, which are generated based on a length (n′) of a public attribute vector and a length (n) of a secret attribute vector such that each of the basis B and the basis B* consists of L partial bases, wherein L is an integer equal to n′+n, each of n′ and n is an integer greater than or equal to 1, and the public attribute vector is published,
acquire a decryption key in which the other one of the predicate vector and the attribute vector is set over the basis B*, and
decrypt the ciphertext by performing a pairing operation on the acquired ciphertext and the acquired decryption key.

### Claim 2 (depends on 1)

The decryption device according to claim 1,
wherein elements of the predicate vector are elements obtained by a product of a matrix representation L that represents an ABP computing a function f and a matrix whose elements in a last row are 1's.

### Claim 3 (depends on 2)

The decryption device according to claim 2,
wherein the processing circuitry computes cofactors of elements in a last column of the matrix representation L,
computes an operation value by performing a pairing operation on the ciphertext and the decryption key, and
computes an output value obtained by decrypting the ciphertext, using the computed cofactors and the computed operation value.

### Claim 4 (depends on 3)

The decryption device according to claim 3,
wherein the processing circuitry computes a value resulting from inputting the attribute vector to the function f, using an inner-product and the cofactors, and computes the output value based on the computed value.

### Claim 5 (depends on 4)

The decryption device according to claim 4,
wherein the processing circuitry acquires a ciphertext CT indicated in Formula 1,
acquires a decryption key SK(f) indicated in Formula 2,
computes the operation values Λ′j and Λj by performing a pairing operation as indicated in Formula 3,
computes a value Λ as indicated in Formula 4, and computes an output value depending on a value of the value Λ
CT
=
(
x
→
,
{
c
′
⁡
(
ι
′
)
}
ι
′
∈
[
n
′
]
,
{
c
(
ι
)
}
ι
∈
[
n
]
)
ω
⟵
U
𝔽
q
,
for
⁢
ι
′
∈
[
n
'
]
ϕ
ι
′
′
⟵
U
𝔽
q
,
c
′
⁡
(
ι
′
)
=
(
ω
⁡
(
1
,
x
ι
′
)
,
0
→
4
,
0
→
2
,
ϕ
ι
′
′
)
𝔹
ι
′
,
for
⁢
ι
∈
[
n
]
ϕ
ι
⟵
U
𝔽
q
,
c
(
ι
)
=
(
ω
⁡
(
1
,
z
ι
)
,
0
→
4
,
0
→
2
,
ϕ
ι
)
𝔹
n
′
+
ι
,
[
Formula
⁢
1
]
where
n′,n∈,
({right arrow over (x)},{right arrow over (z)})∈qn′×qn are attribute vectors,
SK
⁢
(
f
)
=
(
f
,
{
k
′
⁡
(
j
′
)
}
j
′
∈
[
m
]
,
{
k
(
j
)
}
j
∈
[
n
]
)
,
(
(
{
σ
j
}
j
∈
[
n
]
,
{
α
j
′
,
γ
j
′
}
j
′
∈
[
m
]
)
,
ρ
⁢
:
[
m
]
→
[
n
′
]
)
⟵
R
PGB
⁡
(
f
)
,
ς
⟵
U
𝔽
q
,
for
⁢
j
′
∈
[
m
]
κ
→
′
⁡
(
j
′
)
⟵
U
𝔽
q
2
,
k
′
(
j
′
)
=
(
(
γ
j
′
,
α
j
′
)
,
0
→
4
,
κ
→
′
(
j
′
)
,
0
)
𝔹
ρ
⁡
(
j
′
)
*
,
for
⁢
j
∈
[
n
]
κ
→
(
j
)
⟵
U
𝔽
q
2
,
k
⁡
(
j
)
=
(
(
σ
j
,
ς
)
,
0
→
4
,
κ
→
(
j
)
,
0
)
𝔹
n
′
+
1
*
[
Formula
⁢
2
]
where
PGB(f) is an algorithm that takes as input a function f, and outputs a set of constants ({σj}j∈[n], {αj′,γj′}j′∈[m])∈Fqn×(Fq2)m, which are elements of a predicate vector, along with a function ρ: [m]→[n′],
Λ′j′=e(c′(ρ(j′)),k′(j′)) for j′∈[m],
Λj=e(c(j),k(j)) for j∈[n] [Formula 3]
Λ
=
(
∏
j
′
∈
[
m
]
Λ
j
′
′Ω
j
′
′
)
⁢
(
∏
j
∈
[
n
]
Λ
j
Ω
j
)
,
(
{
Ω
j
}
j
∈
[
n
]
,
{
Ω
′
j
′
}
j
′
∈
[
m
]
)
=
R
⁢
E
⁢
C
⁡
(
f
,
x
→
)
,
[
Formula
⁢
4
]
where
REC(f,{right arrow over (x)}) is an algorithm that takes as input a function f and x→∈Fqn′, and
outputs a set of coefficients ({Ωj}j∈[n], {Ω′j′}j′∈[m])∈Fqn+m.

### Claim 6 (depends on 4)

The decryption device according to claim 4,
wherein the processing circuitry acquires a ciphertext CT indicated in Formula 5,
acquires a decryption key SK(f) indicated in Formula 6,
computes the operation values Λ′0, Λ′j, and Λj by performing a pairing operation as indicated in Formula 7,
computes a value Λ as indicated in Formula 8, and computes a value ΛΛ′0 as the output value
CT
=
(
x
→
,
{
c
′
⁡
(
ι
′
)
}
ι
′
∈
[
0
,
n
′
]
,
{
c
(
ι
)
}
ι
∈
[
n
]
)
,
ω
,
ξ
,
ϕ
0
′
⟵
U
𝔽
q
,
c
′
⁡
(
0
)
=
(
ω
,
0
→
2
,
ξ
,
0
,
ϕ
0
′
)
𝔹
0
,
for
⁢
ι
′
∈
[
n
'
]
ϕ
ι
′
′
⟵
U
𝔽
q
,
c
′
⁡
(
ι
′
)
=
(
ω
⁡
(
1
,
x
ι
′
)
,
0
→
4
,
0
→
2
,
ϕ
ι
′
′
)
𝔹
ι
′
,
for
⁢
ι
∈
[
n
]
ϕ
ι
⟵
U
𝔽
q
,
c
(
ι
)
=
(
ω
⁡
(
1
,
z
ι
)
,
0
→
4
,
0
→
2
,
ϕ
ι
)
𝔹
n
′
+
ι
,
[
Formula
⁢
5
]
where
n′,n∈,
({right arrow over (x)},{right arrow over (z)})∈qn′×qn are attribute vectors,
SK
⁢
(
f
)
=
(
f
,
{
β
j
′
′
}
j
′
∈
[
m
]
,
{
β
j
}
j
∈
[
n
]
,
{
k
′
(
j
′
)
}
j
′
∈
[
0
,
m
]
,
{
k
(
j
)
}
j
∈
[
n
]
)
,
(
(
{
σ
j
}
j
∈
[
n
]
,
{
α
j
′
,
γ
j
′
}
j
′
∈
[
m
]
)
,
ρ
⁢
:
[
m
]
→
[
n
′
]
)
⟵
R
PGB
⁡
(
f
)
,
r
0
,
κ
0
′
,
ς
⟵
U
𝔽
q
,
k
′
⁡
(
0
)
=
(
-
r
0
,
0
→
2
,
1
,
κ
0
′
,
0
)
𝔹
0
*
,
for
⁢
j
′
∈
[
m
]
β
j
′
′
⟵
U
𝔽
q
,
κ
→
(
j
′
)
⟵
U
𝔽
q
2
,
γ
j
′
+
=
γ
j
′
+
β
j
′
,
r
0
,
k
′
(
j
′
)
=
(
(
γ
j
′
+
,
α
j
′
)
,
0
→
4
,
κ
→
′
(
j
′
)
,
0
)
𝔹
ρ
⁡
(
j
′
)
*
,
for
⁢
j
∈
[
n
]
β
j
⟵
U
𝔽
q
,
κ
→
(
j
)
⟵
U
𝔽
q
2
,
σ
j
+
=
σ
j
+
β
j
⁢
r
0
⁢
k
⁡
(
j
)
=
(
(
σ
j
+
,
ς
)
,
0
→
⁢
4
,
κ
→
(
j
)
,
0
)
𝔹
n
′
+
j
*
,
[
Formula
⁢
6
]
where
PGB(f) is an algorithm that takes as input a function f, and outputs a set of
constants ({σj}j∈[n], {αj′,γj′}j′∈[m])∈Fqn×(Fq2)m, which are elements of a predicate vector, along with a function ρ:[m]→[n],
Λ′0=e(c′(0),k′(0)),
Λ′j′=e(c′(ρ(j′)),k′(j′)) for j′∈[m],
Λj=e(c(j),k(j)) for j∈[n] [Formula 7]
Λ
=
(
∏
j
′
∈
[
m
]
Λ
j
′
′Ω
j
′
′
)
⁢
(
∏
j
∈
[
n
]
Λ
j
Ω
j
)
1
∑
j
∈
[
m
]
′
Ω
j
′
′
⁢
β
j
′
′
+
∑
j
∈
[
n
]
Ω
j
⁢
β
j
,
(
{
Ω
j
}
j
∈
[
n
]
,
{
Ω
j
′
′
}
j
′
∈
[
m
]
)
=
R
⁢
E
⁢
C
⁡
(
f
,
x
→
)
,
[
Formula
⁢
8
]
where
REC(f,{right arrow over (x)}) is an algorithm that takes as input a function f and x→∈Fqn′, and outputs
a set of coefficients ({Ωj}j∈[n], {Ω′j′}j′∈[m])∈Fqn+m′.

### Claim 7

A cryptographic system comprising:
an encryption device to generate a ciphertext by setting, in the ciphertext, one of a predicate vector of arithmetic branching programs (ABP) and an attribute vector over a basis B, wherein the basis B and a basis B* are dual bases in dual vector spaces, which are generated based on a length (n′) of a public attribute vector and a length (n) of a secret attribute vector such that each of the basis B and the basis B* consists of L partial bases, wherein L is an integer equal to n′+n, each of n′ and n is an integer greater than or equal to 1, and the public attribute vector is published;
a key generation device to generate a decryption key by setting, in the decryption key, the other one of the predicate vector and the attribute vector over the basis B*; and
a decryption device to decrypt the ciphertext by performing a pairing operation on the ciphertext generated by the encryption device and the decryption key generated by the key generation device.

### Claim 8

A decryption method comprising:
acquiring a ciphertext in which one of a predicate vector of arithmetic branching programs (ABP) and an attribute vector is set over a basis B, wherein the basis B and a basis B* are dual bases in dual vector spaces, which are generated based on a length (n′) of a public attribute vector and a length (n) of a secret attribute vector such that each of the basis B and the basis B* consists of L partial bases, wherein L is an integer equal to n′+n, each of n′ and n is an integer greater than or equal to 1, and the public attribute vector is published;
acquiring a decryption key in which the other one of the predicate vector and the attribute vector is set over the basis B*; and
decrypting the ciphertext by performing a pairing operation on the acquired ciphertext and the acquired decryption key.