METHOD AND APPARATUS FOR GENERATING SHORTER SIGNATURES ALMOST TIGHTLY RELATED TO STANDARD ASSUMPTIONS
The present principles use the message to be signed as a label—of the private key augmented with a QA-NIZK proof that the encrypted value is a persistent hidden secret. One-time homomorphic signatures are used to generate the signature and the public key. The private key for the one-time homomorphic signatures is included in the private key for signing the message, and the public key for the one-time homomorphic signatures is included in the public key for verifying the signature. Consequently, we obtain DLIN-based signatures comprised of only 6 group elements. The security proof uses a sequence of hybrid games, gradually moves to a game where all signatures contain an encryption of a random value while the QA-NIZK proofs are simulated proofs for false statements.
1 . A method for signing a message, comprising:
accessing a first private key and a first set of public key elements, the first set of public key elements including a first set of vectors based on elements of a bilinear group and a second set of vectors based on one-time linearly homomorphic signatures, wherein at least one of the first set of vectors and the second set of vectors is generated using a probabilistic process;
determining a first portion of a signature responsive to the message, the first private key and the first set of vectors;
determining a second portion of the signature responsive to the first private key and the one-time linearly homomorphic signatures;
forming the signature responsive to the first portion and the second portion; and
transmitting the signature through a communication channel.
2 . The method of claim 1 , wherein the signature under a K-linear assumption consists of 2K+2 elements from the bilinear group, and wherein each of the first portion and the second portion of the signature corresponds to K+1 elements from the bilinear group.
3 . The method of claim 2 wherein K=2.
4 . The method of claim 1 , wherein the determining a first portion of a signature comprising:
determining a first element of the first portion of the signature responsive to the message, the first private key and the first set of vectors; and
determining each of remaining elements of the first portion of the signature responsive to a respective generator included in the first set of public key elements.
5 . The method of claim 4 , wherein the first set of vectors are {right arrow over (V)} j =(V j,1,0 , V j,1,1 , . . . , V j,L,0 , V j,L,1 )ε 2L , wherein is the bilinear group and V j,l,0 , V j,l,1 for j=1 to K and l=1 to L.
6 . The method of claim 5 , wherein the first element of the first portion of the signature is determined as σ 0 =g Σ j=1 ω j K ·Π j=1 K H({right arrow over (V)} j ,M) r j , wherein M=M[1] . . . M[L]ε{0,1} L represents the message being signed, ω 1 , . . . , ω K are included in the first private key, r j are random integers, and H({right arrow over (V)} j ,M)=Π l=1 L V j,l,M[l] for each jε{1, . . . , K}.
7 . The method of claim 5 , wherein the one-time linearly homomorphic signatures are generated responsive to matrix
(
M
i
,
j
)
i
,
j
=
(
V
→
1
T
1
d
f
1
,
2
L
…
1
2
L
×
2
L
1
…
…
1
⋮
⋱
⋱
⋮
⋱
⋮
V
→
K
T
1
2
L
×
2
L
…
1
d
f
K
,
2
L
1
⋮
g
1
1
L
×
2
L
1
2
L
×
2
L
u
1
1
…
1
g
1
1
L
×
2
L
1
2
L
×
2
L
1
u
2
⋮
g
1
1
L
×
2
L
1
2
L
×
2
L
⋮
…
⋱
⋮
g
1
1
L
×
2
L
…
1
2
L
×
2
L
1
…
u
K
)
wherein Id f j ,2L =f j I 2L ε 2L×2L and I 2L is an identity matrix in 2L×2L , p is the order of group , and generators g, f 1 , . . . , f K , u 1 , . . . , u K .
8 . The method of claim 7 , wherein the one-time linearly homomorphic signatures {(Z i , R i,1 , . . . , R i,K )} i=1 K(2L+1) are determined on rows {right arrow over (M)} i =(M i,1 , . . . , M i,4L+2 )ε K(2L+1)+1 of M=(M i,j ) i,j , using a private key sk hsps =({χ i , {γ j,i } j=1 K } i=1 K(2L+1)+1) , wherein χ i , γ j,i .
9 . The method of claim 8 , wherein the first private key includes the private key sk hsps for the one-time linearly homomorphic signatures.
10 . A method for verifying a signature of a message, comprising:
accessing the message, the signature, and a first set of public key elements, the first set of public key elements including a first set of vectors based on elements of a bilinear group and a second set of vectors based on one-time linearly homomorphic signatures, wherein at least one of the first set of vectors and the second set of vectors is generated using a probabilistic process,
wherein a first portion of the signature is determined responsive to the message, the first private key and the first set of vectors, and
wherein a second portion of the signature is determined responsive to the first private key and the one-time linearly homomorphic signatures; and
verifying whether the signature is valid responsive to the first set of public key elements and the message.
11 . The method of claim 10 , wherein the signature under a K-linear assumption consists of 2K+2 elements from the bilinear group, and wherein each of the first portion and the second portion of the signature corresponds to K+1 elements from the bilinear group.
12 . The method of claim 11 wherein K=2.
13 . An apparatus for signing a message, comprising:
an interface configured to access a first private key and a first set of public key elements, the first set of public key elements including a first set of vectors based on elements of a bilinear group and a second set of vectors based on one-time linearly homomorphic signatures, wherein at least one of the first set of vectors and the second set of vectors is generated using a probabilistic process; and
a processor configured to
determine a first portion of a signature responsive to the message, the first private key and the first set of vectors,
determine a second portion of the signature responsive to the first private key and the one-time linearly homomorphic signatures, and
form the signature responsive to the first portion and the second portion.
14 . The apparatus of claim 13 , wherein the signature under a K-linear assumption consists of 2K+2 elements from the bilinear group, and wherein each of the first portion and the second portion of the signature corresponds to K+1 elements from the bilinear group.
15 . The apparatus of claim 14 wherein K=2.
16 . The apparatus of claim 13 , wherein the processor is configured to:
determine a first element of the first portion of the signature responsive to the message, the first private key and the first set of vectors; and
determine each of remaining elements of the first portion of the signature responsive to a respective generator included in the first set of public key elements.
17 . The apparatus of claim 16 , wherein the first set of vectors are {right arrow over (V)} j =(V j,1,0 , V j,1,1 , . . . , V j,L,0 , V j,L,1 )ε 2L , wherein is the bilinear group and V j,l,0 , V j,l,1 for j=1 to K and l=1 to L.
18 . The apparatus of claim 17 , wherein the first element of the first portion of the signature is determined as σ 0 =g Σ j=1 ω j K ·Π j=1 K H({right arrow over (V)} j ,M) r j , wherein M=M[1] . . . M[L]ε{0,1} L represents the message being signed, ω 1 , . . . , ω K are included in the first private key, r j are random integers, and H({right arrow over (V)} j ,M)=Π l=1 L V j,l,M[l] for each jε{1, . . . , K}.
19 . The apparatus of claim 17 , wherein the one-time linearly homomorphic signatures are generated responsive to matrix
(
M
i
,
j
)
i
,
j
=
(
V
→
1
T
Id
f
1
,
2
L
…
1
2
L
×
2
L
1
…
…
1
⋮
⋱
⋱
⋮
⋱
⋮
V
→
K
T
1
2
L
×
2
L
…
Id
f
K
,
2
L
1
⋮
g
1
1
×
2
L
1
1
×
2
L
u
1
1
…
1
g
1
1
×
2
L
1
1
×
2
L
1
u
2
⋮
g
1
1
×
2
L
1
1
×
2
L
⋮
…
⋱
⋮
g
1
1
×
2
L
…
1
1
×
2
L
1
…
u
K
)
wherein Id f j ,2L =f j I 2L ε 2L×2L and I 2L is an identity matrix in 2L×2L , p is the order of group , and generators g, f 1 , . . . , f K , u 1 , . . . , u K .
20 . The apparatus of claim 19 , wherein the one-time linearly homomorphic signatures {(Z i , R i,1 , . . . , R i,K )} i=1 K(2L+1) are determined on rows {right arrow over (M)} i =M i,1 , . . . , M i,4L+2 )ε K(2L+1)+1 of M=(M i,j ) i,j , using a private key sk hsps =({χ i , {γ j,i } j=1 K } i=1 K(2L+1)+1) , wherein χ i , γ j,i p .
21 . The apparatus of claim 20 , wherein the first private key includes the private key sk hsps for the one-time linearly homomorphic signatures.
22 . An apparatus for verifying a signature of a message, comprising:
an interface configured to access the message, the signature, and a first set of public key elements, the first set of public key elements including a first set of vectors based on elements of a bilinear group and a second set of vectors based on one-time linearly homomorphic signatures, wherein at least one of the first set of vectors and the second set of vectors is generated using a probabilistic process,
wherein a first portion of the signature is determined responsive to the message, the first private key and the first set of vectors, and
wherein a second portion of the signature is determined responsive to the first private key and the one-time linearly homomorphic signatures; and
a processor configured to verify whether the signature is valid responsive to the first set of public key elements and the message.
23 . The apparatus of claim 22 , wherein the signature under a K-linear assumption consists of 2K+2 elements from the bilinear group, and wherein each of the first portion and the second portion of the signature corresponds to K+1 elements from the bilinear group.
24 . The apparatus of claim 22 wherein K=2.