Prefix Puncturable Signatures with Smaller Signing Key from HIBS⋆ Masayuki Tezuka1,2( 1 2
) and Keisuke Tanaka2
Nagoya City University, Nagoya, Japan Institute of Science Tokyo, Tokyo, Japan [email protected]
arXiv:2609.24503v1 [cs.CR] 21 Sep 2026
September 20, 2026 Abstract. Puncturable signatures, proposed by Bellare et al. (EUROCRYPT 2016), allow a signing key to be punctured (updated) so that it loses the ability to sign particular messages while retaining the ability to sign all others. Halevi et al. (ASIACRYPT 2017) introduced prefix puncturable signatures, in which the signing key can be punctured with respect to a target prefix so that it cannot sign messages whose prefixes match the target prefix. So far, several generic constructions of prefix puncturable signature schemes have been proposed, including constructions based on identity-based signatures (IBS) (ESORICS 2022) and delegated constrained signatures (IEEE Trans. Inf. Forensics Secure. 2024). However, these constructions suffer from drawbacks in terms of key size. When the prefix space is the set of all ℓ-bit strings, the former construction requires a signing key consisting of 2ℓ IBS signing keys. The latter construction, when instantiated with a lattice-based delegated constrained signature scheme, yields a punctured signing key whose size grows quadratically with the number of puncturing operations QPunc . In this paper, we present a generic construction of prefix puncturable signatures from hierarchical identity-based signature (HIBS) schemes. When the prefix space is {0, 1}ℓ and our construction is instantiated with the lattice-based HIBS scheme HIBSGPV by Rückert (PQC 2010), our construction achieves a punctured signing key size bounded by O(ℓQPunc ). Keywords: Prefix puncturable signatures · Hierarchical identity-based signatures · Generic construction
1
Introduction
(Prefix) Puncturable Signatures. Puncturable signatures, proposed by Bellare, Stepanovs, and Waters [6], are a special type of signatures that allow us to puncture (update) the signing key sk. For a target message msg∗ , the signing key sk can be punctured (updated) to obtain a punctured signing key skmsg∗ . The punctured signing key skmsg∗ loses the ability to sign the target message msg∗ while retaining the ability to sign all other messages. This functionality naturally allows us to view puncturable signatures as a special case of policy-based signatures [5], functional signatures [9], or delegatable signatures [3]. Halevi, Ishai, Jain, Komargodski, and Sahai [15] proposed puncturable signatures that allow us to puncture sk with respect to a prefix prf ∗ of a message, rather than msg∗ itself. A signing key skprf ∗ punctured with respect to prf ∗ allows us to sign any message msg whose prefix is different from prf ∗ . Guan and Zhandry [14] referred to this type of scheme as a prefix puncturable signature scheme. Application of Puncturable Signatures. Prefix puncturable signatures are used as a building block for non-interactive multiparty computation [15], disappearing signatures [14], blockchain protocols [20,17], and privacy-aware data reporting for vehicular digital twin networks (VDTNs) [27]. Moreover, puncturable signatures provide forward secrecy at a fine-grained level [16]. Forward-secure signatures provide a protection mechanism against key exposure by periodically updating the secret key. This ensures that even if the secret key at the current time period ⋆
A preliminary version of this paper will appear at the 28th International Conference on Information and Communications Security (ICICS 2026).
is compromised, an adversary cannot forge signatures from past time periods, thereby achieving forward secrecy. However, forward-secure signatures only provide protection at the granularity of time periods and do not support fine-grained control over individual messages or messages with particular features. Puncturable signatures can be used to realize forward-secure signatures with revocation of the signing capacity for individual messages or messages with a pattern at a specific time interval. Previous Works on Puncturable Signatures. So far, several (prefix) puncturable signature schemes have been proposed. The first puncturable signature scheme was given by Bellare et al. [6]. They constructed the scheme from a one-way function and indistinguishability obfuscation (iO) [4]. After their seminal work, Halevi et al. [15] gave a prefix puncturable signature scheme by combining a non-interactive zero-knowledge (NIZK) proof system and a statistically binding commitment scheme. Li, Xu, Fan, Wang, and Zhang [2,20] proposed a prefix puncturable signature scheme by combining a Bloom filter [7] and the Chinese IBS, an identity-based signature scheme standardized in ISO/IEC 14888-3 [1]. Their scheme supports puncturing operations on a signing key, and its security is proven under the τ -strong Diffie-Hellman (τ -SDH) assumption [8] in pairing groups. Jiang, Duong, and Susilo [16] revisited the prefix puncturable signature scheme of Li et al. [20] and pointed out several drawbacks arising from the use of Bloom filters. Concretely, hash collisions may cause false-positive errors, meaning that a signer may fail to sign even for nonpunctured prefixes. Moreover, the use of Bloom filters complicates the security proof because multiple keys may correspond to a single prefix. Motivated by these observations, Jiang et al. proposed a generic construction from an identity-based signature (IBS) scheme without relying on Bloom filters. After their work, Jiang, Li, Susilo, and Duong [17] gave a generic construction from a delegated constrained signature scheme. Shaw and Dutta [24] proposed an isogeny-based puncturable signature scheme from SQISign [11]. 1.1
Motivation
(Punctured) Signing Key Size. Several proposed schemes suffer from drawbacks. The constructions [6] and [15] rely on iO or NIZK, and the resulting schemes are impractical due to heavy computation. The construction [20] is a pairing-based scheme that is vulnerable to quantum computers. The generic constructions [16] and [17] allow us to obtain schemes that are resistant to quantum computers. However, these generic constructions have the drawback of large (punctured) secret key size. Here, we consider the key sizes of [16] and [17] when instantiated with lattice-based primitives. Key Size of Lattice-Based Instantiations. When the prefix space is the set of all ℓ-bit strings, the generic construction [16] requires a signing key to contain 2ℓ IBS signing keys. A punctured signing key consists of (2ℓ −QPunc ) IBS signing keys, where QPunc denotes the number of puncturing operations applied to the signing key. The generic construction [17] requires a signing key to contain a single signing key of a delegated constrained signature scheme. A punctured signing key also consists of a single delegated constrained signing key. Jiang et al. [17] provided a comparison table between lattice-based instantiations of the puncturable signature schemes in [17] and [16]. They compared the schemes obtained from the generic construction of [16] instantiated with an efficient IBS by Tian and Huang [25], and the generic construction of [17] instantiated with a delegated constrained signature scheme by Tsabary [26]. We highlight this table with respect to key size in Fig. 1. From Fig. 1, we observe that the lattice-based puncturable signature scheme obtained from the generic construction [17] instantiated with Tsabary’s delegated constrained signature scheme [26] 2
Scheme [16] [17] PPSOurs [HIBSGPV ]
sk
skprf
2ℓ · Zm×m q Zm×m q Zm×m q
vk
(2ℓ − QPunc ) · Zm×n q (m+Q
Zq
Punc
·n⌈log q⌉)×(m+Q
Punc
O(ℓQPunc ) · Zm×m q
·n⌈log q⌉)
Zn×m q n×(m+(ℓ+1)·n⌈log q⌉)
Zq
1 +m2 2 Zn×m + 2ℓ · Zn×m q q
Fig. 1. Key size comparison among lattice-based puncturable signature schemes on the prefix space {0, 1}ℓ . In the column “Scheme”, [16] denotes the scheme instantiated the generic construction [16] with the IBS in [25]. [17] denotes the generic construction [17] with the delegated constrained signature scheme by Tsabary [26]. PPSOurs [HIBSGPV ] denotes the scheme obtained from our generic construction of a puncturable signature scheme using the hierarchical identity-based signature scheme HIBSGPV by Rückert [22]. The columns “sk”, “skprf ”, and vk denote a signing key, a punctured signing key, and a verification key, respectively. The parameter QPunc denotes the number of puncturing operations applied to a signing key, and ℓ denotes the prefix length. The same parameter settings for q, n, and m = n⌈log q⌉ are used in these schemes. These parameters are determined by the same lattice trapdoor generation algorithm. The parameters m1 , m2 > 0 satisfy m1 + m2 = m.
suffers from a drawback in the punctured signing key size. In particular, the punctured signing key size grows quadratically in the number of puncturing operations QPunc . Such quadratic growth in QPunc is undesirable in some applications. For example, we consider an application of a puncturable signature scheme to a forwardsecure signature scheme [16]. In this application, message prefixes in the puncturable signature scheme are interpreted as time periods. Then, by puncturing the signing key with respect to the prefix corresponding to the current time period and updating the signing key accordingly, the punctured signing key realizes the key-update mechanism of a forward-secure signature scheme. If the maximum number of time periods is T , then T puncturing operations are required. Consequently, it is undesirable for the punctured signing key size to grow as Ω(T 2 ). Current Open Question. To summarize the above facts, the following remains open in latticebased prefix puncturable signatures: Is it possible to construct a lattice-based prefix-puncturable signature scheme with prefix space {0, 1}ℓ whose punctured signing key size grows subquadratically in QPunc and sublinearly in the size of the prefix space 2ℓ ? 1.2
Our Result
Main Result. In this work, we give an affirmative answer to this question. More precisely, we present a generic construction of a prefix puncturable signature scheme PPSOurs [HIBS] from a hierarchical identity-based signature (HIBS) scheme HIBS. If we instantiate our construction with a lattice-based adaptively secure HIBS scheme, we obtain a lattice-based puncturable signature scheme. Key Size Comparison. For our lattice-based instantiation, we consider the lattice-based HIBS scheme HIBSGPV [22]. The scheme HIBSGPV is based on the signature scheme by Gentry, Peikert, and Vaikuntanathan [12], and its security is proven under the short integer solution (SIS) problem in the random oracle model (ROM). We denote the instantiation of our scheme PPSOurs with HIBSGPV as PPSOurs [HIBSGPV ]. The key size comparison between lattice-based instantiations of PPSOurs and previous works for prefix space {0, 1}ℓ is given in Fig. 1. In our instantiation PPSOurs [HIBSGPV ], the punctured signing key size is O(ℓQPunc ), where QPunc is the number of puncturing operations applied to the original signing key. When the number of puncturing operations increases, our scheme achieves a smaller punctured signing key size than the lattice-based instantiation of [17]. 3
Future Directions. Our construction is generic and can be instantiated with any adaptively secure HIBS scheme. Constructing more efficient lattice-based HIBS schemes that are adaptively secure in the QROM and obtaining more efficient prefix-puncturable signature schemes are interesting open problems. 1.3
How to Obtain Our Scheme
Starting Point. We explain the main idea of our construction. Our construction is obtained by building on the generic construction of Jiang et al. [16]. Their construction uses an IBS scheme. We briefly recall the idea of their construction. To simplify the exposition, we consider constructing a prefix-puncturable signature scheme with prefix space {0, 1}ℓ from their generic construction. In their construction, the key generation algorithm generates the public parameters and a master secret key (pp, msk) of IBS by running the setup algorithm of IBS. Next, for all prf ∈ {0, 1}ℓ , the algorithm generates the signing key skprf corresponding to prf by running the key-extraction algorithm of IBS. Then, the algorithm deletes msk and returns a list L of IBS secret keys as the signing key sk of the prefix puncturable signature scheme, where skprf is stored in L[prf] for all prf ∈ {0, 1}ℓ . The puncturing algorithm takes a signing key sk = L and a prefix prf ∗ . It then updates the list entry as L[prf ∗ ] ← ⊥ and returns the updated list L as the new signing key sk′ . In their approach, the signing key consists of 2ℓ secret keys of the underlying IBS scheme, which is undesirable in practice. Our Solution. To address this drawback, we use a hierarchical identity-based signature (HIBS) scheme instead of an IBS scheme. We consider a level-ℓ HIBS scheme with identity space ID = ID1 × ID2 × · · · × IDℓ = {0, 1}ℓ (i.e., the level i identity space IDi = {0, 1}). For this tree, the root is labeled with the empty string ϵ. For every node at level i labeled by x ∈ {0, 1}i , its left and right children are labeled by x0 and x1, respectively. In our construction of a prefix puncturable signature scheme, a signing key sk is the master secret key msk of the HIBS scheme. Let skt be the current (punctured) signing key and D be a set of punctured prefixes so far. To puncture (revoke) a prefix prf from a signing key skt , we compute a set C whose elements correspond to the roots of subtrees such that: – Every leaf whose label is not in D ∪ {prf} lies in the subtree of at least one node in C. – No leaf whose label is in D ∪ {prf} lies in the subtree of any node in C. That is, C is a set of labels of roots of subtrees that cover all leaves except the leaves whose labels are contained in D ∪{prf}. By deriving the HIBS signing keys corresponding to labels in C from skt by running the key extraction algorithm of the HIBS scheme, we obtain the punctured key skt+1 = {skprf }prf∈C . This operation can be performed by running the cover set algorithm of Naor et al. [21], and the number of elements in C is bounded by O(ℓQPunc ), where QPunc denotes the number of puncturing operations. As a result, we obtain a generic construction whose (punctured) signing key consists of O(ℓQPunc ) HIBS signing keys. 1.4
Related Works
(Hierarchical) Identity-Based Signatures. The concept of identity-based signatures (IBS) was introduced by Shamir [23]. In an IBS system, a trusted authority called the Key Generation Center (KGC) generates a public parameter pp and a master secret key msk. When a signer with identity id joins the system, the KGC uses the master secret key msk to generate a signing key skid associated with id and sends it to the signer. Then, the signer signs a message msg with skid and generates a signature σ. The generated signature σ is verified using the public parameters pp and the signer’s identity id. A strength of IBS is that it reduces the number of public keys that need to be managed and significantly simplifies key management, thereby removing the overhead associated with traditional public-key infrastructures. On the other hand, IBS has a 4
weakness that the KGC must generate signing keys for all users using the master secret key msk, which makes it a scalability bottleneck in large-scale systems. Hierarchical identity-based signatures (HIBS), proposed by Gentry and Silverberg [13], extend IBS by organizing identities into a hierarchical structure, enabling signing keys to be delegated from higher-level entities to lower-level entities. In a HIBS system, an entity holding a signing key for an identity at level k can derive signing keys for its descendant identities. This allows key generation to be delegated to lower-level entities without involving the root authority for every user. Security of Hierarchical Identity-Based Signatures. The unforgeability of (H)IBS schemes is considered under two security notions: selective-ID security and adaptive-ID security. In the selective-ID setting, the forger is required to declare a target identity id∗ before a public parameter pp is given. The adaptive-ID setting allows the forger to choose the target identity id∗ after seeing the public parameter pp and making signing and key corruption queries. The adaptive-ID security is stronger than the selective-ID security. In this work, we use an adaptive-ID secure HIBS for our construction. In previous work, several HIBS schemes satisfying adaptive-ID security have been proposed. Kiltz, Mityagin, Panjwani, and Raghavan [18] proposed a generic construction of an adaptive-ID secure HIBS scheme from an append-only signature scheme. They also gave a generic construction of an append-only signature scheme from a digital signature scheme. As a result, we can obtain an adaptive-ID secure HIBS scheme from a digital signature scheme. Rückert [22] proposed two selective-ID secure lattice-based HIBS schemes. One scheme is based on the lattice-based signature scheme by Gentry et al. [12], and its security is proven under the hardness of the SIS problem in the random oracle model (ROM). The other scheme is based on the lattice-based signature scheme by Cash, Hofheinz, Kiltz, and Peikert [10], and its security is proven under the hardness of the SIS problem without the ROM. Moreover, they also constructed adaptive-ID secure HIBS schemes by combining each lattice-based scheme with a chameleon hash function [19]. For our lattice-based instantiation, we use the HIBS scheme HIBSGPV , which is obtained by combining the former selective-ID secure scheme with a chameleon hash function.
2
Preliminaries
In this section, we introduce notation and review the definition of a hierarchical identity-based signature scheme and its security notion. 2.1
Notations
We introduce the notation used throughout this paper. Let 1λ be the security parameter. A function f (λ) is negligible in λ if f (λ) tends to 0 faster than λ1c for every constant c > 0. We write f (λ) = negl(λ) to indicate that f is negligible in λ. For a positive integer n, we define a $
set [n] := {1, . . . , n}. For a finite set S, s ← − S denotes that s is chosen from S uniformly at random. For finite sets S and T , we denote by S\T the set obtained by removing the elements of T from S. We denote the set of arbitrary-length bit strings by {0, 1}∗ . For strings s and t, we denote the concatenation of these strings by s||t. For a list L, |L| represents the number of elements in L. For an algorithm A, we write y ← A(x) to denote that A outputs y on input x. We abbreviate probabilistic polynomial time as PPT. 2.2
Hierarchical Identity-Based Signatures
We review a definition of an ℓ-level hierarchical identity-based signature scheme and its security notion. 5
Definition 1 (Hierarchical Identity-Based Signature Scheme). An ℓ-level hierarchical identity-based signature scheme HIBS with an identity space ID = ID1 × ID2 × · · · × IDℓ and message space M is a tuple of algorithms (Setup, Extract, Sign, Verify). – Setup(1λ ) : A setup algorithm takes as an input a security parameter 1λ . It returns a public parameter pp and a master signing key skϵ . – Extract(pp, skid1 ||...||idj−1 , idj ) : A key extraction algorithm takes as an input a public parameter pp, a signing key skid1 ||...||idj−1 for an identity (prefix) id1 || . . . ||idj−1 , and an identity idj where j ∈ [ℓ]. It returns a signing key skid for an identity (prefix) id1 || . . . ||idj−1 ||idj . (In the case of j = 1, Extract takes a tuple (pp, skϵ , id1 ) and outputs a signing key skid1 . For j ≤ ℓ, we call id1 || . . . ||idj−1 an identity prefix.) – Sign(pp, skid , id, msg) : A signing algorithm takes as an input a public parameter pp, a signing key skid , an identity id, and a message msg ∈ M . It returns a signature σ. – Verify(pp, id = id1 || . . . ||idℓ , msg, σ) : A verification algorithm takes as an input a public parameter pp, an identity id = id1 || . . . ||idℓ , a message msg, and a signature σ. It returns a bit b ∈ {0, 1}. We require HIBS to satisfy the following correctness. Correctness. An ℓ-level hierarchical identity-based signature scheme HIBS = (Setup, Extract, Sign, Verify) satisfies correctness if ∀λ ∈ N, ∀idi ∈ IDi for i ∈ [ℓ], (pp, skϵ ) ← Setup(1λ ), skid1 ← Extract(pp, skϵ , id1 ), skid1 ||...||idi−1 ||idi ← Extract(pp, skid1 ||...||idi−1 , idi ) for i ∈ {2, . . . , ℓ}, ∀msg ∈ M , id = id1 || . . . ||idℓ , and σ ← Sign(pp, skid , id, msg), Pr[Verify(pp, id, msg, σ)] = 1 − negl(λ) holds, where the probability is taken over the randomness of Setup, Extract, Sign, and Verify. We review the security definition of an ℓ-level hierarchical identity-based signature scheme. To define the security, we introduce some notations. For an identity prefix id1 || . . . ||idi , we define the set I[id1 || . . . ||idi ] as ( ) j ∈ {i, . . . , ℓ}, I[id1 || . . . ||idi ] := id1 || . . . ||idj . idi+1 ∈ IDi+1 , . . . , idj ∈ IDj That is, I[id1 || . . . ||idi ] denotes the set consisting of the identity id1 || . . . ||idi itself and all its descendant identities. Definition 2 (EUF-AID-CMA Security [18]). Let HIBS = (Setup, Extract, Sign, Verify) be an ℓ-level hierarchical identity-based signature scheme and A be a PPT adversary. The existential unforgeability under chosen message attacks with adaptive identity (EUF-AID-CMA) security is defined via the following EUF-AID-CMA game GEUF-AID-CMA (1λ ) between a challenger C and HIBS,A the adversary A. – Initial Setup: C initializes lists LSign ← {}, LCorrupt ← {}, runs (pp, skϵ ) ← Setup(1λ ), and sends pp to A. – Query Phase: A makes the following corruption queries and signing queries polynomially many times in an arbitrary order. • Corruption query: For a corruption query on id1 || . . . ||idj where j ∈ [ℓ], if there is an e 1 || . . . ||id e k ∈ LCorrupt such that id1 || . . . ||idj ∈ I[id e 1 || . . . ||id e k ], C returns ⊥. identity prefix id Corrupt Corrupt Otherwise C updates L ←L ∪ {id1 || . . . ||idj }, runs skid1 ← Extract(pp, skϵ , id1 ) and skid1 ||...||idi−1 ||idi ← Extract(pp, skid1 ||...||idi−1 , idi ) for i ∈ {2, . . . , j}. C returns skid1 ||...||idj to A. • Signing query: For a signing query on (msg, id = id1 || . . . ||idℓ ), if there is an identity e 1 || . . . ||id e k ∈ LCorrupt such that id ∈ I[id e 1 || . . . ||id e k ], C returns ⊥. Otherwise C prefix id updates LSign ← LSign ∪ {(id, msg)}, runs skid1 ← Extract(pp, skϵ , id1 ), skid1 ||...||idi−1 ||idi ← Extract(pp, skid1 ||...||idi−1 , idi ) for i ∈ {2, . . . , ℓ}, σ ← Sign(pp, skid , id, msg). C returns σ to A. 6
– Finalization: A finally outputs a forgery (id∗ = id∗1 || . . . ||id∗ℓ , msg∗ , σ ∗ ) to C. If there is an e 1 || . . . ||id e k ∈ LCorrupt such that id∗ ∈ I[id e 1 || . . . ||id e k ], return 0. If (id∗ , msg∗ ) ∈ identity prefix id ∗ Sign ∗ ∗ L , return 0. If Verify(pp, id , msg , σ ) = 1 return 1. Otherwise, return 0. (λ) := Pr[GEUF-AID-CMA (1λ ) ⇒ 1]. We say The advantage of A is defined as AdvEUF-AID-CMA HIBS,A HIBS,A (λ) that HIBS satisfies the EUF-AID-CMA security if for any PPT adversary A, AdvEUF-AID-CMA HIBS,A is negl(λ).
3
Prefix Puncturable Signatures
In this section, we review the definition of a prefix puncturable signature scheme and its security notion. Then, we revisit the security notion and propose a new security model. 3.1
Prefix Puncturable Signature Scheme
We review a definition of a prefix puncturable signature scheme and its security notion. Definition 3 (Prefix Puncturable Signature Scheme). A prefix puncturable signature scheme PPS with a message space M = P × S is a tuple of algorithms (KGen, Punc, Sign, Verify), where P denotes the prefix space and S denotes the suffix space. – KGen(1λ ) : A key generation algorithm takes as an input a security parameter 1λ . It returns a verification key vk and a signing key sk0 . – Punc(vk, ski , prf) : A puncturing algorithm takes as an input a current signing key ski and a prefix prf ∈ P . It returns an updated punctured signing key ski+1 . – Sign(vk, ski , msg = prf||sff) : A signing algorithm takes as an input a verification key, a signing key ski and a message msg = prf||sff ∈ M . It returns a signature σ. – Verify(vk, msg = prf||sff, σ) : A verification algorithm takes as an input a verification key vk, a message msg = prf||sff ∈ M , and a signature σ. It returns a bit b ∈ {0, 1}. We require PPS to satisfy the following correctness. Correctness. A prefix puncturable signature scheme PPS = (KGen, Punc, Sign, Verify) satisfies correctness if ∀λ ∈ N, ∀t ∈ N ∪ {0}, (vk, sk0 ) ← KGen(1λ ), ∀prf 1 , . . . , prf t ∈ P , ski ← Punc(vk, ski−1 , prf i ) for i ∈ [t], ∀prf ∈ P \{prf 1 , . . . , prf t }, ∀sff ∈ S, σ ← Sign(vk, skt , msg = prf||sff), Pr[Verify(vk, msg = prf||sff, σ)] = 1 − negl(λ), where the probability is taken over the randomness of KGen, Punc, Sign, and Verify. Definition 4 (EUF-AP-CMA Security [16]). Let PPS = (KGen, Punc, Sign, Verify) be a prefix puncturable signature scheme and A be a PPT adversary. The existential unforgeability under chosen message attacks with adaptive puncturing (EUF-AP-CMA) security is defined via the following EUF-AP-CMA game GEUF-AP-CMA (1λ ) between a challenger C and the adversary PPS,A A. – Initial Setup: C initializes lists LSign ← {}, LPunc ← {} and a variable t ← 0. C runs (vk, sk0 ) ← KGen(1λ ) and sends vk to A. – Query Phase: A makes the following puncturing queries and signing queries polynomially many times in an arbitrary order. • Puncturing Query: For a puncturing query on prf, if prf ∈ LPunc , C returns ⊥. Otherwise C updates LPunc ← LPunc ∪ {prf}, t ← t + 1, skt ← Punc(vk, skt−1 , prf). • Signing Query: For a signing query on msg = prf||sff, if prf ∈ LPunc , C returns ⊥. Otherwise C updates LSign ← LSign ∪ {msg}, runs σ ← Sign(vk, skt , msg), and returns σ to A. 7
– Challenge Phase: A outputs a target prefix prf ∗ . After outputting prf ∗ , A makes the puncturing queries and signing queries as described in the query phase polynomially many times in an arbitrary order. – Corruption Phase: If prf ∗ ∈ LPunc , C sends a current signing key skt to A. Otherwise, C sends ⊥ to A. – Finalization: A finally outputs a forgery (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) to C. If prf ∗ ∈ LPunc ∧msg∗ ∈ / Sign ∗ ∗ L ∧ Verify(vk, msg , σ ) = 1 holds, return 1. Otherwise, return 0. (λ) := Pr[GEUF-AP-CMA (1λ ) ⇒ 1]. We say that The advantage of A is defined by AdvEUF-AP-CMA PPS,A PPS,A (λ) is PPS satisfies the EUF-AP-CMA security if for any PPT adversary A, AdvEUF-AP-CMA PPS,A negl(λ). 3.2
Security Revisited and Our Security Model
Here, we recall the security definition of a prefix puncturable signature scheme given in Definition 4. In this definition, an adversary A in the EUF-AP-CMA game must submit a target prefix prf ∗ in the challenge phase. To win the EUF-AP-CMA game, A is required to output a forgery for prf ∗ . However, requiring the adversary to specify prf ∗ before obtaining the punctured signing key seems unnatural, since this requirement prevents the adversary from choosing its target based on the information contained in the exposed signing key. This distinction can also be viewed as analogous to selective and adaptive identity selection in identity-based cryptography: regarding a prefix as playing a role analogous to an identity, it is natural to consider both non-adaptive and adaptive choices of the target prefix. Instead, it appears more natural to remove the challenge phase from the EUF-AP-CMA game and allow A to output a forgery for any prefix prf ∗ on which a puncturing query has been made in the finalization phase. Motivated by this observation, we propose a new security notion called existential unforgeability under chosen message attacks with adaptive puncturing and adaptive target prefix (EUFAP-ATP-CMA) security. Our security model allows the adversary to choose the target prefix when producing the final forgery, after observing the punctured signing key, and therefore models a more adaptive adversary. Definition 5 (EUF-AP-ATP-CMA Security (Our Proposal)). Let PPS = (KGen, Punc, Sign, Verify) be a prefix puncturable signature scheme and A be a PPT adversary. The existential unforgeability under chosen message attacks with adaptive puncturing and adaptive target prefix (EUF-AP-ATP-CMA) security is defined via the following EUF-AP-ATP-CMA game (1λ ) between a challenger C and the adversary A. GEUF-AP-ATP-CMA PPS,A – Initial Setup: C initializes lists LSign ← {}, LPunc ← {}, and a variable t ← 0. C runs (vk, sk0 ) ← KGen(1λ ) and sends vk to A. – Query Phase: A makes the following puncturing queries and signing queries polynomially many times in an arbitrary order. • Puncturing Query: For a puncturing query on prf, if prf ∈ LPunc , C returns ⊥. Otherwise C updates LPunc ← LPunc ∪ {prf}, t ← t + 1, skt ← Punc(vk, skt−1 , prf). • Signing Query: For a signing query on msg = prf||sff, if prf ∈ LPunc , C returns ⊥. Otherwise C updates LSign ← LSign ∪ {msg}, runs σ ← Sign(vk, skt , msg), and returns σ to A. – Corruption Phase: A outputs an instruction corrupt to C. Then, C sends a current signing key skt to A. – Finalization: A finally outputs a forgery (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) to C. If prf ∗ ∈ LPunc ∧msg∗ ∈ / LSign ∧ Verify(vk, msg∗ , σ ∗ ) = 1 holds, return 1. Otherwise, return 0. 8
(λ) := Pr[GEUF-AP-ATP-CMA (1λ ) ⇒ 1]. We The advantage of A is defined by AdvEUF-AP-ATP-CMA PPS,A PPS,A (λ) say that PPS satisfies the EUF-AP-ATP-CMA security if for any PPT adversary A, AdvEUF-AP-ATP-CMA PPS,A is negl(λ). Here, we clarify the fact that the EUF-AP-ATP-CMA security implies the EUF-AP-CMA security. Theorem 1. Let PPS = (KGen, Punc, Sign, Verify) be a prefix puncturable signature scheme and A be a PPT adversary against the EUF-AP-CMA security of PPS. Then, there is a PPT adversary R against the EUF-AP-ATP-CMA security of PPS that satisfies AdvEUF-AP-CMA (λ) = AdvEUF-AP-ATP-CMA (λ). PPS,A PPS,R Proof. We prove Theorem 1 by assuming the existence of a PPT adversary A that breaks the EUF-AP-CMA security of PPS, and constructing a PPT adversary R that breaks the EUF-APATP-CMA security of PPS. Let C be the challenger of the EUF-AP-ATP-CMA security of PPS. The construction of R is given as follows. – R takes an instance vk of the EUF-AP-ATP-CMA security game. Then, R initializes lists LSign ← {}, LPunc ← {} and invokes A on input vk. – For a puncturing query prf from A, if prf ∈ LPunc , R returns ⊥. Otherwise R updates LPunc ← LPunc ∪ {prf} and makes a puncturing query to C. – For a signing query on msg = prf||sff, if prf ∈ LPunc , R returns ⊥. Otherwise R updates LSign ← LSign ∪ {msg}, makes a signing query with msg = prf||sff, receives a signature σ. Then, R returns σ to A. – In the challenge phase of A, R receives a target prefix prf ∗ and stores it. For puncturing queries and signing queries after receiving prf ∗ , R responds to these queries the same way as described above. – In the corruption phase of A, if prf ∗ ∈ LPunc , R sends an instruction corrupt to C, receives skt , and returns skt to A. Otherwise, R sends ⊥ to A. – After receiving the final output (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) from A, R outputs (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) as the final output. It is clear that R perfectly simulates the challenger of the EUF-AP-CMA game. If A outputs a valid forgery (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) for the EUF-AP-CMA game, then R also outputs a valid forgery for the EUF-AP-ATP-CMA game. Thus, we conclude Theorem 1. ⊓ ⊔ We prove the reverse implication (i.e., the EUF-AP-CMA security implies the EUF-APATP-CMA security). Note that we prove this claim via a non-tight reduction. Theorem 2. Let PPS = (KGen, Punc, Sign, Verify) be a prefix puncturable signature scheme and A be a PPT adversary against the EUF-AP-ATP-CMA security of PPS that makes QPunc puncturing queries. Then, there is a PPT adversary R against the EUF-AP-CMA security of PPS that satisfies AdvEUF-AP-ATP-CMA (λ) ≤ QPunc · AdvEUF-AP-CMA (λ). PPS,A PPS,R Proof. We prove Theorem 2 by assuming the existence of a PPT adversary A that breaks the EUF-AP-ATP-CMA security of PPS, and constructing a PPT adversary R that breaks the EUFAP-CMA security of PPS. Let C be the challenger of the EUF-AP-CMA security of PPS. The construction of R is given as follows. – R takes an instance vk of the EUF-AP-CMA security game. R initializes lists LSign ← {}, LPunc ← {}. Then, R invokes A on input vk. – For a puncturing query prf from A, if prf ∈ LPunc , R returns ⊥. Otherwise R updates LPunc ← LPunc ∪ {prf} and makes a puncturing query to C. 9
– For a signing query on msg = prf||sff, if prf ∈ LPunc , R returns ⊥. Otherwise R updates LSign ← LSign ∪ {msg}, makes a signing query with msg = prf||sff, receives a signature σ. Then, R returns σ to A. $ f∗ ← – In the corruption phase of A, if R receives corrupt, R chooses a guessed target prefix prf − f ∗ to C, moves to the corruption phase of LPunc , moves to the challenge phase of R, sends prf R, receives skt , and returns skt to A. f ∗ = prf ∗ holds, R returns – R receives the final output (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) from A. If prf (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) to C. Otherwise, R aborts. It is clear that R perfectly simulates the challenger of the EUF-AP-ATP-CMA game. If A outputs a valid forgery (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) for the EUF-AP-ATP-CMA game, then R outputs 1 f ∗ = prf ∗ holds. The probability that prf f ∗ = prf ∗ holds is at least Punc a valid forgery if prf . Q From this fact, we see that Pr[GEUF-AP-CMA (1λ ) ⇒ 1] ≥ PPS,R
1 · Pr[GEUF-AP-ATP-CMA (1λ ) ⇒ 1] PPS,A QPunc ⊔ ⊓
holds. Thus, we conclude Theorem 2.
By Theorem 1 and Theorem 2, the notions of EUF-AP-ATP-CMA security and EUF-APCMA security are equivalent in the sense that reductions exist in both directions. However, this equivalence does not appear to be tight, since the reduction incurs a loss factor of QPunc , where QPunc denotes the number of puncturing operations applied to the secret key.
4
Prefix Puncturable Signatures from HIBS
In this section, we review the complete subtree algorithm CS which is used for our construction. Then, we present a generic construction of a prefix puncturable signature scheme PPSOurs from a hierarchical identity-based signature scheme. 4.1
Complete Subtree Algorithm
We use the complete subtree algorithm CS [21] for our construction. We consider a complete binary tree T of level ℓ whose nodes are labeled with binary strings. The root (i.e., the node of level 0) is labeled with the empty string ϵ. For every node at level i labeled by x ∈ {0, 1}i , its left and right children are labeled by x0 and x1, respectively. The deterministic algorithm CS takes as input a set D of leaf labels and outputs a set C of tree node labels such that: – Every leaf whose label is not in D lies in the subtree of at least one node in C. – No leaf whose label is in D lies in the subtree of any node in C. We illustrate an example of the input and output of this algorithm in Fig. 2. For a complete binary tree T of level ℓ and any set D of leaf labels, there exists a collection of O(ℓ|D|) subtrees that covers all leaves outside D while excluding all leaves in D. We also use the following property of the complete subtree algorithm CS. For D ⊆ D′ , for every node w′ ∈ CS(D′ ), there exists a node w ∈ CS(D) such that either w = w′ or w′ is a descendant of w. 4.2
Our Construction
Let HIBS = (HIBS.Setup, HIBS.Extract, HIBS.Sign, HIBS.Verify) be an ℓ-level hierarchical identitybased signature scheme with an identity space IDHIBS = ID1 × ID2 × · · · × IDℓ and message space M HIBS = {0, 1}m . To simplify the discussion, we assume that the identity space at each level IDi is {0, 1} (i.e., IDHIBS = {0, 1}ℓ ). 10
ϵ
0
1
00
000
01
001
010
10
011
100
11
101
110
111
Fig. 2. An example of the input and output of CS for a complete binary tree. For example, suppose that ℓ = 3 and CS takes D = {100, 111} as input, corresponding to the leaves highlighted in blue in the figure. Then, CS outputs C = {0, 101, 110} , corresponding to the nodes highlighted in red.
Let CS be the complete subtree algorithm for a level ℓ binary tree. Let T be a complete binary tree of level ℓ whose nodes are labeled with binary strings in the same way as described in Section 4.1. We refer to the following algorithm as the non-covered-leaf algorithm NCL. The algorithm NCL takes as input a set C of node labels and outputs a set D of leaf labels such that no leaf in D belongs to any subtree rooted at a node in C. We illustrate an example of the input and output of this algorithm in Fig. 3.
ϵ
0
1
00
000
01
001
010
10
011
100
11
101
110
111
Fig. 3. An example of the input and output of NCL. For example, suppose that ℓ = 3 and NCL takes C = {00, 11, 100} as input, where C corresponds to the nodes highlighted in red in the figure. Then, NCL outputs D = {010, 011, 101} , where D corresponds to the leaves highlighted in blue.
Now, we are ready to present our construction of a prefix puncturable signature scheme. We give our construction PPSOurs [HIBS] with a message space M PPS = P PPS × S PPS = IDHIBS × M HIBS in Fig. 4. 4.3
Analysis
We analyze our construction PPSOurs [HIBS]. The correctness of PPSOurs [HIBS] follows directly from that of HIBS. The security of our construction is proven under the adaptive-ID security of HIBS. Theorem 3. If the scheme HIBS satisfies the EUF-AID-CMA security, then our construction PPSOurs [HIBS] satisfies the EUF-AP-ATP-CMA security. 11
PPS.KGen(1λ ) : (ppHIBS , skHIBS ) ← HIBS.Setup(1λ ), C ← {ϵ}. ϵ PSS HIBS Return (vk , skPSS , ((skHIBS ), C)). 0 ) ← (pp ϵ PSS PSS HIBS PPS.Punc(vk , ski = ((skw )w∈C , C), prf i ∈ {0, 1}ℓ ) : D ← NCL(C), D′ ← D ∪ {prf i }, C ′ ← CS(D′ ). Compute (skHIBS )w∈C ′ from (skHIBS )w∈C by running HIBS.Extract. w w PSS ′ ′ Return ski+1 ← ((skHIBS ) , C ). w∈C w PPS.Sign(vkPSS , skPSS = ((skHIBS )w∈C , C), msg = prf||sff) : w i D ← NCL(C). If prf ∈ NCL(C), return ⊥. Find w′ ∈ CS(D) such that prf ∈ I[w′ ], where I[w′ ] is a set of strings that have w′ as a prefix. Derive skHIBS from skHIBS by running HIBS.Extract. prf w′ Return σ ← HIBS.Sign(ppHIBS , skHIBS prf , prf, sff). PPS.Verify(vkPSS = ppHIBS , msg = prf||sff, σ) : If HIBS.Verify(ppHIBS , prf, sff, σ) = 1, return 1. Otherwise, return 0. Fig. 4. Our construction PPSOurs [HIBS].
More precisely, let A be a PPT adversary against the EUF-AP-ATP-CMA security of PPSOurs [HIBS]. Then, there is a PPT reduction algorithm R against the EUF-AID-CMA security of HIBS that satisfies (λ). (λ) = AdvEUF-AID-CMA AdvEUF-AP-ATP-CMA HIBS,R PPSOurs ,A Proof. Let A be a PPT adversary against the EUF-AP-ATP-CMA security of the scheme PPSOurs [HIBS] and C be the challenger of the EUF-AID-CMA security game for HIBS. We prove Theorem 3 by constructing a reduction algorithm R against the EUF-AID-CMA security of the scheme HIBS. We describe the construction of R as follows. – R takes an instance ppHIBS of the EUF-AID-CMA security game. R sets LSign ← {}, D ← {}, t ← 0, vkPSS ← ppHIBS . Then, R invokes A with the input vkPSS . – For a puncturing query on prf, if prf ∈ D, R returns ⊥. Otherwise R updates D ← D ∪ {prf}. – For a signing query on msg = prf||sff, if prf ∈ D, R returns ⊥. Otherwise R updates LSign ← LSign ∪ {msg}, makes a signing query on (prf, sff) to C, obtains a signature σ, and returns σ to A. – For an instruction corrupt from A, R computes C ← CS(D). Then, for each w ∈ C, R makes a corruption query on w to C and obtains skHIBS . R sets skPSS ← ((skHIBS )w∈CS(D) , C) and w t w sends skPSS to A. t e ∗ = prf ∗ , msg g∗ = – After receiving the final output (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) from A, R outputs (id ∗ ∗ sff , σ ) as the final output. Clearly, R perfectly simulates the challenger of the EUF-AP-ATP-CMA game. It remains to show that a valid forgery (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) for the EUF-AP-ATP-CMA game of PPSOurs [HIBS] produced by A yields a valid forgery for the EUF-AID-CMA game of HIBS. Suppose that A outputs a valid forgery (msg∗ = prf ∗ ||sff ∗ , σ ∗ ) for the EUF-AP-ATP-CMA game of PPSOurs [HIBS]. Since A wins the game, we have prf ∗ ∈ D and msg∗ = prf ∗ ||sff ∗ ∈ / LSign . In the corruption phase, R makes corruption queries on every w ∈ C = CS(D). By the definition of CS(D), no leaf in D belongs to a subtree rooted at a node in C. Since prf ∗ ∈ D, we have prf ∗ ∈ / I[w] for every w ∈ C. Hence, the corruption queries made by R do not violate the winning condition of the EUF-AID-CMA game for the target identity prf ∗ . Moreover, since prf ∗ ||sff ∗ ∈ / LSign , R has never made a signing query on (prf ∗ , sff ∗ ) to C. This fact implies ∗ ∗ that (prf , sff ) is not contained in the signing-query list of the EUF-AID-CMA game. Finally, 12
if PPS.Verify(vkPSS , prf ∗ ||sff ∗ , σ ∗ ) = 1 holds, then HIBS.Verify(ppHIBS , prf ∗ , sff ∗ , σ ∗ ) = 1 holds. Therefore, (prf ∗ , sff ∗ , σ ∗ ) is a valid forgery for the EUF-AID-CMA game of HIBS. Then, we see that Pr[GEUF-AID-CMA (1λ ) ⇒ 1] = Pr[GEUF-AP-ATP-CMA (1λ ) ⇒ 1] HIBS,R PPSOurs ,A ⊔ ⊓
holds. Thus, we conclude Theorem 3.
Acknowledgement A part of this work was supported by JSPS KAKENHI JP24H00071, JST CREST JPMJCR2113, and JST K Program JPMJKP24U2.
References 1. It security techniques — digital signatures with appendix — part 3: Discrete logarithm based mechanisms, Nov. 2018. URL: https://www.iso.org/standard/76382.html. 2. Puncturable signatures and applications in proof-of-stake blockchain protocol. IACR Cryptol. ePrint Arch., 2019:970, 2019. Withdrawn. URL: https://eprint.iacr.org/2019/970. 3. M. Backes, S. Meiser, and D. Schröder. Delegatable functional signatures. In C. Cheng, K. Chung, G. Persiano, and B. Yang, editors, Public-Key Cryptography - PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I, Lecture Notes in Computer Science, pages 357–386. Springer, 2016. doi:10.1007/978-3-662-49384-7\_14. 4. B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. P. Vadhan, and K. Yang. On the (im)possibility of obfuscating programs. In J. Kilian, editor, Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, Lecture Notes in Computer Science, pages 1–18. Springer, 2001. doi:10.1007/3-540-44647-8\_1. 5. M. Bellare and G. Fuchsbauer. Policy-based signatures. In H. Krawczyk, editor, Public-Key Cryptography PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings, Lecture Notes in Computer Science, pages 520–537. Springer, 2014. doi:10.1007/978-3-642-54631-0\_30. 6. M. Bellare, I. Stepanovs, and B. Waters. New negative results on differing-inputs obfuscation. In M. Fischlin and J. Coron, editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, Lecture Notes in Computer Science, pages 792–821. Springer, 2016. doi:10.1007/978-3-662-498965\_28. 7. B. H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422–426, 1970. doi:10.1145/362686.362692. 8. D. Boneh and X. Boyen. Short signatures without random oracles. In C. Cachin and J. Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004, Proceedings, Lecture Notes in Computer Science, pages 56–73. Springer, 2004. doi:10.1007/978-3-540-24676-3\_4. 9. E. Boyle, S. Goldwasser, and I. Ivan. Functional signatures and pseudorandom functions. In H. Krawczyk, editor, Public-Key Cryptography - PKC 2014 - 17th International Conference on Practice and Theory in Public-Key Cryptography, Buenos Aires, Argentina, March 26-28, 2014. Proceedings, Lecture Notes in Computer Science, pages 501–519. Springer, 2014. doi:10.1007/978-3-642-54631-0\_29. 10. D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert. Bonsai trees, or how to delegate a lattice basis. In H. Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, Lecture Notes in Computer Science, pages 523–552. Springer, 2010. doi:10.1007/978-3-642-13190-5\_27. 11. L. D. Feo, D. Kohel, A. Leroux, C. Petit, and B. Wesolowski. Sqisign: Compact post-quantum signatures from quaternions and isogenies. In S. Moriai and H. Wang, editors, Advances in Cryptology - ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7-11, 2020, Proceedings, Part I, Lecture Notes in Computer Science, pages 64–93. Springer, 2020. doi:10.1007/978-3-030-64837-4\_3. 12. C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In C. Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 197–206. ACM, 2008. doi:10.1145/1374376.1374407. 13. C. Gentry and A. Silverberg. Hierarchical id-based cryptography. In Y. Zheng, editor, Advances in Cryptology - ASIACRYPT 2002, 8th International Conference on the Theory and Application of Cryptology and Information Security, Queenstown, New Zealand, December 1-5, 2002, Proceedings, Lecture Notes in Computer Science, pages 548–566. Springer, 2002. doi:10.1007/3-540-36178-2\_34.
13
14. J. Guan and M. Zhandry. Disappearing cryptography in the bounded storage model. In K. Nissim and B. Waters, editors, Theory of Cryptography - 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8-11, 2021, Proceedings, Part II, Lecture Notes in Computer Science, pages 365–396. Springer, 2021. doi:10.1007/978-3-030-90453-1\_13. 15. S. Halevi, Y. Ishai, A. Jain, I. Komargodski, A. Sahai, and E. Yogev. Non-interactive multiparty computation without correlated randomness. In T. Takagi and T. Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part III, Lecture Notes in Computer Science, pages 181–211. Springer, 2017. doi:10.1007/978-3-319-70700-6\_7. 16. M. Jiang, D. H. Duong, and W. Susilo. Puncturable signature: A generic construction and instantiations. In V. Atluri, R. D. Pietro, C. D. Jensen, and W. Meng, editors, Computer Security - ESORICS 2022 - 27th European Symposium on Research in Computer Security, Copenhagen, Denmark, September 26-30, 2022, Proceedings, Part II, Lecture Notes in Computer Science, pages 507–527. Springer, 2022. doi:10.1007/9783-031-17146-8\_25. 17. M. Jiang, Y. Li, W. Susilo, and D. H. Duong. Quantum-safe puncturable signatures with their application in blockchain. IEEE Trans. Inf. Forensics Secur., 19:2761–2770, 2024. doi:10.1109/TIFS.2024.3353074. 18. 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, Languages and Programming, 32nd International Colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005, Proceedings, Lecture Notes in Computer Science, pages 434–445. Springer, 2005. doi:10.1007/11523468\_36. 19. H. Krawczyk and T. Rabin. Chameleon signatures. In Proceedings of the Network and Distributed System Security Symposium, NDSS 2000, San Diego, California, USA. The Internet Society, 2000. URL: https: //www.ndss-symposium.org/ndss2000/chameleon-signatures/. 20. X. Li, J. Xu, X. Fan, Y. Wang, and Z. Zhang. Puncturable signatures and applications in proof-of-stake blockchain protocols. IEEE Trans. Inf. Forensics Secur., 15:3872–3885, 2020. doi:10.1109/TIFS.2020. 3001738. 21. D. Naor, M. Naor, and J. Lotspiech. Revocation and tracing schemes for stateless receivers. In J. Kilian, editor, Advances in Cryptology - CRYPTO 2001, 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19-23, 2001, Proceedings, Lecture Notes in Computer Science, pages 41–62. Springer, 2001. doi:10.1007/3-540-44647-8\_3. 22. M. Rückert. Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles. In N. Sendrier, editor, Post-Quantum Cryptography, Third International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010. Proceedings, Lecture Notes in Computer Science, pages 182–200. Springer, 2010. doi:10.1007/978-3-642-12929-2\_14. 23. A. Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley and D. Chaum, editors, Advances in Cryptology, Proceedings of CRYPTO ’84, Santa Barbara, California, USA, August 19-22, 1984, Proceedings, Lecture Notes in Computer Science, pages 47–53. Springer, 1984. doi:10.1007/3-540-395687\_5. 24. S. Shaw and R. Dutta. Compact identity-based signature and puncturable signature from sqisign. In H. Seo and S. Kim, editors, Information Security and Cryptology - ICISC 2023 - 26th International Conference on Information Security and Cryptology, ICISC 2023, Seoul, South Korea, November 29 - December 1, 2023, Revised Selected Papers, Part I, Lecture Notes in Computer Science, pages 282–305. Springer, 2023. doi: 10.1007/978-981-97-1235-9\_15. 25. M. Tian and L. Huang. Identity-based signatures from lattices: Simpler, faster, shorter. Fundam. Informaticae, 145(2):171–187, 2016. doi:10.3233/FI-2016-1353. 26. R. Tsabary. An equivalence between attribute-based signatures and homomorphic signatures, and new constructions for both. In Y. Kalai and L. Reyzin, editors, Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12-15, 2017, Proceedings, Part II, Lecture Notes in Computer Science, pages 489–518. Springer, 2017. doi:10.1007/978-3-319-70503-3\_16. 27. C. Wang, Y. Ming, H. Liu, S. Zhang, and R. Lu. Puncturable signature and applications in privacy-aware data reporting for vdtns. IEEE Trans. Serv. Comput., 18(3):1669–1682, 2025. doi:10.1109/TSC.2025.3562318.
14
Table of Contents
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Our Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 How to Obtain Our Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Hierarchical Identity-Based Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Prefix Puncturable Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Prefix Puncturable Signature Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Security Revisited and Our Security Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Prefix Puncturable Signatures from HIBS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Complete Subtree Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Our Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 2 3 4 4 5 5 5 7 7 8 10 10 10 11