論文 / 著書情報
Article / Book Information
題目(和文)

集約署名の研究

Title(English)

Studies on Aggregate Signature

著者(和文)

手塚真徹

Author(English)

Masayuki Tezuka

出典(和文)

学位:博士(理学),学位授与機関:東京工業大学,
報告番号:甲第11711号,
授与年月日:2022年3月26日,
学位の種別:課程博士,
審査員:田中 圭介,伊東 利哉,尾形 わかは,鹿島 亮,安永 憲司

Citation(English)

Degree:Doctor (Science),
Conferring organization: Tokyo Institute of Technology,
Report number:甲第11711号,
Conferred date:2022/3/26,
Degree Type:Course doctor,
Examiner:,,,,

学位種別(和文)

博士論文

Type(English)

Doctoral Thesis

Powered by T2R2 (Tokyo Institute Research Repository)

Studies on Aggregate Signature
Masayuki Tezuka
Supervisor: Keisuke Tanaka
Department of Mathematical and Computing Science
School of Computing
Tokyo Institute of Technology

February 1, 2022

Acknowledgements
First and foremost, I would express my great deal of gratitude to my supervisor Professor
Keisuke Tanaka for support and encouragement. I appreciate that he spent a lot of time forour discussion and gave us valuable advice. I am very honored to belong to his laboratory.
I would like to thank Prof. Toshiya Ito, Prof. Wakaha Ogata, Prof. Ryo Kashima, andProf. Kenji Yasunaga, undertaking the referee of my doctoral thesis. Based on their feedbacks,
we would be more than happy to improve my work.
I would also like to thank all members and related members of Tanaka Laboratory. Especially, I would thanks to Dr. Masahiro Ishii, Dr. Yuyu Wang, Dr. Kazumasa Shinagawa, Dr.
Cid Reyes Bustos, Keisuke Hara, Yusuke Yoshida, Xiangyu Su, Shinji Yoshino, Daiki Hiraga,
Kyohei Sudo, and Hiroki Yamamuro. I am happy to have a fruitful time in collaboration
studies with them.
At last, I would express my gratitude to my parents for their support. Also I would liketo thank my beloved dogs’ Pudding, Candy, and Karin.

1

Contents
1 Introduction

4

1.1

A Study on the Synchronized Aggregate Signature Scheme . . . . . . . . . . .

4

1.2

A Study on the T-out-of-N Redactable Signature Scheme . . . . . . . . . . . .

8

1.3Road Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

122 Preliminaries

14

2.1

Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.2

Bilinear Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.3

Computational Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.4

Digital Signature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.5

Random Oracle Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3 Synchronized Aggregate Signature

18

3.1

Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.2

Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

3.3

Modiﬁed Camenisch-Lysyanskaya Signature Scheme . . . . . . . . . . . . . . .

21

3.4

Synchronized Aggregate Signature Scheme by Lee et al. . . . . . . . . . . . . .

22

3.5

Conversion from MCL Signature to Aggregate Signature by Lee et al. . . . . .

24

3.6

New Security Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

4 T-out-of-N Redactable Signature

31

4.1

Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

4.2

Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

4.3

BGLS Aggregate Signature Scheme . . . . . . . . . . . . . . . . . . . . . . . .

38

4.4

Shamir’s Secret Sharing Scheme . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.5

Our Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

2

4.6

Security Proof for Unforgeability . . . . . . . . . . . . . . . . . . . . . . . . .

43

4.7

Security Proof for Transparency . . . . . . . . . . . . . . . . . . . . . . . . . .

56

5 Conclusion

57

3

Chapter 1
Introduction
This thesis consists of two studies which are related to aggregate signature. These studies
summarized as follows.

1.1

A Study on the Synchronized Aggregate Signature
SchemeAggregate Signature. Aggregate signature schemes originally introduced by Boneh, Gentry, Lynn, and Shacham [11] allow anyone to convert n individual signatures (σ1 , . . . , σn )produced by diﬀerent n signers on diﬀerent messages into the aggregate signature Σ whose
size is much smaller than a concatenation of the individual signatures. This feature leads signiﬁcant reductions of bandwidth and storage space in BGP (Border Gateway Protocol) routing[11, 40, 8], bundling software updates [1], sensor network data [1], authentication [47], andblockchain protocol [54, 29, 59]. After the introduction of aggregate signature schemes, various
aggregate signature schemes have been proposed: sequential aggregate signature schemes [41],identity-based aggregate signature schemes [23], synchronized aggregate signature schemes[23, 1], and fault-tolerant aggregate signature schemes [25].
Synchronized Aggregate Signature. Synchronized aggregate signature schemes are a
special type of aggregate signature schemes. The concept of the synchronized setting aggregate
signature scheme was introduced by Gentry and Ramzan [23]. Ahn, Green, and Hohenberger[1] revisited the Gentry-Ramzan model and formalized the synchronized aggregate signaturescheme. In this scheme, all of the signers have a synchronized time period t and each signer4can sign a message at most once for each period t. A set of signatures that are all generated
for the same period t can be aggregated into a short signature.
It is useful to adopt synchronized aggregate signature schemes to systems which havea natural reporting period, such as log or sensor data. As mentioned in [29], synchronized
aggregate signature schemes are also useful for blockchain protocols. For instance, we consider
a blockchain protocol that records several signed transactions in each new block creation. The
creation of an additional block is a natural synchronization event. These signed transactions
could use a synchronized aggregate signature scheme with a block number as a time period
number. This reduces the signature overhead from one per transaction to just one synchronizedsignature per block iteration.
Several provable secure synchronized aggregate signature schemes with bilinear groups havebeen proposed (see Fig. 1.1). Ahn, Green, and Hohenberger [1] constructed two synchronized
aggregate signature schemes based on the Hohenberger-Waters [28] short signature scheme.
One is constructed in the random oracle model and the other is constructed in the standard
model. The security of both schemes relies on the computational Diﬃe-Hellman (CDH) assumption. Lee, Lee, and Yung [38] proposed a synchronized aggregate signature scheme basedon the Camenisch-Lysyanskaya signature (CL) scheme [16]. This is the eﬃcient synchronized
aggregate signature scheme with bilinear groups in that the number of pairing operations in
the veriﬁcation of an aggregate signature and the number of group elements in an aggregate
signature is smaller than those of [23, 1]. The security of this scheme relies on the one-time
Lysyanskaya-Rivest-Sahai-Wolf (OT-LRSW) assumption [42] in the random oracle model. As
the provable secure synchronized aggregate signature schemes without bilinear groups, Hohenberger and Waters [29] proposed the synchronized aggregate signature scheme based on the
RSA assumption.
Camenisch-Lysyanskaya Signature Scheme. Camenisch and Lysyanskaya [16] proposed
the CL scheme which has a useful feature called randomizability. This property allows anyone
to randomize a valid signature σ to σ ′ where σ and σ ′ are valid signatures on the samemessage. The CL scheme is widely used to construct various schemes: anonymous credentials[16], anonymous attestation [5], divisible E-cash [17], batch veriﬁcation [15], group signatures[6], ring signatures [4], and aggregate signatures [55]. The security of the CL scheme relies on
the Lysyanskaya-Rivest-Sahai-Wolf (LRSW) assumption which is an interactive assumption.
An interactive assumption allows us to design an eﬃcient scheme, however, these are notpreferable.

5SchemeAssumption

Security

pp

vk

Agg

Agg Ver

size

size

size

(in Pairings)

GR [23]

CDH + ROM

EUF-CMA∗

O(1)

ID

3

3

AGH [1] §4

CDH

EUF-CMA in CK

O(k)

1

3

k+3

AGH [1] §A

CDH + ROM

EUF-CMA in CK

O(1)

1

3

4

LLY [38]

OT-LRSW + ROM

EUF-CMA in CK

O(1)

1

2

3

EUF-CMA in CK

O(1)

1

2

3

(interactive assumption)
LLY [38]

1-MSDH-2 + ROM(New proof)(static assumption)

In our work, we prove that the scheme LLY [38] satisﬁes the EUF-CMA security in the certiﬁed-key model
under the 1-MSDH-2 assumption in the random oracle model.

Figure 1.1: Summary of synchronized aggregate signature schemes with bilinear groups. In thecolumn of “Assumption”, “ROM” means the random oracle model. In the column of “Security”,“CK” means the certiﬁed-key model. “pp size”, “vk size”, “Agg size”, “Agg Ver” mean the numberof group elements in a public parameter pp, a veriﬁcation key vk, an aggregate signature, andthe number of pairing operations in aggregate signatures veriﬁcation respectively.
GR [23] is an identity-based scheme that has a veriﬁcation key size of “ID”.
AGH [1], k is a special security parameter.

The scheme

In the scheme

As mentioned in [1], k could be ﬁve in practice.

∗ Note that Gentry and Ramzan [23] only provided heuristic security arguments.

Modiﬁed Camenisch-Lysyanskaya Signature Scheme. Pointcheval and Sanders [50]proposed the Modiﬁed q-Strong Diﬃe-Hellman-2 (q-MSDH-2) assumption which is deﬁned ona type 1 bilinear group. This assumption is a q-type assumption [9] where the number of input elements depends on the number of adversarial queries. They proved that the q-MSDH-2
assumption holds in the generic bilinear group model [10] and the CL scheme satisﬁes the weakexistentially unforgeable under chosen message attacks (weak-EUF-CMA) security under the
q-MSDH-2 assumption. Moreover, they proposed the modiﬁed Camenisch-Lysyanskaya signature (MCL) scheme which has randomizability. Then, they showed that the MCL scheme
satisﬁes the existentially unforgeable under chosen message attacks (EUF-CMA) security under the q-MSDH-2 assumption. Their modiﬁcation from the CL scheme to the MCL scheme

6incurs a slight increase in the complexity.∗
Our Results. To our knowledge, the most eﬃcient synchronized aggregate signature schemewith bilinear groups is Lee et al.’s [38] scheme. However, the security of this scheme relies on
the interactive assumption (the OT-LRSW assumption). Even if interactive assumptions holdin the generic group model or bilinear group model, the concerns about these assumptions arise
in a cryptographic community. This fact causes a barrier to the use of this scheme. Also, it is
not desired that the security of the scheme depends on q-type assumptions. Because the size ofthese assumptions grows dynamically and this fact leads to ineﬃciency of the scheme. Hence,
it is desirable to prove the security of this scheme under the non-q-type (static) assumptions
or construct another eﬃcient synchronized aggregate signature scheme whose security does
not rely on interactive assumptions or q-type assumptions.
Security Proof under the Static Assumption. In this paper, we give a new security
proof for Lee et al.’s synchronized aggregate scheme under the static assumption in the random oracle model. More speciﬁcally, we convert from the MCL scheme to Lee et al.’s [38]synchronized aggregate signature scheme. Then, we reduce the security of Lee et al.’s scheme
to the one-time EUF-CMA (OT-EUF-CMA) security of the MCL scheme in the random oracle model. We refer the reader to Section 3.5 for details about these techniques. Since the
OT-EUF-CMA security of the MCL scheme is implied by the 1-MSDH-2 assumption, thesecurity of Lee et al.’s scheme can be proven under the 1-MSDH-2 assumption. We can regard
the 1-MSDH-2 assumption as the static assumption. Therefore, we can see that the securityof Lee et al.’s scheme relies on the static assumption. Notably, while the EUF-CMA securityof the MCL scheme is proved under the q-type assumption, the security of Lee et al.’s synchronized aggregate signature scheme can be proven under the static assumption in the random
oracle model.
In general, there is a trade-oﬀ that eﬃciency is reduced when we design a scheme based on
weaker computational assumptions. Surprisingly, we can change the assumptions underlying
the security of Lee et al.’s [38] scheme from the interactive assumption (OT-LRSW) to thestatic assumption (1-MSDH-2) with almost the same reduction loss. Speciﬁcally, the size of
veriﬁcation key vk, the size of aggregate signature Σ, and the number of pairing operations inan aggregate signature veriﬁcation do not increase at all.
∗

Their modiﬁcation from the CL scheme to the MCL scheme increases the number of group elements in asignature and an aggregate signature from 2 to 3.

7

Related Works Boneh et al. [11] proposed the ﬁrst full aggregate signature scheme whichallows any user to aggregate signatures of diﬀerent signers. Furthermore, this scheme allows us
to aggregate individual signatures as well as already aggregated signatures in any order. They
constructed a full aggregate signature scheme in the random oracle model. Hohenberger, Sahai,
and Waters [27] ﬁrstly constructed a full aggregate signature scheme in the standard model byusing multilinear maps. Hohenberger, Koppula, and Waters [26] constructed a full aggregate
signature scheme in the standard model by using the indistinguishability obfuscation.
Several variants of aggregate signature schemes have been proposed. One major variant isa sequential aggregate signature scheme which was ﬁrstly proposed by Lysyanskaya, Micali,
Reyzin, and Shacham [41]. In this scheme, an aggregate signature is constructed sequentially,
with each signer modifying the aggregate signature in turn. They constructed a sequential
aggregate signature scheme in the random oracle model by using families of trapdoor permutations. Lu, Rafail Ostrovsky, Sahai, Shacham, and Waters [40] ﬁrstly constructed thesequential aggregate signature scheme in the standard model based on the Waters signaturescheme.
Furthermore, Lee et al. [38] proposed a combined aggregate signature scheme. In thisscheme, a signer can use two modes of aggregation (sequential aggregation or synchronized
aggregation) dynamically. They constructed a combined aggregate signature scheme in the
random oracle model based on the CL scheme.

1.2

A Study on the T-out-of-N Redactable Signature
SchemeRedactable Signature. Recently, due to the development of IoT devices, the number ofelectronic data is steadily increasing. It is indispensable for future information society to makeuse of these data. When we use data, it is important to prove that the data has not been
modiﬁed in any way. A digital signature enables a veriﬁer to verify the authenticity of M bychecking that σ is a legitimate signature on M . However, in our real-world scenario, when
we use data, the conﬁdential information should be deleted from the original data. A digital
signature cannot verify the validity of a message with parts of the message removed.
A redactable signature scheme (RSS) is a useful cryptographic scheme for such a situation.
This scheme consists of a signer, a redactor, and a veriﬁer. A signer signs a message M with asecret key sk and generates a valid signature σ. A redactor who can become anyone removes

8

some parts of a signed message from M , generate a redacted message M ′ , and updates thecorresponding signature σ ′ without the secret key sk. A veriﬁer still veriﬁes the validity of thesignature σ ′ on message M ′ using vk.
An idea of a redactable signature scheme was introduced by Steinfeld, Bull, and Zheng [57]as a content extraction signature scheme (CES). This scheme allows generating an extracted
signature on selected portions of the signed original document while hiding removed parts ofportions. Johnson, Molnar, Song, and Wagner [35] proposed a redactable signature scheme(RSS) which is similar to a content extraction signature scheme.
Security of Redactable Signature. Security of a redactable signature scheme was argued
in many works. Brzuska, Busch, Dagdelen, Fischlin, Franz, Katzenbeisser, Manulis, Onete,
Peter, Poettering, and Schröder [13] formalized three security notions of a redactable signature
for tree-structured messages in the game-based deﬁnition.
• Unforgeability: Without the secret key sk it is hard to generate a valid signature σ ′ ona message M ′ except to redact a signed message (M, σ).
• Privacy: Except for a signer and redactors, it is hard to derive any information about
removed parts of the original message M from the redacted message M ′ .
• Transparency: It is hard to distinguish whether (M, σ) directly comes from the signer
or has been processed by a redactor.
Derler, Pöhls, Samelin, and Slamanig [21] gave a general framework of a redactable signaturescheme for arbitrary data structures and deﬁned its security.
Camenisch, Dubovitskaya, Haralambiev, and Kohlweiss [14] proposed unlinkable redactablesignature. This signature satisﬁes unforgeability and unlinkability which is a variant security
notion of privacy. They used an unlinkable redactable signature scheme to construct ananonymous credential scheme [18]. Later, Sanders [52] constructed an unlinkable redactablesignature scheme to obtain an eﬃcient anonymous credential scheme. Moreover, Sanders [53]constructed a revokable group signature scheme based on an unlinkable redactable signaturescheme.
Additional Functionalities. Following additional functionalities for a redactable signaturescheme were proposed.

9• Disclosure Control [46, 44, 45, 24, 32, 33, 30, 51, 43]: Miyazaki, Iwamura, Matsumoto,
Sasaki, Yoshiura, Tezuka, and Imai [46] proposed the disclosure control. The signer orintermediate redactors can control to prohibit further redactions for parts of the message.
• Identiﬁcation of a Redactor [31, 34]: Izu, Kanaya, Takenaka, and Yoshioka [31] proposed the redactable signature scheme called “Partial Information Assuring Technology
for Signature” (PIATS). PIATS allows a veriﬁer to identify the redactor of the signed
message.
• Accountability [49]: Pöhls and Samelin proposed an accountable redactable signaturescheme that allows deriving the accountable party of a signed message.
• Update and Marge [39, 48]: Lim, Lee, and Park [39] proposed the redactable signaturescheme where a signer can update signature by adding new parts of a message. Moreover,Pöhls and Samelin [48] proposed the updatable redactable signature scheme that can
update a signature and marge signatures derived from the same signer.
• Compactness [58]: Most redactable signature schemes, to remove parts of the signed
message, we need pieces of information for each part we want to remove. That is, if asigned message consists of l elements, the number of elements in an original signature is atleast linear in l. Tezuka and Tanaka [58] introduce compactness for redactable signatureschemes. Compactness requires that the size of an original signature and signature for a
subdocument (redacted message) are indipendent regardless of the number of elements
in messages.
Motivation. Consider the case where a citizen requests the signed secret document disclosure to the government. To disclose the secret signed document, the government must remove
sensitive data from it. A decision of deletion for conﬁdential information of a document isperformed by multiple oﬃcers in the government meeting.
One of the simple solutions is that the signer of the secret document gives the signing key
sk to the meeting chair. The chair takes a vote on removing sensitive information and removes
it from the secret document and signed it using sk. However, if the meeting chair is malicious,
it is risky for the secret document signer to give the meeting chair a signing key sk. Therefore,
the secret document signer wants to avoid giving a signing key sk to others.
If we try to adapt the original RSS on this situation, we suﬀer from the following problem.
RSS allows anyone to redact message parts and even removes the necessary information.

10Moreover, a malicious chair can redact message parts form the signed document regardless ofthe decision of the oﬃcers.
Our Contributions. We introduce the new notion of t-out-of-n redactable signature scheme
to overcome this problem. This scheme is composed of a signer, n redactors, a combiner, anda veriﬁer. The signer designates n redactors and a combiner, generates a key pair (vk, sk)
and redactor’s secret key {rk[i]}ni=1 and sends rk[i] to the redactor i. Then signer decides
parts of a message that redaction is allowed, signs the message, and sends its signature to n
redactor and a combiner. Each redactor i selects parts of the signed message that he or she
wants to remove, generates a piece of redaction information RIi , and sends it to the combiner.
The combiner collects all redaction information {RIi }ni=1 , extracts signed message parts which
at least t redactors want to remove using {RIi }ni=1 , generates the redactable signature. The
veriﬁer can verify the validities of signatures.
Now, we reconsider applying the t-out-of-n redactable signature scheme to the above redaction problem. Let the secret document signer be a signer of the t-out-of-n redactable signaturescheme, oﬃcers be redactors, and the meeting chair be a combiner. The secret document signer
does not have to give the signing key sk to the chair. Our t-out-of-n redactable signature only
allows the chair to redact parts of message which at least t oﬃcers wants to remove.
We consider the one-time redaction model which allows redacting signed message only one
time for each signature and gives the unforgeability, privacy, and transparency security of the tout-of-n redactable signature scheme in the one-time redaction model. Also, we give a concrete
construction of the t-out-of-n redactable signature scheme which satisﬁes the unforgeability,
privacy, and transparency security.
Our construction is based on the (t, n)-Shamir’s secret sharing scheme and the redactablesignature scheme proposed by Miyazaki, Hanaoka, and Imai [44] which use the aggregate
signature scheme proposed by Boneh, Gentry, Lynn, and Shacham [11] based on the BLS
signature scheme [12]. Our technical point is to adapt (t, n)-Shamir’s secret share scheme andcompute Lagrangian interpolation at the exponent part of the group element to reconstruct
information for the redaction. Security of our scheme is based on the computational co-CDH
assumption in the random oracle model.
Related Works. We present several signatures that allow editing signed message. Moredetails of the overview of related works, see [20, 7].
• Append-Only Signature [36]: Kiltz, Mityagin, Panjwani, and Raghavan [36] introduce

11the notion of the append-only signature scheme. In this scheme, we can only publicly
append message blocks to a signed message and update the signature correspondingly.
• Sanitizable Signature [2]: Ateniese, Chou, de Medeiros, and Tsudik [2] introduce thenotion of the sanitizable signature scheme. In this scheme, a signer selects a sanitizer
who can modify the signed message and generate a signature. The sanitizer can modify
some parts of message blocks of the signed document, but he or she cannot remove
message blocks. In the redactable signature, anyone can redact parts of the signed
message without the secret key. However, in the sanitizable signature scheme, eachsanitizer has the sanitizer’s secret key and the only the sanitizer designated by signer
can sanitize parts of the message using own sanitizer’s secret key.
• Protean Signature [37]: Krenn, Pöhls, Samelin, and Slamanig [37] introduce the notionof the protean signature scheme. This scheme allows removing and editing some partsof message blocks. They give the construction of the protean signature scheme from asanitizable signature scheme and a redactable signature scheme in the black box way.

1.3

Road Map

We describe the road map of this thesis. In Chapter 2, we introduce notations and review
bilinear groups, digital signature and the random oracle model (ROM). These primitives play
an important role in both our studies.
In Chapter 3, we study for the Camenish-Lysyanskaya signature based synchronized aggregate signature scheme. At ﬁrst, we review the deﬁnition of synchronized aggregate signaturescheme and its security. Second, we review the modiﬁed Camenisch-Lysyanskaya (MCL) signature scheme [50] whose security is used to prove the synchronized aggregate signature by
Lee et al. [38]. Then, we review the synchronized aggregate signature by Lee et al. [38]and provide the high-level idea of our new conversion technique from a MCL signature to asynchronized aggregate signature by Lee et al. Finally, we provide the improved security proof
for the aggregate signature by Lee et al. by using our conversion technique.
In Chapter 4, we study for the extension of redactable signature. At ﬁrst, we propose at-out-of-n redactable signature signature scheme and its security notions. Second, we review
the BGLS aggregate signature scheme and the Shamir’s secret sharing scheme. Then, based onthese primitives, we propose our t-out-of-n redactable signature scheme construction. Finally,
we prove security for our construction of t-out-of-n redactable signature scheme.

12

In Chapter 5, we summarize our result and describe some open problems.

13Chapter 2
Preliminaries
2.1

Notations

Let 1λ be the security parameter. A function f (λ) is negligible in λ if f (λ) tends to 0 fasterthan λ1c for every constant c > 0. PPT stands for probabilistic polynomial time. For an integer$n, [n] denotes the set {1, . . . , n}. For a ﬁnite set S, s ←− S denotes choosing an element s
from S uniformly at random. For a group G, we deﬁne G∗ := G\{1G }. For an algorithm A,y ← A(x) denotes that the algorithm A outputs y on input x.

2.2

Bilinear Groups

We introduce a bilinear group generator. Let G be a bilinear group generator that takes
as an input a security parameter 1λ and outputs the descriptions of multiplicative groups
G = (p, G1 , G2 , GT , e) where G1 , G2 , and GT are groups of prime order p and e is an eﬃcientcomputable, non-degenerating bilinear map e : G1 × G2 → GT .
1. Bilinear: for all u ∈ G1 , v ∈ G2 and a, b ∈ Zp , then e(ua , v b ) = e(u, v)ab .
2. Non-degenerate: for any g1 ∈ G∗ and g2 ∈ G∗2 , e(g1 , g2 ) ̸= 1GT .
Bilinear groups are classiﬁed into following three types [22]: Type 1 pairings: G1 = G2 ;Type 2 pairings: G1 ̸= G2 but there exists an eﬃcient homomorphism ψ : G2 → G1 ; Type3 pairings: G1 ̸= G2 and there are no eﬃciently computable homomorphisms between G1and G2 .

14

2.3

Computational Assumptions

Boneh, Gentry, Lynn, and Shacham [11] introduced the computational co-Diﬃe-Hellman assumption (co-CDH) which is the variant of the computational Diﬃe-Hellman (CDH) assumption. They used this assumption to prove the security of their aggregate signature scheme.∗
Assumption 2.1 (Computational co-Diﬃe-Hellman Assumption [11]). Let G be a type-2
pairing-group generator. The computational co-Diﬃe-Hlleman (co-CDH) assumption over G isthat for all λ ∈ N, for all G = (p, G1 , G2 , GT , e) ← G(1λ ), given (G, g1 , g1α , h) where g1 , h ← G2$

and α ←
− Zp as an input, no PPT adversary can, without non-negligible probability, outputs
hα . We write the advantage of co-Diﬃe-Hlleman assumption for A as
h
i
$
$
$
α
λ
α
,
h)
=
h
(p,
G
,
G
,
G
,
e)
←
G(1
),
α
←
−
Z
,
g
←
−
G
,
h
←
−
G
Advco-CDH
=
Pr
A(g
,
g
1
2
T
q 1
1
2 .
1 1
G,A
Pointcheval and Sanders [50] introduced the new q-type assumption which is called theModiﬁed q-Strong Diﬃe-Hellman-2 (q-MSDH-2) assumption. This is a variant of the q-Strong
Diﬃe-Hellman (q-SDH) assumption and deﬁned on a type 1 bilinear group. By using thisassumption, the weak EUF-CMA security for CL signature scheme and EUF-CMA security
The q-MSDH-2 assumption holds in the generic bilinear group model [10]. In this work, we
ﬁx the value to q = 1 and only use 1-MSDH-2 assumption in a static way. We can regard
1-MSDH-2 as a static assumption.
Assumption 2.2 (Modiﬁed 1-Strong Diﬃe-Hellman-2 Assumption [50]). Let G be a type1 pairing-group generator. The Modiﬁed 1-Strong Diﬃe-Hellman-2 (1-MSDH-2) assumption
over G is that for all λ ∈ N, for all G = (p, G, GT , e) ← G(1λ ), given (G, g, g x , g x , g b , g bx , g bx , g a , g abx )22$where g ← G∗ and a, b, x ←− Z∗p as an input, no PPT adversary can, without non-negligible1aprobability, output a tuple (w, P, h x+w , h x·P (x) ) with h ∈ G, P a polynomial in Zp [X] of degree
at most 1, and w ∈ Z∗p such that X + w and P (X) are relatively prime.†

2.4

Digital SignatureDeﬁnition 2.3 (Digital Signature Scheme). A digital signature scheme DS is composed offollowing four algorithms (DS.Setup, DS.KeyGen, DS.Sign, DS.Verify).
∗†

In the case of G1 = G2 , the co-CDH assumption reduces to the CDH assumption.
q+1
q+1
In the q-MSDH-2 assumption, an input is changed to (G, g, g x , . . . , g x , g b , g bx , . . . , g bx , g a , g abx ) andthe condition of the order of P (x) is changed to at most q.

15

• DS.Setup(1λ ) : Given a security parameter λ, return the public parameter pp. We assume
that pp deﬁnes the message space Mpp .
• DS.KeyGen(pp) : Given a public parameter pp, return a veriﬁcation key vk and a signing
key sk.
• DS.Sign(pp, sk, m) : Given a public parameter pp, a signing key sk, and a message m ∈Mpp , return the signature σ.
• DS.Verify(pp, vk, m, σ) : Given a public parameter pp, a veriﬁcation key vk, a message
m ∈ Mpp , and a signature σ, return either 1 (Accept) or 0 (Reject).
For DS, we require the following correctness.
• Correctness: A digital signature scheme DS is correct if for all λ ∈ N, pp ← DS.Setup(1λ ),for all m ∈ Mpp , (vk, sk) ← DS.KeyGen(pp), σ ← DS.Sign(pp, sk, m), then DS.Verify(pp,vk, m, σ) = 1 holds.
Deﬁnition 2.4 (EUF-CMA). Existentially unforgeable under chosen-message attacks (EUFCMA) security for a digital signature scheme DS is deﬁned by the following unforgeability
game between a challenger and an adversary A.
• The challenger computes pp ← DS.Setup(1λ ), (vk, sk) ← DS.KeyGen(pp) initializes Q ←{}, and sends (pp, vk) to A.
• A is given access to a signing oracle OSign (·). Given an input m, OSign computes σ ←DS.Sign(pp, sk, m), update Q ← Q ∪ {m} and returns σ to A.
• Finally, A outputs a forgery (m∗ , σ ∗ ).
DS is EUF-CMA secure if for all λ ∈ N and all PPT adversaries A, the advantage
AdvEUF-CMA:= Pr [DS.Verify(pp, vk, m∗ , σ ∗ ) = 1 ∧ m∗ ∈/ Q] is negligible in λ.
DS,A
If the number of signing oracle OSign query is restricted to the one-time in the unforgeability
security game, we call DS satisﬁes the one-time EUF-CMA (OT-EUF-CMA) security.

16

2.5

Random Oracle ModelIn this thesis, security of signature schemes is proved in the random oracle model (ROM) [3].
In this model, a hash function is regarded as an ideal random function. Instead of computing
a hash value, all the parties can obtain hash values by querying the random oracle with an
input.
In a security reduction in the ROM, the reduction simulates security the random oracle
in the security game. The reduction can set(program) and output hash values as long as the
distribution of output value is indistinguishable from a uniform distribution. This property
is called programmability and widely used in security reductions. Compared to the standard
model, it allows us to construct eﬃcient signature schemes with the provable security.

17

Chapter 3
Synchronized Aggregate Signature
In this cahpter, at ﬁrst, we review the deﬁnition of a synchronized aggregate signature scheme
and its security model, review the DSMCL scheme proposed by Pointcheval and Sanders [50].
This is used for security proof for the synchronized aggregate signature scheme proposed by
Lee et al. Then, we describe Lee et al.’s aggregate signature scheme construction. Finally,
we give a new security proof for Lee et al.’s scheme under the 1-MSDH-2 assumption in the
random oracle model.

3.1

SyntaxSynchronized aggregate signature schemes [23, 1] are a special type of aggregate signatureschemes. In this scheme, all of the signers have a synchronized time period t and each signer
can sign a message at most once for each period t. A set of signatures that are all generated forthe same period t can be aggregated into a short signature. The size of an aggregate signatureis the same size as an individual signature. Now, we review the deﬁnition of synchronized
aggregate signature schemes.
Deﬁnition 3.1 (Synchronized Aggregate Signature Schemes [23, 1]). A synchronized aggregate signature scheme SAS for a bounded number of periods is a tuple of algorithms (SAS.Setup,SAS.KeyGen, SAS.Sign, SAS.Verify, SAS.Aggregate, SAS.AggVerify).
• SAS.Setup(1λ , 1T ) : Given a security parameter λ and the time period bound T , return
the public parameter pp. We assume that pp deﬁnes the message space Mpp .
• SAS.KeyGen(pp) : Given a public parameter pp, return a veriﬁcation key vk and a signing
key sk.

18

• SAS.Sign(pp, sk, t, m) : Given a public parameter pp, a signing key sk, a time periodt ≤ T , and a message m ∈ Mpp , return the signature σ.
• SAS.Verify(pp, vk, m, σ) : Given a public parameter pp, a veriﬁcation key vk, a message
m ∈ Mpp , and a signature σ, return either 1 (Accept) or 0 (Reject).
• SAS.Aggregate(pp, (vk1 , . . . , vkr ), (m1 , . . . , mr ), (σ1 , . . . , σr )) : Given a public parameter
pp, a list of veriﬁcation keys (vk1 , . . . , vkr ), a list of messages (m1 , . . . , mr ), and a list of
signatures (σ1 , . . . , σr ), return either the aggregate signature Σ or ⊥.
• SAS.AggVerify(pp, (vk1 , . . . , vkr ), (m1 , . . . , mr ), Σ) : Given a public parameter pp, a listof veriﬁcation keys (vk1 , . . . , vkr ), a list of messages (m1 , . . . , mr ), and an aggregate
signature, return either 1 (Accept) or 0 (Reject).
Correctness: Correctness is satisﬁed if for all λ ∈ N, T ∈ N, pp ← SAS.Setup(1λ , 1T ), forany ﬁnite sequence of key pairs (vk1 , sk1 ), . . . (vkr , skr ) ← SAS.KeyGen(pp) where vki are all
distinct, for any time period t ≤ T , for any sequence of messages (m1 , . . . mr ) ∈ Mpp , σi ←SAS.Sign(pp, ski , t, mi ) for i ∈ [r], Σ ← SAS.Aggregate(pp, (vk1 , . . . , vkr ), (m1 , . . . , mr ), (σ1 , . . . , σr )),we have
SAS.Verify(pp, vki , mi , σi ) = 1 for all i ∈ [r]∧ SAS.AggVerify(pp, (vk1 , . . . , vkr ), (m1 , . . . , mr ), Σ) = 1.
In a signature aggregation, it is desirable to conﬁrm that each signature is valid. This isbecause if there is at least one invalid signature, the generated aggregate signature will be
invalid.∗ In this work, before aggregating signatures, SAS.Aggregate checks the validity of eachsignature.

3.2

Security

We introduce the security notion of synchronized aggregate signature schemes. The EUF-CMA
security of synchronized aggregate signature schemes proposed by Gentry and Ramzan [23]captures that it is hard for adversaries to forge an aggregate signature without signing key∗

Fault-tolerant aggregate signature schemes [25] allow us to determine the subset of all messages belonging

to an aggregate signature that were signed correctly. However, this scheme has a drawback that the aggregate
signature size depends on the number of signatures to be aggregated into it.

19sk∗ . However, they only provided heuristic security arguments in their synchronized aggregate
signature scheme.
Ahn, Green, and Hohrnberger [1] introduced the certiﬁed-key model for the EUF-CMA
security of synchronized aggregate signature schemes. In this model, signers must certify
their veriﬁcation key vk by proving knowledge of their signing key sk. In other words, noveriﬁcation key vk is allowed except those correctly generated by the SAS.KeyGen algorithm. In
certiﬁed-key model, to ensure the correct generation of a veriﬁcation key vki ̸= vk∗ , EUF-CMA
adversaries must submit (vki , ski ) to the certiﬁcation oracle OCert . As in [1, 38], we consider
the EUF-CMA security in the certiﬁed-key model.
Deﬁnition 3.2 (EUF-CMA Security in the Certiﬁed-Key Model [1, 38]). The EUF-CMA
security of a sequential aggregate signature scheme SAS in the certiﬁed-key model is deﬁned
by the following unforgeability game between a challenger C and a PPT adversary A.
• C runs pp∗ ← SAS.Setup(1λ , 1T ), (vk∗ , sk∗ ) ← SAS.KeyGen(pp∗ ), sets Q ← {}, L ← {},tctr ← 1, and gives (pp, vk∗ ) to A.
• A is given access (throughout the entire game) to a certiﬁcation oracle OCert (·, ·). Given
an input (vk, sk), OCert performs the following procedure.
– If the key pair (vk, sk) is valid, L ← L ∪ {vk} and return “accept”.
– Otherwise return “reject”.
(A must submit key pair (vk, sk) to OCert and get “accept” before using vk.)
• A is given access (throughout the entire game) to a sign oracle OSign (·, ·). Given an input(“inst”, m), OSign performs the following procedure.
(“inst” ∈ {“skip”, “sign”} represent the instruction for OSign where “skip” implies
that A skips the concurrent period tctr and “sign” implies that A require the signature
on message m. )– If tctr ∈/ [T ], return ⊥.
– If “inst” = “skip”, tctr ← tctr + 1.
– If “inst” = “sign”, Q ← Q ∪ {m}, σ ← SAS.Sign(pp∗ , sk∗ , t, m), tctr ← tctr + 1,
return σ.
• A outputs a forgery ((vk∗1 , . . . , vk∗r∗ ), (m∗1 , . . . , m∗r∗ ), Σ∗ ).

20

A sequential aggregate signature scheme SAS satisﬁes the EUF-CMA security in the certiﬁedkey model if for all PPT adversaries A, the following advantage

SAS.AggVerify(pp∗ , (vk∗1 , . . . , vk∗r∗ ), (m∗1 , . . . , m∗r∗ ), Σ∗ ) = 1


∗
∗
∗
∗


:=
Pr
AdvEUF-CMA
∈
L
∧
For
all
j
∈
[r
]
such
that
vk
=
̸
vk
,
vk
SAS,A
j
j


∗
∗
∗
∗
∗
/Q
∧ For some j ∈ [r ] such that vkj ∗ = vk , mj ∗ ∈is negligible in λ.

3.3

Modiﬁed Camenisch-Lysyanskaya Signature Scheme

Pointcheval and Sanders [50] proposed the modiﬁed Camenisch-Lysyanskaya signature scheme
which supports a multi-message (vector message) signing. In this work, we only need a singlemessage signing scheme. Here, we review the single-message modiﬁed Camenisch-Lysyanskayasignature scheme DSMCL = (DSMCL .Setup, DSMCL .KeyGen, DSMCL .Sign, DSMCL .Verify) as follows.
• DSMCL .Setup(1λ ) :G = (p, G, GT , e) ← G(1λ ). (G is a type-1 pairing-group generator)
Return pp ← G.
• DSMCL .KeyGen(pp) :
$

$

$

$

g←
− G∗ , x ←− Z∗p , y ←− Z∗p , z ←− Z∗p , X ← g x , Y ← g y , Z ← g z .
Return (vk, sk) ← ((g, X, Y, Z), (x, y, z)).
• DSMCL .Sign(pp, sk, m) :Parse sk as (x, y, z)$$w←− Zp , A ←− G∗ , B ← Ay , C ← Az , D ← C y , E ← Ax B mx Dwx .
Return σ ← (w, A, B, C, D, E).
• DSMCL .Verify(pp, vk, m, σ) :Parse vk as (g, X, Y, Z), σ as (w, A, B, C, D, E).
If (e(A, Y ) ̸= e(B, g)) ∨ (e(A, Z) ̸= e(C, g)) ∨ (e(C, Y ) ̸= e(D, g)), return 0.
If e(AB m Dw , X̃) = e(E, g), return 1.
Otherwise return 0.

21

Pointcheval and Sanders [50] proved that if the q-MSDH-2 assumption holds, then the
DSMCL scheme satisﬁes the EUF-CMA security where q is a bound on the number of adaptive
signing queries. In this work, we only need the OT-EUF-CMA security for the DSMCL scheme.
Theorem 3.3 ([50]). If the 1-MSDH-2 assumption holds, then the DSMCL scheme satisﬁes the
OT-EUF-CMA security.

3.4

Synchronized Aggregate Signature Scheme by Lee
et al.

We describe the synchronized aggregate signature scheme by Lee et al. [38]. Let T be abounded number of periods which is a polynomial in λ. The synchronized aggregate signature scheme by Lee et al. SASLLY = (SASLLY .Setup, SASLLY .KeyGen, SASLLY .Sign, SASLLY .Verify,
SASLLY .Aggregate, SASLLY .AggVerify) [38] is given as follows.†• SASLLY .Setup(1λ , 1T ) :$1. G = (p, G, GT , e) ← G(1λ ), g ←− G∗ . (G is a type-1 pairing-group generator)
2. Choose hash functions:
H1 : [T ] → G, H2 : [T ] → G∗ , H3 : [T ] × {0, 1}∗ → Zp .
3. Return pp ← (G, g, H1 , H2 , H3 ).
• SASLLY .KeyGen(pp) :$1. x ←− Z∗p , X ← g x .
2. Return (vk, sk) ← (X, x).
• SASLLY .Sign(pp, sk, t, m) :′1. m′ ← H3 (t, m), E ← H1 (t)sk H2 (t)m sk .
2. Return (E, t).
• SASLLY .Verify(pp, vk, m, σ) :†The SASLLY scheme described here is slightly diﬀerent from the original ones [38] in that the range of H2

is changed from G to G∗ .

22

1. m′ ← H3 (t, m), parse σ as (E, t),.
′2. If e(E, g) = e(H1 (t)H2 (t)m , vk), return 1.
3. Otherwise return 0.
• SASLLY .Aggregate(pp, (vk1 , . . . , vkr ), (m1 , . . . , mr ), (σ1 , . . . , σr )) :1. For i = 1 to r, parse σi as (Ei , ti ).
2. If there exists i ∈ {2, . . . , r} such that ti ̸= t1 , return ⊥.
3. If there exists (i, j) ∈ [r] × [r] such that i ̸= j ∧ vki = vkj , return ⊥.
4. If there exists i ∈ [r] suth that SASLLY .Verify(pp, vki , mi , σi ) ̸= 0,
return ⊥.
Q
5. E ′ ← ri=1 Ei .
6. Return Σ ← (E ′ , w).
• SASLLY .AggVerify(pp, (vk1 , . . . , vkr ), (m1 , . . . , mr ), Σ) :1. There exists (i, j) ∈ [r] × [r] such that i ̸= j ∧ vki = vkj , return 0.
2. For i = 1 to r, m′i ← H3 (t, mi ).
3. Parse Σ as (E ′ , w).
′

4. If e(E , g) = e (H1 (t),Qri=1 vki ) · e
H2 (t),

Qrm′i
i=1 vki, return 1.

5. Otherwise, return 0.
Now, we conﬁrm the correctness. Let (vki , ski ) ← SASLLY .KeyGen(pp) and σi ← SASLLY .Sign(pp,′ski , t, mi ) for i ∈ [r] where vki are all distinct. Then, for all i ∈ [r], Ei ← H1 (t)ski H2 (t)mi ski
holds where m′i ← H3 (t, mi ) and σi = (Ei , t). This fact implies that SASLLY .Verify(pp, vki , mi , σi ) =1. Furthermore, let Σ ← SASLLY .Aggregate(pp, (vk1 , . . . , vkr ), (m1 , . . . , mr ), (σ1 , . . . , σr )). Then,
E′ =

r
Y

∑n

Ei = H1 (t)i=1 ski∑n

H2 (t)′
i=1 mi ski

i=1

holds where Σ = (E ′ , t) and m′i ← H3 (t, mi ) for all i ∈ [r]. This fact implies that SASLLY .AggVerify(pp,(vk1 , . . . , vkr ), (m1 , . . . , mr ), Σ) = 1.

23

3.5

Conversion from MCL Signature to Aggregate Signature by Lee et al.

Before security analysis the synchronized aggregate signature proposed by Lee et al, we explain
an intuition that there is a relationship between the DSMCL scheme and Lee et al.’s aggregate
signature scheme. Concretely, we explain that there is a conversion from the DSMCL scheme
to Lee et al.’s aggregate signature scheme.
Our idea of conversion is a similar technique in [38] which converts the Camenisch-Lysyanskayasignature CL scheme to the synchronized aggregate signature scheme. However, the form ofsignatures in CL and DSMCL , we cannot immediately convert DSMCL scheme to the synchronized
aggregate signature scheme. Thus, we need to modify the conversion technique in [38].
Now, we explain an intuition of our conversion. We start from the DSMCL scheme in Section
3.3. A signature of the DSMCL scheme on a message m is formed as
σ = (w, A, B = Ay , C = Az , D = C y , E = Ax B mx Dwx ).
$$where w ←− Zp and A ←− G∗1 . If we can force signers to use same w, A, B = Ay , C = Az , and
D = C y , we can obtain an aggregate signatureΣ=

w, A, B, C, D, E ′ =rY

Ei = A∑r

i=1 xiB∑r

i=1 mi xi

D

∑r

!

i=1 wxi

i=1

on a message list (m1 , . . . , mr ) from valid signatures (σ1 , . . . σr ) where σi = (w, A, B, C, D, Ei ) isa signature on a message mi generated by each signer. If we regard E ′ as E ′ = (ADw )∑r

i=1 xiB∑r

i=1 mi xi

veriﬁcation of the aggregate signature Σ on the message list (m1 , . . . , mr ) can be done bychecking the following equation.
e(E ′ , g) = e ADw ,

r
Y

!
vki

i=1

· e B,

r
Y

!
i
vkm
i

i=1

Then, required elements to verify the aggregate signature Σ are F = ADw , B, and E ′ . Similar
to Lee et al.’s conversion, the three veriﬁcation equations e(A, Y ) = e(B, g), e(A, Z) = e(C, g),e(C, Y ) = e(D, g) in DSMCL .Verify is discarded in this conversion. We use hash functions toforce signers to use the same F and B for each period t. We choose hash functions H1 andH2 and set F ← H1 (t) and B ← H2 (t). Then, we can derive Lee et al.’s aggregate signaturescheme. In this derived aggregate signature scheme, a signature on a message m and period t
is formed as
σ = (E = H1 (t)x H2 (t)mx , t).

24,

An aggregate signature Σ′ on a message list (m1 , . . . , mr ) and period t is formed as
!
r
Y
∑r
∑r
Σ = E′ =Ei = H1 (t) i=1 xi H2 (t) i=1 mi xi , t
i=1

where σi = (Ei = H1 (t)xi H2 (t)mi xi , t) is a signature on a message mi generated by each signer.
In our conversion, we need to hash a message with a time period for the security proof. This
conversion technique is used for our security proof in next section.

3.6

New Security Proof

We reassess the EUF-CMA security of the SASLLY scheme. In particular, we newly prove
the EUF-CMA security of the SASLLY scheme under the 1-MSDH-2 assumption. By using
the conversion technique described previous section, we simulate a signature in the aggregate
signature scheme Lee et al. in the reduction.
Theorem 3.4. If the DSMCL scheme satisﬁes the OT-EUF-CMA security, then, in the random
oracle model, the SASLLY scheme satisﬁes the EUF-CMA security in the certiﬁed-key model.
proof. We give an overview of our security proof. Similar to the work in [38], we reduce the
EUF-CMA security of the SASLLY scheme to the OT-EUF-CMA security of the DSMCL scheme.
We construct a reduction algorithm according to the following strategy. First, the reduction
algorithm chooses a message mDSMCL at random, make signing query on mDSMCL , and obtains
its signature σDSMCL = (wDSMCL , ADSMCL , BDSMCL , CDSMCL , DDSMCL , EDSMCL ) of the DSMCL scheme.
Then, the reduction algorithm guesses the time period t′ of a forged aggregate signature andan index k ′ ∈ [qH3 ] at random where qH3 be the maximum number of H3 hash queries. ThenwDS

MCL
reduction algorithm programs hash values as H1 (t′ ) = ADSMCL DDSMCL, H2 (t′ ) = BDSMCL , andH3 (t′ , mk′ ) = mDSMCL . For a signing query on period t ̸= t′ , the reduction algorithm generate
the signature by programmability of hash functions H1 , H2 , and H3 . For a signing query on
period t ̸= t′ , if the query index j of H3 is equal to the index k ′ , the reduction algorithm cancompute a valid signature by using σDSMCL (This can be done by using the conversion techniquein Section 3.5.). Otherwise, the algorithm should abort the simulation. Finally, the reduction
algorithm extracts valid forgery of the DSMCL scheme from a forged aggregate signature ontime period t′ of the SASLLY scheme.
Now, we give the security proof. Let A be an EUF-CMA adversary of the SASLLY scheme,
C be the OT-EUF-CMA game challenger of the DSMCL scheme, and qH3 be the maximum

25

number of H3 hash queries. We construct the algorithm B against the OT-EUF-CMA gameof the DSMCL scheme. The construction of B is given as follow.
• Initial setup: Given an input pp = GDSMCL and vk = (gDSMCL , XDSMCL , YDSMCL , ZDSMCL )from C, B performs the following procedure.
– G ← GDSMCL , g ← gDSMCL , pp∗ ← (G, g), vk∗ ← XDSMCL . t′ ←− [T ], k ′ ←− [qH3 ], tctr ← 1,$$

L ← {}, T1 ← {}, T2 ← {}, T3 ← {}, Q ← {}.
$– mDSMCL ←− Zp , query C for the signature on the message mDSMCL and get its signature
σDSMCL = (wDSMCL , ADSMCL , BDSMCL , CDSMCL , DDSMCL , EDSMCL ),– Give (pp∗ , vk ∗ ) to A as an input.
• OCert (vk, sk) : If vk = g sk , update a list L ← L ∪ {vk} and return “accept” to A.
Otherwise return “reject” to A.
• OH1 (ti ) : Given an input ti , B responds as follows.
– If there is an entry (ti , ·, Fi ) (‘·’ represents an arbitrary value or ⊥) for some Fi ∈ G1
in T1 , return Fi .
$– If ti ̸= t′ , r(1,i) ←− Zp , Fi ← g r(1,i) , T1 ← T1 ∪ {(ti , r(1,i) , Fi )}, return Fi .
wDS

wDS

MCL
MCL
– If ti = t′ , T1 ← T1 ∪ {(ti , ⊥, ADSMCL DDSMCL}, return ADSMCL DDSMCL.

• OH2 (ti ) : Given an input ti , B responds as follows.
– If there is an entry (ti , ·, Bi ) (‘·’ represents an arbitrary value or ⊥) for some Bi ∈ G∗1
in T3 , return Bi .
$– If ti ̸= t′ , r(2,i) ←− Z∗p , Bi ← g r(2,i) , T2 ← T2 ∪ {(ti , r(2,i) , Bi )}, return Di .
– If ti = t′ , T2 ← T2 ∪ {(ti , ⊥, BDSMCL )}, return BDSMCL .
• OH3 (ti , mj ) : Given an input (ti , mj ), B responds as follows.
– If there is an entry (ti , mj , m′(i,j) ) for some m′(i,j) ∈ Zp in T3 , return m′(i,j) .
$– If ti ̸= t′ ∨ j ̸= k ′ , m′(i,j) ←− Zp , T3 ← T3 ∪ {(ti , mj , m′(i,j) )}, return m′(i,j) .
– If ti = t′ ∧ j = k ′ , T3 ← T3 ∪ {(ti , mj , mDSMCL )}, return mDSMCL .
• OSign (“inst”, mj ) : Given an input (“inst”, mj ), B performs the following procedure.

26

– If tctr ∈/ [T ], return ⊥.
– If “inst” = “skip”, tctr ← tctr + 1.
– If “inst” = “sign”,
r(2,ctr) m′(ctr,j)r(1,ctr)∗ If tctr ̸= t′ , E ← XDS
XDSMCL
MCL

where r(1,i) , r(2,i) , and m′(i,j) are retreived

from (tctr , r(1,ctr) , Fctr ) ∈ T1 , (tctr , r(2,ctr) , Bctr ) ∈ T2 , and (tctr , mj , m′(ctr,j) ) ∈ T3
respectively. Q ← Q∪{mj }, return σctr,j ← (E, tctr ), then update tctr ← tctr +1.
∗ If tctr = t′ ∧ j = k ′ , Q ← Q ∪ {mj }, return σctr,j ← (EDSMCL , ti ), then update
tctr ← tctr + 1∗ If tctr = t′ ∧ j ̸= k ′ , abort the simulation.
• Output procedure: B receives a forgery ((vk∗1 , . . . , vkr∗∗ ), (m∗1 , . . . , m∗r∗ ), Σ∗ ) outputtedby A. Then B proceeds as follows.
1. If SASLLY .AggVerify(pp∗ , (vk∗1 , . . . , vk∗r∗ ), (m∗1 , . . . , m∗r∗ ), Σ∗ ) ̸= 1, then abort.
2. If there exists j ∈ [r∗ ] such that vk∗j ̸= vk∗ ∧ vk∗j ∈/ L, then abort.
3. If there is no j ∗ ∈ [r∗ ] such that vk∗j ∗ = vk∗ ∧ m∗j ∗ ∈/ Q, then abort.
4. Set j ∗ ∈ [r∗ ] such that vk∗j ∗ = vk∗ ∧ m∗j ∗ ∈/ Q.
5. Parse Σ∗ as (E ∗′ , t∗ ).
6. If t∗ ̸= t′ , then abort.
7. m∗j ∗ ′ ← H3 (t∗ , m∗j ∗ )8. If m∗j ∗ ′ = mDSMCL , then abort.
9. For i ∈ [r∗ ]\{j ∗ }, retrieve xi ← sk∗i of vk∗i from L.
10. F ′ ← H1 (t∗), B ′ ← H2 (t∗ ), m′i ← H3 (t∗ , m∗i ) for i ∈ [r∗ ]\{j ∗ },E ′ ← E ∗′ · F ′∑i∈[r ∗ ]\{j ∗ } xi

B′

∑

′
i∈[r ∗ ]\{j ∗ } xi mi

−1

.

∗
11. Return (m∗DSMCL , σDS) ← (m∗j ∗ , (wDSMCL , ADSMCL , B ′ , CDSMCL , DDSMCL , E ′ )).
MCL

We conﬁrm that if B does not abort, B can simulate the EUF-CMA game of the SASLLY
scheme.
• Initial setup: First, we discuss the distribtuon of pp∗ . In the original EUF-CMA gameof the SASLLY scheme, pp∗ = (G, g) is constructed by G = (p, G, GT , e) ← G(1λ ) and$g←− G∗ . In the simulation of B, pp∗ is a tuple (GDSMCL , gDSMCL ). This tuple is constructed27

$by C as GDSMCL = (p, G, GT , e) ← G(1λ ) and gDSMCL ←− G∗ . Therefore, B simulates pp∗
perfectly. Next, we discuss the distribution of vk∗ . In the original EUF-CMA game of
the SASLLY scheme, vk is computed by x ←− Z∗p and vk∗ ← g x . In the simulation of B, vk∗$$

is set by XDSMCL . Since XDSMCL is computed by C as xDSMCL ←− Zp and XDSMCL ← g xDSMCL ,distributions of vk between the original game and simulation of B are identical. Hence,the distributions of (pp∗ , vk∗ ) are identical.
• Output of OCert : This is clearly that B can simulate the original EUF-CMA game of
the SASLLY scheme perfectly.
• Output of OH1 : In the original game, hash values of H1 is chosen from G uniformly
at random. In the simulation of B, if ti ̸= t′ , the hash value H(ti ) is set by g r(1,i)$

where r(1,i) ←− Zp . Obviously, in this case, B can simulate OH1 perfectly. If ti =
wDS

1+yDS

MCL
t′ , the hash value H(ti ) is set by F = ADSMCL DDSMCL= ADSMCLMCLzDSMCL wDSMCL

where

yDSMCLzDSMCLYDSMCL = gDSMCL, ZDSMCL = gDSMCL, and wDSMCL is chosen by C as wDSMCL ← Zp . For$$− Zp and wDSMCL ←− Zp ,
ﬁxed yDSMCL ∈ Z∗p and zDSMCL ∈ Z∗p , the distribution α where α ←α ← 1 + yDSMCL zDSMCL wDSMCL are identical. This fact implies that B also simulate OH1

perfectly in the case of ti = t′ . Therefore, B simulates OH1 perfectly.
• Output of OH2 : As the same argument of OH1 , if ti ̸= t′ , B can simulate hash values
H(ti ) perfectly. In the case of ti = t′ , the hash value H(ti ) is set by BDSMCL = AyDSMCL =$− Z∗p , B ←g xDSMCL yDSMCL . For ﬁxed xDSMCL ∈ Z∗p , the distributions of B where yDSMCL ←$− G∗ are identical. Therefore, B simulates OH2 perfectly.
g xDSMCL yDSMCL and B ←• Output of OH3 : If ti ̸= t′ ∨j ̸= k ′ , clearly B can simulate OH3 perfectly. If ti = t′ ∧j = k ′ ,$the hash value H3 (ti , mj ) is set by mDSMCL . Since mDSMCL is chosen by B as mDSMCL ←− Zp ,
B simulates OH3 perfectly.
xDS

MCL(xDSMCL ∈ Z∗p ).
• Output of OSign : For the sake of argument, we denote XDSMCL = gDSMCLrr(2,i) m′(1,i)
XDSMCL (i,j) and output the signature σ = (E, ti ). Now we
If ti ̸= t′ , B sets E ← XDS
MCL

conﬁrm that σ is a valid signature on the message mj . The following equationrr(2,i) m′

′

xDS

xDS

(1,i)
MCL r(2,i) m(i,j)
MCL r(1,i)))(gDSMCLE = XDSXDSMCL (i,j) = (gDSMCLMCL′= H1 (ti )xDSMCL H2 (ti )xDSMCL m(i,j)
holds where m′(i,j) = H3 (ti , mj ). This fact implies that′e(E, g) = e(H1 (ti )H2 (ti )m(i,j) , vk∗ )28

holds. Therefore, σ is valid signature on the message mj .
If ti ̸= t′ ∧ j = k ′ , B sets E ← EDSMCL , return σi,j ← (E, ti ) to A. We also conﬁrm
wDS

MCL
that σ is a valid signature on the message mj . In the case, H1 (ti ) = ADSMCL DDSMCL,

H2 (ti ) = BDSMCL , and H3 (ti , mj ) = m′(i,j) = mDSMCL hold. Since EDSMCL is the valid
signature of the DSMCL scheme on message mDSMCL ,
mDS

wDS

MCL
MCL
e(EDSMCL , g) = e(ADSMCL BDSMCLDDSMCL, XDSMCL )

wDS

mDS

MCL
MCL
= e((ADSMCL DDSMCL)BDSMCL, XDSMCL )′holds. This implies that e(E, g) = e(H1 (ti )H2 (ti )m(i,j) , vk∗ ) where m′(i,j) = H3 (ti , mj ).
By the above discussion, we can see that B does not abort, B can simulate the EUF-CMA
game of the SASLLY scheme.
Second, we conﬁrm that when A successfully output a valid forgery ((vk∗1 , . . . , vk∗r∗ ), (m∗1 , . . . ,m∗r∗ ), Σ∗ ) of the SASLLY scheme, B can forge a signature of the DSMCL scheme. Let ((vk∗1 , . . . , vk∗r∗ ),(m∗1 , . . . , m∗r∗ ), Σ∗ ) be a valid forgery output by A. Then there exists j ∗ ∈ [r∗ ] such thatvk∗j ∗ = vk∗ . By the veriﬁcation equation of SASLLY .Verify,
!
!
r∗
r∗
Y
Y
∗
e(E ∗′ , g) = e H1 (t∗ ),vk∗i · e H2 (t∗ ), (vk∗i )mi
i=1

i=1

holds where Σ∗ = (E ∗′ , t∗ ) and H3 (t∗ , m∗i ) = m∗i ′ for i ∈ [r∗ ]. If B does not abort in StepwDS

MCL
6 of Output procedure, t∗ = t′ holds. This means that H1 (t∗ ) = ADSMCL DDSMCLand

H2 (t∗ ) = BDSMCL hold. These facts imply that
∑r ∗

∑r ∗

∗

∗′

∗

E ∗′ = H1 (t∗ ) i=1 ski H2 (t∗ ) i=1 mi ski∗∑ri=1∑r ∗x∗iwDSMCLm∗i ′ x∗i
= ADSMCL DDSMCLBDSi=1MCL
holds where sk∗i = x∗i is a secret key corresponding to vk∗i .
wDS

MCL
By setting F ′ ← ADSMCL DDSMCLand B ′ ← BDSMCL ,

′

∗′



E =E · F′∑i∈[r ∗ ]\{j ∗ } xi

wDS

∗

B

′

∑

′
i∈[r ∗ ]\{j ∗ } xi mi

−1m∗∗ ′ x∗∗

MCL xj ∗) BDSjMCLj= (ADSMCL DDSMCL

Moreover, e(ADSMCL , YDSMCL ) = e(BDSMCL , gDSMCL ), e(ADSMCL , ZDSMCL ) = e(CDSMCL , gDSMCL ), ande(CDSMCL , YDSMCL ) = e(DDSMCL , gDSMCL ) holds. If B does not abort in Step 8 of Output procedure, m∗j ∗ is a not queried message for the signing of the OT-EUF-CMA game of the DSMCL

29

∗scheme. Therefore, if B does not abort and outputs (m∗DSMCL , σDS) ← (m∗j ∗ , (wDSMCL , ADSMCL , B ′ ,MCL

CDSMCL , DDSMCL , E ′ )), B can forge a signature of the DSMCL scheme.
Finally, we analyze the probability that B succeeds in forging a signature of the DSMCL
scheme. First, we consider the probability that B does not abort at the simulation of signatures.
B aborts the simulation of OSign if tctr = t′ ∧ j ̸= k ′ . The probability that B succeeds insimulating OSign is at least 1/qH3 . Next, we consider the probability that B aborts in Step 6
of Output procedure. Since B chooses the target period t′ ← [T ], the probability t∗ ̸= t′
is 1/[T ]. Finally, the probability that B aborts in Step 8 of Output procedure is 1/p.
Let AdvEUF-CMA
SASLLY ,A be the advantage of the EUF-CMA game for the SASLLY scheme of A. The
advantage of the OT-EUF-CMA game for the DSMCL scheme of B is
AdvOT-EUF-CMA≥
DSMCL ,B

AdvEUF-CMA
SASLLY ,A
T × qH 3



1
1−
.
p

Therefore, we can conclude the proof of Theorem 3.4.
By combining Theorem 3.3 and Theorem 3.4, we have the following corollary.
Corollary 3.5. If the 1-MSDH-2 assumption holds, then, in the ROM, the SASLLY scheme
satisﬁes the EUF-CMA security in the certiﬁed-key model.

30

Chapter 4
T-out-of-N Redactable Signature
In this chapter, at ﬁrst, we introduce the notion of t-out-of-n redactable signature, deﬁne its
security. Second, we review the aggregate signature scheme by Boneh, Gentry, Lynn, andShacham [11] and Shamir’s secret sharing scheme [56]. Then, we give a t-out-of-n redactablesignature scheme by using these primitives. Finally, we prove that our scheme satisﬁes unforgeability and transparency.

4.1

SyntaxWe explain the t-out-of-n redactable signature scheme in the one-time redaction model. A tout-of-n redactable signature scheme in the one-time redaction model (t, n)-RS is a signaturescheme that has a signer, n redactors, a combiner, and a veriﬁer. The signer designates n
redactors and the combiner.
The signer selects a threshold t and the number of redactors n. Then, he or she runs key
generation algorithm and gets (vk, sk, {rk[i]}ni=1 ). The vk is published and the redactor’s key
rk[i] is sent to the redactor i.
The signer signs a message M with an admissible description ADM which represents partsof the message that redactors cannot remove from the message M . In the processing of thesigning, a random document ID (DID) is added to the message M , then the signature σ isgenerated. (M, ADM, DID, σ) generated by the signer is sent to n redactors and the combiner.
Each redactor i checks whether DID has never been seen before. If he or she has seen it,then aborts. Also, if the signature is invalid, then aborts. Otherwise, he or she selects partsof the message that he or she wants to remove and makes the redaction information RIi andsends it to the combiner. The protocol works only once for DID which redactors have not seen31

before.
The combiner collects pieces of redaction information {RIi }ni=1 . From {RIi }ni=1 , the combiner
extracts parts which at least t redactor want to remove. Finally, the combiner outputs theredacted message M ′ , ADM, DID, and its updated valid signature σ ′ .
The signature is veriﬁed using the signer’s public key vk. In the veriﬁcation, it is possible
to prove the validity of the (M, ADM, DID, σ) made by a legitimate signer or redacted by theredaction protocol for that signature while keeping redactors anonymity.
Now, we formalize the t-out-of-n redactable signature scheme in the one-time redaction
model for set. In the following, we assume that a message M is a set and use following
notations. An admissible description ADM is a set containing all elements which must not be
redacted.
A modiﬁcation instruction MOD is a set containing all elements which a redactor want toredact from M . ADM ⪯ M means that ADM is a valid description. (i.e.,ADM ∩ M = ADM.)
ADM

MOD ⪯ M means that MOD is valid redaction description respect to ADM and M . (i.e.,MOD

MOD ∩ ADM = ∅ ∧ MOD ⊂ M .) A redaction M ′ ← M would be M ′ ← M \MOD. In thefollowing deﬁnition, we explicit ADM and DID in the syntax.
Deﬁnition 4.1. A t-out-of-n redactable signature scheme in the one-time redaction model(t, n)-RS is composed of four components (RS.Setup, RS.KeyGen, RS.Sign, RS.Redact, RS.Verify).
• RS.Setup(1λ ) : A setup algorithm is a randomized algorithm. Given a security parameter
λ, return the public parameter pp. We assume that pp deﬁnes the message space Mpp .
• RS.KeyGen(pp, t, n) : A key generation algorithm is a randomized algorithm that a signer
runs. Given a public parameter 1λ , a threshold t and the number of redactors n, returna signer’s public key vk, a signer’s secret key sk, and redactor’s secret keys {rk[i]}ni=1 .
• RS.Sign(pp, sk, M, ADM) : A signing algorithm is a randomized algorithm that a signer
runs. Given a public parameter pp, signer’s secret key sk, a message M and an admissible
description ADM, return a message M , an admissible description ADM, a document ID(DID), and a signature σ.
• RS.Redact : A redact protocol is a 1-round interactive protocol between the combiner
and n redactors. Each redactor i generates redaction information RIi and sends to the
combiner. The combiner collects all redaction informations {RIi }ni=1 and ﬁnally outputs
the redacted signature (M ′ , ADM, DID, σ ′ ). We describe the protocol as follows:32

– Given an input (M, ADM, DID, σ) from the signer, each redactor i selects a modiﬁcation instruction MODi and runs a redact information algorithm RS.RedInf with(pp, vk, rk[i], M, ADM, DID, σ, MODi , Lu−1). Lu−1is the list which stores on DID sentiifrom the signer. It is used for t-th input of the RS.RedInf by redactor i and L0 = ∅.
In the processing in RS.RedInf, if DID is previous input to RS.RedInf then redactor
i stop interacting with a combiner. Otherwise, output the redact information RIi
and the updated list Lui . Each redactor i sends RIi to the combiner.
– The combiner runs a deterministic threshold redact algorithm RS.ThrRed with(pp, vk, M, ADM, DID, σ, {RIi }ni=1 ) as an input. In the algorithm RS.ThrRed, MOD
is derived from {RIi }ni=1 and it redacts a message M based on MOD. RS.ThrRed
outputs a redacted message M ′ , ADM, DID and the updated signature σ ′ . Finally,
the combiner outputs (M ′ , ADM, DID, σ ′ ) as an output of RS.Redact protocol.
• RS.Verify(pp, vk, M, ADM, DID, σ) : Given an input (pp, vk, M, ADM, DID, σ), return either 1 (Accept) or 0 (Reject).
Correctness
We require the correctness that all honestly computed and redacted signatures are accepted.
Deﬁnition 4.2 (Correctness). A t-out-of-n redactable signature scheme in the one-time redaction model (t, n)-RS is correct, ∀λ ∈ N, ∀k ∈ N,
ADMu

∀M0u , ∀ADMu ⪯ M0u , ∀MODui ⪯ M0u for u ∈ [k] and i ∈ [n],pp ← RS.Setup(1λ ), (vk, sk, {rk[i]}ni=1 ) ← RS.KeyGen(pp, t, n),
For u = 1 to k,(M0 , ADMu , DIDu , σ0u ) ← RS.Sign(pp, sk, M0u , ADMu ),For i ∈ [n],(RIui , Lui ) ← RS.RedInf(pp, vk, rk[i], M0u , ADMu , DIDu , σ0u , MODui , Lu−1),i
(M1u , ADMu , DID, σ1u ) ← RS.ThrRed(pp, vk, M0u , ADMu , DIDu , σ0u , {RIui }ni=1 ),we require the following for all u ∈ [k]:• If DIDk ∈/ Lu−1, RS.Verify(pp, vk, Mtu , ADMu , DIDu , σbu ) = 1 for all b ∈ {0, 1}.
i• If DIDk ∈ Lu−1
, RS.Verify(pp, vk, M0u , ADMu , DIDu , σ0u ) = 1.
i

33

4.2

Security

We give the security notion of unforgeability, privacy, and transparency for a redactable signature scheme in the one-time redaction model.
Unforgeability. Unforgeability requires that without a signer’s secret key sk, it should be
infeasible to compute a valid signature σ ′ on (M ′ , ADM, DID) except to redact a signed message(M, ADM, DID, σ) even if t − 1 redactors keys are corrupted.
Deﬁnition 4.3 (Unforgeability). The unforgeability against redactors security of a t-out-of-n
redactable signature scheme in the one-time redaction model (t, n)-RS Π is deﬁned by thefollowing unforgeability game between a challenger C and a PPT adversary A.
1. C runs pp ← RS.Setup(1λ ), (vk, sk, {rk[i]}ni=1 ) ← RS.KeyGen(pp, t, n), and gives (pp, vk)
to an adversary A.
2. A is given access (throughout the entire game) to a sign oracle OSign (·, ·) such that
OSign (M, ADM), returns (M, ADM, DID, σ) ← RS.Sign(pp, sk, M, ADM).
3. A is given access (throughout the entire game) to a redact oracle ORedact (·, ·, ·, ·, ·). ORedact
is deﬁned as follows:
For an u-th query (M, ADM, DID, σ, MOD):(a) (RIi , Lui ) ← RS.RedInf(pp, vk, rk[i], M, ADM, DID, σ, MOD, Lu−1
) for i = 1, ..., n.
i(b) (M ′ , ADM, DID, σ ′ ) ← RS.ThrRed(pp, vk, M, ADM, DID, σ, {RIi }ni=1 ).
(c) Return (M ′ , ADM, DID, σ ′ ).
4. A is given up to t − 1 times access (throughout the entire game) to a corrupt oracle
OCorrupt (·), where OCorrupt (i) outputs a rk[i] of a redactor i.
5. A outputs (M ∗ , ADM∗ , DID∗ , σ ∗ ).
A t-out-of-n redactable signature scheme in the one-time redaction model (t, n)-RS satisUf-(t,n)-RSS

ﬁes the unforgeability security if for all PPT adversaries A, the advantage Adv(t,n)-RS,A=

Pr[RS.Verify(pp, vk, M ∗ , ADM∗ DID∗ , σ ∗ ) = 1 ∧ (M ∗ , ADM∗ , DID∗ ) ∈/ (QSign ∪ QRedact )] is negligible in λ.
Here, qs is the total number of queries to OSign , (Mi , ADMi ) is an i-th input for OSign ,Ss(M i , ADMi , DIDi , σ i ) is an i-th output of OSign and QSign := qi=1{(M i , ADMi , DIDi )}. Also, qr

34

is the total number of queries to ORedact , (M i , ADMi , DIDi , σ i , MODi ) is an i-th input for ORedact ,Sr(M ′ i , ADMi , DIDi , σ ′ i ) is an i-th output of ORedact and QRedact := qi=1{(M ′ i , ADMi , DIDi )}.
Privacy. Privacy requires that except for a signer, n redactors, and a combiner, it is infeasible to derive information on redacted message parts when given a message-ADM-DID-signaturepair.
Deﬁnition 4.4 (Privacy). The privacy of a t-out-of-n redactable signature scheme in the
one-time redaction model (t, n)-RS Π is deﬁned by the following weak privacy game betweena challenger C and a PPT adversary A.
1. C runs pp ← RS.Setup(1λ ), (vk, sk, {rk[i]}ni=1 ) ← RS.KeyGen(pp, t, n), and gives (pp, vk)
to an adversary A.
2. A is given access (throughout the entire game) to a sign oracle OSign (·, ·) such that
OSign (M, ADM), returns (M, ADM, DID, σ) ← RS.Sign(pp, sk, M, ADM).
3. A is given access (throughout the entire game) to a redact oracle ORedact (·, ·, ·, ·, ·). ORedact
is deﬁned as follows:
For an u-th query (M, ADM, DID, σ, MOD):Let w be the number of queries to OLoRredact when A makes an u-th query to ORedact .
(a) (RIi , Lu+2w) ← RS.RedInf(pp, vk, rk[i], M, ADM, DID, σ, MOD, Lu+2w−1
) for
i
i
i = 1, ..., n.
(b) (M ′ , ADM, DID, σ ′ ) ← RS.ThrRed(pp, vk, M, ADM, DID, σ, {RIi }ni=1 ).
(c) Return (M ′ , ADM, DID, σ ′ ).
4. A is given access (throughout the entire game) to a left-or-right redact oracle OLoRredact (·, ·, ·, ·, ·, ·).
OLoRredact is deﬁned as follows:
For an w-th query (M 0 , ADM0 , MOD0 , M 1 , ADM1 , MOD1 ):Let u be the number of queries to ORedact when A makes an w-th query to OLoRredact .
(a) Compute (M c , ADMc , DIDc , σ c ) ← Sign(pp, sk, M c , ADMc ) for c ∈ {0, 1}.
(b) For i = 1, · · · n, compute)(RI0i , Lu+2w−1 ) ← RS.RedInf(pp, vk, rk[i], M 0 , ADM0 , DID0 , σ 0 , MOD0 , Lu+2w−2i(RI1i , Lu+2w ) ← RS.RedInf(pp, vk, rk[i], M 1 , ADM1 , DID1 , σ 1 , MOD1 , Lu+2w−1
).
i

35

(c) For i = 1, ..., n, compute(M c′ , ADMc , DIDc , σ c′ ) ← RS.ThrRed(pp, vk, M c , ADMc , DIDc , σ c , {RIci }ni=1 ).
(d) If M 0′ ̸= M 1′ ∨ ADM0 ̸= ADM1 , return ⊥.
(e) Return (M b′ , ADMb , DIDb , σ b′ ). ( b is chosen by C in step 1.)
5. A outputs b∗ .
A t-out-of-n redactable signature scheme in the one-time redaction model (t, n)-RS satisﬁes
Priv-(t,n)-RSS

the privacy security if for all PPT adversaries A, the following advantage Adv(t,n)-RS,A=∗|Pr[b = b ] − 1/2| is negligible in λ.
Transparency. Transparency requires that except for a signer, n redactors, and a combiner,
it is infeasible to distinguish whether a signature directly comes from the signer or has beenredacted by redactors.
Deﬁnition 4.5 (Transparency). The privacy of a t-out-of-n redactable signature scheme in the
one-time redaction model (t, n)-RS Π is deﬁned by the following weak privacy game betweena challenger C and a PPT adversary A.
$

1. C chooses a bit b ←− {0, 1}, runs pp ← RS.Setup(1λ ), (vk, sk, {rk[i]}ni=1 ) ← RS.KeyGen(pp, t, n),
and gives (pp, vk) to an adversary A.
2. A is given access (throughout the entire game) to a sign oracle OSign (·, ·) such that
OSign (M, ADM), returns (M, ADM, DID, σ) ← RS.Sign(pp, sk, M, ADM).
3. A is given access (throughout the entire game) to a redact oracle ORedact (·, ·, ·, ·, ·). ORedact
is deﬁned as follows:
For an u-th query (M, ADM, DID, σ, MOD):Let w be the number of queries to OSign/Redact when A makes an u-th query to ORedact .
(a) (RIi , Lu+2w) ← RS.RedInf(pp, vk, rk[i], M, ADM, DID, σ, MOD, Lu+2w−1
) for
i
i
i = 1, ..., n.
(b) (M ′ , ADM, DID, σ ′ ) ← RS.ThrRed(pp, vk, M, ADM, DID, σ, {RIi }ni=1 ).
(c) Return (M ′ , ADM, DID, σ ′ ).

36

4. A is given access (throughout the entire game) to a sign or redact oracle OSign/Redact (·, ·, ·).
OSign/Redact is deﬁned as follows:
For an w-th query (M, ADM, MOD):Let u be the number of queries to ORedact when A makes an w-th query to OSign/Redact .
(a) Compute (M, ADM, DID0 , σ) ← RS.Sign(pp, sk, M, ADM).
(b) For i = 1, . . . n, compute(RIi , Lu+2w−1) ← RS.RedInf(pp, vk, rk[i], M, ADM, DID0 , σ, MOD, Lu+2w−2).
ii(c) Compute (M ′ , ADM, DID0 , σ 0 ) ← RS.ThrRed(pp, vk, M, ADM, DID0 , σ, {RIi }ni=1 ).
(d) Compute (M ′ , ADM, DID1 , σ 1 ) ← RS.Sign(pp, sk, M ′ , ADM).
(e) For i = 1, . . . n, Lu+2w← Lu+2w−1∪ {DID1 }.
ii(f) Return (M ′ , ADM, DIDb , σ b ).

5. A outputs b∗ .
A t-out-of-n redactable signature scheme in the one-time redaction model (t, n)-RS Π satisﬁes
Tran-(t,n)-RSS

the transparency security if for all PPT adversaries A, the following advantage Adv(t,n)-RS,A=∗|Pr[b = b ] − 1/2| is negligible in λ.
Theorem 4.6. If t-out-of-n redactable signature scheme in the one-time redaction model(t, n)-RS Π satisﬁes transparency, then it satisﬁes privacy.
We prove Theorem 4.6 in a similar way of [13, 21].
proof. Assume that PPT adversary APriv that wins the privacy game with probability 1/2 +ϵPriv where ϵPriv is non-negligible in λ. Let CTran be the challenger in transparency game.
Now we construct a PPT adversary BTran that wins the transparency game with probability
1/2 + ϵPriv /2 using APriv . The operation of BTran is following.
• BTran receives (pp, vk) from CTran , chooses a bit c ← {0, 1} and sends vk to APriv .
• For each query (M, ADM) of APriv to OSign , BTran queries (M, ADM) to OSign and gets
(M, ADM, DID, σ) and sends it to APriv .

37

• For each query (M 0 , ADM0 , MOD0 , M 1 , ADM1 , MOD1 ) of APriv to OLoRredact , BTran checks
M 0′ = M 1′ where M 0′ = M 0 /MOD0 and M 1′ = M 1 /MOD1 . If so, BTran queries(M c , ADMc , MODc ) to OSign/Redact and BTran returns its result to APriv . Otherwise, BTranreturns ⊥ to APriv .
• BTran receives a guess b∗ from APriv . If b∗ = c, BTran outputs 0, otherwise BTran outputs 1.
If b = 0, OSign/Redact always redacts and the view of APriv is the same as in the privacy
game. However, if b = 1, each signature is fresh and the output of APriv is useless to win thetransparency game. Therefore, the win probability of BTran in transparency game is ϵTran =1/2(1/2 + ϵPriv ) + 1/2 · 1/2 = 1/2 + ϵPriv /2. Therefore, the advantage of BTran in transparency
game is non-negligible in λ.

4.3

BGLS Aggregate Signature Scheme

Boneh, Gentry, Lynn, and Shacham [11] proposed the aggregate signature scheme which isbased on the Boneh-Lynn-Shacham (BLS) signature scheme [12]. Our construction of t-out-ofn redactable signature is based on the BGLS aggregate signature scheme. Here, we review thethe BGLS aggregate signature scheme ASBGLS = (ASBGLS .Setup, ASBGLS .KeyGen, ASBGLS .Sign,
ASBGLS .Verify, ASBGLS .Aggregate, ASBGLS .AggVerify) is given as follows.∗• ASBGLS .Setup(1λ ) :$$1. G = (p, G1 , G2 , GT , e) ← G(1λ ), g1 ←− G∗1 , g2 ←− G∗2 . (G is a type-2 pairing-group
generator)
2. Choose hash functions: H : {0, 1}∗ → G1 .
3. Return pp ← (G, g1 , g2 , H).
• ASBGLS .KeyGen(pp) :$1. x ←− Zp , X ← g2x .
2. Return (vk, sk) ← (X, x).
• ASBGLS .Sign(pp, sk, m) :∗If we remove two algorithms ASBGLS .Aggregate and ASBGLS .AggVerify from ASBGLS , then this scheme cor-

respond to the BLS signature scheme.

381. h ← H(m), σ ← hsk .
2. Return σ.
• ASBGLS .Verify(pp, vk, m, σ) :1. h ← H(m).
2. If e(σ, g2 ) = e(h, vk), return 1.
3. Otherwise return 0.
• ASBGLS .Aggregate(pp, (vk1 , . . . , vkr ), (m1 , . . . , mr ), (σ1 , . . . , σr )) :1. If there exists (i, j) ∈ [r] × [r] such that i ̸= j ∧ mi = mj , return ⊥.
2. If there exists i ∈ [r] suth that ASBGLS .Verify(pp, vki , mi , σi ) ̸= 0,
return ⊥.
Q
3. Σ ← ri=1 σi .
4. Return Σ.
• ASBGLS .AggVerify(pp, (vk1 , . . . , vkr ), (m1 , . . . , mr ), Σ) :1. If there exists i ∈ [r] suth that ASBGLS .Verify(pp, vki , mi , σi ) ̸= 0,
return 0.
2. For i = 1 to r, hi ← H(mi ).
Q
3. If e(Σ, g2 ) = ri=1 e (Hi , vki ), return 1.
4. Otherwise, return 0.
Boneh et al prove that the EUF-CMA security of [11] the BGLS aggregate signature scheme
under the co-CDH assumption in the ROM.

4.4

Shamir’s Secret Sharing Scheme

In order to construct a t-out-of-n redactable signature scheme, we use the (t, n)-Shamir’s secretsharing scheme [56]. The (t, n)-secret sharing scheme is composed of a dealer and n users.
The dealer decides a secret s, computes secret shares {si }ni=1 , and gives the secret share si tothe user i. If any t of n secret shares or more shares are collected, we can reconstruct thesecret s from them. While, with less than t secret shares, we cannot recover the secret s.
We refer to the (t, n)-shamir’s secret sharing scheme in [19].

391. The dealer chooses the secret s ∈ Z and sets a0 ← s.
2. The dealer chooses a1 , · · · , at−1 ∈ {0, · · · , p − 1} independently at random and gets thePt−1polynomial f (X) = i=0
ai X i .
3. The dealer computes f (i), sets si ← (i, f (i)), and sends the secret share si to the user i.
If we collect t or more secret shares, we can reconstruct the secret s by the Lagrange interpolation. Let J ⊂ {1, · · · ,n} and |J| = t. If we have secret shares {sj }j∈J = {(j, f (j))}j∈J , weQP
−1.
can compute s = i∈J f (i) j∈J,j̸=i j(j − i)

4.5

Our Construction

We give a concrete construction of t-out-of-n redactable signature scheme in one-time redaction
model (t, n)-RS Π1 . Let ℓ, d be polynomials in λ and M a message having a set data structure(i.e., M = {m1 , ..., mℓ }) and #M ≤ ℓ.
RS.Setup(1λ ) :1. Run G = (p, G1 , G2 , GT , e) ← G(1λ ).
$$2. Choose g1 ←− G∗1 , g2 ←− G∗2 .
3. Choose a hash function H : {0, 1}∗ → G1 .
4. Return pp = (G, g1 , g2 , H)
RS.KeyGen(pp, t, n) :$1. Choose x̃ ←− Zq , compute ỹ ← g2x̃ , and set (vkFix , skFix ) ← (ỹ, x̃).
$− Zq independently at random and gets the polynomial f (X) =2. Choose a0 , a1 , · · · , at−1 ←Pt−1i
i=0 ai X .
f (i)3. For i = 0 to n, compute xi ← f (i), yi ← g2 .
4. Set (vkAgg , skAgg ) ← (y0 , x0 ), rk[i] ← (i, xi ) for all i ∈ [n].
5. Set (vk, sk) ← ((vkFix , vkAgg , t, n), (skFix , skAgg )).
6. Return (vk, sk, {rk[i]}ni=1 ).

40

RS.Sign(pp, sk, M, ADM) : (Note that ADM is a set containing all blocks which must not be
redacted.):1. Parse sk as (skFix , skAgg ).
2. If ADM ⪯̸ M , (i.e., ADM ∩ M ̸= ADM.) then abort.
$

3. Choose document ID DID ←− {0, 1}d .
4. Compute hADM ← H(DID||ord(ADM)).
ord(ADM) denotes a lexicographic ordering to the elements in ADM.
5. For mj ∈ M , compute hmj ← H(DID||mj ).
Fix
6. Compute σFix ← hsk
ADM .

sk

sk

Agg
for mj ∈ M .
7. Compute σADM ← hADM
, σmj ← hmAggj

8. Compute Σagg ← σADM ·Q

mj ∈M σmj .

9. Set σ ← (σFix , Σagg ).
10. Return (M, ADM, DID, σ).
RS.Redact : RS.Redact is an interactive protocol between the combiner and n redactor. The
combiner interacts with the n redactors and ﬁnally outputs the redacted signature.
1. Each redactor i selects a modiﬁction instruction MODi . Let Li be the list which stores
DIDs, L0i = ∅, and Liu−1 the list which used in the input of u-th running of the PPT
algorithm RS.RedInf by the redactor i.
The redactor i runs RS.RedInf(pp, vk, rk[i], M, ADM, DID, σ, MODi , Lu−1).
i
RS.RedInf(pp, vk, rk[i], M, ADM, DID, σ, MODi , Lu−1):i(a) Parse vk as (vkFix , vkAgg , t, n) and σ as (σFix , Σagg ).
(b) If DID ∈ Lu−1
then abort.
i(c) Update Lui ← Liu−1 ∪ {DID}.
ADM(d) Check MODi ⪯ M . (i.e., MODi ∩ ADM = ∅ ∧ MODi ⊂ M .)41

(e) Compute hADM ← H(DID||ord(ADM)).
ord(ADM) denotes a lexicographic ordering to the elements in ADM.
(f) For mj ∈ M , compute hmj ← H(DID||mj ).
(g) If e(σFix , g2 ) ̸= e(hADM , vkFix ) then abort.
Q(h) If e(Σagg , g2 ) ̸= e (hADM , vkAgg ) · mj ∈M e(hmj , vkAgg ) then abort.
rk[i](i) For mj ∈ MODi , compute RIi,mj ← hmj .
(j) For mj ∈/ MODi , set RIi,mj ← ∅.
(k) Set a redaction information RIi of redactor i as RIi ← {RIi,mj }mj ∈M(l) Output (RIi , Lui ).
For one DID, redactor i runs RS.RedInf only once. This can be done by introducing atable Li .

2. Each redactor i sends (i, RIi ) to the combiner.
3. The combiner collects all n redaction information {RIi }ni=1 .
4. The combiner runs the PPT algorithm RS.ThrRed(pp, vk, M, ADM, DID, σ, {RIi }ni=1 ).
RS.ThrRed(vk, M, ADM, DID, σ, {RIi }ni=1 ) :(a) Parse vk as (vkFix , vkAgg , t, n) and σ as (σFix , Σagg ).
(b) Parse RIi as {RIi,mj }mj ∈M .
(c) For mj ∈ M , deﬁne RImj = {RIi,mj }ni=1 .
(d) Deﬁne MOD = {mj |mj ∈ M ∧ #RImj ≥ t}(e) For mj ∈ MOD, deﬁne InRImj ← {i ∈ N|{RIi,mj } ̸= ∅}.
(f) For mj ∈ MOD, choose subset Jmj ⊂ InRImj such that #Jmj = t.
γQ(g) For mj ∈ MOD, compute σmj ← i∈Jm RIi,mj i,Jmj ,jQwhere γi,Jmj = j∈Jm ,j̸=i j(j − i)−1 .
jQ(h) Compute σMOD ← mj ∈MOD σmj , Σ′agg ← Σagg /σMOD .
(i) Set M ′ ← M \{MOD}, σ ′ ← (σFix , Σ′agg ).

42

(j) Return (M ′ , ADM, DID, σ ′ ).
5. The combiner outputs (M ′ , ADM, DID, σ ′ ).
RS.Verify(pp, vk, M, ADM, DID, σ) :1. Parse vk as (vkFix , vkAgg , t, n) and σ as (σFix , Σagg ).
2. If ADM ∩ M ̸= ADM, return 0.
3. Compute hADM ← H(DID||ord(ADM)).
ord(ADM) denotes a lexicographic ordering to the elements in ADM.
4. For mj ∈ M , compute hmj ← H(DID||mj ).
5. If e(σFix , g2 ) ̸= e(hADM , vkFix ), return 0
6. If e(Σagg , g2 ) = e (hADM , vkAgg ) ·Q

mj ∈M e(hmj , vkAgg ), return 1. Otherwise output 0.

Correctness
If pp ← RS.Setup(1λ ), RS.KeyGen(pp, t, n), and (M, ADM, DID, σ) is honestly generated by the
RS.Sign and has not been processed by the RS.Redact protocol, RS.Verify(M, ADM, DID, σ) = 1
always holds. If (M, ADM, DID, σ) is honestly generated the RS.Sign and (M ′ , ADM, DID, σ ′ )is honestly redacted from (M, ADM, DID, σ) by RS.Redact protocol, (M ′ , ADM, DID, σ ′ ) passes
the veriﬁcation in the RS.Verify. Therefore, our construction of t-out-of-n redactable signaturescheme in the one-time redaction model satisﬁes correctness.

4.6

Security Proof for Unforgeability

Overview of Unforgeability Security Proof. Before describing unforgeability security
proof for our proposed scheme, we explain the outline of the proof. For convenience of our
security proof, we introduce new notations. Let qs be the total number of queries from anadversary to OSign , (Mi , ADMi ) an i-th input for OSign , (M i , ADMi , DIDi , σ i ) the i-th output
of OSign . We denote
QSign :=

qs[{(M , ADM , DID )},
i

i

i

QAD
Sign :=

qs[{(ADMi , DIDi )}.

i=1

i=1

43

Also, let qr be the total number of queries from an adversary to ORedact ,(M i , ADMi , DIDi , σ i , MODi ) an i-th input for ORedact , (M ′ i , ADMi , DIDi , σ ′ i ) the i-th output of
ORedact . We denote
QRedact :=qr[{(M ′ , ADMi , DIDi )}, QAD
Redact :=
i

i=1

qr
[

{(ADMi , DIDi )}.

i=1

We assume the following three types of PPT adversaries that breaks the unforgeability
security in our proposed scheme.
• An adversary A1 that outputs a forgery (M ∗ , DID∗ , ADM∗ , σ ∗ ) such that (ADM∗ , DID∗ ) ∈
/
AD
(QAD
Sign ∪ QRedact ).

• An adversary A2 that outputs a forgery (M ∗ , DID∗ , ADM∗ , σ ∗ ) which satisﬁes (ADM∗ , DID∗ ) ∈
∗
∗
AD
(QAD
Sign ∪ QRedact ). Moreover, there is M̃ such that (M̃ , ADM , DID ) ∈ (QSign ∪ QRedact ).

• An adversary A3 that outputs a forgery (M ∗ , DID∗ , ADM∗ , σ ∗ ) which satisﬁes (ADM∗ , DID∗ ) ∈
∗
∗
AD
(QAD
Sign ∪QRedact ). Moreover, there are no M̃ such that (M̃ , ADM , DID ) ∈ (QSign ∪QRedact )and M̃ ⊈ M .
To prove the theorem, for each Ai , we consider a sequential of games from the original
unforgeability game to game which is directly related to solving the co-CDH problem. Then,
We construct Bi which breaking the co-CDH assumption using Ai . B1 breaks the co-CDH∗
assumption using the forgery σFix
. In the case of B2 and B3 , they use the forgery Σ∗agg to breakthe co-CDH assumption. One diﬀerence between B2 and B3 is how to program the hash value.
Theorem 4.7. In the random oracle model, if the computational co-Diﬃe-Hellman problem
assumption holds, then our proposed t-out-of-n redactable signature scheme in the one-time
redaction model (t, n)-RS Π1 satisﬁes the unforgeability property.
proof. We consider three types of adversary described above.
Case 1:
We consider an adversary A1 that can generate a valid forgery with ϵUf1 against our proposal
redactable signature scheme. Let Game1−0 be the original unforgeability game in a redactablesignature scheme and Game1−5 be directly related to solving the computational co-DiﬃeHellman problem. Deﬁne AdvA1 [Game1−X ] as the advantage of an adversary A1 in Game1−X .

44• Game1−0 : Original unforgeability game in a redactable signature scheme.
AdvA1 [Game1−0 ] = ϵUf1
• Game1−1 : We change a key generation algorithm RS.KeyGen in Step 1.
$$

Choose x̃ ←− Zq , r̃ ←− Zq and compute u ← g2x̃ , ỹ ← g2x̃+r̃ .
Set (vkFix , skFix ) ← (ỹ, x̃ + r̃).
$• Game1−2 :We change a setting of the random oracle OH . Fix h ←− G2 and let T be atable that maintains a list of tuples ⟨v, w, b, c⟩ as explain below. We refer to this list for
the query to Oh . The initial state of T is empty. For queries v (i) to OH :– If ⟨v (i) , w(i) , ·, ·⟩ (Here, ‘·’ represents an arbitrary value) already appears in T, thenreturn w(i) .
$– Choose s(i) ←− Zq .
– Flip a biased coin c(i) ∈ {0, 1} such that Pr[c(i) = 0] = 1 − 1/(qs + 1) and Pr[c(i) =1] = 1/(qs + 1).
(i)– If c(i) = 0, compute w(i) = ϕ(g2 )b .
– If c(i) = 1, compute w(i) = h · ϕ(g2 )b .
(i)

– Insert ⟨v (i) , w(i) , s(i) , c(i) ⟩ in T and return w(i) .
• Game1−3 : We modify the signing algorithm RS.Sign in Step 4 as follows:– Set v (0) ← (DID||ord(ADM)).
– Query v (0) to OH . We assume ⟨v (0) , w(0) , b(0) , c(0) ⟩ to be the tuple in T for v (0) .
– If c(0) = 1, return ⊥ and abort.
• Game1−4 : We modify the signing algorithm RS.Sign in Step 6 as follows:– Compute σFix ← ϕ(u)b(0)· ϕ(g2 )r̃b .
(0)(A signature σFix can be generated without a knowledge of skFix .)• Game1−5 : We receive a valid forgery (M ∗ , ADM∗ DID∗ , σ ∗ ) from the adversary A1 , weoperate as follows:– Set v (0) ← (DID∗ ||ord(ADM∗ )).

45

– Query v (0) to OH . We assume ⟨v (0) , w(0) , s(0) , c(0) ⟩ to be the tuple in T for each v (0) .
– If c(0) = 0, then abort.
Lemma 4.8. The following equation holds.
AdvA1 [Game1−1 ] = AdvA1 [Game1−0 ].
Since the distribution of (vkFix , skFix ) in Game1−0 and Game1−1 are same.
Lemma 4.9. If H is the random oracle model, the following eqauation holds.
AdvA1 [Game1−2 ] = AdvA1 [Game1−1 ]Since the distribution of outputs of OH in Game1−1 and Game1−2 are identical.
Lemma 4.10. The following inequality holds.
AdvA1 [Game1−3 ] ≥ (1 − 1/(qs + 1))qs × AdvA1 [Game1−2 ].
Since the probability that each signing query does not abort at least 1 − 1/(qs + 1).
Lemma 4.11. The following equation holds.
AdvA1 [Game1−4 ] = AdvA1 [Game1−3 ].
Since outputs of Sign in Game1−3 and Game1−4 are same.
Lemma 4.12. The following inequality holds.
AdvA1 [Game1−5 ] ≥ (1/(qs + 1)) × AdvA1 [Game1−4 ].
Since the probability that the forged signature satisﬁes c(0) = 1 at least 1/(qs + 1).
To summarize from Lemma 4.8 to Lemma 4.12, the following holds.
(In the following equation, e represents the Napier’s constant.)
AdvA1 [Game1−5 ] ≥ (1 − 1/(qs + 1))qs × (1/(qs + 1)) × AdvA1 [Game1−0 ]≥ (1/e) × (1/(qs + 1)) × AdvA1 [Game1−0 ]Now we construct the algorithm B1 which breaking the computational co-Diﬃe-Hellman
assumption using the algorithm A1 . The operation of B1 for the input co-Diﬃe-Hellman
problem instance (g2 , g2α , h∗ ) is changed to h to h∗ and u to g2α in Game1−5 . Suppose B1 does
not abort receiving a forgery (M ∗ , ADM∗ , DID∗ , σ ∗ ) from A1 .

46

∗
∗
(0)
← (DID∗ ||ord(ADM∗ )) and computes w(0) ← h∗ · ϕ(g2 )b .
B1 parses σ ∗ as (σFix∗ , Σagg ), sets v(0)∗Since (M ∗ , ADM∗ , DID∗ , σ ∗ ) is valid and vkFix = g2α+r̃ , e(σFix, g2 ) = e((w(0) )α+r̃ , g2 ) holds. It∗∗
implies that σFix
= (w(0) )α+r̃ = (h∗ · ϕ(g2 )b )α+r̃ . Therefore, B1 computes (h∗ )α = σFix·(0)

(ϕ(u)b(0)· (h∗ )r̃ · ϕ(g2 )r̃b )−1 and outputs the solution (h∗ )α of the computational co-Diﬃe(0)Hellman problem instance (g2 , g2α , h∗ ).
Let ϵco-cdh is the probability that B1 break the computational co-Diﬃe-Hellman assumption.
We can bound the probability ϵco-cdh1 ≥ AdvA1 [Game 1−5] and ϵco-cdh1 ≥ (1/e)×(1/qs +1)×ϵuf1
holds. (e represents the Napier’s constant.) Hence, if ϵuf1 is non-negligiable in λ, B1 breaks
the computational co-Diﬃe-Hellman assumption with non-negligiable in ϵco-cdh1 .
Case 2:
We consider an adversary A2 that can generate a valid forgery with ϵuf2 against our proposal redactable signature scheme. Let Game2−0 be the original unforgeability game in aredactable signature scheme and Game2−6 be directly related to solve the computational
co-Diﬃe-Hellman problem. Deﬁne AdvA2 [Game2−X ] as the advantage of an adversary A2 in
Game2−X .
• Game2−0 : Original unforgeability game in a redactable signature scheme.
AdvA2 [Game2−0 ] = ϵuf2
• Game2−1 : We change a setting of ORedact .
We introduce a table Lu that store DIDs and L0 = ∅.
For a u-th query (M, ADM, DID, σ, MOD) to ORedact :– Parse vk as (vkFix , vkAgg , t, n) and σ as (σFix , Σagg ).
– If DID ∈ Lu−1 , then abort.
– Set Lu ← Lu−1 ∪ {DID}.
– If MOD ⊈ M ∨ MOD ∩ ADM ̸= ∅, then abort.
– Compute hADM ← H(DID||ord(ADM)).
ord(ADM) denotes a lexicographic ordering to the elements in ADM.
– For mj ∈ M , compute hmj ← H(DID||mj ).
– If e(σFix , g2 ) ̸= e(hADM , vkFix ), then abort.

47

– If e(Σagg , g2 ) ̸= e (hADM , vkAgg ) ·Q

mj ∈M e(hmj , vkAgg ), then abort.

– For mj ∈ MOD, compute σmj ← H(DID||mj )skAgg .
Q– Compute σMOD ← mj ∈MOD σmj , Σ′agg ← Σagg /σMOD .
– Set M ′ ← M \MOD, σ ′ ← (σFix , Σ′agg ).
– Return (M ′ , ADM, DID, σ ′ ).
(Redactions are done using skAgg instead of using {rk[i]}ni=1 .)• Game2−2 : We change settings of RS.KeyGen and OCorrupt .
– We change a key generation algorithm RS.KeyGen in Step 2 to 6.
$$∗ Choose x ←− Zq , r ←− Zq , compute u ← g x , y ← g2x+r .
∗ Set vkAgg ← y, skAgg ← x + r.
∗ Return (vk, sk) ← ((vkFix , vkAgg , t, n), (skFix , skAgg )).
(Redactor’s keys {rk[i]}ni=1 are not generated in the KeyGen.)– We change the setting of OCorrupt as follows:
Let CR is a list to store a redactor’s key information (i, rk[i])For a query i to OCorrupt ,∗ If (i, rk[i]) already appears in CR, then return rk[i].
$∗ Choose f (i) ←− Zq , set CR ← CR ∪ {(i, f (i))}.
∗ Return rk[i] ← (i, f (i)).
$• Game2−3 : We change a setting of the random oracle OH . Fix h ←− G2 and let T be atable that maintains a list of tuples ⟨v, w, b, c⟩ as explain below. We refer to this list for
the query to Oh . The initial state of T is empty. For queries v (i) to OH :– If ⟨v (i) , w(i) , ·, ·⟩ (Here, ‘·’ represents an arbitrary value) already appears in T, thenreturn w(i) .
$– Choose s(i) ←− Zq .
– Flip a biased coin c(i) ∈ {0, 1, 2} such that such that Pr[c(i) = 1] = 1−1/((ℓ+1)(qs +qr )+1), Pr[c(i) = 1] = 1/(2(ℓ+1)(qs +qr )+2), Pr[c(i) = 2] = 1/(2(ℓ+1)(qs +qr )+2).
(i)– If c(i) = 0, compute w(i) = ϕ(g2 )b .
– If c(i) = 1, compute w(i) = h · ϕ(g2 )b .
(i)

48

– If c(i) = 2, compute w(i) = h−1 · ϕ(g2 )b .
(i)

– Insert ⟨v (i) , w(i) , s(i) , c(i) ⟩ in T and return w(i) .
• Game2−4 :We modify the signing algorithm RS.Sign in Step 6 as follows:– Set v (0) ← (DID||ord(ADM)), v (j) ← (DID||mj ) (1 ≤ j ≤ #M ).
– Query v (j) (0 ≤ j ≤ #M ) to OH . We assume ⟨v (j) , w(j) , b(j) , c(j) ⟩ to be the tuple in
T for each v (j) (1 ≤ j ≤ #M ).
– If c(0) = 2, c(1) = 1, c(j) = 0 (2 ≤ ∀j ≤ #M ) or c(j) = 0 (0 ≤ ∀j ≤ #M ), go to
Step 6 of Sign. Otherwise return ⊥ and abort.
• Game2−5 : We modify the signing algorithm RS.Sign in Step 7, 8 as follows:– If c(0) = 2, c(1) = 1, c(j) = 0 (2 ≤ ∀j ≤ #M ),∗ Compute σADMm1 ← ϕ(u)b(0) +b(1)· ϕ(g2 )r(b(0) +b(1) )∗ For all mj ∈ M \{m1 }, compute σmj ← ϕ(u)bQ∗ Compute Σagg ← σADMm1 · mj ∈M \{m1 } σmj .

(j).

· ϕ(g2 )rb .
(j)– If c(j) = 0 (0 ≤ ∀j ≤ #M ),∗ Compute σADM ← ϕ(u)b(0)· ϕ(g2 )rb .
(0)∗ For all mj ∈ M , compute σmj ← ϕ(u)bQ∗ Compute Σagg ← σADM · mj ∈M σmj .

(j)· ϕ(g2 )rb .
(j)(By above modiﬁcation, a signature Σagg can be generated without a knowledge of theskAgg .)• Game2−6 : We change a setting of ORedact .
– Parse vk as (vkFix , vkAgg , t, n) and σ as (σFix , Σagg ).
– If DID ∈ Lu−1 , then abort.
– Set Lu ← Lu−1 ∪ {DID}.
– If MOD ⊈ M ∨ MOD ∩ ADM ̸= ∅, then abort.
– Set v (0) ← (DID||ord(ADM)), v (j) ← (DID||mj ) (1 ≤ j ≤ #M ).
– Query v (j) (0 ≤ j ≤ #MOD) to OH . We assume ⟨v (j) , w(j) , b(j) , c(j) ⟩ to be the tuple
in T for each v (j) (1 ≤ j ≤ #MOD).

49

– If e(σFix , g2 ) ̸= e(w(0) , vkFix ), then abort.
Q– If e(Σagg , g2 ) ̸= 0≤j≤#M e(w(j) , vkAgg ), then abort.
– If c(j) = 0 (∀mj ∈ MOD), go to next step. Otherwise return ⊥ and abort.
– For all mj ∈ MOD, compute σmj ← ϕ(u)b · ϕ(g2 )rb .
Q– Compute σMOD ← mj ∈MOD σmj , Σ′agg ← Σagg /σMOD .
(j)

(j)

– Set M ′ ← M \MOD, σ ′ ← (σFix , Σ′agg ).
– Return (M ′ , ADM, DID, σ ′ ).
(Redactions can be done without the knowledge of the skAgg .)• Game2−7 : We receiving the output forgery (M ∗ , ADM∗ , DID∗ , σ ∗ ) from the adversary
A3 ,– Set v (0) ← (DID∗ ||ord(ADM∗ )), v (j) ← (DID||m∗j ) (1 ≤ j ≤ #M ∗ ).
– Query v (j) (0 ≤ j ≤ #M ∗ ) to OH . We assume ⟨v (j) , w(j) , s(j) , c(j) ⟩ to be the tuple
in T for each v (j) (0 ≤ j ≤ #M ∗ ).
– If c(0) = 1 and c(j) = 0 (1 ≤ j ≤ #M ∗ ), then accept. Otherwise reject and abort.
Lemma 4.13. The following equation holds.
AdvA2 [Game2−1 ] = AdvA2 [Game2−0 ].
Since outputs of ORedact in Game2−0 and Game2−1 are same.
Lemma 4.14. The following equation holds.
AdvA2 [Game2−2 ] = AdvA2 [Game2−1 ].
To simplify the discussion, let A2 get rk[i], . . . , rk[t − 1] from OCorrupt . In [Game2−1 ], thefollowing equation holds.

 


a0
f (0)
1
0
0

 


 a1   f (1) 
 1
1
1

 



 


2
22
V  a2  =  f (2)  where V =  1
 .  


..
..
..
 ..  

 ...
.
.
.

 


at−1
f (t − 1)
1 t − 1 (t − 1)2

50

···

0

···

1

···

2t−1
..
.

···

· · · (t − 1)t−1






.




Since V is the Vandermonde matrix, V is the regular matrix. Distributions of (a0 , a1 , · · · , at−1 )and (f (0), f (1), . . . , f (t−1)) are identical. Therefore, distributions of (skAgg , rk[1], . . . , rk[t−1]) in [Game2−1 ] and [Game2−2 ] are same.
Lemma 4.15. If H is the random oracle model, the following equation holds.
AdvA2 [Game2−3 ] = AdvA2 [Game2−2 ].
Since the distribution of outputs of OH in Game2−3 and Game2−2 is identical.
Lemma 4.16. The following inequality holds.
AdvA2 [Game2−4 ] ≥ (1 − 1/((ℓ + 1)(qs + qr ) + 1))(ℓ+1)qs × AdvA2 [Game2−3 ].
Since the probability that each signing query does not abort at least(1 − 1/((ℓ + 1)(qs + qr ) + 1))(ℓ+1) .
Lemma 4.17. The following equation holds.
AdvA2 [Game2−5 ] = AdvA2 [Game2−4 ].
Since outputs of Sign in Game2−5 and Game2−4 are same.
Lemma 4.18. The following inequality holds.
AdvA2 [Game2−6 ] ≥ (1 − 1/((ℓ + 1)(qs + qr ) + 1))(ℓ+1)qr × AdvA2 [Game2−5 ].
Since the probability that each redaction query does not abort at least(1 − 1/((ℓ + 1)(qs + qr ) + 1))(ℓ+1) .
Lemma 4.19. The following inequality holds.
AdvA2 [Game2−7 ]≥

1
2(ℓ+1)(qs +qr )+2

1 − (ℓ+1)(qs1+qr )+1

2



+

2

1
2(ℓ+1)(qs +qr )+2

2 × AdvA2 [Game2−6 ]= (1/(4(ℓ + 1)2 (qs + qr )2 + 1)) × AdvA2 [Game2−6 ].
Since an output (M ∗ , ADM∗ , DID∗ , σ ∗ ) satisﬁes (c(0) , c(1) ) = (0, 0) or (2, 1).

51

To summarize from Lemma 4.13 to Lemma 4.19, the following holds.
(In the following equation, e represents the Napier’s constant.)
AdvA2 [Game2−7 ] ≥ (1 − 1/((ℓ + 1)(qs + qr ) + 1))(ℓ+1)(qs +qr )× 1/(4(ℓ + 1)2 (qs + qr )2 + 1) × AdvA2 [Game2−0 ]≥ (1/e) × (1/(4(ℓ + 1)2 (qs + qr )2 + 1)) × AdvA2 [Game2−0 ]Now we construct the algorithm B2 which breaking the computational co-Diﬃe-Hellman
assumption using the algorithm A2 . The operation of B2 for the input co-Diﬃe-Hellman problem instance (g2 , g2α , h∗ ) is changed to h in Game2−7 to h∗ and u to g2α .
Suppose B2 do not abort receiving a forgery (M ∗ , ADM∗ , DID∗ , σ ∗ ) from A2 . B3 parses σ ∗∗∗(j)as (σADM← (DID∗ ||m∗j ) (1 ≤ j ≤ #M ∗ ), and computes w(1) ← h · ϕ(u)b ·∗ , Σagg ), sets v
Q#M ∗
(1)
(j)
(j)
∗
∗
ϕ(g2 )rb , w(j) ← ϕ(u)b ·ϕ(g2 )rb (2 ≤ j ≤ #M ∗ ). Then B3 computes σm∗ ← Σagg /j=2 σmj .
1

∗
∗
α+r
∗
(1) α+r∗∗
Since (M , ADM , DID , σ ) is valid signature and vkAgg = g2 , e(σm∗1 , g2 ) = e (w ) , g2
(1)∗(1) α+r
holds. It implies that σm)= (h∗ · ϕ(g2 )b )α+r . Therefore, B3 computes (h∗ )α =∗ = (w
1
(1)

∗
b
σm
∗ · (ϕ(u)1(1)· (h∗ )r · ϕ(g2 )rb )−1 and outputs the solution (h∗ )α of the computational co(1)Diﬃe-Hellman problem instance (g2 , g2α , h∗ ).
Let ϵco-cdh2 is the probability that B2 break the computational co-Diﬃe-Hellman assumption. We can bound the probability ϵco-cdh2 ≥ AdvA2 [Game2−7 ] and ϵco-cdh2 ≥ (1/e) × (1/(4(ℓ +1)2 (qs + qr )2 + 1)) × ϵuf2 holds. (e represents the Napier’s constant.) If ϵuf2 is non-negligiable inλ, B2 breaks the computational co-Diﬃe-Hellman assumption with non-negligiable in ϵco-cdh2 .
Case 3:
We consider an adversary A3 that can generate a valid forgery with ϵuf3 against our proposal redactable signature scheme. Let Game3−0 be the original unforgeability game in aredactable signature scheme and Game3−6 be directly related to solve the computational
co-Diﬃe-Hellman problem. Deﬁne AdvA3 [Game3−X ] as the advantage of an adversary A3 in
Game3−X .
• Game3−0 : Original unforgeability game in a redactable signature scheme.
AdvA3 [Game3−0 ] = ϵuf3
• Game3−1 : Game3−1 is the same as Game2−1 .
• Game3−2 : Game3−2 is the same as Game2−2 .

52$• Game3−3 : We change a setting of the random oracle OH . Fix h ←− G2 and let T be atable that maintains a list of tuples ⟨v, w, b, c⟩ as explain below. We refer to this list for
the query to Oh . The initial state of T is empty. For queries v (i) to OH :– If ⟨v (i) , w(i) , ·, ·⟩ (Here, ‘·’ represents an arbitrary value) already appears in T, thenreturn w(i) .
$– Choose s(i) ←− Zq .
– Flip a biased coin c(i) ∈ {0, 1} such that Pr[c(i) = 0] = 1 − 1/((ℓ + 1)(qs + qr ) + ℓ),Pr[c(i) = 1] = 1/((ℓ + 1)(qs + qr ) + ℓ).
(i)– If c(i) = 0, compute w(i) = ϕ(g2 )b .
– If c(i) = 1, compute w(i) = h · ϕ(g2 )b .
(i)

– Insert ⟨v (i) , w(i) , s(i) , c(i) ⟩ in T and return w(i) .
• Game3−4 :We modify the signing algorithm RS.Sign in Step 6 as follows:– Set v (0) ← (DID||ord(ADM)), v (j) ← (DID||mj ) (1 ≤ j ≤ #M ).
– Query v (j) (0 ≤ j ≤ #M ) to OH . We assume ⟨v (j) , w(j) , b(j) , c(j) ⟩ to be the tuple in
T for each v (j) (1 ≤ j ≤ #M ).
– If c(j) = 0 (0 ≤ ∀j ≤ #M ), go to Step 6 of RS.Sign. Otherwise return ⊥ and abort.
• Game3−5 : We modify the signing algorithm RS.Sign in Step 7, 8 as follows:– Compute σADM ← ϕ(u)b(0)· ϕ(g2 )rb .
(0)– For all mj ∈ M , compute σmj ← ϕ(u)bQ– Compute Σagg ← σADM · mj ∈M σmj .

(j)· ϕ(g2 )rb .
(j)(By above modiﬁcation, a signature Σagg can be generated without a knowledge of theskAgg .)• Game3−6 : We change a setting of ORedact .
– Parse vk as (vkFix , vkAgg , t, n) and σ as (σFix , Σagg ).
– If DID ∈ Lu−1 , then abort.
– Set Lu ← Lu−1 ∪ {DID}.
– If MOD ⊈ M ∨ MOD ∩ ADM ̸= ∅, then abort.

53

– Set v (0) ← (DID||ord(ADM)), v (j) ← (DID||mj ) (1 ≤ j ≤ #M ).
– Query v (j) (0 ≤ j ≤ #MOD) to OH . We assume ⟨v (j) , w(j) , b(j) , c(j) ⟩ to be the tuple
in T for each v (j) (1 ≤ j ≤ #MOD).
– If e(σFix , g2 ) ̸= e(w(0) , vkFix ), then abort.
Q– If e(Σagg , g2 ) ̸= 0≤j≤#M e(w(j) , vkAgg ), then abort.
– If c(j) = 0 (∀mj ∈ MOD), go to next step. Otherwise return ⊥ and abort.
– For all mj ∈ MOD, compute σmj ← ϕ(u)b · ϕ(g2 )rb .
Q– Compute σMOD ← mj ∈MOD σmj , Σ′agg ← Σagg /σMOD .
(j)

(j)

– Set M ′ ← M \MOD, σ ′ ← (σFix , Σ′agg ).
– Return (M ′ , ADM, DID, σ ′ ).
(Redactions can be done without the knowledge of the skAgg .)• Game3−7 : We receiving the output forgery (M ∗ , ADM∗ , DID∗ , σ ∗ ) from the adversary
A3 ,– Set v (0) ← (DID∗ ||ord(ADM∗ )), v (j) ← (DID||m∗j ) (1 ≤ j ≤ #M ∗ ).
– Query v (j) (0 ≤ j ≤ #M ∗ ) to OH . We assume ⟨v (j) , w(j) , s(j) , c(j) ⟩ to be the tuple
in T for each v (j) (0 ≤ j ≤ #M ∗ ).
– If c(1) = 1 and c(j) = 0 (2 ≤ j ≤ #M ∗ ), then accept. Otherwise reject and abort.
Lemma 4.20. If H is the random oracle model, the following equation holds.
AdvA3 [Game3−3 ] = AdvA1 [Game3−2 ]Since the distribution of outputs of OH in Game3−3 and Game3−2 is identical.
Lemma 4.21. The following inequality holds.
AdvA3 [Game3−4 ] ≥ (1 − 1/((ℓ + 1)(qs + qr ) + ℓ))(ℓ+1)qs × AdvA3 [Game3−3 ].
Since the probability that each signing query does not abort at least(1 − 1/((ℓ + 1)(qs + qr ) + (ℓ + 1)))(ℓ+1) .
Lemma 4.22. The following equation holds.
AdvA3 [Game3−5 ] = AdvA3 [Game3−4 ].

54Since outputs of Sign in Game3−5 and Game3−4 are same.
Lemma 4.23. The following inequality holds.
AdvA3 [Game3−6 ] ≥ (1 − 1/((ℓ + 1)(qs + qr ) + ℓ))(ℓ+1)qr × AdvA3 [Game3−5 ].
Since the probability that each redaction query does not abort at least(1 − 1/((ℓ + 1)(qs + qr ) + ℓ))(ℓ+1) .
Lemma 4.24. The following inequality holds.
AdvA3 [Game3−7 ] ≥(1 − 1/((ℓ + 1)(qs + qr ) + ℓ))ℓ−1
× (1/((ℓ + 1)(qs + qr ) + ℓ)) × AdvA3 [Game3−6 ].
Since an output (M ∗ , ADM∗ , DID∗ , σ ∗ ) satisﬁes c(0) = 0. The probability that (M ∗ , ADM∗ , DID∗ , σ ∗ )satisﬁes c(1) = 1 and c(i) = 0 (2 ≤ i ≤ #M ∗ ) at least (1 − 1/((ℓ + 1)(qs + qr ) + ℓ))(ℓ−1) ×(1 − 1/((ℓ + 1)(qs + qr ) + ℓ)).
To summarize from Lemma 4.13, Lemma 4.14, and from Lemma 4.20 to Lemma 4.24, thefollowing holds. (In the following equation, e represents the Napier’s constant.)
AdvA3 [Game3−7 ] ≥ (1 − 1/((ℓ + 1)(qs + qr ) + ℓ))(ℓ+1)(qs +qr )+ℓ−1
× (1/((ℓ + 1)(qs + qr ) + ℓ)) × AdvA3 [Game3−0 ]≥ (1/e) × (1/((ℓ + 1)(qs + qr ) + ℓ)) × AdvA3 [Game3−0 ]Now we construct the algorithm B3 which breaking the computational co-Diﬃe-Hellman
assumption using the algorithm A3 . The operation of B3 for the input co-Diﬃe-Hellman problem instance (g2 , g2α , h∗ ) is changed to h in Game3−7 to h∗ and u to g2α .
Suppose B3 do not abort receiving a forgery (M ∗ , ADM∗ , DID∗ , σ ∗ ) from A3 . B3 parses σ ∗∗∗(j)← (DID∗ ||m∗j ) (1 ≤ j ≤ #M ∗ ), and computes w(1) ← h · ϕ(u)b ·as (σADM∗ , Σagg ), sets v
Q#M ∗
(1)
(j)
(j)
∗
∗
ϕ(g2 )rb , w(j) ← ϕ(u)b ·ϕ(g2 )rb (2 ≤ j ≤ #M ∗ ). Then B3 computes σm∗ ← Σagg /j=2 σmj .
1

∗
∗
α+r
∗
∗
∗
(1) α+r
Since (M , ADM , DID , σ ) is valid signature and vkAgg = g2 , e(σm∗1 , g2 ) = e (w ) , g2
(1)∗(1) α+r
holds. It implies that σm)= (h∗ · ϕ(g2 )b )α+r . Threfore, B3 computes (h∗ )α =∗ = (w
1
(1)

∗
b
σm
∗ · (ϕ(u)1(1)· (h∗ )r · ϕ(g2 )rb )−1 and outputs the solution (h∗ )α of the computational co(1)Diﬃe-Hellman problem instance (g2 , g2α , h∗ ).
Let ϵco-cdh3 is the probability that B3 break the computational co-Diﬃe-Hellman assumption. We can bound the probability ϵco-cdh3 ≥ AdvA3 [Game3−7 ] and ϵco-cdh3 ≥ (1/e) × (1/((ℓ +1)(qs +qr )+ℓ))×ϵuf3 holds. (e represents the Napier’s constant.) Hence, if ϵuf3 is non-negligiablein λ, B3 breaks the computational co-Diﬃe-Hellman assumption with non-negligiable in ϵco-cdh3 .

55

4.7

Security Proof for Transparency

Theorem 4.25. Our proposed t-out-of-n redactable signature scheme in the one-time redaction model (t, n)-RS Π1 satisﬁes the transparency.
proof. We proceed by a sequence of games. Deﬁne AdvA [Gamei ] as the advantage of an
adversary A in Gamei .
• Game0 : Original transparency game in a redactable signature scheme.
• Game1 : We change the redaction algorithm RS.Redact in OSign/Redact .
– Skip the step 2 of RS.RedInf.
Let qr be the total number of queries from an adversary A to ORedact . Then, |AdvA [Game1 ] −AdvA [Game0 ]| ≤ qr × qr /2d holds. We consider distribution of output OSign/Redact in caseof b = 0 and b = 1 of Game1 . Given an input (M, ADM, MOD) to OSign/Redact , OSign/Redact
compute• (M, ADM, DID0 , σ) ← Sign(pp, sk, M, ADM).
• RIi ← RS.RedInf(pp, vk, rk[i], M, ADM, DID0 , σ, MOD) for 1 ≤ i ≤ n.
• (M ′ , ADM′ , DID0 , σ0 ) ← RS.ThrRed(pp, vk, M, ADM, DID0 , σ, {RIi }ni=1 ).
• (M ′ , ADM′ , DID1 , σ1 ) ← Sign(pp, sk, M ′ , ADM′ ).
Distributions of DID0 and DID1 in Game1 are identical and OSign/Redact skips the step 2
of RS.RedInf. Therefore, distributions of {(M ′ , ADM′ , DID0 , σ0 )} and {(M ′ , ADM′ , DID1 , σ1 )}outputted by OSign/Redact are identical. It means that AdvA [Game1 ] = 1/2. Let ϵTran isthe advantage of an adversary A in original Game0 . We can bound the probability ϵTran ≤qr ×qr /2d +1/2. Therefore, our proposed t-out-of-n redactable signature scheme in the one-time
redaction model (t, n)-RS Π1 satisﬁes transparency.
By Theorem 4.6 and Theorem 4.25, our proposed scheme satisﬁes the privacy.

56

Chapter 5
Conclusion
In this thesis, ﬁrst, we give a new security proof for the synchronized aggregate signaturescheme by Lee et al. [38] under the OT-EUF-CMA security for the DSMCL scheme in theROM. Since the OT-EUF-CMA security for the DSMCL scheme is proven under the 1-MSDH-2
assumption, our result shows that the aggregate signature by Lee et al. [38] can be provenunder the non-interactive and static assumption in the ROM.
However, there still have problems for the security of the synchronized aggregate signaturescheme by Lee et al. [38]. First, the 1-MSDH-2 assumption is not standard assumption, it isdesirable that the security is proven under a standard assumption (e.g., CDH assumption).
Second, we prove the EUF-CMA for the aggregate signature scheme by Lee et al. in the certify
key model. This model limits the use scenarios for the synchronized aggregate signaturescheme. Removing the certify key model is an important open problem for practicality.
Second, we introduce the new notion of t-out-of-n redactable signature. Then we construct
the t-out-of-n redactable signature scheme based on the aggregate signature scheme by Bonehet al. [11] and Shamir’s secret sharing schemes. Then, we prove that our construction satisﬁes
unforgeability and transparency.
However, our proposed model supports only the one-time redaction model which allows
redacting signed message only one time for each signature. Our construction Π1 does notsatisfy the unforgeability in a model that allows redacting signed message many times. For
example, M = {m1 , m2 , m3 } and ADM = ∅, an adversary who does the following operation
generates a valid forgery in a multiple redactions model.
1. Given vk from C.
2. Query (M, ADM) to OSign and get (M, ADM, DID, σ).

57

3. Let MOD1 = {m1 } MOD2 = {m2 }. Query (M, ADM, DID, σ, MOD1 ) to ORedact and get(M ′ , ADM, DID, σ ′ ) and query (M ′ , ADM, DID, σ ′ , MOD2 ) to ORedact and get (M ′′ , ADM,
DID, σ ′′ ).
′′′4. Parse σ as (σFix , Σagg ), σ ′ as (σFix, Σ′agg ), and σ ′′ as (σFix, Σ′′agg ).

5. Compute σm1 ← Σagg · (Σ′agg )−1 , Σ∗agg ← σm1 · Σ′′agg .
6. Set M ∗ ← {m1 , m3 }, σ ∗ ← (σFix , Σ∗agg ) and output (M ∗ , DID, ADM, σ ∗ )Giving a construction of (t, n)-RS in the multiple redactions model is an interesting open
problem.

58

Bibliography[1] J. H. Ahn, M. Green, and S. Hohenberger. Synchronized aggregate signatures: newdeﬁnitions, constructions and applications. In Proceedings of the 17th ACM Conference
on Computer and Communications Security, CCS 2010, Chicago, Illinois, USA, October
4-8, 2010, pages 473–484, 2010. URL: https://doi.org/10.1145/1866307.1866360,
doi:10.1145/1866307.1866360.
[2] G. Ateniese, D. H. Chou, B. de Medeiros, and G. Tsudik. Sanitizable signatures. In
S. D. C. di Vimercati, P. F. Syverson, and D. Gollmann, editors, Computer Security ESORICS 2005, 10th European Symposium on Research in Computer Security, Milan,
Italy, September 12-14, 2005, Proceedings, volume 3679 of Lecture Notes in Computer
Science, pages 159–177. Springer, 2005. URL: https://doi.org/10.1007/11555827_10,
doi:10.1007/11555827\_10.
[3] M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designingeﬃcient protocols. In CCS ’93, Proceedings of the 1st ACM Conference on Computerand Communications Security, Fairfax, Virginia, USA, November 3-5, 1993., pages 62–
73, 1993. URL: http://doi.acm.org/10.1145/168588.168596, doi:10.1145/168588.
168596.
[4] A. Bender, J. Katz, and R. Morselli. Ring signatures: Stronger deﬁnitions, and constructions without random oracles. In Theory of Cryptography, Third Theory of Cryptography
Conference, TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings, pages 60–79,
2006. URL: https://doi.org/10.1007/11681878_4, doi:10.1007/11681878\_4.
[5] D. Bernhard, G. Fuchsbauer, E. Ghadaﬁ, N. P. Smart, and B. Warinschi. Anonymous
attestation with user-controlled linkability. Int. J. Inf. Sec., 12(3):219–249, 2013. URL:
https://doi.org/10.1007/s10207-013-0191-z, doi:10.1007/s10207-013-0191-z.

59[6] P. Bichsel, J. Camenisch, G. Neven, N. P. Smart, and B. Warinschi. Get shorty via
group signatures without encryption. In Security and Cryptography for Networks, 7thInternational Conference, SCN 2010, Amalﬁ, Italy, September 13-15, 2010. Proceedings,
pages 381–398, 2010. URL: https://doi.org/10.1007/978-3-642-15317-4_24, doi:
10.1007/978-3-642-15317-4\_24.
[7] A. Bilzhause, H. C. Pöhls, and K. Samelin. Position paper: The past, present, andfuture of sanitizable and redactable signatures. In Proceedings of the 12th International
Conference on Availability, Reliability and Security, Reggio Calabria, Italy, August 29 September 01, 2017, pages 87:1–87:9. ACM, 2017. URL: https://doi.org/10.1145/
3098954.3104058, doi:10.1145/3098954.3104058.
[8] A. Boldyreva, C. Gentry, A. O’Neill, and D. H. Yum. Ordered multisignatures andidentity-based sequential aggregate signatures, with applications to secure routing. In
Proceedings of the 2007 ACM Conference on Computer and Communications Security,
CCS 2007, Alexandria, Virginia, USA, October 28-31, 2007, pages 276–285, 2007. URL:
https://doi.org/10.1145/1315245.1315280, doi:10.1145/1315245.1315280.
[9] D. Boneh and X. Boyen. Short signatures without random oracles. In Advances in
Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings, pages 56–73, 2004. URL: https://doi.org/10.1007/978-3-540-24676-3_4,
doi:10.1007/978-3-540-24676-3\_4.
[10] D. Boneh, X. Boyen, and E. Goh. Hierarchical identity based encryption with constant size ciphertext.

In Advances in Cryptology - EUROCRYPT 2005, 24th An-

nual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, pages 440–456, 2005. URL:
https://doi.org/10.1007/11426639_26, doi:10.1007/11426639\_26.
[11] D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and veriﬁably encryptedsignatures from bilinear maps. In Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques,
Warsaw, Poland, May 4-8, 2003, Proceedings, pages 416–432, 2003.

URL: https://doi.org/10.1007/3-540-39200-9_26, doi:10.1007/3-540-39200-9\_26.

60

[12] D. Boneh, B. Lynn, and H. Shacham. Short signatures from the weil pairing. In C. Boyd,
editor, Advances in Cryptology - ASIACRYPT 2001, 7th International Conference on the
Theory and Application of Cryptology and Information Security, Gold Coast, Australia,
December 9-13, 2001, Proceedings, volume 2248 of Lecture Notes in Computer Science,
pages 514–532. Springer, 2001. URL: https://doi.org/10.1007/3-540-45682-1_30,
doi:10.1007/3-540-45682-1\_30.
[13] C. Brzuska, H. Busch, Ö. Dagdelen, M. Fischlin, M. Franz, S. Katzenbeisser, M. Manulis,
C. Onete, A. Peter, B. Poettering, and D. Schröder. Redactable signatures for treestructured data: Deﬁnitions and constructions. In J. Zhou and M. Yung, editors, Applied
Cryptography and Network Security, 8th International Conference, ACNS 2010, Beijing,
China, June 22-25, 2010. Proceedings, volume 6123 of Lecture Notes in Computer Science,
pages 87–104, 2010. URL: https://doi.org/10.1007/978-3-642-13708-2_6, doi:10.
1007/978-3-642-13708-2\_6.
[14] J. Camenisch, M. Dubovitskaya, K. Haralambiev, and M. Kohlweiss. Composable andmodular anonymous credentials: Deﬁnitions and practical constructions. In T. Iwata
and J. H. Cheon, editors, Advances in Cryptology - ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security,
Auckland, New Zealand, November 29 - December 3, 2015, Proceedings, Part II, volume9453 of Lecture Notes in Computer Science, pages 262–288. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48800-3_11, doi:10.1007/978-3-662-48800-3\_11.
[15] J. Camenisch, S. Hohenberger, and M. Ø. Pedersen. Batch veriﬁcation of short signatures. In Advances in Cryptology - EUROCRYPT 2007, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain,
May 20-24, 2007, Proceedings, pages 246–263, 2007. URL: https://doi.org/10.1007/
978-3-540-72540-4_14, doi:10.1007/978-3-540-72540-4\_14.
[16] J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials frombilinear maps. In Advances in Cryptology - CRYPTO 2004, 24th Annual International
CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings,
pages 56–72, 2004. URL: https://doi.org/10.1007/978-3-540-28628-8_4, doi:10.
1007/978-3-540-28628-8\_4.

61

[17] S. Canard, D. Pointcheval, O. Sanders, and J. Traoré. Divisible e-cash made practical. In Public-Key Cryptography - PKC 2015 - 18th IACR International Conference on
Practice and Theory in Public-Key Cryptography, Gaithersburg, MD, USA, March 30- April 1, 2015, Proceedings, pages 77–100, 2015. URL: https://doi.org/10.1007/
978-3-662-46447-2_4, doi:10.1007/978-3-662-46447-2\_4.
[18] D. Chaum. Security without identiﬁcation: Transaction systems to make big brother
obsolete. Commun. ACM, 28(10):1030–1044, 1985. URL: https://doi.org/10.1145/
4372.4373, doi:10.1145/4372.4373.
[19] H. Delfs and H. Knebl. Introduction to Cryptography - Principles and Applications,Third Edition. Information Security and Cryptography. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47974-2, doi:10.1007/978-3-662-47974-2.
[20] D. Demirel, D. Derler, C. Hanser, H. Pöhls, D. Slamanig, and G. Traverso. PRISMACLOUD D4.4: Overview of Functional and Malleable Signature Schemes. 2015.
[21] D. Derler, H. C. Pöhls, K. Samelin, and D. Slamanig. A general framework for redactablesignatures and new constructions. In S. Kwon and A. Yun, editors, Information Security and Cryptology - ICISC 2015 - 18th International Conference, Seoul, South Korea, November 25-27, 2015, Revised Selected Papers, volume 9558 of Lecture Notes
in Computer Science, pages 3–19. Springer, 2015. URL: https://doi.org/10.1007/
978-3-319-30840-1_1, doi:10.1007/978-3-319-30840-1\_1.
[22] S. D. Galbraith, K. G. Paterson, and N. P. Smart. Pairings for cryptographers. Discrete
Applied Mathematics, 156(16):3113–3121, 2008. URL: https://doi.org/10.1016/j.
dam.2007.12.010, doi:10.1016/j.dam.2007.12.010.
[23] C. Gentry and Z. Ramzan. Identity-based aggregate signatures. In Public Key Cryptography - PKC 2006, 9th International Conference on Theory and Practice of Public-Key
Cryptography, New York, NY, USA, April 24-26, 2006, Proceedings, pages 257–273, 2006.
URL: https://doi.org/10.1007/11745853_17, doi:10.1007/11745853\_17.
[24] S. Haber, Y. Hatano, Y. Honda, W. G. Horne, K. Miyazaki, T. Sander, S. Tezoku,
and D. Yao. Eﬃcient signature schemes supporting redaction, pseudonymization, anddata deidentiﬁcation. In M. Abe and V. D. Gligor, editors, Proceedings of the 2008
ACM Symposium on Information, Computer and Communications Security, ASIACCS

62

2008, Tokyo, Japan, March 18-20, 2008, pages 353–362. ACM, 2008. URL: https://doi.org/10.1145/1368310.1368362, doi:10.1145/1368310.1368362.
[25] G. Hartung, B. Kaidel, A. Koch, J. Koch, and A. Rupp. Fault-tolerant aggregate signatures. In Public-Key Cryptography - PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 69, 2016, Proceedings, Part I, pages 331–356, 2016. URL: https://doi.org/10.1007/
978-3-662-49384-7_13, doi:10.1007/978-3-662-49384-7\_13.
[26] S. Hohenberger, V. Koppula, and B. Waters. Universal signature aggregators. In Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on
the Theory and Applications of Cryptographic Techniques, Soﬁa, Bulgaria, April 2630, 2015, Proceedings, Part II, pages 3–34, 2015. URL: https://doi.org/10.1007/
978-3-662-46803-6_1, doi:10.1007/978-3-662-46803-6\_1.
[27] S. Hohenberger, A. Sahai, and B. Waters. Full domain hash from (leveled) multilinear
maps and identity-based aggregate signatures. In Advances in Cryptology - CRYPTO
2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22,
2013. Proceedings, Part I, pages 494–512, 2013.

URL: https://doi.org/10.1007/

978-3-642-40041-4_27, doi:10.1007/978-3-642-40041-4\_27.
[28] S. Hohenberger and B. Waters.
sumption.

Short and stateless signatures from the RSA as-

In Advances in Cryptology - CRYPTO 2009, 29th Annual International

Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings,
pages 654–670, 2009. URL: https://doi.org/10.1007/978-3-642-03356-8_38, doi:
10.1007/978-3-642-03356-8\_38.
[29] S. Hohenberger and B. Waters. Synchronized aggregate signatures from the RSA assumption. In J. B. Nielsen and V. Rijmen, editors, Advances in Cryptology - EUROCRYPT
2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part II, volume10821 of Lecture Notes in Computer Science, pages 197–229. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-78375-8_7, doi:10.1007/978-3-319-78375-8\_7.
[30] T. Izu, M. Izumi, N. Kunihiro, and K. Ohta. Yet another sanitizable and deletablesignatures. In 25th IEEE International Conference on Advanced Information Networking
and Applications Workshops, WAINA 2011, Biopolis, Singapore, March 22-25, 2011,63

pages 574–579. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/WAINA.
2011.117, doi:10.1109/WAINA.2011.117.
[31] T. Izu, N. Kanaya, M. Takenaka, and T. Yoshioka. PIATS: A partially sanitizable signature scheme. In Information and Communications Security, 7th International Conference,
ICICS 2005, Beijing, China, December 10-13, 2005, Proceedings, pages 72–83, 2005. URL:
https://doi.org/10.1007/11602897_7, doi:10.1007/11602897\_7.
[32] T. Izu, N. Kunihiro, K. Ohta, M. Sano, and M. Takenaka. Sanitizable and deletablesignature. In K. Chung, K. Sohn, and M. Yung, editors, Information Security Applications, 9th International Workshop, WISA 2008, Jeju Island, Korea, September 23-25,
2008, Revised Selected Papers, volume 5379 of Lecture Notes in Computer Science, pages
130–144. Springer, 2008.

URL: https://doi.org/10.1007/978-3-642-00306-6_10,

doi:10.1007/978-3-642-00306-6\_10.
[33] T. Izu, N. Kunihiro, K. Ohta, M. Sano, and M. Takenaka. Yet another sanitizablesignature from bilinear maps. In Proceedings of the The Forth International Conference
on Availability, Reliability and Security, ARES 2009, March 16-19, 2009, Fukuoka, Japan,
pages 941–946. IEEE Computer Society, 2009. URL: https://doi.org/10.1109/ARES.
2009.14, doi:10.1109/ARES.2009.14.
[34] T. Izu, N. Kunihiro, K. Ohta, M. Takenaka, and T. Yoshioka. A sanitizable signaturescheme with aggregation. In E. Dawson and D. S. Wong, editors, Information Security Practice and Experience, Third International Conference, ISPEC 2007, Hong Kong,
China, May 7-9, 2007, Proceedings, volume 4464 of Lecture Notes in Computer Science,
pages 51–64. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-72163-5_6,
doi:10.1007/978-3-540-72163-5\_6.
[35] R. Johnson, D. Molnar, D. X. Song, and D. A. Wagner. Homomorphic signature schemes.
In B. Preneel, editor, Topics in Cryptology - CT-RSA 2002, The Cryptographer’s Trackat the RSA Conference, 2002, San Jose, CA, USA, February 18-22, 2002, Proceedings,
volume 2271 of Lecture Notes in Computer Science, pages 244–262. Springer, 2002. URL:
https://doi.org/10.1007/3-540-45760-7_17, doi:10.1007/3-540-45760-7\_17.
[36] E. Kiltz, A. Mityagin, S. Panjwani, and B. Raghavan. Append-only signatures. In
L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, and M. Yung, editors, Automata,64

Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, volume 3580 of Lecture Notes in Computer Science, pages 434–445. Springer, 2005. URL: https://doi.org/10.1007/11523468_36,
doi:10.1007/11523468\_36.
[37] S. Krenn, H. C. Pöhls, K. Samelin, and D. Slamanig.

Protean signature schemes.

In J. Camenisch and P. Papadimitratos, editors, Cryptology and Network Security 17th International Conference, CANS 2018, Naples, Italy, September 30 - October 3,
2018, Proceedings, volume 11124 of Lecture Notes in Computer Science, pages 256–276. Springer, 2018. URL: https://doi.org/10.1007/978-3-030-00434-7_13, doi:
10.1007/978-3-030-00434-7\_13.
[38] K. Lee, D. H. Lee, and M. Yung. Aggregating cl-signatures revisited: Extended functionality and better eﬃciency. In Financial Cryptography and Data Security - 17th International Conference, FC 2013, Okinawa, Japan, April 1-5, 2013, Revised Selected Papers, pages 171–188, 2013. URL: https://doi.org/10.1007/978-3-642-39884-1_14,
doi:10.1007/978-3-642-39884-1\_14.
[39] S. Lim, E. Lee, and C. Park. A short redactable signature scheme using pairing. Security
and Communication Networks, 5(5):523–534, 2012. URL: https://doi.org/10.1002/
sec.346, doi:10.1002/sec.346.
[40] S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, and B. Waters.

Sequential aggregate

signatures and multisignatures without random oracles. In Advances in Cryptology EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006,
Proceedings, pages 465–485, 2006.

URL: https://doi.org/10.1007/11761679_28,

doi:10.1007/11761679\_28.
[41] A. Lysyanskaya, S. Micali, L. Reyzin, and H. Shacham. Sequential aggregate signatures from trapdoor permutations. In Advances in Cryptology - EUROCRYPT 2004,
International Conference on the Theory and Applications of Cryptographic Techniques,Interlaken, Switzerland, May 2-6, 2004, Proceedings, pages 74–90, 2004. URL: https://doi.org/10.1007/978-3-540-24676-3_5, doi:10.1007/978-3-540-24676-3\_5.
[42] A. Lysyanskaya, R. L. Rivest, A. Sahai, and S. Wolf. Pseudonym systems. In Selected
Areas in Cryptography, 6th Annual International Workshop, SAC’99, Kingston, Ontario,

65Canada, August 9-10, 1999, Proceedings, pages 184–199, 1999. URL: https://doi.org/
10.1007/3-540-46513-8_14, doi:10.1007/3-540-46513-8\_14.
[43] J. Ma, J. Liu, M. Wang, and W. Wu. An eﬃcient and secure design of redactablesignature scheme with redaction condition control. In M. H. A. Au, A. Castiglione,
K. R. Choo, F. Palmieri, and K. Li, editors, Green, Pervasive, and Cloud Computing 12th International Conference, GPC 2017, Cetara, Italy, May 11-14, 2017, Proceedings,
volume 10232 of Lecture Notes in Computer Science, pages 38–52, 2017. URL: https://doi.org/10.1007/978-3-319-57186-7_4, doi:10.1007/978-3-319-57186-7\_4.
[44] K. Miyazaki, G. Hanaoka, and H. Imai. Digitally signed document sanitizing scheme basedon bilinear maps. In F. Lin, D. Lee, B. P. Lin, S. Shieh, and S. Jajodia, editors, Proceedingsof the 2006 ACM Symposium on Information, Computer and Communications Security,
ASIACCS 2006, Taipei, Taiwan, March 21-24, 2006, pages 343–354. ACM, 2006. URL:
https://doi.org/10.1145/1128817.1128868, doi:10.1145/1128817.1128868.
[45] K. Miyazaki, G. Hanaoka, and H. Imai. Invisibly sanitizable digital signature scheme.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 91-A(1):392–402, 2008.
URL: https://doi.org/10.1093/ietfec/e91-a.1.392, doi:10.1093/ietfec/e91-a.
1.392.
[46] K. Miyazaki, M. Iwamura, T. Matsumoto, R. Sasaki, H. Yoshiura, S. Tezuka,
and H. Imai.

Digitally signed document sanitizing scheme with disclosure condi-tion control. IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 88-A(1):239–
246, 2005.

URL: http://search.ieice.org/bin/summary.php?id=e88-a_1_239&

category=D&year=2005&lang=E&abst=.
[47] M. O. Ozmen, R. Behnia, and A. A. Yavuz. Fast authentication from aggregate signatures with improved security. In Financial Cryptography and Data Security - 23rd
International Conference, FC 2019, Frigate Bay, St. Kitts and Nevis, February 18-22,
2019, Revised Selected Papers, pages 686–705, 2019. URL: https://doi.org/10.1007/
978-3-030-32101-7_39, doi:10.1007/978-3-030-32101-7\_39.
[48] H. C. Pöhls and K. Samelin.

On updatable redactable signatures.

In I. Boure-anu, P. Owesarski, and S. Vaudenay, editors, Applied Cryptography and Network Security - 12th International Conference, ACNS 2014, Lausanne, Switzerland, June 1013, 2014. Proceedings, volume 8479 of Lecture Notes in Computer Science, pages 457–66

475. Springer, 2014. URL: https://doi.org/10.1007/978-3-319-07536-5_27, doi:
10.1007/978-3-319-07536-5\_27.
[49] H. C. Pöhls and K. Samelin. Accountable redactable signatures. In 10th International
Conference on Availability, Reliability and Security, ARES 2015, Toulouse, France, August 24-27, 2015, pages 60–69, 2015. URL: https://doi.org/10.1109/ARES.2015.10,
doi:10.1109/ARES.2015.10.
[50] D. Pointcheval and O. Sanders. Reassessing security of randomizable signatures. In
Topics in Cryptology - CT-RSA 2018 - The Cryptographers’ Track at the RSA Conference 2018, San Francisco, CA, USA, April 16-20, 2018, Proceedings, pages 319–
338, 2018. URL: https://doi.org/10.1007/978-3-319-76953-0_17, doi:10.1007/
978-3-319-76953-0\_17.
[51] K. Samelin, H. C. Pöhls, A. Bilzhause, J. Posegga, and H. de Meer. Redactable signatures
for independent removal of structure and content. In M. D. Ryan, B. Smyth, and G. Wang,
editors, Information Security Practice and Experience - 8th International Conference,
ISPEC 2012, Hangzhou, China, April 9-12, 2012. Proceedings, volume 7232 of Lecture
Notes in Computer Science, pages 17–33. Springer, 2012. URL: https://doi.org/10.
1007/978-3-642-29101-2_2, doi:10.1007/978-3-642-29101-2\_2.
[52] O. Sanders. Eﬃcient redactable signature and application to anonymous credentials. In
A. Kiayias, M. Kohlweiss, P. Wallden, and V. Zikas, editors, Public-Key Cryptography- PKC 2020 - 23rd IACR International Conference on Practice and Theory of PublicKey Cryptography, Edinburgh, UK, May 4-7, 2020, Proceedings, Part II, volume 12111
of Lecture Notes in Computer Science, pages 628–656. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-45388-6_22, doi:10.1007/978-3-030-45388-6\_22.
[53] O. Sanders. Improving revocation for group signature with redactable signature. In
J. A. Garay, editor, Public-Key Cryptography - PKC 2021 - 24th IACR International
Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May
10-13, 2021, Proceedings, Part I, volume 12710 of Lecture Notes in Computer Science,
pages 301–330. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-75245-3_
12, doi:10.1007/978-3-030-75245-3\_12.
[54] A. Saxena, J. Misra, and A. Dhar.

Increasing anonymity in bitcoin.

In Finan-cial Cryptography and Data Security - FC 2014 Workshops, BITCOIN and WAHC

67

2014, Christ Church, Barbados, March 7, 2014, Revised Selected Papers, pages 122–
139, 2014.

URL: https://doi.org/10.1007/978-3-662-44774-1_9, doi:10.1007/

978-3-662-44774-1\_9.
[55] D. Schröder. How to aggregate the CL signature scheme. In Computer Security ESORICS 2011 - 16th European Symposium on Research in Computer Security, Leuven, Belgium, September 12-14, 2011. Proceedings, pages 298–314, 2011. URL: https://doi.org/10.1007/978-3-642-23822-2_17, doi:10.1007/978-3-642-23822-2\_17.
[56] A. Shamir. How to share a secret. Commun. ACM, 22(11):612–613, 1979. URL: http://doi.acm.org/10.1145/359168.359176, doi:10.1145/359168.359176.
[57] R. Steinfeld, L. Bull, and Y. Zheng. Content extraction signatures. In K. Kim, editor, Information Security and Cryptology - ICISC 2001, 4th International Conference Seoul, Korea, December 6-7, 2001, Proceedings, volume 2288 of Lecture Notes in Computer Science,
pages 285–304. Springer, 2001. URL: https://doi.org/10.1007/3-540-45861-1_22,
doi:10.1007/3-540-45861-1\_22.
[58] M. Tezuka and K. Tanaka. Redactable signature with compactness from set-commitment.
IEICE Transactions on Fundamentals of Electronics, Communications and Computer
Sciences, E104.A(9):1175–1187, 2021. doi:10.1587/transfun.2020DMP0013.
[59] Y. Zhao. Practical aggregate signature from general elliptic curves, and applications
to blockchain. In Proceedings of the 2019 ACM Asia Conference on Computer andCommunications Security, AsiaCCS 2019, Auckland, New Zealand, July 09-12, 2019,
pages 529–538, 2019.

URL: https://doi.org/10.1145/3321705.3329826, doi:10.

1145/3321705.3329826.

68