IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020

141

PAPER

Special Section on Cryptography and Information Security

A Constant-Size Signature Scheme with a Tighter Reduction fromthe CDH Assumption∗
Kaisei KAJITA†a) , Nonmember, Kazuto OGAWA† , and Eiichiro FUJISAKI†† , Members

SUMMARY
We present a constant-size signature scheme under the
CDH assumption. It has a tighter security reduction than any otherconstant-size signature scheme with a security reduction to solving someintractable search problems. Hofheinz, Jager, and Knapp (PKC 2012) presented a constant-size signature scheme under the CDH assumption with areduction loss of O(q), where q is the number of signing queries. They also
proved that the reduction loss of O(q) is optimal in a black-box security
proof. To the best of our knowledge, no constant-size signature scheme has
been proposed with a tighter reduction (to the hardness of a search problem)
than that proposed by Hofheinz et al., even if it is not re-randomizable. We
remark that our scheme is not re-randomizable. We achieve the reduction
loss of O(q/d), where d is the number of group elements in a public key.
key words: digital signature, CDH assumption, trapdoor commitment,tight security reduction

1.

Introduction

1.1

Background

Digital signatures are one of the most elemental cryptographic primitives that guarantee authenticity of electronic
documents. When using a digital signature scheme, eachsigner has a pair of secret (signing) and public (verification)
keys. A signer signs documents by using one secret key,
and authenticity of a signature is publicly verifiable with the
public key. Digital signatures are widely used in the realworld. They are used in transport layer security (TLS), ecommerce, and Cryptocurrency among others.
The performance of cryptographic primitives can beevaluated by reduction loss to a certain difficult problem.
The security reduction is a particular way of a mathematical proof to ensure that a cryptographic primitive is secure. It shows that breaking the primitive is at least as difficult as solving the difficult problem. Reduction loss is the
gap in difficulty between breaking the primitive and solving the difficult problem. When there is approximately no
security-reduction loss, it is called tightly secure. More
Manuscript received March 18, 2019.
Manuscript revised June 18, 2019.
†
The authors are with the Science and Technology ResearchLaboratories, Japan Broadcasting Corporation, Tokyo, 157-8310
Japan.
††
The author is with the School of Information Science, Japan
Advanced Institute of Science and Technology (JAIST), Nomi-shi,
923-1292 Japan.
∗
This paper is the revised version of the paper that appearedin the 20th Information Security Conference (ISC2017), Ho Chi
Minh, Vietnam, Nov. 2017 [23]. This revised one has fixed many
mistakes in the previous one.
a) E-mail: kajita.k-bu@nhk.or.jp
DOI: 10.1587/transfun.2019CIP0015

strictly speaking, if a t-time adversary attacks the schemewith success probability ε, then a t0 -time algorithm can beconstructed to solve some difficult problem with successprobability ε0 . A cryptographic scheme is tightly secure if
ε0 ≈ ε/θ and t0 ≈ t. The constant θ measures the security
loss of the reduction of the primitives from the underlying
assumption and does not depend on other parameters under the adversary’s control (e.g., the number of queries, thescheme’s security parameter, and the adversary’s own success probability). In this paper, we focus on the securityreduction of signature schemes. It is important to reduce thereduction loss of a cryptosystem, which enables the choosing of as small a security parameter as needed without compromising security as much as possible; hence, enablingsmall security parameters for cryptosystems, i.e., signaturesand verification keys, and fast computations of signature
generation and verification, etc.
1.2

Related Work

There are many provably secure digital signature schemes[3], [4], [6], [8], [10], [14], [19], [22], [27]. The security ofsignature schemes was first discussed in the random oracle
model. Those signature schemes have heuristic security arguments [16]. Then digital signatures in the standard model
were developed [3]. Those schemes use two major problems for security proofs; decisional problems, e.g., the decisional Diffie-Hellman (DDH) problem, and search problem, e.g., the Computational Diffie-Hellman (CDH) problem. Generically, search problems are more difficult thandecisional problems, namely, solving the CDH problem ismore difficult than solving the DDH problem. If a signature consists of a small constant number of group elements,
the size of the signature is called constant-size. We discuss
constant-size signature schemes in the standard model fromnow on. The digital signatures that can be reduced to decisional problems have been extensively studied, and their
reduction loss O(l) to the DDH problem has been achieved,
where l is the bit length of a message [12], [18]. On theother hand, there are a few digital signatures secure under
the difficulty of CDH problems. We show them in Table 1.
Waters proposed a signature scheme [27] that is efficient andprovably secure under the CDH assumption in the standard
model. Some digital signatures under the CDH assumption
based on the Waters signature scheme have been developed[6], [7], [20], [22], [26]. However, their reduction loss to the
CDH problem is not so tight. The reductions loss of the Wa-

Copyright c 2020 The Institute of Electronics, Information and Communication Engineers

IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020

142
Table 1 Constant-size signature schemes under the CDH assumption in the standard model: κ is the
security parameter, τG is the size of the group element, τF p is the size of the exponent, q is the maximum
bound of the signing queries, c and d are constants satisfying c > 1, and ε is the success probability of
the adversary. ω(1) means any strictly increasing function in κ; e.g., log log κ.
SchemeVerification key size

Signature size

Reduction loss

Wat05 [27]HK08 [21]HJK12 [20]O(κ)τG
O(κ)τG
O(κ)τG

2τG
2τG
2τG

O(κq)
√
O( κq)
O(q) !
c c

BHJ+13 [6], BHJ+15 [7]O(logc κ)τG

2τG + τF p

Seo14 [26]Ours

ω(1)τG
O(κ)τG2τG + τF p
2τG + τF pters signature scheme is O(8(l + 1)q), where q is the numberof adversarial signature queries. The technique called programmable hash functions (PHFs) √[21] improves the tightness of the security reduction to O( lq). As far as we know,
the tightest security reduction to the CDH problem fromknown constant-size signature schemes is O(q), presented
by Hofheinz et al. [20]. They proposed a re-randomizablesignature scheme (shown in Sect. 2.1) by applying an errorcorrecting code to the Waters signature scheme. They also
proved that the reduction loss of O(q) is optimal if signatureschemes are re-randomizable.
Böhl et al. presented a new paradigm for the construction of signature schemes in standard computational
assumptions [6], [7]. They present an efficient mildly secure scheme based on the CDH assumption in pairingfriendly groups. Moreover, they apply trapdoor commitment and some modification and achieve EUF-CMA security of the signature scheme if the CDH assumption holds.
In their construction, pseudorandom functions, which affect the security-reduction loss, are used to achieve security
against a non-adaptive attack. Their security proof uses a“confined guessing” technique, which is a new proof technique by using tags. After that, Seo proposed the signaturescheme [26] with a short verification key and the same security reduction as the Waters signatures by improving Böhl
et al.’s signature scheme.
In spite of many of these splendid previous studies,constant-size signatures with a tight reduction to the CDH
problem in the standard model remain undeveloped. If conditions are relaxed, there are some signature schemes witha tight reduction. For example, the tree-based signaturescheme [8] achieves a tight reduction to search problems
but its signature size is not constant. Besides, there exists
a non constant-size signature scheme with a tight reduction
from the strong RSA assumption [11]. Unless a signaturescheme is in the standard model, there exists a constant-size
signature scheme with a tight reduction in the random oracle
model [24]. So it is open to give a constant-size signaturescheme under the difficulty of a search problem with a tight
reduction.
1.3

Our Contributions

In general, the fully secure EUF-CMA signature scheme
is constructed from some mildly secure schemes. Böhl

O 2

2+

d qd
c

+c

εd

O(κq)
O( dq )

et al. construct the EUF-CMA secure scheme from theschemes that are secure in mild security models by using
generic transformation. In this paper, in order to achieve
the EUF-CMA security, we use an existential unforgeability
against the extended random message attack (EUF-XRMA
security) presented by Abe et al. [1] as mild security. The
exact definition of the EUF-XRMA security will be described in Sect. 2.2. Intuitively, in the EUF-XRMA security, messages are generated uniformly by a message generator with auxiliary information. Our signature scheme isconstructed as follows: first, we construct an EUF-XRMA
secure signature scheme, and then, we convert it to an EUFCMA signature scheme by using a method given in [1]. Interestingly, the underlying signature scheme in [1] is slightly
more secure than EUF-XRMA. Indeed, it is secure even if
messages are not randomly chosen. In our scheme, however,the underlying scheme is just EUF-XRMA secure–it is notsecure unless messages are randomly chosen. To the best of
our knowledge, our proposal is the first scheme that essentially needs the conversion of [1] from EUF-XRMA security
to EUF-CMA security.
We present a signature scheme with a tighter security reduction than known constant-size (i.e., the signature
contains a constant number of group elements) signatureschemes under the CDH assumption. We modify the Böhl etal.’s signature scheme and reduce its security to the CDH assumption more efficiently. Their scheme has compact public keys at the price of a loose security-reduction loss. We
find out that there is a trade-off between public key size
and a security-reduction loss in their scheme. Moreover,by removing a pseudorandom generator and using a generictransformation from the scheme with extended randommessage-attack security to that with chosen-message-attack
security shown in [1], we can obtain a signature scheme withthe reduction loss of O(q/d), where d is the number of groupelements in a verification key.
2.

Preliminaries$

For n ∈ N, [n] denotes the set {1, . . . , n}. a ←− A denotes sampling a uniformly and randomly from a finite set
A. negl(κ) denotes an unspecified function f (κ) such thatf (κ) = κ−ω(1) , saying that such a function is negligible inκ. For a probabilistic polynomial-time (PPT) algorithm A,
we write y ← A(x) to denote the experiment of running A

KAJITA et al.: A CONSTANT-SIZE SIGNATURE SCHEME WITH A TIGHTER REDUCTION FROM THE CDH ASSUMPTION

143

for a given x, selecting an inner coin r uniformly from anappropriate domain, and assigning the result of this experiment to the variable y, i.e., y = A(x; r). Let X = {Xκ }κ∈N
and Y = {Yκ }κ∈N be probability ensembles such that eachXκ and Yκ are random variables ranging over {0, 1}κ . The
statisticaldistance between Xκ and Yκ is Dist(Xκ , Yκ ) ,1 P|
κs∈{0,1} Pr[Xκ = s] − Pr[Yκ = s]|. We write X ≡ Y if
2
Dist(Xκ , Yκ ) = 0.
2.1

Security Class of Digital Signatures

EUF-CMA: A digital signature scheme SIG is said to
be existentially unforgeable against adaptively chosenmessage attack (EUF-CMA) [17], if for any PTT A,
AdvEUF-CMA(κ) := Pr[ExptEUF-CMA(κ) = 1] = negl(κ), where
SIG,A
SIG,A
EUF-CMA
ExptSIG,A (κ) is defined in Fig. 1.
EUF-XRMA: Let MsgGen is a PPT algorithm, called
the message generator, which takes as input security parameter 1κ and outputs m ∈ Mκ and auxiliary information
w. A digital signature scheme SIG is said to be existentially unforgeable against extended random-message attack(EUF-XRMA) [1] with respect to MsgGen, if for any PPT(κ) := Pr[ExptEUF-XRMA(κ) = 1] = negl(κ),
A, AdvEUF-XRMA
SIG,A
SIG,A
EUF-XRMA
where ExptSIG,A(κ) is defined in Fig. 2.
2.3

If m∗ ∈ Qm , then return 0
Return Vrfy(vk, m∗ , σ∗ )Fig. 1 The EUF-CMA experiment. Sign sk (·) is a signing oracle withrespect to sk. It takes as input m and returns σ ← Sign sk (m), and then,records m to Qm which is initially an empty list.

ExptEUF-XRMA
(κ):
SIG,A
(vk, sk) ← KGen(1κ );Digital Signatures

Digital Signatures: A digital signature scheme is given
by a triple, SIG = (KGen, Sign, Vrfy), of PPT Turing machines, where for every (sufficiently large) κ ∈ N, KGen,
the key-generation algorithm, takes as input security parameter 1κ and outputs a pair of verification and signing keys,(vk, sk). Here let Mκ be message space. The signing algorithm Sign takes as input (vk, sk) and a message m ∈ Mκand produces a signature σ. The verification algorithm Vrfy
takes as input vk, m, and σ, and outputs a verification result bit. For correctness, it is required that for any (vk, sk)
pair generated with KGen(1κ ) and for any m ∈ Mκ , it holds
Vrfy(vk, m, σ) = 1, where σ = Sign(sk, m).
Re-Randomizable Signatures: Intuitively, re-randomizablesignatures [20] have a property that, given vk, m, and validσ, one can efficiently generate a new signature σ0 that is
distributed properly over the set of all possible signatures
on m under vk. Formally, let SIG = (KGen, Sign, Vrfy)
be a signature scheme. Let us denote the set of σ form that can be verified correctly under vk by Σ(vk, m) ={σ | Vrfy(vk, m, σ) = 1}. We say that SIG is re-randomizable
if there is a PPT algorithm Rerand such that for all (vk, m, σ)with Vrfy(vk, m, σ) = 1, the output of Rerand(vk, m, σ) is
distributed over Σ(vk, m) identically to that of Sign(sk, m).
2.2

ExptEUF-CMA
(κ):
SIG,A
(vk, sk) ← KGen(1κ ); (m∗ , σ∗ ) ← ASign sk (·) (vk)

Cryptographic Tools

Trapdoor Commitments: We define a trapdoor commitment scheme, following [13].
Let TCOM =(KGentc , Comtc , TComtc , TColtc ) be a tuple of the four algorithms. KGentc is a PPT algorithm that takes as input

For ∀i ∈ [q],(mi , wi ) ← MsgGen(1κ ); σi ← Sign sk (mi )q(m∗ , σ∗ ) ← A(vk, {mi , σi , wi }i=1 )If m∗ ∈ Qm , then return 0
Return Vrfy(vk, m∗ , σ∗ )Fig. 2The EUF-XRMA experiment. Qm = {m1 , . . . , mq }.

security parameter 1κ and outputs a pair of public and trapdoor keys (pk, tk) ← KGentc (1κ ). Comtc is a PPT algorithm that takes as input pk and m, selects a randomr ← COINcom , where r ∈ Z/pZ, and outputs a commitment ψ = Comtcpk (m; r). TComtc is a PPT algorithm thatκ
takes as input 1κ and tk, and outputs (ψ, χ) ← TComtc
tk (1 ),
tc
where χ is auxiliary information. TCol is a deterministic
polynomial-time algorithm that takes as input tk, ψ, χ andm̂, and outputs r̂ ∈ Z/pZ such that ψ = Comtcpk (m̂; r̂).
We say that TCOM is a trapdoor commitment scheme
if the following conditions holds, perfect hiding, computational binding, and trapdoor property.
Perfect Hiding. For any pk generated with KGentc (1κ ), andany m, m0 ∈ Mκ , the following random variables are identical.
no(ψ, m, r) | ψ = Comtcpk (m; r); r ← COINcomno≡ (ψ0 , m0 , r0 ) | ψ0 = Comtcpk (m0 ; r0 ); r0 ← COINcom ,Computational Binding. For any PPT A, (pk, tk) ← KGentc (1κ );



εbind := Pr (m1 , m2 , r1 , r2 ) ← A(pk) :


tc
tc
Com pk (m1 ; r1 ) = Com pk (m2 ; r2 )∧(m1 , m2 )= negl(κ).
Trapdoor Property. For any pk generated with KGentc (1κ ),no(ψ, m, r) | ψ = Comtcpk (m; r); r ← COINcomnotcκ≡ (ψ, m, r) | (ψ, χ) ← TComtc
tk (1 ); r = TColtk (ψ, χ, m) .
Bilinear Groups: Let G be a bilinear group generator [9]that, on input of a security parameter κ, outputs a descriptionof bilinear groups (G, GT , e, p, g) such that G and GT are
cyclic groups of prime order p, g is a generator of G, and amap e : G × G → GT satisfies the following properties:• (Bilinear:) for any g, h ∈ G and any a, b ∈ Z/pZ,e(ga , hb ) = e(g, h)ab ,IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020

144

• (Non-degenerate:) e(g, g) has order p in GT , and• (Efficiently computable:) e(·, ·) is efficiently computable.
Computational Diffie-Hellman Assumption: Let G be abilinear group generator, that on input of a security parameter κ, outputs a cyclic group. We say that the CDH assumption holds if for any polynomial-time algorithm A thefollowing advantage is negligible function in κ:


$


cdh
(G,
G
,
e,
p,
g)
←
G(κ)
;
(α,
β)
←
−
Z/pZ
:
T


ε := Prα βαβA(G, p, g, g , g ) = g= negl(κ).
3.

bilinear group G in the proposed signature scheme.
We provide a useful lemma.
Lemma 1: Let T be a finite set. Let q = O(poly(κ)) ande·qd = O(κ). If #T > d+1,
Pr[(d + 1)-foldideal ] := Pr[∃i1 , . . . , id+1 ∈ [q] s.t ti1 = · · · = tid+1 ]is exponentially small in κ, where t1 , . . . , tq are independently and uniformly chosen from T and e denotes the baseof the natural logarithm.
Proof. Let n = #T .
Pr[∃i1 , . . . , id+1 ∈ [q] s.t ti1 = · · · = tid+1 ]!d1= q Cd+1n!dq · (q − 1) · · · (q − d) 1=
(d + 1)!
n
!
d
1
qd+1
· · · (∗)≤
(d + 1)! n e d+1 1 !dqd+1
≤ √· · · (∗∗)
n2π(d + 1) d + 1
!d
e·q
e·q
= √
.
2π(d + 1) · (d + 1) n(d + 1)

Mildly Secure Signature Scheme and Message Generator

We propose a signature scheme SIG0 and a message generator MsgGen. We later prove that SIG0 is EUF-XRMA
secure with respect to MsgGen under the CDH assumption. SIG0 is similar to the non-adaptively secure signaturescheme built in the optimized CDH-based signature schemein [7]. The main differences from theirs are that d = O(κ)
instead of constant, and that tags, t(1) , . . . , t(l) are made in adifferent manner.
We describe SIG0 in Fig. 3. Its correctness is describedin Appendix A. We let l = ω(log2 κ) and d = O(κ). Let us
define T j = {0, 1} j for 1 ≤ j ≤ l. For a, b ∈ Z/pZ, we definet( j) = ((am + b) mod p) mod 2 j

Inequality (∗∗) holds by Stirling’s approximation
 x x√√  x x
2πx
≤ x! ≤ e x
.
e
e

(1)

for 1 ≤ j ≤ l, where m ∈ Z/pZ is a message to be signed.
We note that to sign a single message m, SIG0 generates ltags, t(1) , . . . , t(l) , from m.
We now define MsgGen used in the later theorems.
Let p = 2 (mod 3) and E : y2 = x3 + 1. We knowthat E/F p is a super-singular elliptic curve defined over F pof order #E/F p = p + 1. Now we additionally assume
that p = `q0 − 1 where q0 (> 3) is a prime. We can assume that ` = 6. Define G0 as a cyclic sub-group in E/F pof order q. Since G0 is cyclic of prime order q0 , it is easy
to construct a trapdoor commitment scheme TCOM on G0 .
Let ψ = (x, y) ∈ F p × F p be an affine encoding of an element in G0 . Then, the map ρ : G0 ,→ F p , defined byρ(ψ) = y, is injective. We now define (m, w) ← MsgGenκas the algorithm that runs (ψ, χ) ← TComtc
tk (1 ) and outputs (m, w) := (ρ(ψ), χ). We note that it is not clear thatelements of ρ(ψ) is uniformly distributed in [0, p − 1]. To
prove Theorem 2, tags t( j) should be distributed uniformly
in T j . Therefore, we use the universal hashing technique
to distribute t( j) = H(ρ(ψ)) mod 2 j almost uniformly in T j ,which is the reason why we add a, b ∈ Z/pZ into vk. We
remark that although we explicitly provide a candidate of
G0 , one can use any cyclic group G0 if (1) the DL problem on G0 is believed to be hard, and (2) there is an efficiently computable injective map from G0 to Z/pZ such thatlog(p) − log(#G0 ) = const, where p denotes the order of the

eq
e·q
e·q
Now, we set n > d+1
then n(d+1)< 1, and √2π(d+1)·(d+1)
ispolynomial in κ. Hence, Pr[∃i1 , . . . , id+1 ∈ [q] s.t ti1 = · · · =tid+1 ] is exponentially small in κ.
The lemma above with constant d is known as a generalized birthday bound lemma, which often appears in theliterature, including [6], [26]. In our case, d is not constant, which leads to somehow different consequence from[6], [26]. For constant d, the probability Pr[(d + 1)-fold] =d+1
O( qnd ), because (d + 1)! is still constant. For d = O(κ),
however, (d + 1)! cannot be ignored. By using Stirling’s approximation with suitable parameter selection, we have theresult mentioned above.

3.1

EUF-XRMA Security

Theorem 2: Let MsgGen be a message generator mentioned above. Then SIG0 is EUF-XRMA secure with respect to MsgGen under the CDH assumption on G. Here,the reduction loss is O( dq ), where q is the number of queriesof the adversary.
Proof. Suppose that there exists a PPT A against SIG0 and
MsgGen. We show that we can construct an algorithm B
that uses A as an internal sub-algorithm to solve the CDH
problem.

KAJITA et al.: A CONSTANT-SIZE SIGNATURE SCHEME WITH A TIGHTER REDUCTION FROM THE CDH ASSUMPTION

145
KGen(1κ )Sign(sk, m)(G, GT , e, p, g) ← G(κ)

r←
− Z/pZQiu(m) = di=0 um
i$a, b, α ←− Z/pZ (H(x) := (ax + b) mod p)$(g, h, {ui }di=0 , {z j }lj=1 ) ←−Gdαvk = (H, g, g , h, {ui }i=0 , {z j }lj=1 )sk = (α, vk)
return (vk, sk)

Fig. 3

Vrfy(vk, m, σ)$

For j := 1 to l dot( j) = H(m) mod 2 jQ( j)z(m) = lj=1 ztj
α
σ0 = u(m) (z(m)h)r
σ1 = gr
return σ = (σ0 , σ1 )For j := 1 to l dot( j) = H(m) mod 2 j
If e(σ0 , g), e(u(m), gα )e(z(m)h, σ1 )return 0
else
return 1

SIG0 : the EUF-XRMA secure signature scheme under the CDH assumption.

Setup.

r(X) :=

B receives a CDH challenge (g, gα , gβ ) ∈ G3 . B thenruns MsgGen to receive {(mi , wi )}qi=1 . Let us define M :={mi }qi=1 and T j := {0, 1} j for j ∈ [l]. B picks up ran-

d
X
k=0

γ(X) := xh +∗M0 := {m ∈ M | t˜ = H(m)mod 2 j }.

If #M0 ≥ d +1, B aborts; otherwise, sets the verification key
parameters as follows.
Let d0 = #M0 . By definition, d0 ≤ d. B makes apolynomial f (X) of degree d0 such that f (m) = 0 for all m ∈M0 . If d0 = 0, define f (X) ≡ 1. By polynomial expansion,
we havef (X) =d0X

µk X kk=0

for some coefficients, µ0 , . . . , µd0 ∈ Z/pZ.
B then chooses randomly and independently r0 , . . . , rd ,$x1 , . . . , xl , xh ←− Z/pZ. B sets h as
h = (gβ )−t˜g xh .
For 0 ≤ k ≤ d, B sets uk as
uk = (gβ )µk grk ,where µk = 0 for d0 < k. B sets z1 , . . . , zl as
z j = g x j for 1 ≤ j ≤ l, j , j∗ ,z j∗ = gβ g x j∗$

B finally chooses a, b ←− Z/pZ and sets up vk =(a, b, g, gα , h, {uk }dk=0 , {z j }lj=1 ). For the sake of convenience,
we define r(X), γ(X) as follows;lX

xi t( j) .

j=1$

domly a, b ←− Z/pZ and define H : Z/pZ → Z/pZ as
H(m) = (am + b) mod p. B sets j∗ to be the smallest j∗e·q)c + 1. We note that #T j∗ is polynosuch that j∗ > blog2 ( d+1
mial in κ. Since #T j∗ > b(e · q/(d + 1)c + 1, The probability
that event (d + 1)-fold happens is exponentially small if q
tags are independently and uniformly chosen from T j∗ , due
to Lemma 1.
$
B randomly chooses t˜ ←− T j∗ . To jump into the conclusion, B can solve the CDH problem when A outputs forged∗pair (m∗ , σ∗ ) such that t˜ = H(m∗ ) mod 2 j . Let

rk X k ,∗Let t := H(X) mod 2 j . Then, we haveu(X) =dY

ukX = (gβ ) f (X) gr(X) ,k=0
β t−t˜ γ(X)z(X)h = (g ) g

.

(2)
(3)

Hence, the signature on message m holds, for r ∈ Z/pZ,
α 
r

(4)
σ0 = (gβ ) f (m) gr(m) (gβ )t−t˜gγ(m) ,σ1 = gr .

(5)Here, note that f (X), r(X), γ(X) are all known polynomials
for B and kept for the signature simulation.
Signature simulation.
B creates q signatures σ1 , . . . , σq for q messages in M.
Let m ∈ M be a message to be signed. Set t :=∗H(m) mod 2 j . Note that t is the tag for message m in T j∗ .
Case 1 (t = t˜): By definition, f (m) = 0. Therefore, byEq. (4), it holds that
σ0 = (gα )r(m) (z(m)h)r ,σ1 = gr .
Therefore, it is obvious that B computes (σ0 , σ1 ) on m.
Case 2 (t , t˜): Then, it holds that f (m) , 0. Let r = −αt−f (m)t˜(mod p). By simple calculation and the equations, (4) and(5), it holds that

α 
r
σ0 = (gβ ) f (m) gr(m) ) (gβ )t−t˜gγ(m)r= (gαβ ) f (m) (gα )r(m) (gβ )t−t˜gγ(m)−α f (m)= (gαβ ) f (m) (gβ )(t−t˜)· t−t˜ (gα )r(m) gγ(m)r= (gα )r(m) gγ(m)r= (gα )r(m) (gα )− f (m)γ(m)t−t˜.

As above, B can compute σ0 . To make a signature with0
the proper distribution, B just sets r = −αt−f (m)t˜ + r (mod p),

IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020

146$

where r0 ←− Z/pZ. It is obvious that r is uniformly distributed over Z/pZ since r0 is uniformly chosen. B then sets
(σ0 , σ1 ) as
σ0 = (gα )r(m) (gα )ασ1 = (g )− f (m)t−t˜− f (m)γ(m)t−t˜0(z(m)h)r ,By the claim above, Pr[(d + 1)-foldreal ] = 2−O(κ) , sincePr[(d + 1)-foldideal ] = 2−O(κ) . We have now concluded theproof.
4.

EUF-CMA Full Security Scheme

r0

g .

In this section, we show the construction of a fully
EUF-CMA secure scheme from SIG0 by applying trapdoor
commitment TCOM.

B feeds (vk, {mi , σi , wi }qi=1 ) to A.
A’s stage.
Given (vk, {mi , σi , wi }qi=1 ) from B, A runs following its strategy. Consider the case that A successfully produces aforged signature σ∗ = (σ∗0 , σ∗1 ) on a fresh message m∗ < M.
Solving the CDH problem.
When A succeeds to forge (m∗ , σ∗ ), it holds that f (m∗ ) , 0∗
by construction. B then check the tag t∗ = H(m∗ ) mod 2 j .
If t∗ , t˜, then B aborts; otherwise, it outputs the solution of
the CDH problem gαβ as follows:1/ f (m∗ )σ∗0= gαβ .
∗)∗ γ(m∗ )
α
r(m
(g )
(σ1 )

4.1

Construction

Let SIG1 be a signature scheme constructed by applying
TCOM to SIG0 . We describe it in Fig. 4. The correctness
of SIG1 can be shown in the same way as SIG0 , so it isomitted here (See Appendix B).
Lemma 4: The signature scheme SIG1
randomizable.

is non-re-

Proof. Let vk = (H, g, gα , h, {ui }di=0 , {z j }lj=1 ) be a given vk,
and σ = ((σ0 , σ1 ), r) be a valid signature for message m,i.e., σ satisfiese(σ0 , g) = e (u(ψ), gα ) e (z(ψ)h, σ1 ) .

Security Analysis.
By construction, it is obvious that the simulated verification
key and signatures are properly distributed conditioned that(d+1)-fold doesn’t happen on chosen tag t˜ ∈ T j∗ , i.e., #M0 ≤∗d, where M0 := {m ∈ M | t˜ = H(m) mod 2 j }. Let us denoterealby (d+1)-fold the event that (d+1)-fold happens on sometag in T j∗ when t1( j) , . . . , tq( j) in T j∗ are chosen according to the
distribution of MsgGen. Then, the forging probability of A
is at least  euf-xrma − Pr[(d + 1)-foldreal ].
B can solve the CDH problem as above when t∗ =∗t˜ where t∗ := H(m∗ ) mod 2 j . Note that the information about t˜ is perfectly hidden from the adversary’s view.
Hence, the probability that B can solve the CDH problem is1
euf-xrma− Pr[(d + 1)-foldreal ]). Since #T1j∗ = O( dq ), we#T j∗ (haveq
 euf-xrma = O( ) ·  cdh + Pr[(d + 1)-foldreal ].
dFinally, we prove that Pr[(d + 1)-foldtially small.

real] is exponen-(6)

The set of all σ satisfying (6) is therefore identical to the setΣ(vk, m) = {σ|Vrfy(vk, m, σ, r) = 1}


α
s
s



 σ0 = (u(ψ)) (z(ψ)h) , σ1 = g ; 

= 
.

$


com
 s←

− Z/pZ, r ← COIN
Consider a PPT algorithm Rerand taking as input vk, σ,$

and message m. We assume that Rerand samples s0 ←−Z/pZ and returns σ0 = (σ00 , σ01 ) distributed uniformly overΣ(vk, m). However, since Rerand cannot generate ψ =Comtcpk (x; r); r ← COINcom , there is no Rerand that returns the new signature σ0 distributed uniformly over theset of all possible signatures for m. Hence, SIG1 is non-rerandomizable.

4.2

Security Analysis

Claim 3: Pr[(d + 1)-foldreal ] = Pr[(d + 1)-foldideal ] + 2−O(κ) ,where T = T j∗ .

Theorem 5: If TCOM = (KGentc , Comtc , TComtc , TColtc )is a trapdoor commitment scheme described in section 3 and
SIG0 be EUF-XRMA secure, with respect to MsgGen then
SIG1 is EUF-CMA secure.

Proof of Claim 3. Let m be a message outputted by MsgGen
defined in Sec. 3. By construction, m can be seen as an element in Z/pZ. Although m is not distributed uniformly over
Z/pZ, we know that H∞ (m) = κ − 1, since p = 2q0 − 1.
Therefore, due to the left-over hash lemma, the distribution∗∗of t( j ) = H(m) mod 2 j derived by MsgGen is statisticallyclose to the uniform distribution over T j∗ , whose distance is−(H∞ (m)−ω(log κ))
2bounded by 21 2
= 2−O(κ) . Considering independent q messages of MsgGen, the distance should be multipled by q = O(poly(κ)), but still 2−O(κ) .
Proof. As we can regard commitments as input in SIG0
-xrma
instead of messages, let a PPT Beufas the adversary
SIG0
against EUF-XRMA security with TCOM of SIG0 , and a
PPT Bbind be a adversary against computational binding for-cma
TCOM. Now we show that if a PPT Aeuf
who can break
SIG1
-xrma
EUF-CMA security of SIG1 exists, then Beufor Bbind
SIG0
exists.
We consider two cases with respect to the outputsof a EUF-XRMA with TCOM game; when commitments{ψ1 , . . . , ψq } queried as messages do not contain challenge

KAJITA et al.: A CONSTANT-SIZE SIGNATURE SCHEME WITH A TIGHTER REDUCTION FROM THE CDH ASSUMPTION

147
KGen(1κ )Sign(sk, m)(G, GT , p, e, g) ← G(κ).

r ← COINcom , s ←− Z/pZψ = Comtcpk (m; r)

ψ = Comtcpk (m; r)Q
ψiu(ψ) = di=0 ui

For i := 1 to l do

For j := 1 to l dot( j) = H(ψ) mod 2 jQ( j)z(ψ) = lj=1 ztj
α
σ0 = u(ψ) (z(ψ)h) s
σ1 = g s
return (σ = (σ0 , σ1 ), r)

If e(σ0 , g), e(u(ψ), gα )e(z(ψ)h, σ1 )return 0
else
return 1$α←− Z/pZ$a, b ←− Z/pZ (H(x) := (ax + b) mod p)$(h, {ui }di=0 , {z j }lj=1 ) ←−G(tk, pk) ← KGentc (1κ )vk = (H, g, gα , h, {ui }di=0 , {z j }lj=1 , pk)
sk = (α, vk)
return (vk, sk)
Fig. 4

Vrfy(vk, m, σ, r)$t( j) = H(ψ) mod 2 j

SIG1 : EUF-CMA-secure signature scheme with TCOM under the CDH assumption.

-xrma
commitment ψ∗ , Beuf
which breaks EUF-XRMA secuSIG0
rity with TCOM exists (Case 1) and when {ψ1 , . . . , ψq } contains ψ∗ , Bbind which breaks computational binding exists(Case 2).
Here, we write the verification key and signing key of-cma
SIG0 as (vk0 , sk0 ). From the view of Aeuf
, it is statistiSIG1
euf-xrmaand Bbind .
cally indistinguishable that views of BSIG0

Setup
We consider TComtc
tk as MsgGen of EUF-XRMA, thencommitments are generated with auxiliary information such
euf-xrmakthat (ψi , ri ) ← TComtc
receives the verificatk (1 ). BSIG0
tion key vk0 , for 1 ≤ i ≤ q, commitment ψi , signature σiof SIG0 , and auxiliary information wi = (pk, tk, ri ), where
pk is the public key and tk is the trapdoor key for TCOM.
The commitment ψi satisfies that ψi = Comtcpk (xi ; ri ) for-xrma
xi ∈ Mκ and σi is the signature of SIG0 for ψi . Beuf
SIG0
euf-cmasets vk = (vk0 , pk) and send vk to ASIG1 .
Signing
-cma
Aeuf
SIG1
euf-cmaASIG1

makes q signing queries. For 1 ≤ i ≤ q,
-xrma
-xrma
gives a message mi to Beuf
. Then Beuf
SIG0
SIG0
t
computes ri = TColtc
t k c(ψi , r̄i , mi ), where ri satisfies ψi =tc t
Com p k c(mi ; ri ). According to the trapdoor property ofTCOM, it is statistically indistinguishable whether ψi wasreceived from TComtc
tk as MsgGen in Setup or generated-xrma
from mi by Comtcpk . Beufthen returns (σi , ri ) for ψi corSIG0-xrma
responding to mi . Here, the signatures which Beuf
firstly
SIG0
received as input are regarded as that of SIG1 since messages can be just replaced by commitments.
-cma
Forgery of Aeuf
SIG1
-xrma
Beuf
receives a forgery (m∗ , σ∗ , r∗ ) of SIG1 from
SIG0
-cma
-xrma
Aeuf
, where m∗ < {m1 , . . . , mq }. Beufthen computes
SIG1
SIG0
tc
∗
∗ ∗
commitment ψ = Com pk (m ; r ).
Case 1: ψ∗ < {ψ1 , . . . , ψq }. In this case that ψ∗ <euf-xrma{ψ1 , . . . , ψq }, BSIG
outputs (ψ∗ , σ∗ ). This means the ad0
versary succeeds in breaking EUF-XRMA with TCOM security of SIG0 . This goes against the fact that any adversary
who breaks the EUF-XRMA security of SIG0 does not exists in Theorem 2.
Case 2: ψ∗ ∈ {ψ1 , . . . , ψq }. In this case that ψ∗ ∈{ψ1 , . . . , ψq }, Bbind outputs (m∗ , r∗ , mi , ri ) such that (ψ∗ =-xrma
ψi ) ∩ (m∗ , mi ) for 1 ≤ i ≤ q. This means Beuf
succeeds
SIG0
in breaking computational binding for trapdoor commitment
as Bbind .
Analysis-xrma, εbind be an
Let εeuf-xrma be an advantage of Beuf
SIG0
bind
euf-cmaadvantage of B , and εbe an advantage of
euf-xrma-cma
breaksEUF-XRMA
security when ψ∗ <
.
B
Aeuf
SIG0
SIG1
{ψ1 , . . . , ψq } or Bbind breaks computational binding for trapdoor commitments when ψ∗ ∈ {ψ1 , . . . , ψq }. Therefore
-cma
-xrma
εeuf
is bounded by sum of εeuf
and εbind . Hence,
SIG1
SIG0

εeuf-cma ≤ εbind + εeuf-xrma .
5.

Discussion

The reduction loss of Böhl et al.’s signature scheme is
εCDH ≥

1  euf-cmaε− εPRF − Pr[(d + 1)-foldreal ] ,T j∗where T j∗ is the size of tag sets. In our scheme, #T j∗ =O( dq ) since its tag space is T j∗ := b(d + 1)/e · qc + 1. The
advantage εPRF regarding PRF is 1/2O(κ) , which is the gap
between the case in which tags are chosen uniformly andthat in which tags are generated as t( j) = m mod 2 j . In
Böhl et al.’s scheme, the key lemma is as follows:
Pr[(d + 1)-foldreal ]= Pr[∃i1 , . . . , id+1 ∈ [q] | ti1 = · · · = tid+1 ]
qd+1
≤ d .
n
Since they assumed that the size of d is constant, the evaluation was sufficient. However, we assume d = O(κ); thus, weevaluate the probability more strictly. Lemma 1 shows thatthe probability is exponentially small. Moreover, we caneliminate the reduction loss of PRF thanks to EUF-XRMA
security where messages are generated of by a message generator MsgGen instead of the PRF in the experiment.
According to Theorems 2 and 5,

IEICE TRANS. FUNDAMENTALS, VOL.E103–A, NO.1 JANUARY 2020

148

εCDH
!
1
1
euf-xrmareal≥ε− Pr[(d + 1)-fold ] − O(κ)
T j∗
2
!
d
≥O
· εeuf-xrmaq!
d  euf-cma≥O· ε− εbindq
Hence,
εeuf-cma ≤ Oqd· εCDH + εbind .

Computational binding is reduced to the discrete logarithm problem. The whole security-reduction loss to the
CDH problem, a search problem, is O(q/d).
The tag set of Böhl et al.’s scheme is chosen from ajsparse tag set whose size is 2bc c , where c is constant. Our tag
set size is 2 j , which is appropriate for choosing a small T j∗e·qsuch that T j∗ > d+1. On the other hand, d is constant in Böhl
et al. ’s scheme, while d = O(κ) in our scheme. The size ofthe vk increases according to the size of d. Hence, although
the vk size of our scheme is larger than that of Böhl et al.’sscheme, our scheme achieves a constant-size signature witha tighter reduction.
6.

Conclusion

The optimal security-reduction loss to the CDH problem
from a constant-size signature scheme is O(q) if signatureschemes are re-randomizable. We proposed a constant-size
non-re-randomizable signature scheme that is secure under
the CDH assumption with tighter security-reduction than
any constant-size signature schemes. Particularly, its security reduction, O(q/d), is the tightest thus far.
References[1] M. Abe, M. Chase, B. David, M. Kohlweiss, R. Nishimaki, and
M. Ohkubo, “Constant-size structure-preserving signatures: Genericconstructions and simple assumptions,” J. Cryptol., vol.29, no.4,
pp.833–878, 2016.
[2] D. Boneh and M. Franklin, “Identity-based encryption from Weilparing,” Annual International Cryptology Conference, pp.213–229,
2001.
[3] D. Boneh, and X. Boyen, “Efficient selective-ID secure identitybased encryption without random oracles,” International Conference on the Theory and Applications of Cryptographic Techniques,pp.223–238, 2004.
[4] X. Boyen, “Lattice mixing and vanishing trapdoors: A frameworkfor fully secure short signatures and more,” Public Key Cryptography, LNCS, vol.6056, pp.499–517, 2010.
[5] E. Boyle, S. Goldwasser, and I. Ivan, “Functional signatures andpseudorandom functions,” International Workshop on Public Key
Cryptography, pp.501–519, 2014.
[6] F. Böhl, D. Hofheinz, T. Jager, J. Koch, J.H. Seo, and C. Striecks,“Practical signatures from standard assumptions,” Annual International Conference on the Theory and Applications of Cryptographic
Techniques, pp.461–485, 2013.
[7] F. Böhl, D. Hofheinz, T. Jager, J. Koch, and C. Striecks, “Confined
guessing: New signatures from standard assumptions,” J. Cryptol.,

vol.28, no.1, pp.176–208, 2015.
[8] O. Blazy, S.A. Kakvi, E. Kiltz, and J. Pan, “Tightly-secure signatures from chameleon hash functions,” Public Key Cryptography,
pp.256–279, 2015.
[9] D. Boneh, I. Mironov, and V. Shoup, “A secure signature schemefrom bilinear maps,” CT-RSA, LNCS, vol.2612, pp.98–110, 2003.
[10] B. Chevallier-Mames, “An efficient CDH-based signature schemewith a tight security reduction,” Annual International Cryptology
Conference, pp.511–526, 2005.
[11] B. Chevallier-Mames and M. Joye, “A practical and tightly secure signature scheme without hash function,” CT-RSA, LNCS,
vol.4377, pp.339–356, 2007.
[12] J. Chen, and H. Wee, “Fully, (almost) tightly secure IBE and dual
system groups,” Advances in Cryptology CRYPTO 2013, pp.435–
460, 2013.
[13] I. Damgård, “Efficient concurrent zero-knowledge in the auxiliary
string model,” International Conference on the Theory and Applications of Cryptographic Techniques, pp.418–430, 2000.
[14] L. Ducas and D. Micciancio, “Improved short lattice signatures inthe standard model,” International Cryptology Conference, pp.335–
352, 2014.
[15] O. Goldreich, “Foundation of cryptography (in two volumes: Basic
tools and basic applications),” Electronic Colloquium on Computational Complexity, 2001.
[16] E.J. Goh, and S. Jarecki, “A signature scheme as secure as the DiffieHellman problem,” International Conference on the Theory and Applications of Cryptographic Techniques, pp.401–415, 2003.
[17] S. Goldwasser, S. Micali, and R. Rivest, “A digital signature scheme
secure against adaptive chosen-message attacks,” SIAM J. Comput.,
vol.17, no.2, pp.281–308, 1988.
[18] D. Hofheinz, “Algebraic partitioning: Fully compact and (almost)tightly secure cryptography,” Theory of Cryptography Conference,
pp.251–281, 2016.
[19] D. Hofheinz and T. Jager, “Tightly secure signatures and public-key
encryption,” International Cryptology Conference, LNCS, vol.7417
pp.590–607, 2012.
[20] D. Hofheinz, T. Jager, and E. Knapp, “Waters signatures with optimal security reduction,” International Workshop on Public Key
Cryptography, pp.66–83, 2012.
[21] D. Hofheinz and E. Kiltz, “Programmable hash functions and theirapplications,” J. Cryptol., vol.25, no.3, pp.484–527, 2012.
[22] S. Hohenberger and B. Waters, “Realizing hash-and-sign signatures
under standard assumptions,” Annual International Conference on
the Theory and Applications of Cryptographic Techniques, pp.333–
350, 2009.
[23] K. Kajita, K. Ogawa, and E. Fujisaki, “A constant-size signaturescheme with tighter reduction from CDH assumption,” International
Conference on Information Security, pp.137–154, 2017.
[24] J. Katz and N. Wang, “Efficiency improvements for signatureschemes with tight security reductions,” Proc. 10th ACM conference
on Computer and communications security, pp.155–164, 2003.
[25] S. Schäge, “Tight proofs for signature schemes without random oracles,” International Conference on Theory and Applications of Cryptographic Techniques, LNCS, vol.6632, pp.189–206, 2011.
[26] J.H. Seo, “Short signatures from Diffie-Hellman, revisited: Sublinear public key, CMA security, and tighter reduction,” IACR Cryptology ePrint Archive: 138, 2014.
[27] B. Waters, “Efficient identity-based encryption without random oracles,” Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp.114–127, 2005.

Appendix A:

The Correctness of SIG0

The correctness of SIG0 can be proved as follows.
Proof. We show Vrfy(vk, m, σ) = 1 for all m ∈ Mκ andKAJITA et al.: A CONSTANT-SIZE SIGNATURE SCHEME WITH A TIGHTER REDUCTION FROM THE CDH ASSUMPTION

149

σ = Sign(sk, m).
In the algorithm Sign(sk, m), t = {t(1) , . . . , t(l) } is generated, andσ = (σ0 , σ1 )σ0 = u(m)α (z(m)h)r
σ1 = g re(σ0 , g) = e (u(m)α (z(m)h)r , g)
= e (u(m)α , g) e ((z(m)h)r , g)
= e (u(m), gα ) e ((z(m)h), gr )= e (u(m), gα ) e ((z(m)h), σ1 ) .
Hence, Vrfy(vk, m, σ) always returns 1 for all m ∈ Mκ .
Appendix B:

The Correctness of SIG1

The correctness of SIG1 can be proved as follows.
Proof. We show Vrfy(vk, m, σ, r) = 1 for all m ∈ Mκ andσ = Sign(sk, m).
In both of the algorithms Sign(sk, m) and Vrfy(vk, m, σ, r),
ψ = Comtcpk (m; r) and t = {t(1) , . . . , t(l) }, where t( j) =ψ mod 2 j , are generated. Then,σ = (σ0 , σ1 )σ0 = u(ψ)α (z(ψ)h) s
σ1 = g se(σ0 , g) = e (u(ψ)α (z(ψ)h) s , g)
= e (u(ψ)α , g) e ((z(ψ)h) s , g)
= e (u(ψ), gα ) e (z(ψ)h, g s )= e (u(ψ), gα ) e (z(ψ)h, σ1 ) .
Hence, Vrfyt (vk, m, σ, r) always returns 1 for all m ∈ Mκ . 

Kaisei Kajita
received the B.S. degree from
University of Electro Communication in 2015
and M.S. degree from Tokyo Institure of Technology in 2017. He joined NHK (Japan Broadcasting Corporation) in 2017. He is currently a
research engineer of NHK Science & Technology Research Laboratories. His research interest include cryptography, information security,
Integrated Broadcast-Broadband (IBB) system.

Kazuto Ogawa
received the B.E. and Ph.D.
degrees from the University of Tokyo in 1987
and 2008, respectively. He joined NHK (Japan
Broadcasting Corporation) in 1987. He has
mainly engaged in research and development onvideo image processing systems and digital content rights management systems. He is currently
a research engineer of NHK Science & Technology Research Laboratories.

Eiichiro Fujisaki
received the B.S. and
Ph.D. degrees from Tokyo Institute of Technology in 1991 and 2005, respectively. He joined
Nippon Telegraph and Telephone Corporation(NTT) Laboratories in 1991. He mainly engaged in research on cryptography and information security. Since 2017, he has been a Professor in School of Information Science, Japan
Advanced Institute of Science and Technology(JAIST). His research interests include cryptography, network security, and computer-aided
proofs. He is a member of IEICE, IPSJ, and IACR.