arXiv CSopen access

Hierarchical Identity-Based Signature with Designated Aggregator from Lattices

Hierarchical Identity-Based Signature with Designated Aggregator from Lattices Stuti Kumari1 , Kunal Dey2 , Vikas Srivastava3 , and Sumit Kumar Debnath1 1

arXiv:2606.14090v1 [cs.CR] 12 Jun 2026

National Institute of Technology Jamshedpur, Jamshedpur 831014, India [email protected], [email protected] 2 SRM University-AP, Andhra Pradesh, India-522240 [email protected], [email protected] 3 National Institute of Technology, Warangal - 506004, Telangana, India [email protected]

Abstract. In hierarchical organizations, authenticating data from multiple users can be complex and resource-intensive. Hierarchical Identity-Based Signature with Designated Aggregator (HIBS-DA) provides an efficient solution by allowing users at different levels to generate signatures that can be combined into a single, compact signature. We first introduce the HIBS-DA framework and present the first lattice-based construction of HIBS-DA. Our scheme allows users at different hierarchical levels to generate individual signatures that can be aggregated into a single, compact signature, reducing communication and verification costs. The proposed construction is secure, correct, and resistant to forgery, making it suitable for large-scale environments such as universities, corporations, and government agencies.

Keywords: Hierarchical identity-based signature · Aggregate Signature · Lattices · SIS Problems.

1

Introduction

In classical public-key cryptography, a certification authority (CA) issues digital certificates to users to bind their identities to public keys, resulting in significant certificate management overhead. The idea of identitybased cryptography was originally put forward by Shamir (1985) [1], wherein identities like email addresses function as public keys, with corresponding secret keys issued by a PKG. Boneh and Franklin [2] introduced the earliest practical scheme for Identity-based encryption in 2001, based upon the bilinear Diffie-Hellman (BDH) assumption, which subsequently led to further constructions including IBS schemes [3]. Subsequently, various extensions have appeared in the literature, including identity-based signature (IBS) schemes [3]. However, IBS typically employs a single PKG, which can become a performance bottleneck, making such systems unsuitable for large organizations due to the potential overload on the PKG. In many modern applications, such as secure data sharing [4], e-governance [5], and distributed systems [6], it is often necessary to authenticate data from multiple users organized in hierarchical structures. Moreover, when numerous signatures are involved, storing and verifying each individually becomes costly in terms of time and space. To address these challenges, Hierarchical Identity-Based Signature with Designated Aggregator (HIBS-DA) schemes have been introduced. An HIBS-DA scheme combines the advantages of hierarchical identity-based cryptography (HIBC) [7] and aggregate signatures [8]. In a hierarchical identity-based setting, users are organized into a tree-like structure with a trusted Private Key Generator (PKG) at the root. The PKG delegates key generation down the hierarchy, enabling scalable and decentralized key management. This is particularly useful in large organizations, government departments, academics, hospitals, companies where authority and access are distributed across multiple levels. On the other hand, an aggregate signature scheme [8] allows multiple signatures possibly from different users and on different messages, to be merged into one compact signature. This aggregated signature can subsequently be verified efficiently, authenticating all underlying messages simultaneously. An HIBS-DA scheme, therefore, supports signatures by multiple users at different levels of a hierarchy,

Identity-based key generation without relying on certificates. Such a system is highly beneficial in scenarios where multiple users from different branches of a hierarchy need to sign data, and the verifier requires a compact and efficient authentication mechanism. In this setting, a single private key generator (PKG) and multiple hierarchical groups of users exist. Each group forms a hierarchy of depth t, with a total of N such hierarchies, each having the same depth t. Now, suppose for a specific application, it is required to obtain documents signed by the k-th level signer from each hierarchy. That is, the signers denoted as s1k , s2k , . . . , sN k from the figure 1 corresponding to the k-th level user in each of the N hierarchies are required to generate signatures on their respective data. These signatures, along with the signed data, must be submitted wherever needed and stored for verification. Instead of storing and verifying N individual signatures, we can leverage an aggregate signature scheme. This allows all the individual signatures from the k-th signer in each hierarchy to be compressed into a single, compact aggregate signature. This one signature is sufficient to authenticate all the corresponding documents, significantly improving efficiency in terms of storage and verification. In this paper, we begin the investigation of HIBS-DA. We formalize its syntax, security architecture, and provide the first lattice-based construction, and evaluate its efficiency using comprehensive complexity estimates. 1.1

Application

The hierarchical identity-based signature with designated aggregator (HIBS-DA) schemes have several practical applications, we present an application of HIBS-DA in detail as follows. Consider an academic institution organized in a hierarchical structure comprising a Director at the top level, followed by N Heads of Departments (HoDs) (h1 , h2 , . . . , hN ), and N Financial Officers (f1 , f2 , . . . , fN ), with authority delegated in that order. This hierarchical structure reflects a natural delegation model, where the Director acts as the root Private Key Generator (PKG), enabling identity-based key generation throughout the levels of the hierarchy. Now, consider two scenarios for a particular academic year: (i) Departmental Placement Records Authentication: Each HoD (hi ) is responsible for submitting the placement records of their respective departments, digitally signed to ensure authenticity and integrity. Rather than storing and verifying all N individual signatures, a designated aggregator can be employed to compress these signatures into a single aggregate signature. This compact signature can then be used to authenticate all placement records of different departments at once, improving efficiency in verification and storage. (ii) Departmental Financial Records Authentication: Each Financial Officer (fi ) submits the financial report for their respective department, again digitally signed. As in the previous case, the individual signatures from all financial officers can be aggregated into a single signature. This single compact signature serves as a proof of authenticity for all departmental financial records. By employing the HIBS-DA scheme in such a setting, the institution achieves: Efficient key delegation aligned with its organizational hierarchy, Compact and scalable authentication of multiple signed documents, Postquantum security is built upon lattice-based assumptions. Such a model is ideal for hierarchical organizations that handle structured, multi-source data submissions while aiming to minimize computational and communication overhead. Refer to Figure 1 for a visual demonstration. 1.2

Review of Literature

An overview of current lattice-based approaches to hierarchical identity-based signatures and aggregate signatures is presented in this section. Gentry and Silverberg [7] introduced the hierarchical identity-based signature (HIBS) scheme, which extends traditional identity-based signature (IBS) systems by incorporating a multi-level hierarchical structure, similar to those found in real-world organizations. In a HIBS scheme, multiple private key generators (PKGs) are arranged hierarchically, with each PKG’s secret key being generated by its parent. This approach 2

Fig. 1. HIBS-DA.

reduces the computational burden on the root PKG, making it highly suitable for large-scale deployments. Most HIBS schemes in the literature [7,9,10] rely on the difficulty of solving the discrete logarithm problem. However, in 1997, Shor demonstrated that quantum algorithms could solve this problem efficiently, posing a threat to such systems. Several lattice-based HIBS schemes have been developed. Rückert [11], inspired by the basis delegation techniques of [12], introduced the first HIBS scheme built on lattices, both in the random-oracle setting and in the standard model. Despite these advances, these schemes tend to involve large system parameters, and the efficiency of both the private key generation and the signing process depends on the signer’s position within the hierarchy. To enhance efficiency, Tian et al. [13] introduced a novel HIBS scheme based on lattices that does not rely on random oracles and offers better performance. Then, lattice-based HIBS schemes [14,15,16] have been proposed. The idea of aggregate signatures was initially proposed by Boneh et al.[8]. It merges several signatures, each linked to distinct messages, into a single compact signature. This compact signature can authenticate several message-signature pairs for different users simultaneously. Such a scheme significantly reduces the storage space needed for signatures, lowers the transmission bandwidth demand, and minimizes the computational cost of verifying signatures. Various lattice-based aggregate signature schemes [17,18] have been developed.

3

2

Our Contributions

To the best of our knowledge, no HIBS-DA scheme has been proposed in the existing literature. Therefore, we propose to construct a lattice-based HIBS-DA scheme to address this gap. We propose the first HIBSDA scheme based on lattices that simultaneously supports hierarchical key delegation and aggregation of signatures from multiple branches in a hierarchical PKG structure. To achieve the HIBS-DA scheme, we integrate the Chinese Remainder Theorem (CRT) technique described in (see in Appendix 8.1,8.2) with the hierarchical identity-based signature scheme proposed by Tian et al. [13]. The construction of our HIBS-DA scheme is presented in Section 5, while its correctness and security proofs are provided in the subsequent subsections. The detailed efficiency analysis of our HIBS-DA scheme, describing round complexity, communication complexity, and computation complexity, is given in Section 6. In this part, we give a quick summary of our HIBS-DA framework. Section 4 provides a formal syntax, a full security analysis as well as a complete discussion of the methods. Syntax. A HIBS-DA scheme is defined by six polynomial time algorithms HIBS-DA=(HIBS-DA.Setup, HIBSDA.Derive, HIBS-DA.Sign, HIBS-DA.Verify, HIBS-DA.Aggregate, HIBS-DA.AggregateVerify). • HIBS-DA.Setup(1λ , 1t ) → (pp, M P K, M SK): Takes security parameter λ and maximum hierarchy depth t; outputs public parameters pp, master public key M P K, and master secret key M SK. • HIBS-DA.Derive(pp, SKID|ir , ID|ik ) → SKID|ik : Derives child identity secret key SKID|ik from parent key SKID|ir . • HIBS-DA.Sign(ID|ik , Mik , SKID|ik ) → vik : Produces signature vik on message Mik for identity ID|ik . • HIBS-DA.Verify(pp, ID|ik , Mik , vik ) → (1/0): Verifies signature vik for message Mik under identity ID|ik .
N • HIBS-DA.Aggregate {Mik }N → vk : Combines N message-signature pairs into aggregate i=1 , {vik }i=1 signature vk . • HIBS-DA.AggregateVerify({Mik }N i=1 , vk , M P K) → (1/0): Verifies aggregate signature vk against messages {Mik }N using M P K. i=1 Security. The standard notion for security used for our HIBS-DA scheme is Existential Unforgeability under Adaptive Identity and Chosen Message Attack (EUF-ID-CMA). In this security game, a PPT adversary A interacts with a challenger C, attempting to forge a valid aggregate signature for a specific hierarchical level k after making adaptive key and signature queries. The scheme is EUF-ID-CMA secure if for all PPT (λ) in winning this game is negligible in the security parameter λ. adversaries A, the advantage AdvHIBS-DA A Technical Overview. We now present a technical overview of our proposed HIBS-DA scheme. The system is built upon a cryptographic infrastructure headed by a Root Private Key Generator (Root PKG) at level 0, which oversees a hierarchy of depth t with levels indexed from 1 to t. Each level k (where 1 ≤ k ≤ t) consists of a fixed population of N entities. An entity at the k-th level of branch i is uniquely identified by the tuple ID|ik = (IDi1 , . . . , IDik ). Moreover, ID0 = IDi0 is the root PKG’s identity for each i = 1, 2, . . . , N . We consider a hierarchical setting in which, for a fixed hierarchical level k ∈ {1, . . . , t}, each of the N signers generates an individual signature on its corresponding message. A designated aggregator then collects all individual signatures and combines them into a single compact aggregate signature. The HIBS-DA framework is structured into six core phases (Setup, Derive, Sign, Verify, Aggregate, and AggregateVerify). The Setup phase, executed by a trusted third party (TTP), takes a security parameter 1λ and maximum depth 1t to produce a master public key M P K = A and a corresponding master secret key M SK = TA for the root PKG by using the TrapGen algorithm. The TTP also provides the designated aggregator with a short basis T for an intersection lattice, which is defined in Appendix 8.1 by using Lemma 1. In the Derive phase, a child entity at identity ID|ik derives its secret key from its parent’s secret key SKID|ir . This involves computing a public matrix PID|ik from the parent’s matrix and the child’s identity component, and then using the BasisDel algorithm to derive a basis consisting of short vectors S′ik for the child’s lattice, which becomes its secret key SKID|ik . For the Sign phase, a user ID|ik signs a message Mik by generating a lattice-based signature vik using the SamplePre algorithm with their secret key, which a verifier checks for validity. Finally, 4

in the Aggregate phase, the designated aggregator combines N individual signatures {vik }N i=1 on messages {Mik }N into a single compact signature v using the CRT (refer8.1,8.2) and the SamplePre algorithm. The k i=1 resulting aggregate signature vk can be efficiently verified to authenticate the entire set of messages and identities from level k. Security: The proposed HIBS-DA scheme is existentially unforgeable under adaptive identity and chosen message attack (EUF-ID-CMA) under the hardness assumption of the SIS problem.

. Fig. 2. Practical application of HIBS-DA.

2.1

A Toy Example

Figure 2 presents a toy example of our proposed HIBS-DA scheme. The scenario involves an institute with a Director, designated as the Root PKG, managing a system with three branches (N = 3) and a hierarchy depth t = 2. The scheme operates as follows: Departmental Record Aggregation: The Head of Department (HOD) at each branch, i.e., of each department signs their respective Placement Record Pi . Specifically, HODi signs Pi to produce signature si , for each i = 1, 2, 3. A designated aggregator then combines these three signatures {s1 , s2 , s3 } into a single aggregate 5

signature s, which validates the entire collection of placement records (P1 , P2 , P3 ). Financial Record Aggregation: In a parallel process, the financial officer (F Oi ) of each department generates a signature s′i on their respective Financial Record F Ri . A designated aggregator then compresses these signatures {s′1 , s′2 , s′3 } into a single aggregate signature s′ . This signature s′ provides collective authentication for the complete set of financial records (F R1 , F R2 , F R3 ). This approach allows the Director or any designated party to verify all placement records and financial records of each department using only two aggregate signatures (s and s′ ) instead of six individual ones, demonstrating significant efficiency gains.

3

Prelminaries

Notation. For an integer q ≥ 2, let Zq represents the ring of integers modulo q, and Zn×m denotes the q collection of all n × m matrices whose entries belong to Zq . Throughout, vectors are expressed using bold lowercase letters, while matrices are indicated by bold uppercase letters. Definition 1. (Lattices) [19]: A lattice in the Euclidean space Rn is generated by a set of m linearly independent vectors y1 , . . . , ym ∈ Rn with n ≥ m. It is defined as (m ) X L(y1 , . . . , ym ) = ci yi : ci ∈ Z i=1

that is, the collection of all integer linear combinations of the basis vectors yi . Here, m is the rank, and n is the dimension of the lattice. The set of vectors y1 , . . . , ym is referred to as a lattice basis. , we define For any A ∈ Zn×m q m L⊥ q (A) = {y ∈ Z : Ay = 0 mod q} . m Lu q (A) = {y ∈ Z : Ay = u mod q} ⊥ u ⊥ The lattice Lu q (A) is a coset of Lq (A); that is, Lq (A) = Lq (A)+t for any vector t satisfying A.t = u mod q.

Definition 2. TrapGen(n, m, q) [20]: The algorithm TrapGen is a probabilistic procedure that, given system parameters n, matrix width m, and a modulus q, outputs a pair TrapGen(n, m, q) −→ (A, T), where is a matrix chosen uniformly at random and T is a trapdoor basis having low norm for the lattice A ∈ Zn×m q ⊥ Λq (A) = { x ∈ Zm : Ax ≡ 0 (mod q) }. Definition 3. SamplePre(T,u,t) [20]: The sampling algorithm, runs in probabilistic polynomial time n (PPT), is given as input a pair (A, T) generated by the TrapGen(n, m, √ q) algorithm, a vector u ∈ Z , and a m Gaussian parameter t. It produces a vector x ∈ Z such that ∥x∥ ≤ t m and satisfies the modular equation Ax = u mod q. Definition 4. Domain sampling and uniform output [20]: √ SampleDom(1n ) samples an x from some m (possibly non-uniform) distribution over Dn = {e ∈ Z : ∥e∥ ≤ s m}, for which the distribution of Ax is uniform over Znq , where s is some prescribed bound. Definition 5. preimage min-entropy [20]: Let A ∈ Zn×m For each b ∈ Znq , the conditional min-entropy q n of c sampled from SampleDom(1 ), given that Ac = b, is no less than ω(log n). Definition 6. SampleRwithBasis [21] Let c1 , . . . , cm ∈ Znq be the column vectors comprising the matrix C ∈ Zn×m . q 1. Execute TrapGen(q, n, m) to obtain a uniformly distributed full-rank matrix D ∈ Zn×m together with a q trapdoor basis TD for Λ⊥ (D) satisfying q p g e ∥T D ∥ ≤ LTG = σR /ω( log m). 6

2. For each i = 1, . . . , m: (2a) Draw ri ← SamplePre(D, TD , ci , σR ). Then Dri = ci mod q. Moreover, the statistical distribution ci of ri is close to DΛ ⊥ (D),σ . R q (2b) Perform step (2a) repeatedly until ri is no longer a linear combination of r1 , . . . , ri−1 . 3. Consider R ∈ Zm×m constructed by placing r1 , . . . , rm as its columns. By construction, R has full rank modulo q. Output R and TD . Since DR = C mod q, it follows that D = CR−1 mod q. Therefore, TD is a basis consisting of short vectors −1 for Λ⊥ ). We need to verify that R is drawn according to some distribution that is close to Dm×m q (CR statistically. Definition 7. Short Integer Solution(SIS) [20]: Suppose q be an integer, A be a matrix from Zn×m , q and a real parameter β, the target is to find a nonzero integer vector x ∈ Zm that satisfies Ax ≡ 0 mod q and whose norm is at most β. Distributions over small-norm matrices. A matrix R ∈ Zm×m has an inverse over Zq , or is called invertible when its reduction modulo q remains invertible in Zm×m . Our construction operates with matrices q possessing this Zq -invertibility whose columns all have small Euclidean norm. Definition 8. Set e T G · ω( σR := L

p p p log m) = n log q ω( log m).

We define Dm×m as the distribution over matrices in Zm×m obtained by drawing each column independently from DZm ,σR and conditioning on ensuring that the resulting matrix is invertible over Zq . Definition 9. SampleR(1m ). The procedure SampleR(1m ) generates matrices over Zm×m whose distribution is within negligible statistical distance of Dm×m . 1. Consider B denote the standard lattice basis of Zm . 2. For each j = 1, . . . , m, sample si ← SampleGaussian(Zm , B, σR , 0). 1. Form the matrix R from the vectors si . Output R when it is invertible modulo q, otherwise, perform step 2 again. Definition 10. Basis delegation: BasisDel(A, R, TA , σ). We next introduce an algorithm for basis delegation which maintains the dimensions of the matrices throughout the computation. This procedure allows one to transform a given lattice basis through a Zq -invertible matrix while preserving the structural properties required for lattice-based cryptographic constructions. Inputs: , representing the original lattice constraints. – A rank-n matrix A ∈ Zn×m q – A Zq -invertible matrix R ∈ Zm×m , sampled from the distribution Dm×m (or a product of such matrices), which defines the transformation applied to the lattice basis. – A basis TA of the lattice Λ⊥ q (A). – A positive real parameter σ ∈ R>0 , controlling the Gaussian sampling in subsequent computations. Output: The algorithm computes B := AR−1 ∈ Zn×m and outputs a basis TB of the lattice Λ⊥ q q (B). This basis TB effectively delegates the structure of TA through the transformation induced by R. Lemma 1. [19] Let L be an n-dimensional lattice. There is a polynomial time algorithm which, given a lattice basis B and linearly independent vectors {b1 , . . . , bm } ⊆ L(B) ordered by non-decreasing norm such ∥b1 ∥ ≤ ∥b2 ∥ ≤ · · ·≤ ∥bm ∥, outputs a basis R = {r1 , . . . , rm } equivalent to B. The output basis √

k ∥bk ∥, ∥bk ∥}, for all k = 1, 2, . . . m. Furthermore, it holds that span(r1 , . . . , rk ) = 2 ∗ span(b1 , . . . , bk ) and ∥rk ∥ ≤ ∥b∗k ∥ for every k = 1, 2, . . . m. Lemma 2. [21] Let A ∈ Zn×m be a rank-n matrix, and let R ∈ Zm×m be a Zq -invertible matrix sampled q

satisfies ∥rk ∥ ≤ max{

from the distribution Dm×m (or obtained as a product of such matrices). Let TA be a basis of the lattice Λ⊥ q (A), and let σ ∈ R>0 be a parameter. Then the algorithm BasisDel(A, R, TA , σ) outputs a basis TB of −1 the lattice Λ⊥ . q (B), where B = AR 7

3.1

Chinese Remainder Theorem (CRT) [22]:

Theorem 1. Consider a commutative ring R with unity, and suppose S1 , S2 , . . . , SN be ideals of R that are pairwise comaximal, i.e., Si + Sj = R for all i ̸= j. Then there is a ring isomorphism R TN

i=1 Si

∼ =

N Y R i=1

Si

,

given by r 7→ (r mod S1 , r mod S2 , . . . , r mod SN ), 3.2

r ∈ R.

Aggregate Signature

An aggregate signature enables N distinct signatures each generated by N different signers on N separate messages to be efficiently combined into a single compact signature. Following the framework introduced by Boneh et al. [8], we define syntax and security properties of Aggregate Signature (AS) scheme. Definition 11 (Syntax). Suppose λ denotes the security parameter. An aggregate signature scheme is specified by a tuple of 5-algorithms AS = (AS.KeyGen, AS.Sign, AS.Verify, AS.Aggregate, AS.AggregateVerify), defined as follows. AS.KeyGen(1λ ) → (pki , ski ): Given the security parameter λ, the Key Generation Centre (KGC) produces and distributes a corresponding public/secret key pair (pki , ski ) to the signer i, for each i = 1, . . . , N . AS.Sign(ski , µi ) → vi : Using its secret key ski and the message µi to be signed, the i-th signer generates the corresponding signature vi for µi . AS.Verify(pki , µi , vi ) → 0/1: Provided the i-th signer’s public key pki along with the message–signature pair (µi , vi ). If (µi , vi ) meets certain verification criteria, then output 1 and accept; otherwise, output 0 and reject. AS.Aggregate({pki , µi , vi }N i=1 ) → v: For each i = 1, . . . , N , the aggregation algorithm takes the message–signature pairs (µi , vi ) along with their respective public verification keys pki , the aggregator produces the aggregate signature v. AS.AggregateVerify(v, {pki , µi }N i=1 ) → 0/1: Provided the aggregate signature v together with the public keys pki and messages µi for all i = 1, . . . , N . If the tuple (v, {pki , µi }N i=1 ) meets the specified verification conditions, produce 1 to accept; otherwise, produce 0 to reject. For the scheme AS, it is essential to ensure correctness together existential unforgeability against chosen-message attack (EUF-CMA). Correctness. For all λ, N ∈ N, for all key pairs (pki , ski ) ← AS.KeyGen(1λ ), and for all messages µi ∈ M, where M denotes the set of message space, and vi ← AS.Sign(ski , µi ) for all i ∈ {1, . . . , N }: N N AS.AggregateVerify({pki }N i=1 , {µi }i=1 , AS.Aggregate({AS.Sign(ski , µi )}i=1 )) = 1,

where 1 denotes True. Security: Existential Unforgeability under Chosen Message Attack. Informally, the security of an aggregate signature scheme is defined by the infeasibility of an adversary successfully producing a forged aggregate signature within the parameters of a specified security game. In this context, existential forgery refers to the ability of the adversary to create a valid aggregate signature over messages of his choosing, purportedly signed by a selected subset of users. We rigorously define this notion using the aggregate chosen-key model for EUF-CMA. Within the framework of this model, an adversary A is given access to a single public key. The adversary’s objective is to perform an 8

existential forgery of an aggregate signature. A is granted the capability to select all public keys except for one challenge key, and may also query a signing oracle associated with this challenge key. The adversary’s advantage, denoted as AdvAggSig , is quantified by its probability of success in the following EUF-CMA game: A Setup. The adversary A receives a public key P K1 , generated uniformly at random. Queries. The adversary A may adaptively request signatures on messages of its choice under the challenge key P K1 . Response. Eventually, A emits k −1 extra public keys P K2 , . . . , P Kk , where k ≤ N , with N being a predefined game parameter. These keys, together with P K1 , form the set of signers in the forged aggregate. A also outputs the corresponding messages M1 , . . . , Mk and an aggregate signature v, allegedly produced by these k users. The adversary wins the game if the aggregate signature v is a valid existential forgery, that is, v verifies correctly for the messages M1 , . . . , Mk under the public keys P K1 , . . . , P Kk , and the forgery is nontrivial. That is, A did not make a signature request on M1 under P K1 . The probability of A’s success is determined based on the random choices made during the key generation and signing procedures of the scheme. 3.3

Hierarchical Identity Based Signature

A Hierarchical Identity-Based Signature (HIBS) lets users in an organization use their identity as their public key. They get private keys from their parent in the hierarchy and can sign messages. Anyone can verify signatures using just the signer’s identity and the organization’s root public key, removing the need for certificates. Building on the framework proposed by Gentry et al. [7], we describe the protocol below. Definition 12 (Syntax). Let λ denote the security parameter. An HIBS scheme is defined by a tuple of five algorithms HIBS=(HIBS.RootSetup, HIBS.LowerLevelSetup, HIBS.Extract, HIBS.Sign, HIBS.Verify) HIBS.RootSetup(1λ , 1t ) → (pp, M SK): The root private key generator (PKG) takes a security parameter λ and the maximum depth t as input and generates the system’s public parameters pp, and the master secret key M SK. The system’s public parameters include a description of the message space M. pp will be publicly available, while only the root PKG will know M SK. HIBS.LowerLevelSetup(pp, ID|r ) → (SKID|r ): The algorithm takes the public parameter pp and an identity ID|r of the child as input and outputs the secret key SKID|r for the given identity, which will be utilized to issue the secret signing key for the child identity ID|r . HIBS.Extract(SKID|r , ID|k ) → SKID|k : Given a parent’s secret key SKID|r for an identity ID|r = (ID0 , ID1 , . . . , IDr ), and the identity ID|k for which secret key is to be extracted as input, the PPT algorithm produces a secret signing key SKID|k for the identity ID|k = (ID0 , . . . , IDr , . . . , IDk ). HIBS.Sign(pp, SKID|k , M ) → v: Using the public parameter pp, private key SKID|k and a message M as input, the PPT algorithm generates a signature v for the specified identity. HIBS.Verify(pp, ID|k , M, v) → (1/0): Given the public parameter pp, a message–signature pair associated with an identity, If the signature verifies correctly, the algorithm returns 1, if it fails verification, it returns 0. For the HIBS scheme, it is crucial to guarantee correctness and Strong Unforgeability against adaptive identity and Chosen Message Attack (SU-aID-CMA) security. Correctness. When skID|k is the private key generated by the HIBS.Extract algorithm for the identity ID|k , then: ∀M ∈ M : HIBS.Verify(pp, ID|k , M, HIBS.Sign(pp, SKID|k , M )) = valid. Strong Unforgeability under adaptive identity and Chosen Message Attack. The strongest security model for a Hierarchical Identity-Based Signature (HIBS) scheme is strong unforgeability against adaptive identity and chosen message attacks (SU-aID-CMA). This security notion is formalised through a security game involving a challenger C and an adversary A, defined as follows: 9

Setup: To generate the system parameters pp, the Setup algorithm is executed by the challenger C and the adversary A is provided pp. Extract Queries: The adversary A can adaptively request private keys for any chosen identity ID. Upon receiving such a request, the challenger C executes the Extract algorithm to generate the corresponding secret key SID and returns it to A. Sign Queries: A may adaptively select an identity ID along with a message M and request a signature. The challenger C determine the signature ν = HIBS.Sign(M, SID ) and returns it to A. Forgery: Finally, the adversary A outputs a forged signature (ν ∗ , M ∗ , ID∗ ). The adversary is considered successful if HIBS.Verify(ν ∗ , M ∗ , ID∗ ) = 1 and neither ID∗ nor any of its prefixes were queried during the Extract phase, and the pair (M ∗ , ID∗ ) was not used in the Sign phase. In summary, the adversary A wins the SU-aID-CMA game if it can produce a valid signature for a new message–identity pair without having obtained the corresponding private key or signature from the challenger.

4

Hierarchical Identity-Based Signature with Designated Aggregator (HIBS-DA)

Consider a hierarchical cryptographic infrastructure governed by a Root Private Key Generator (Root PKG) at level 0. The secret key and public key for the Root PKG is M SK and M P K, respectively, where M SK is defined as SKID|i0 , for each i ∈ {1, . . . , N }. The system has a hierarchical depth t, comprising t distinct levels beneath the root. These subordinate levels are sequentially indexed from 1 (immediately below the root) to t (the leaf level). Each hierarchical level k (1 ≤ k ≤ t) contains a fixed population of N entities, referred to as nodes or individuals. Let IDik denote the identity of i-th entity at hierarchical level k, where k ∈ {1, 2, . . . , t} denotes the hierarchical level and i ∈ {1, 2, . . . , N } denotes the entity index within the level. A trapdoor delegation mechanism based on BasisDel (refer 10) allows a parent in the hierarchy to securely derive a child’s private key without revealing its own trapdoor. This supports arbitrary depth up to t + 1 while preserving security. The primary objective of this scheme is to perform cryptographic aggregation of digital signatures originating from a specific hierarchical level k, for some 1 ≤ k ≤ t. This process aims to consolidate the N distinct signatures generated by all members at level k into a single, compact cryptographic attestation. The aggregation mechanism proceeds as follows: Each entity ID|ik , where ID|ik is defined as ID|ik = (IDi1 , . . . , IDik ), for all 1 ≤ k ≤ N at hierarchical level k, generates signatures on their messages Mik using their respective private key SKID|ik . A designated aggregator collects all N signatures and computes an aggregate signature vk for the hierarchical level k. The aggregate signature vk can be verified against the public key corresponding to all N members of level k. Upon completion, the Root PKG (or any authorized entity) possesses the aggregate signature vk . Definition 13 (Syntax). Let λ be the security parameter. An HIBS-DA scheme is formally defined by six algorithms HIBS-DA=(HIBS-DA.Setup, HIBS-DA.Derive, HIBS-DA.Sign, HIBS-DA.Verify, HIBS-DA.Aggregate, HIBS-DA.AggregateVerify). HIBS-DA.Setup(1λ , 1t ) → (pp, M P K, M SK): Given a security parameter λ and the maximum depth t, the setup algorithm generates the system public parameters pp, the master public key M P K and the master secret key M SK for the root PKG. HIBS-DA.Derive(pp, SKID|ir , ID|ik ) → SKID|ik : Given the system public parameter pp, private key SKID|ir corresponding to an identity ID|ir = (IDi1 , . . . , IDir ) of a parent and an identity ID|ik = (IDi1 , . . . , IDir , . . . , IDik ) of a child as input, the algorithm produces a secret key SKID|ik for the identity ID|ik . HIBS-DA.Sign(ID|ik , Mik , SKID|ik ) → vik : Given an identity ID|ik , a private key SKID|ik corresponding to the identity ID|ik and a message Mik , the sign algorithm produces a signature vik for the identity ID|ik . HIBS-DA.Verify(pp, ID|ik , Mik , vik ) → (1/0): Given system public parameter, corresponding identity ID|ik , message Mik , and signature vik , outputs 1 if the signature is valid and 0 otherwise. 10

N HIBS-DA.Aggregate {Mik }N i=1 , {vik }i=1 → vk : An algorithm that, given message-signature pairs (Mik , vik ), for each i = 1, . . . , N , the honest designated aggregator produces the aggregate signature vk . N HIBS-DA.AggregateVerify({Mik }N i=1 , vk , M P K) → (1/0): On input messages {Mik }i=1 , aggregate signature vk , and the master public key M P K. It yields 1, provided that the signature is valid. Otherwise, 0. The HIBS-DA scheme must achieve correctness and Existential Unforgeability under Adaptive Identity and Chosen Message Attack security model. 4.1

Correctness

An HIBS-DA scheme is correct if for all security parameters λ, all hierarchical depths t, all identity tuples ID|ik = (IDi1 , . . . , IDik ), and messages Mik ∈ M: 1. Individual Verification: For any valid (pp, M P K, M SK) ← HIBS-DA.Setup(λ, t) and SKID|ik HIBS-DA.Derive(pp, SKID|ir , ID|ik ):

←

Pr [HIBS-DA.Verify (pp, ID|ik , Mik , vik ) = 1] = 1 where vik ← HIBS-DA.Sign(ID|ik , Mik , SKID|ik ) 2. Aggregate Verification: For any set of N valid pairs {(Mik , vik )}N i=1 : 
 Pr HIBS-DA.AggregateVerify {Mik }N i=1 , vk , M P K = 1 = 1
N where vk ← HIBS-DA.Aggregate {Mik }N i=1 , {vik }i=1 . 4.2

Security Model

The standard security requirement of the HIBS-DA scheme is Existential Unforgeability against Adaptive Identity and Chosen Message Attack (EUF-ID-CMA): We define the security of our HIBS-DA scheme through a game played between a challenger C and a probabilistic polynomial-time (PPT) adversary A, where the adversary aims to forge a valid aggregate signature for a specific hierarchical branch k within the scheme. Definition 14. Security Against Existential Unforgeable under Adaptive Identity and Chosen Message Attack (EUF-ID-CMA). An HIBS-DA scheme is said to be EUF-ID-CMA secure if for all PPT adversaries A, the probability that A wins the above game is negligible in the security parameter λ: AdvHIBS-DA (λ) = Pr[A wins the EUF-ID-CMA game] ≤ negl(λ) A The security game is defined as follows: Setup. The challenger C runs the setup algorithm (M P K, M SK) ← Setup(1λ , 1t ), where λ is the security parameter and t is the maximum hierarchy depth. The challenger gives the master public key M P K to the adversary A and keeps the master secret key M SK private. Query Phase. The adversary A may adaptively make the following oracle queries: (i) Key Extraction Query: A may request the private key for any hierarchical identity ID|ik = (IDi1 , . . . , IDik ). The challenger returns the corresponding secret key SKID|ik . A is not allowed to extract the secret key belonging to the target identity or any among its ancestors. (ii) Signing Query: A may request a signature on any message Mik under a valid identity ID|ik except the target message. The challenger responds with a valid signature vik ← Sign(SKID|ik , Mik ). (iii) Aggregate (Designated Aggregator) Query: A may request the designated aggregator to combine mul|S| |S| tiple signatures {vik }i=1 on messages {Mik }i=1 corresponding to identities S = (ID|1k , . . . , ID||S|k ). The challenger responds with |S| vk,S ← Aggregate({Mik , vik }i=1 ). The adversary is restricted so that no identity appears with different messages in overlapping aggregate queries. 11

Forgery. Finally, A outputs a candidate forgery ∗ ∗ ∗ (S ∗ , {Mik }i∈S ∗ , {IDik }i∈S ∗ , vk,S ∗ ), ∗ ∗ where S ∗ = (ID∗ |1k , . . . , ID∗ ||S ∗ |k ) is a set of hierarchical identities, {Mik } are messages, and vk,S ∗ is an aggregate signature, where k is at most N . Winning Condition. The adversary A wins the game if both of the following hold: (i) The forged aggregate signature verifies correctly: |S ∗ |

∗ ∗ Verify(M P K, S ∗ , {Mik }i=1 , vk,S ∗) = 1

. (ii) There exists at least one identity ID∗ |jk ∈ S ∗ such that A did not query the key extraction oracle for ∗ ID∗ |jk or any of its ancestors, and A did not obtain a signature on message Mjk for ID∗ |jk in any prior signing or aggregation query. In short, the HIBS-DA scheme is considered secure if no efficient adversary can generate a valid aggregate signature that includes at least one new identity–message pair for which it has never obtained the corresponding private key or legitimate signature.

5

Our Construction

Consider a hierarchical cryptosystem of depth t, a Root PKG at level 0 governs t lower levels. Each level k (from 1 to t) consists of N entities, where each entity signs its message Mik with its private key SKID|ik . A designated aggregator collects all N signatures from level k and computes a single aggregate signature vk . The HIBS-DA scheme is constructed below. Let q ≥ 3 be a prime and m ≥ 6n log q. Define ID0 = IDi0 is the root PKG’s identity and ID|ik = (IDi1 , . . . , IDik ) denotes the identity √of k-th level entity of branch i for each i = 1, 2, . . . , N . Let H : {0, 1}∗ −→ Zm×m and σik , σ ≥ ω(log m). The lattices Lik , for each i = 1, 2, . . . , N , and for fixed q k ∈ {1, 2, . . . , t}, are defined in (refer8.1). Below, we detail our lattice-based HIBS-DA scheme.: HIBS-DA.Setup(1λ , 1t ) → (M P K, M SK) On input the security parameter λ and the hierarchy depth t, a trusted third party does the following: for the lattice and a short generating basis TA ∈ Zm×m (i) Run TrapGen(1λ ) to derive a matrix A ∈ Zn×m q q ⊥ Λq (A). (ii) Disclose the master public key M P K = A and retain the master secret key M SK = TA confidential. (iii) Consider SK ID|i0 = TA and PID|i0 = A, for each i ∈ {1, . . . , N }, are the secret key and public key of the root PKG, respectively. (iv) Generate a basis T for the lattice L1k ∩ L2k ∩ . . . ∩ LN k by using Lemma 1 and give the basis T to the designated aggregator. HIBS-DA.Derive(PID|i0 , SKID|ir , ID|ik ) → (SKID|ik ) On input the public key PID|i0 of root PKG, a secret signing key SKID|ir corresponding to a “parent” identity ID|ir = (IDi1 , . . . , IDir ), and a “child” identity ID|ik = (IDi1 , . . . , IDir , . . . , IDik ) where k ≤ t: (i) Let RID|ir = H(IDir ) · · · H(IDi2 )H(IDi1 ) ∈ Zm×m and q n×m PID|ir = AR−1 ∈ Z . Then SK is a short reduced basis (refer 2) for Λ⊥ ID|ir q q (PID|ir ). ID|ir −1 m×m (ii) Compute Rik = H(IDik ) · · · H(IDi(r+1) ) ∈ Zq and set PID|ik = PID|ir Rik . 12

(iii) Evaluate S′ik ← BasisDel(PID|ir , Rik , SKID|ir , σik ) to get a short, randomly generated basis for Λ⊥ q (PID|ik ). ′ (iv) Output the private key obtained through delegation SKID|ik = Sik . ′ (v) SKID|ik = Sik and PID|ik = PID|ir R−1 ik are secret key and public key, respectively corresponding to the identity ID|ik

HIBS-DA.Sign(ID|ik , SKID|ik , Mik ) → vik Given a user ID|ik holding a secret signing key SKID|ik along with a message Mik ∈ {0, 1}∗ . (i) Choose a string bik ∈ {0, 1}n , for i = 1, 2, . . . , N . (ii) Compute vik ← SamplePre(PID|ik , SKID|ik , σik , h(Mik , bik , ID|ik )), where h : {0, 1}∗ → Znq is a hash √ function. Moreover, the resulting signature vik satisfies PID|ik vik = h(Mik , bik , ID|ik ) and ∥vik ∥ ≤ σik m. (iii) Output the individual signature vik . HIBS-DA.Verify(PID|ik , ID|ik , vik , Mik ) → accept/reject For each i = 1, 2, . . . N , on input the public key PID|ik , identitity ID|ik , where k ∈ {1, 2, . . . t}, a signature vik and a message Mik , the verifier will accept the√ signature precisely when PID|ik vik = h(Mik , bik , ID|ik ) and ∥vik ∥ ≤ σik m. N HIBS-DA.Aggregate({Mik }N i=1 , {vik }i=1 , T ) → vk

The honest designated aggregator performs the following operations to combine N message-signature pairs (Mik , vik ) by using Chinese Remainder Theorem 1. (i) Computes x ∈ Zm such that x ≡ v1k (mod L1k ) x ≡ v2k (mod L2k ) .. . x ≡ vN k (mod LN k ) (ii) This x may not be short. To get a short signature, the designated aggregator does the following: (a) Output vk ← SamplePre(L1k ∩ L2k ∩ . . . ∩ LN k , T , x, σ) ∈ (L1k ∩ L2k ∩ . . . ∩ LN k ) + x. (b) The hierarchical identity-based signature with designated aggregator (HIBS-DA) is vk . HIBS-DA.AggregateVerify(M P K, ID|ik , vk , {Mik }N i=1 ) → accept/reject On input the master public key A, identities ID|ik , aggregate signature vk and messages {Mik }N i=1 , The verifier will accept the signature only when PN PN √ −1 vk = i=1 h(Mik , bik , ID|ik ) and ∥vk ∥ ≤ σ m. i=1 A[H(IDik ), . . . , H(IDi1 )] 13

5.1

Correctness

The correctness of SamplePre ensures that each vik is short and satisfies the equation −1 PID|ik vik = PID|ir Rik vik −1 −1 = ARID| Rik vik ir

 −1  −1 = A H(IDir ), . . . , H(IDi1 ) H(IDik ), . . . , H(IDi(r+1) ) vik    = A H(IDi1 )−1 , . . . , H(IDir )−1 H(IDi(r+1) )−1 , . . . , H(IDik )−1 vik  −1 = A H(IDik ), . . . , H(IDi1 ) vik = h(Mik , bik , IDik ). As a result, the correctness of each individual signature is verified. The solution derived from these equations  x ≡ v1k (mod L1k )     x ≡ v2k (mod L2k ) ..   .    x ≡ vN k (mod LN k )

(1)

is a vector x. According to the CRT (refer 1), x corresponds uniquely to the tuple (v1k , . . . , vN k ). However, x 1k 2k Nk might not be short. To shorten, we √ apply algorithm SamplePre((L ∩ L ∩ . . . ∩ L ), T , x, σ) to get vk . This vk is short enough. i.e., ∥vk ∥ ≤ σ m, with vk being in the same coset as x. It follows that vk satisfies equation 1 and is of short length. i.e., vk mod Lik = vik mod Lik . We now observe that

N X

A[H(IDik ), . . . , H(IDi1 )]−1 vk =

i=1

N X

h(Mik , bik , ID|ik ).

i=1

Hence, vk authenticates all the messages Mik , for i = 1, 2, . . . N and for some fixed k ∈ {1, . . . , t}.

5.2

Security Proof

Theorem 2. If the SIS problem is computationally infeasible, then the proposed HIBS-DA scheme is existentially unforgeable under adaptive identity and chosen message attack (EUF-ID-CMA) secure. Proof. Suppose A is a probabilistic polynomial-time (PPT) adversary that aims to break the security of the HIBS-DA scheme, where H and h both are treated as random oracles, and let QH and qh be the total queries performed by A respectively and t be the maximum hierarchy depth, and suppose A forges the signature for the level k (let), for 1 ≤ k ≤ t, that is A forges the aggregate signature produced by the identities {ID|1k , . . . , ID|N k }, then there is a PPT algorithm C that solves the SIS problem. We employ A to build an algorithm that solves the SIS problem. Setup. C sets up an environment that imitates attack conditions for A in the following manner. 1. Pick N · t integers Q∗i1 , . . . , Q∗it ∈ [QH ], where i ∈ {1, . . . , N } uniformly at random and QH specifies the maximum number of queries to H that A can submit for each i. 14

∗ ∗ ∗ 2. Sample N · t matrices Ri1 , . . . , Rit ∼ Dm×m uniformly at random by executing Rij ← SampleR(1m ) for j = 1, . . . , t and i = 1, . . . , N . 3. Construct a random matrix A0 ∈ Zn×m . q ∗ ∗ , i = 1, . . . , N. Because A0 is uniform · · · Ri1 4. Pick w ∈ [t] uniformly at random and assign Ai ← A0 Riw n×m ∗ in Zq and all Rij are invertible modulo q, each Ai is uniformly distributed over Zn×m . q 5. Issue parameter pp = Ai publicly.

Random-oracle hash queries (H). The adversary A is permitted to, at any time, adaptively query the random oracle H on any identity ID|ik = (IDi1 , . . . , IDik ) of its choosing. The challenger C handles the QH -th distinct query as described below. For simplicity, we assume that all queries are unique; if A repeats a query, the simulator returns the previously stored output and does not increment the counter QH . Let i = |(ID|ik )| denotes the identity’s ID|ik depths. When such a query corresponds to Q∗ik (meaning ∗ QH = Q∗ik ), we proceed to assign H(ID|ik ) ← Rik and output H(ID|ik ). ∗ In all other cases, when QH ̸= Qik : ∗ ∗ ∗ −1 1. Evaluate Aik = Ai · (R(i−1)k · · · R2k R1k ) ∈ Zn×m (where A1k = A1 ). q 2. Execute SampleRwithBasis(Aik ) to generate Rk ∼ Dm×m uniformly at random and a concise basis TBk for Bk = Aik Rk−1 mod q. 3. Store the 5-tuple (i, ID|ik , Rk , Bk , TBk ) for later employ, and output H(ID|ik ) ← Rk .

Secret key queries. The adversary A adaptively make interactive queries that extract keys for arbitrary identities ID|ik , of its choice. C responds a query on ID|mk = (ID1k , ID2k , . . . , IDmk ) of length |(ID|mk )| = m ∈ [t] as detailed below. ∗ 1. Let us suppose j ∈ [m] denote the earliest level where H(ID|jk ) ̸= Rjk . If, in the unexpected case, ∗ H(ID|jk ) = Rjk for every j = 1, . . . , m, the simulator terminates, at which point the process does not succeed. 2. Recover the previously stored tuple (j, ID|jk , Rk , Bk , TBk ) from the recorded query history of the hash oracle H. This tuple arises from answering a query to H(ID|jk ). (Without loss of generality, we may suppose that any extraction query on ID|mk is introduced by queries to the hash oracle across all prefixes of ID|mk .) As a consequence of the construction, ∗ −1 ∗ Bk = Aj · (R1k ) · · · (R(j−1)k )−1 · H(ID|jk )−1

mod q,

and TBk constitutes a concise basis of Λ⊥ q (Bk ). Observe that Bk is precisely the signature matrix PID|jk (as specified by the signing algorithm) for identity ID|jk = (ID1k , ID2k , . . . , IDjk ) of the ancestor and therefore TBk is a trapdoor for Λ⊥ q (PID|jk ). 3. Execute BasiDel(PID|jk , H(ID|mk ) . . . H(ID|(j+1)k ), TBk , σjk ) to produce a secret signing key for ID|jk and delivers the resulting secret key to A. Random-oracle hash queries(h) and sign queries. C generates a list L to record the responses to the ∗ h queries. C runs A on public key PID|ik , for i ∈ {1, . . . , N } and A declares to C the identity IDik chosen ∗ for the challenge along with a message Mik to be signed and provides a simulation of the random oracle h ∗ ∗ ∗ together with signing oracle as follows. Since, k = |(IDik )|. Recall that Ai = A0 Riw · · · Ri1 . If w ̸= k then the ∗ ∗ ∗ for simulator terminates and does not succeed. Next, assume w = k and IDik is satisfying H(IDik ) = Rik ∗ −1 ∗ −1 all i ∈ {1, . . . , k}. It follows directly from the definition that PID|∗ik = Ai (Ri1 ) . . . (Rik ) = A0 ∈ Zn×m . q Assume, without loss of generality that A queries h for each message Mik prior to issuing a signing query on Mik for fixed k. – For each query made to h on a different Mik ∈ {0, 1}∗ , C chooses aik ∈ {0, 1}n uniformly at random, runs vik ← SampleDom(1n ), and stores (Mik , aik , ID|ik , h, vik ) in the list L, and returns PID|ik vik = h(Mik , aik , ID|ik ) to A. (If h already been queried on Mik , C searches for (Mik , vik ) and supplies PID|ik vik .) 15

– Whenever A issues a signing query on the pair (Mik , ID|ik ), C looks up the list in its local memory and outputs vik as the resulting signature. ∗ Let us suppose, without loss of generality that prior to producing its attempted forgery (Mik , ID|∗ik , vik ), A ∗ ∗ ∗ ∗ queries h on (Mik , ID|ik ) and produces the signature vik for the message-identity pair (Mik , ID|∗ik ).

Aggregate queries. The adversary A is allowed to request aggregate signatures on any set of tuples {(Mik , IDik , vik )}N i=1 of its choice except the list containing challenged message-identity pair. Upon receiving such a request, the challenger C computes a compact aggregate signature by employing the Chinese Remainder Theorem (CRT) and the sampling algorithm sampleDom(1n ). The resulting HIBS-DA signature vk satisfies N X i=1

PID|ik · vk =

N X

h(Mik , aik , ID|ik ).

i=1

Forgery. After obtaining sufficient information through oracle queries, A outputs a forged aggregate signature vk∗ . In order for the forgery to be valid, the adversary must include at least one identity–message pair ∗ ∗ (IDik , Mik ) that was not queried to the signing oracle, although it may have queried the hash oracle on that pair. Upon receiving the forged signature vk corresponding to the tuples {(Mik , IDik , vik )}N i=1 , the challenger ∗ ∗ ∗ C inspects its record of message-identity pairs and identifies the corresponding entry (Mik , IDik , vik ). It then ∗ compares the legitimate HIBS-DA signature vk with the forged one, obtaining A0 · (vk − vk∗ ) = 0, which constitutes a valid solution to an SIS instance. We need to only show that vk ̸= vk∗ . Applying the preimage min-entropy property (refer 5) of the employed family of hash functions, the conditional min-entropy of vk , given Ai [H(IDik ) . . . H(IDi1 )]−1 · vk (and the remaining view obtained by A, which is not dependent on vk ) is ω(log n). Consequently, the probability that vk = vk∗ is negligible, and thus the forgery succeeds only with negligible probability.

6

Efficiency Analysis

This section presents the efficiency analysis of our proposed HIBS-DA scheme. We describe the detailed round complexity, the communication complexity, and the computation complexity of our proposed HIBS-DA sheme below. Round Complexity: Our proposed HIBS-DA scheme is non-interactive. The signing process is executed locally by each signer individually by using their corresponding secret key. Subsequently, aggregation requires only a single, one-way transmission of individual signatures from the signers to the designated aggregator, who then performs the aggregation as a local computation. Since an interactive protocol is formally defined as one requiring multiple rounds of communication back and forth between parties, the core operations of our scheme, signing and aggregation, exhibit a round complexity of zero. Communication Complexity: The communication complexity of our proposed HIBS-DA scheme is analyzed in terms of the total number of bits exchanged among the involved entities, namely the root PKG, subordinate PKGs, signers, the designated aggregator, and the verifier. Each phase of the scheme involves the transmission of latticebased matrices or vectors whose sizes depend on the lattice parameters m, n, and the modulus q. Specifically, each element in Zq can be represented using ⌈log2 q⌉ bits, which allows us to express the communication cost in terms of bit lengths. Table 1 summarizes the communication requirements of each phase in bits. 16

Table 1. Communication complexity of our proposed HIBS-DA scheme Phase

Communication Parties Data Transmitted

Setup

PKG → Public

Bit Complexity

Publish A ∈ Zn×m q

nm⌈log2 q⌉ bits (once)

Key Derivation Parent → Child

Send SKID|ir ∈ Zm×m q

m2 ⌈log2 q⌉ bits per delegation

Signing

(Local operation)

None

0 bits

Aggregation

N Signers → Aggregator

Send N signatures vik ∈ Zm q N m⌈log2 q⌉ bits

Verification

Aggregator → Verifier

Send vk ∈ Zm q

m⌈log2 q⌉ bits

The total communication cost of our HIBS-DA scheme is obtained by summing the communication requirements of all components. Since the hierarchical depth is (t + 1), there are t key delegation steps. Hence, the total communication complexity in bits is: Ctotal = (nm⌈log2 q⌉) + (t · m2 ⌈log2 q⌉) + (N m⌈log2 q⌉) + (m⌈log2 q⌉) = (m + tm2 + nm + N m)⌈log2 q⌉
≈ O (tm2 + N m)⌈log2 q⌉ bits.

(2)

Computation complexity: The computation cost of each algorithm in our proposed lattice-based HIBS-DA scheme is summarized in Table 2. The analysis is carried out relative to the lattice parameters n, m, modulus q, hierarchy depth k, and the number of aggregated users N . Here, Õ(·) hides polylogarithmic factors in n and q. During the Setup phase, the TrapGen algorithm dominates the cost, resulting in complexity Õ(n2 ). The Derive phase involves basis delegation and matrix multiplications at each hierarchical level, with an overall complexity of Õ(k · m3 ). Both the Sign and Verify phases rely primarily on Gaussian sampling and matrix–vector operations, yielding Õ(m2 ) and O(m2 ) complexities, respectively. The Aggregate phase introduces an additional Chinese Remainder Theorem (CRT) computation O(N m) and short vector sampling Õ(m2 ). Finally, the AggregateVerify phase performs N parallel matrix–vector multiplications, resulting in O(N m2 ) complexity. Note: Õ(·) hides polylogarithmic factors in n and q.

Table 2. Computation Complexity of our proposed HIBS-DA scheme Algorithm Main Cost Asymptotic Complexity Setup Trapdoor generation Õ(n2 ) Õ(k · m3 ) Derive Basis Delegation Sign Gaussian Sampling Õ(m2 ) Verify Matrix-Vector Multiplication O(m2 ) Aggregate CRT + intersection lattice sampling O(N m) + Õ(m2 ) AggregateVerify N Matrix-Vector Multiplications O(N · m2 )

In this analysis, we have discussed the round complexity, the computation complexity, and the communication complexity in terms of bits where the communication cost depends on the parameters n, m, q.

7

Conclusion

In this paper, we provided the first hierarchical identity-based signature with designated aggregator protocol that effectively addresses the challenges of secure, efficient, and scalable authentication in multi-level organizational settings. Our analysis confirms that the proposed scheme ensures correctness, unforgeability, and consistency, while maintaining scalability and practicality within the hierarchy, making HIBS-DA a strong candidate for deployment 17

in modern decentralized systems that require structured authentication with minimal overhead. Our scheme is
non-interactive with zero round complexity. Moreover, the communication complexity is O (tm2 + N m) ⌈log2 q⌉ bits, and the scheme achieves computation complexities of Õ(n2 ) for Setup, Õ(km3 ) for Derive, Õ(m2 ) for Sign, O(m2 ) for Verify, O(N m) + Õ(m2 ) for Aggregate, and O(N m2 ) for AggregateVerify.

References 1. Adi Shamir. Identity-based cryptosystems and signature schemes. In Workshop on the theory and application of cryptographic techniques, pages 47–53. Springer, 1984. 2. Dan Boneh and Matthew Franklin. Identity-based encryption from the weil pairing. SIAM journal on computing, 32(3):586–615, 2003. 3. Florian Hess. Efficient identity based signature schemes based on pairings. In International workshop on selected areas in cryptography, volume 2595, pages 310–324. Springer, 2002. 4. Shangping Wang, Ru Zhao, and Yaling Zhang. Lattice-based ring signature scheme under the random oracle model. International Journal of High Performance Computing and Networking, 11(4):332–341, 2018. 5. Meenakshi Kansal, Amit Kumar Singh, and Ratna Dutta. Efficient multi-signature scheme using lattice. The Computer Journal, 65(9):2421–2429, 2022. 6. Nabil Alkeilani Alkadri, Nico Döttling, and Sihang Pu. Practical lattice-based distributed signatures for a small number of signers. In International Conference on Applied Cryptography and Network Security, pages 376–402. Springer, 2024. 7. Craig Gentry and Alice Silverberg. Hierarchical id-based cryptography. In International conference on the theory and application of cryptology and information security, volume 2501, pages 548–566. Springer, 2002. 8. Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In International conference on the theory and applications of cryptographic techniques, volume 2656, pages 416–432. Springer, 2003. 9. Sherman SM Chow, Lucas CK Hui, Siu Ming Yiu, and Kam-Pui Chow. Secure hierarchical identity based signature and its application. In International Conference on Information and Communications Security, volume 3269, pages 480–494. Springer, 2004. 10. Leyou Zhang, Yupu Hu, and Qing Wu. New construction of short hierarchical id-based signature in the standard model. Fundamenta Informaticae, 90(1-2):191–201, 2009. 11. Markus Rückert. Strongly unforgeable signatures and hierarchical identity-based signatures from lattices without random oracles. In International workshop on post-quantum cryptography, volume 6061, pages 182–200. Springer, 2010. 12. David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. Bonsai trees, or how to delegate a lattice basis. Journal of cryptology, 25(4):601–639, 2012. 13. Miaomiao Tian, Liusheng Huang, and Wei Yang. A new hierarchical identity-based signature scheme from lattices in the standard model. Int. J. Netw. Secur., 14(6):310–315, 2012. 14. Miaomiao Tian, Liusheng Huang, and Wei Yang. Efficient hierarchical identity-based signatures from lattices. International Journal of Electronic Security and Digital Forensics, 5(1):1–10, 2013. 15. Gaurav Srivastava, Richa Agrawal, Kunwar Singh, Rajeev Tripathi, and Kshirasagar Naik. A hierarchical identitybased security for delay tolerant networks using lattice-based cryptography. Peer-to-Peer Networking and Applications, 13(1):348–367, 2020. 16. Zhuo Yi, Xuehui Du, Ying Liao, and Xin Lu. An access authentication algorithm based on a hierarchical identitybased signature over lattice for the space-ground integrated network. In 2019 International Conference on Advanced Communication Technologies and Networking (CommNet), pages 1–9. IEEE, 2019. 17. Limin Shen, Jianfeng Ma, Ximeng Liu, and Meixia Miao. A provably secure aggregate signature scheme for healthcare wireless sensor networks. Journal of medical systems, 40(11):244, 2016. 18. Rachid El Bansarkhani and Johannes Buchmann. Towards lattice based aggregate signatures. In International Conference on Cryptology in Africa, volume 13508, pages 336–355. Springer, 2014. 19. Daniele Micciancio and Shafi Goldwasser. Complexity of lattice problems: a cryptographic perspective, volume 671. Springer Science & Business Media, 2002. 20. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 197–206, 2008. 21. Shweta Agrawal, Dan Boneh, and Xavier Boyen. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical ibe. In Annual cryptology conference, volume 6223, pages 98–115. Springer, 2010. 22. Michael F Atiyah and Ian Grant Macdonald. Introduction to commutative algebra. CRC Press, 2018.

18

8

Appendix

8.1

A Specific Case of the Chinese Remainder Theorem

In our proposed construction, we employ Theorem 1 to decompose the underlying ring structure and facilitate efficient computation. Specifically, we consider the commutative ring R = Zm and for each i ∈ {1, . . . , N } and for some fixed k, Si = Lik . In particular, let us suppose ei = (y1 , . . . , yi , . . . , ym ), where yj = 1 for i = j and yj = 0 for i ̸= j with i = 1, . . . , m. Suppose PID|ik ∈ Zn×m for i = 1, . . . , N and for some fixed k ∈ {1, . . . , t} (According to the q construction 5). If N < m, consider L1k = L⊥ q (PID|1k ) + ⟨e2 , e3 , . . . , em ⟩, L2k = L⊥ q (PID|2k ) + ⟨e1 , e3 , . . . , em ⟩, .. . L(N −1)k = L⊥ q (PID|(N −1)k ) + ⟨e1 , . . . , eN −2 , eN , . . . , em ⟩, LN k = L⊥ q (PID|N k ) + ⟨e1 , . . . , eN −1 , eN +1 , . . . , em ⟩. If N ≥ m, consider L1k = L⊥ q (PID|1k ) + ⟨e2 , e3 , . . . , em ⟩, L2k = L⊥ q (PID|2k ) + ⟨e1 , e3 , . . . , em ⟩, .. . Lmk = L⊥ q (PID|mk ) + ⟨e1 , e2 , . . . , em−1 ⟩, L(m+1)k = L⊥ q (PID|(m+1)k ) + ⟨e1 , e2 , . . . , em ⟩, .. . LN k = L⊥ q (PID|N k ) + ⟨e1 , e2 , . . . , em ⟩. The lattice Lik is well defined for i = 1, . . . , N . Lik =L⊥ q (PID|ik ) + ⟨e1 , . . . , ei−1 , ei+1 , . . . , em ⟩  = x = (x1 , . . . , xm ) ∈ Zm : PID|ik x = 0 mod q  + a1k e1 + a2k e2 + . . . + a(i−1)k ei−1 + a(i+1)k ei+1 + . . . amk em  = (a1k x1 , a2k x2 , . . . , a(i−1)k xi−1 , xi , a(i+1)k xi+1 , . . . , amk xm ) ∈ Zm : xi , aik ∈ Z, ∀i ∈ {1, 2, . . . m} . So, we obtain N lattices L1 , L2 , . . . , LN such that for i ̸= j,
Li + Lj = L⊥ q (PID|ik ) + ⟨e1 , . . . , ei−1 , ei+1 , . . . , em ⟩
+ L⊥ q (PID|jk ) + ⟨e1 , . . . , ej−1 , ej+1 , . . . , em ⟩ =Zm . Since, R = Zm be a ring. For each i ∈ {1, . . . , N } and for some fixed k, Si = Lik be ideals of R and we have already established that Li + Lj = Zm for i ̸= j. Then by CRT. (refer 1), Zm Zm Zm Zm ∼ × × · · · × . = L1k ∩ L2k ∩ · · · ∩ LN k L1k L2k LN k 19

Therefore, for some fixed k, ∃ a ring isomorphism N

Y Zm Zm ∼ , = TN ik Lik i=1 L i=1 given by t 7→ (t mod L1k , t mod L2k , . . . , t mod LN k ). 8.2

Integration of the CRT into our proposed HIBS-DA scheme

In this subsection, we show how the CRT 8.1 is applied to our proposed HIBS-DA scheme. From Section 5, in Sign algorithm, we observe that the individual signature vik , for each i ∈ {1, . . . , N } and fixed k ∈ {1, . . . , t}, belongs to the lattice Lhq (PID|ik ), where h = h(Mik , bik , ID|ik ) and Lhq (PID|ik ) =  t ∈ Zm : PID|ik t = h(Mik , bik , ID|ik ) (mod q) Since vik ∈ Lhq (PID|ik ) = L⊥ q (PID|ik ) + t1 ,

for some t1 satisfying PID|ik t1 = h

(mod q).

⊥ vik ∈ L⊥ q (PID|ik ) + t1 =⇒ vik ∈ Lq (PID|ik ) + t1 + ⟨e1 , . . . , ei−1 , ei+1 , . . . , em ⟩
m = L⊥ q (PID|ik ) + ⟨e1 , . . . , ei−1 , ei+1 , . . . , em ⟩ + t1 , t1 ∈ Z m

=⇒ vik ∈

Z . Lik

Therefore, (v1k , v2k , . . . , vN k ) ∈ by CRT 1, there exists an element x∈

Zm Zm Zm × × · · · × , L1k L2k LN k

Zm L1k ∩ L2k ∩ · · · ∩ LN k

such that x ≡ v1k

(mod L1k ),

x ≡ v2k .. .

(mod L2k ),

x ≡ vN k

(mod LN k )

defined in 8.1.

20