US 8,897,442 B2Granted

Encryption device, decryption device, encryption method, decryption method, program, and recording medium

AssigneeNippon Telegraph and Telephone Corporation

InventorEiichiro Fujisaki

Life of this patent

Estimating the term…

Abstract

In encryption, a random number r is generated to generate a ciphertext C2=M(+)R(r), function values HS(r, C2), a common key K, a ciphertext C(Ψ+1) of the random number r using the common key K, and ciphertexts C(0) and C(λ) of the common key K that correspond to function values HS(r, C2). In decryption, a common key K′ is decrypted from input ciphertexts C′(0) and C′(λ), an input ciphertext C′(Ψ+1) is decrypted by using the common key K′ to generate a decrypted value r′, and function values HS(r′, C2′) is generated. If the input ciphertexts C′(0) and C′(λ) do not match ciphertexts C″(0) and C″(λ) of the common key K′ that correspond to the function values HS(r′, C2′), decryption is rejected; if they match, the input ciphertext C2′ is decrypted.

Claims34

Dependent claims

An encryption device comprising:

a random number generating unit that generates a random number r;
a first encryption unit that generates a ciphertext C2, the ciphertext C2 being an exclusive OR of a binary sequence dependent on the random number r and a plaintext M, the plaintext M being a binary sequence;
a function calculating unit that generates Smax function values HS(r, C2), where S=1, . . . , Smax and Smax≧1, each of the function values HS(r, C2) being obtained by inputting a pair of the random number r and the ciphertext C2 in each of collision-resistant functions HS;
a common key generating unit that generates a common key K, the common key being an element of a cyclic group GT;
a second encryption unit that encrypts the random number r by common key encryption using the common key K to generate ciphertext C(Ψ+1);
and
a third encryption unit that generates a ciphertext C1 including C(0)=υ·b1(0)+Σι=2Iυι(0)·bι(0), C(λ)=υ·Σκ=1n(λ)wι(λ)·bι(λ)+Σι=n(λ)+1n(λ)+ι(λ)υ(λ)·bι(λ) and the ciphertext C(Ψ+1);
wherein Ψ is an integer greater than or equal to 1, φ is an integer greater than or equal to 0 and less than or equal to Ψ, n(φ) is an integer greater than or equal to 1, ζ(φ) is an integer greater than or equal to 0, λ is an integer greater than or equal to 1 and less than or equal to Ψ, I is a constant greater than or equal to 2 and less than or equal to n(0)+ζ(0), eφ is a nondegenerate bilinear map that outputs one element of the cyclic group GT in response to input of n(φ)+ζ(φ) elements γβ (β=1, . . . , n(φ)+ζ(φ) of a cyclic group G1 and n(φ)+ζ(φ) elements γβ*(β=1, . . . , n(φ)+ζ(φ)) of a cyclic group G2, i is an integer greater than or equal to 1 and less than or equal to n(φ)+ζ(φ), bi(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ)+ζ(φ) elements of the cyclic group G1, bi*(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ)+ζ(φ) elements of the cyclic group G2, δ(i, j) is a Kronecker delta function, eφ(bi(φ), bj*(φ))=gTτ·τ′·δ(i,j) is satisfied for a generator gT of the cyclic group GT and constants τ and τ′, w(λ)→=(w1(λ), . . . , wn(λ)(λ)) are n(λ)-dimensional vectors each consisting of w1(λ), . . . , wn(λ)(λ), and at least some of the values of υ, υ2(0), . . . , υI(0), υn(λ)+1(λ), . . . , υn(λ)+ζ(λ)(λ) correspond to at least some of the function values HS(r, C2).

5 more elements

A decryption device comprising:

a common key generating unit that when constants const(μ) that satisfy SE=τμεSET const(λ)·share(λ) (λεET) exist, generates a common key
K
′
=
e
0
⁡
(
C
′
⁡
(
0
)
,
D
*
⁡
(
0
)
)
·
∏
μ
∈
SET
⋀
LAB
⁡
(
μ
)
=
v
⁡
(
μ
)
->
⁢
e
μ
⁡
(
C
′
⁡
(
μ
)
,
D
*
⁡
(
μ
)
)
const
⁡
(
μ
)
·
∏
μ
∈
SET
⋀
LAB
⁡
(
μ
)
=
⫬
v
⁡
(
μ
)
->
⁢
e
μ
⁡
(
C
′
⁡
(
μ
)
,
D
*
⁡
(
μ
)
)
const
⁡
(
μ
)
/
(
v
⁡
(
μ
)
->
·
w
⁡
(
μ
)
->
)
by using first key information D*(0), second key information D*(λ) and input ciphertexts C′(0) and C′(λ);
a first decryption unit that decrypts an input ciphertext c′(Ψ+1) by using the common key K′ to generate a decrypted value r′;
a function calculating unit that generates Smax function values HS(r′, C2′), where S=1, . . . , Smax and Smax≧1, each of the function values HS(r′, C2′) being obtained by inputting a pair of the decrypted value r′ and an input ciphertext C2′ into each of collision-resistant functions HS;
and
a determination unit that rejects decryption if the ciphertexts C′(0) and C′(λ) do not match ciphertexts C″(0)=υ″·b1(0)+Σι=2Iυι″(0)·bι(0) and C″(λ)=υ″·Σι=1n(λ)wι(λ)·bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι″(λ)·bι(λ);
wherein the values of at least some of υ″, υ2″(0), . . . , υI″(0), υn(λ)+1″(λ), . . . , υn(λ)+ζ(λ)″(λ) correspond to at least some of the function values HS(r′, C2′);
and
Ψ is an integer greater than or equal to 1, φ is an integer greater than or equal to 0 and less than or equal to Ψ, ζ(φ) is an integer greater than or equal to 0, λ is an integer greater than or equal to 1 and less than or equal to Ψ, n(φ) is an integer greater than or equal to 1, I is a constant greater than or equal to 2 and less than or equal to n(0)+ζ(0), eφ is a nondegenerate bilinear map that outputs one element of a cyclic group GT in response to input of n(φ)+ζ(φ) elements γβ of a cyclic group G1 and n(φ)+ζ(φ) elements γβ* of a cyclic group G2, β=1, . . . , n(φ)+ζ(φ), i is an integer greater than or equal to 1 and less than or equal to n(φ)+ζ(φ), bi(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ)+ζ(φ) elements of the cyclic group G1, bi*(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ)+ζ(φ) elements of the cyclic group G2, δ(i, j) is a Kronecker delta function, eφ(bi(φ), bj*(φ))=gTτ·τ′·δ(i, j) is satisfied for a generator gT of the cyclic group GT and constants τ and τ′, v(λ)→=(v1(λ), . . . , vn(λ)(λ)) are n(λ)-dimensional vector each consisting of v1(λ), . . . , vn(λ)(λ), w(λ)→=(w1(λ), . . . , wn(λ)(λ)) are n(λ)-dimensional vectors each consisting of w1(λ), . . . , wn(λ)(λ), labels LAB(λ) where λ=1, . . . , Ψ, are pieces of information each representing the n(λ)-dimensional vector v(λ)→ or the negation v(λ)→ of the n(λ)-dimensional vector v(λ)→, LAB(λ)=v(λ)→ means that LAB(λ) represents the n(λ)-dimensional vector v(λ)→, LAB(λ)=v(λ)→ means that LAB(λ) represents the negation v(λ)→ of the n(λ)-dimensional vector v(λ)→, share(λ), where λ=1, . . . , Ψ, represents share information obtained by secret-sharing of secret information SE, the first key information is D*(0)=−SE·b1*(0)+Σι=2Icoefι(0)·bι*(0), the second key information for λ that satisfies LAB(λ)=v(λ)→ is D*(λ)=(share(λ)+coef(λ)·v1(λ))·b1*(λ)+Σι=2n(λ)coef(λ)·vι(λ)·bι*(λ)+Σι=(λ)+1n(λ)+ζ(λ)coefι(λ)·bι* (λ), the second information for λ that satisfies LAB(λ)=v(λ)→ is D*(λ)=share(λ)·Σι=1n(λ)vι(λ)·bι*(λ)+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)·b*(λ), and SET represents a set of λ that satisfies {LAB(λ)=v(λ)→}^{v(λ)→=0} or {LAB(λ)=v(λ)→}{v(λ)→·w(λ)→≠0}.

128 more elements

An encryption method comprising the steps of:

generating a random number r by a random number generating unit;
generating a ciphertext C2 by a first encryption unit, the ciphertext C2 being an exclusive OR of a binary sequence dependent on the random number r and a plaintext M, the plaintext M being a binary sequence;
generating Smax function values HS(r, C2) by a function calculating unit, where S=1, . . . , Smax and Smax≧1, each of the function values HS(r, C2) being obtained by inputting a pair of the random number r and the ciphertext C2 in each of collision-resistant functions HS;
generating a common key K by a common key generating unit, the common key being an element of a cyclic group GT;
encrypting, by a second encryption unit, the random number r by common key encryption using the common key K to generate ciphertext C(Ψ+1);
and
generating a ciphertext C1 including C(0)=υ·b1(0)+Σι=2Iυι(0)·bι(0), C(λ)=υ·Σι=1n(λ)wι(λ)·bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)·bι(λ) and the ciphertext C(Ψ+1) by a third encryption unit;
wherein Ψ is an integer greater than or equal to 1, φ is an integer greater than or equal to 0 and less than or equal to Ψ, n(φ) is an integer greater than or equal to 1, ζ(φ) is an integer greater than or equal to 0, λ is an integer greater than or equal to 1 and less than or equal to Ψ, I is a constant greater than or equal to 2 and less than or equal to n(0)+ζ(0), eφ is a nondegenerate bilinear map that outputs one element of the cyclic group GT in response to input of n(φ)+ζ(φ) elements γβ of a cyclic group G1 and n(φ)+ζ(φ) elements γβ* of a cyclic group G2, β=1, . . . , n(φ)+ζ(φ), i is an integer greater than or equal to 1 and less than or equal to n(φ)+ζ(φ), bi are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ)+ζ(φ) elements of the cyclic group G1, bi*(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ)+ζ(φ) elements of the cyclic group G2, δ(i, j) is a Kronecker delta function, eφ(bi(φ), bj*(φ))=gTτ·τ′·δ(i, j) is satisfied for a generator gT of the cyclic group GT and constants τ and τ′, w(λ)→=(w1(λ), . . . , wn(λ)(λ)) are n(λ)-dimensional vectors each consisting of w1(λ), . . . , wn(λ)(λ), and at least some of the values of υ, υι(0) (ι=2, . . . , I), υι(λ) (ι=n(λ)+1, . . . , n(λ)+ζ(λ) correspond to at least some of the function values HS(r, C2).

5 more elements

A decryption method comprising the steps of:

when constants const(μ) that satisfy SE=ΣμεSETconst(μ)·share(μ), (μεSET) exist, generating a common key
K
′
=
e
0
⁡
(
C
′
⁡
(
0
)
,
D
*
⁡
(
0
)
)
·
∏
μ
∈
SET
⋀
LAB
⁡
(
μ
)
=
v
⁡
(
μ
)
->
⁢
e
μ
⁡
(
C
′
⁡
(
μ
)
,
D
*
⁡
(
μ
)
)
const
⁡
(
μ
)
·
∏
μ
∈
SET
⋀
LAB
⁡
(
μ
)
=
⫬
v
⁡
(
μ
)
->
⁢
e
μ
⁡
(
C
′
⁡
(
μ
)
,
D
*
⁡
(
μ
)
)
const
⁡
(
μ
)
/
(
v
⁡
(
μ
)
->
·
w
⁡
(
μ
)
->
)
,
by a common key generating unit, using first key information D*(0), second key information D*(λ) and input ciphertexts C′(0) and C′(λ);
decrypting an input ciphertext C′(Ψ+1), by a first decryption unit, using the common key K′ to generate a decrypted value r′;
generating Smax function values HS(r′, C2′) where S=1, . . . , Smax and Smax≧1, by a function calculating unit, each of the function values HS(r′, C2′) being obtained by inputting a pair of the decrypted value r′ and an input ciphertext C2′ into each of collision-resistant function HS;
and
rejecting decryption by a determination unit if the ciphertexts C′(0) and C′(λ) do not match ciphertexts C″(0)=υ″·b1(0)+Σι=2Iυι″(0)·bι(0) and C″(λ)=υ″·Σι=1n(λ)wι(λ)·bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι″(λ)·bι(λ);
wherein the values of at least some of υ″, υ2″(0), . . . , υI″(0), υn(λ)+1″(λ), . . . , υn(λ)+ζ(λ)″(λ) correspond to at least some of the function values HS(r′, C2′);
and
Ψ is an integer greater than or equal to 1, φ is an integer greater than or equal to 0 and less than or equal to Ψ, ζ(φ) is an integer greater than or equal to 0, λ is an integer greater than or equal to 1 and less than or equal to Ψ, n(φ) is an integer greater than or equal to 1, I is a constant greater than or equal to 2 and less than or equal to n(0)+ζ(0), eφ is the nondegenerate bilinear map that outputs one element of a cyclic group GT in response to input of n(φ)+ζ(φ) elements γβ of a cyclic group G1 and n(φ)+ζ(φ) elements γβ* of a cyclic group G2, β=1, . . . , n(φ)+ζ(φ), i is an integer greater than or equal to 1 and less than or equal to n(φ)+ζ(φ), bi(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ)+ζ(φ) elements of the cyclic group G1, bi*(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ)+ζ(φ) elements of the cyclic group G2, δ(i, j) is a Kronecker delta function, eφ(bi(φ), bj*(φ))=gTτ·τ′·δ(i, j) is satisfied for a generator gT of the cyclic group GT and constants τ and τ′, v(λ)→=(v1(λ), . . . , vn(λ)(λ)) are n(λ)-dimensional vectors each consisting of v1(λ), . . . , vn(λ)(λ), w(λ)→=(w1(λ), . . . , wn(λ)(λ)) are n(λ)-dimensional vectors each consisting of w2(λ), . . . , wn(λ)(λ), labels LAB(λ) (λ=1, . . . , Ψ) are pieces of information each representing the n(λ)-dimensional vector v(λ)→ or the negation v(λ)→ of the n(λ)-dimensional vector v(λ)→, LAB(λ)=v(λ)→ means that LAB(λ) represents the n(λ)-dimensional vector v(λ)→, LAB(λ)=v(λ)→ means that LAB(λ) represents the negation v(λ)→ of the n(λ)-dimensional vector, share(λ), where λ=1, . . . , Ψ, represents share information obtained by secret-sharing of secret information SE, the first key information is D*(0)=−SE·b1*(0)+Σι=2I coefι(0)·bι*(0), the second key information for λ that satisfies LAB(λ)=v(λ)→ is D*(λ)=(share(λ)+coef(λ)·v1(λ))·b1*(λ)+Σι=2n(λ)coef(λ)·vι(λ)·bι*(λ)+Σι=n(λ)+1n(λ)+ζ(λ) coefι(λ)·bι*(λ), the second information for λ that satisfies LAB(λ)=v(λ)→ is D*(λ)=share(λ)·Σι=1n(λ)vι(λ)·bι*(λ)+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)·b*(λ), and SET represents a set of λ that satisfies {LAB(λ)=v(λ)→}{v(λ)→·w(λ)→=0} or {LAB(λ)=v(λ)→}{v(λ)→·w(λ)→≠0}.

129 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/703,381Filed 22 Jul 2011
Priority: JP 2010-16640623 Jul 2010
Published: US 2013/0083921 A14 Apr 2013
Granted: 25 Nov 2014
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

H04L 9/0836
Involving conference or group key: using tree structure or hierarchical structure
H04L 9/0847
Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or…:…
H04L 9/085
Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for…:…
H04L 9/3073
Involving algebraic varieties, e.g. elliptic or hyper-elliptic curves: involving pairings, e.g. identity based encryption [IBE], bilinear mappings…

Family

US 2013/0083921 A1Pre-grant publication · published 4 Apr 2013
US 8,897,442 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

patentgrep

Loading patent…

Abstract

An encryption device comprising:

a random number generating unit that generates a random number r;
a first encryption unit that generates a ciphertext C2, the ciphertext C2 being an exclusive OR of a binary sequence dependent on the random number r and a plaintext M, the plaintext M being a binary sequence;
a function calculating unit that generates Smax function values HS(r, C2), where S=1, . . . , Smax and Smax≧1, each of the function values HS(r, C2) being obtained by inputting a pair of the random number r and the ciphertext C2 in each of collision-resistant functions HS;
a common key generating unit that generates a common key K, the common key being an element of a cyclic group GT;
a second encryption unit that encrypts the random number r by common key encryption using the common key K to generate ciphertext C(Ψ+1);
and
a third encryption unit that generates a ciphertext C1 including C(0)=υ·b1(0)+Σι=2Iυι(0)·bι(0), C(λ)=υ·Σκ=1n(λ)wι(λ)·bι(λ)+Σι=n(λ)+1n(λ)+ι(λ)υ(λ)·bι(λ) and the ciphertext C(Ψ+1);
wherein Ψ is an integer greater than or equal to 1, φ is an integer greater than or equal to 0 and less than or equal to Ψ, n(φ) is an integer greater than or equal to 1, ζ(φ) is an integer greater than or equal to 0, λ is an integer greater than or equal to 1 and less than or equal to Ψ, I is a constant greater than or equal to 2 and less than or equal to n(0)+ζ(0), eφ is a nondegenerate bilinear map that outputs one element of the cyclic group GT in response to input of n(φ)+ζ(φ) elements γβ (β=1, . . . , n(φ)+ζ(φ) of a cyclic group G1 and n(φ)+ζ(φ) elements γβ*(β=1, . . . , n(φ)+ζ(φ)) of a cyclic group G2, i is an integer greater than or equal to 1 and less than or equal to n(φ)+ζ(φ), bi(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ)+ζ(φ) elements of the cyclic group G1, bi*(φ) are n(φ)+ζ(φ)-dimensional basis vectors each consisting of n(φ)+ζ(φ) elements of the cyclic group G2, δ(i, j) is a Kronecker delta function, eφ(bi(φ), bj*(φ))=gTτ·τ′·δ(i,j) is satisfied for a generator gT of the cyclic group GT and constants τ and τ′, w(λ)→=(w1(λ), . . . , wn(λ)(λ)) are n(λ)-dimensional vectors each consisting of w1(λ), . . . , wn(λ)(λ), and at least some of the values of υ, υ2(0), . . . , υI(0), υn(λ)+1(λ), . . . , υn(λ)+ζ(λ)(λ) correspond to at least some of the function values HS(r, C2).

5 more elements

Facts

Application

13/703,381Filed 22 Jul 2011

Priority

JP 2010-16640623 Jul 2010

Published

US 2013/0083921 A14 Apr 2013

Granted

25 Nov 2014

Term ends

Not estimatedThe source records don’t support an estimate.

Classification5 codes

H04L 9/0836
Involving conference or group key: using tree structure or hierarchical structure
H04L 9/0847
Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or…:…
H04L 9/085
Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for…:…
H04L 9/3073
Involving algebraic varieties, e.g. elliptic or hyper-elliptic curves: involving pairings, e.g. identity based encryption [IBE], bilinear mappings…