Computers, Materials & Continua DOI:10.32604/cmc.2022.030270
Article

Code-based Sequential Aggregate Signature Scheme

Bennian Dou1,*, Lei Xu1, Xiaoling Yu2, Lin Mei1 and Cong Zuo3

1School of Mathematics and Statistics, Nanjing University of Science and Technology, Nanjing, 210094, China
2College of Data Science, Taiyuan University of Technology, Taiyuan, 030000, China
3SCRIPTS, Nanyang Technological University, 639798, Singapore
*Corresponding Author: Bennian Dou. Email: benniandou@163.com
Received: 22 March 2022; Accepted: 29 May 2022

Abstract: This paper proposes the first code-based quantum immune sequential aggregate signature (SAS) scheme and proves the security of the proposed scheme in the random oracle model. Aggregate signature (AS) schemes and sequential aggregate signature schemes allow a group of potential signers to sign different messages respectively, and all the signatures of those users on those messages can be aggregated into a single signature such that the size of the aggregate signature is much smaller than the total size of all individual signatures. Because of the aggregation of many signatures into a single short signature, AS and SAS schemes can reduce bandwidth and save storage; moreover, when a SAS is verified, not only the valid but also the order in which each signer signed can be verified. AS and SAS schemes can be applied to traffic control, banking transaction and military applications. Most of the existing AS and SAS schemes are based either on pairing or Rivest–Shamir–Adleman (RSA), and hence, can be broken by Shor’s quantum algorithm for Integer Factoring Problem (IFP) and Discrete Logarithm Problem (DLP). There are no quantum algorithms to solve syndrome decoding problems. Hence, code-based cryptography is seen as one of the promising candidates for post-quantum cryptography. This paper shows how to construct quantum immune sequential aggregate signatures based on coding theory. Specifically, we construct our scheme with the first code based signature scheme proposed by Courtois, Finiasz and Sendrier (CFS). Compared to the CFS signature scheme without aggregation, the proposed sequential aggregate signature scheme can save about 90% storage when the number of signers is asymptotically large.

Keywords: Sequential aggregate signature; CFS signature; post-quantum cryptography

1  Introduction

Security systems may often encounter the scenario which is to manage many different signatures on many different messages generated by many distinct users. For example, in a Public Key Infrastructure (PKI) of depth n, user signatures are accompanied by a chain of n certificates. The chain contains n signatures by n Certificate Authorities (CAs) on n distinct certificates. Another example is secure border gateway protocol (S-BGP) [1] in which each router receives a list of n signatures attesting to a certain path of length n in the network. A router signs its own segment in the path and passes the resulting list of n+1 signatures to the next router. Both systems would benefit from a method which can compress the different signatures on different messages issued by different users. The certificate chain would be shortened by compressing the n signatures in the chain into a short single signature.

Aggregate signatures (AS), proposed by Boneh et al. [2] in 2003, are digital signatures that address the problem of compressing signatures. AS allows n members of a given group of potential signers to sign n different messages mi respectively, and all the signatures of those users on those messages can be aggregated into a single short signature σ. This single short signature σ and the n original messages mi are enough to convince the verifier that the n signers did indeed sign the n original messages mi respectively. In the scheme of [2], the aggregate signature can be produced by anyone. Subsequently, at Eurocrypt 2004, Lysyanskaya et al. [3] proposed another aggregate signature, namely sequential aggregate signature (SAS). In a sequential aggregate signature scheme, the aggregate signature cannot be produced by an outsider; instead, it must be constructed sequentially by each signer modifying the aggregate-so-far signature in turn.

Because of the aggregation of many signatures into a single short signature, AS and SAS schemes can reduce bandwidth and save storage; moreover, when a SAS is verified, not only the valid but also the order in which each signer signed can be verified. AS and SAS schemes can be applied to traffic control, banking transaction and military applications. Particularly, AS and SAS schemes are suitable for the secure border gateway protocol (S-BGP) which is designed to improve the security of the global Internet routing system. In the scenario of S-BGP, each router receives a list of n signatures attesting to a certain path of length n in the network. A router signs its own segment in the path and passes the resulting list of n + 1 signatures to the next router. When an AS scheme or a SAS scheme is used in S-BGP, one can significantly reduce associated bandwidth overhead and memory space for signatures.

Since Boneh et al. introduced aggregate signature scheme, there are many AS schemes have been presented [2–8], most of them are constructed either from pairings [2,4–8] or from Rivest–Shamir–Adleman (RSA) [3]. The security of the above schemes except [7] is proved in the random oracle model, and the security of [7] is proved in the standard model.

In 1997, Shor [9] discovered a remarkable quantum algorithm which can solve both the factoring problem and the discrete logarithm problem in finite fields and on elliptic curves in polynomial time. So in the age of quantum, Shor’s algorithm will break all digital signature schemes, including Full Domain Hash RSA (FDHRSA), the Digital Signature Algorithm (DSA) and the Elliptic Curve DSA (ECDSA), which are based on factoring problem and the discrete logarithm problem. Thus, Shor’s algorithm can also break all the aforementioned AS and SAS including Boneh et al.’s AS, Lysyanskaya et al.’s SAS. In response, the cryptographic community has been focusing on a coordinated effort to produce viable alternatives, based on hard problems which are not vulnerable to quantum cryptanalytic attacks. These include cryptosystems based on lattices, linear codes, multivariate equations, and others. Such an effort is led by NIST’s (National Institute of Standards and Technology) call for Post-Quantum Standardization [10], which is currently nearing its end.

In1978, McEliece [11] constructed a public key encryption (PKE) based on coding theory. In 1986, Niederreiter [12] proposed an equivalent code-based PKE. But the first practical code-based signature scheme was proposed by Courtois et al. until 2001 [13], their signature scheme is also known as the CFS signature. The CFS signature adapts the full domain hash (FDH) approach of Bellare et al. [14] to Niederreiter encryption scheme. The security of the CFS signature is based on two difficult problems of coding theory: The Goppa Bounded Decoding problem (GBD), and the Permuted Goppa Code Distinguishing problem (PGD) [13,15].

Our contribution. Up to date, there exists no quantum algorithm solving the GBD and PGD, so the CFS signature is seen as one of the promising candidates for post-quantum signatures [16,17]. After the publishing of the CFS scheme, there are just a few code-based signatures with special properties have been presented, namely blind, (threshold) ring signature, and identity-based signature, for details, refer to the survey paper [17]. To the best knowledge we know, there is no code-based aggregate signature or sequential aggregate signature in the literature.

In this paper, we construct a code-based sequential aggregate signature from the CFS signature. We prove the proposed SAS secure in the random oracle under reasonable assumptions for permuted Goppa code. Due to the anti-quantum of the CFS signature schemes [16,17], to the best knowledge we know, our scheme is the first code-based quantum immune sequential aggregate signature (SAS) scheme. We compare our scheme with some other aggregate schemes in Tab. 1.

Related works. Recently, [18–20] used the Schnorr-Lyubashevsky framework to construct code based signatures without trapdoors. The Schnorr-Lyubashevsky framework has been shown able to produce secure and efficient signature schemes without trapdoors in the lattice-based setting. There are some works [21] analyzed such Schnorr-Lyubashevsky framework code based signatures. Some lattice based aggregate signatures have been proposed in [22,23]. Xu et al. proposed a post-quantum blind signature in [24]. Quantum spin states can be used to construct hybrid cryptosystems and other schemes [25–27].

Organizations. The rest of the paper is organized as follows: In Section 2, we give the formal definitions and security model of sequential aggregate signature schemes. Section 3 reviews coding theory and the CFS signature. A concrete code-based sequential aggregate signature scheme is proposed in Section 4.We compare the efficiency between aggregate and non-aggregate for the CFS signature in Section 5. Finally, we end with concluding remarks in Section 6.

2  Sequential Aggregate Signature Scheme

In this section, we give the formal definitions and security model of sequential aggregate signature (SAS) schemes. We adopt the main notions in [3].

2.1 SAS Schemes

Definition 1. A sequential aggregate signature (SAS) scheme SAS = (KeyGen, AggSign, AggVerify) consists of three algorithms:

KeyGen(1k): KeyGen(1k) generates public and secret key pair (PKi,SKi)of each user Ui.

AggSign: AggSign takes as inputs a secret key SKi, a message mi∈{0,1}∗, and a sequential aggregate-so-far signature σ on messages m1,m2,⋯,mi−1 under respective public keys PK1,PK2,⋯,PKi−1, where m1 is the inmost message. If i=1, the aggregate-so-far σ is taken to be empty. It adds a signature on mi under SKi to the aggregate, outputting a sequential aggregate σ′ on all messages m1,m2,⋯,mi.

AggVerify: AggVerify takes as inputs a sequential aggregate signature σ, messages m1,m2,⋯,mi, and public keys PK1,PK2,⋯,PKi, outputs 1 if σ is a valid sequential aggregate (with m1 inmost) on the given messages under the given keys, otherwise outputs 0.

Fig. 1 shows how a sequential aggregate signature scheme works. SAS schemes can reduce bandwidth and save storage; moreover, when a SAS is verified, not only the valid but also the order in which each signer signed can be verified.

Figure 1: Workflow of a sequential aggregate signature scheme

2.2 Security Model of SAS Schemes

Let SAS = (KeyGen; AggSign; AggVerify) be a sequential aggregate signature scheme. To give the security model of SAS schemes, we consider the following game associated to a challenger C and a forger A. A’s advantage, AdvAggSigA, is defined to be his probability to win in the game.

Setup. The aggregate forger A is provided with a public key PK, generated at random.

Queries. Proceeding adaptively, A requests sequential aggregate signatures with PK on messages of his choice. For each query, he supplies a sequential aggregate signature σ on some messages m1,m2,⋯,mi−1 under distinct keys PK1,PK2,⋯,PKi−1, and an additional message mi to be signed by the oracle under key PK (where i is at most N, a game parameter).

Response. Finally, A outputs i distinct public keys PK1,PK2,⋯,PKi. Here i is at most N. One of these keys must equal PK, the challenge key. Algorithm A also outputs messages m1,m2,⋯,mi, and a sequential aggregate signature σ by the i users, each on his corresponding message, with PK1 inmost.

The forger wins if the sequential aggregate signature σ is a valid sequential aggregate signature on messages m1,m2,⋯,mi under keys PK1,PK2,⋯,PKi, and σ is nontrivial, i.e., A did not request a sequential aggregate signature on messages m1,m2,⋯,mi∗ under keys PK1,PK2,⋯,PKi∗, where i∗ is the index of the challenge key PK in the forgery. Note that i∗ need not equal i. The probability is over the coin tosses of the key-generation algorithm and of A.

Definition 2. We say a sequential aggregate forger A (τ,qh,qs,N,ε)-breaks an N-user aggregate signature scheme in the sequential aggregate chosen-key model if: A runs in time at most τ; A makes at most qh queries to the hash function and at most qs queries to the aggregate signing oracle; AdvAggSigA, is at least ε, and the forged sequential aggregate signature is by at most N users. A sequential aggregate signature scheme is (τ,qh,qs,N,ε) -secure against existential forgery in the sequential aggregate chosen-key model if no forger (τ,qh,qs,N,ε)-breaks it.

3  Coding Theory and CFS Signature

3.1 Coding Theory

A binary [n, k]-code C is a linear subspace of dimension k of the linear space F2n. Elements of F2n are called words and elements of C are codewords. A code is usually given in the form of a (n−k)×n parity check matrix H. The codewords of C are words x that satisfies HxT=0. A syndrome s∈F2n−k is a vector s=HxT for a word x. The support of a word x=(x1,x2,⋯,xn) is defined as support(x)={i|xi≠0}. The Hamming weight of a word x denoted by wt(x) is the cardinality of support(x). The Hamming distance d(x,y) between two words x, y is defined as wt(x−y). The minimum distance d of a [n, k]-code C is min{d(x,y)|x≠y}. A syndrome s is said to be decodable according to a t-error correcting code if there exists a word x∈F2n such that s=HxT with wt(x)≤t. We recall that decoding a syndrome s is retrieving such a word x. Decoding in a random linear code is difficult, which we will restate soon later.

Goppa codes are subfield subcodes of particular alternant codes with efficient decoding algorithm. Goppa codes are widely used in coding-based cryptography. For given integers m and t, Goppa codes are of length n=2m, of dimension k = n − mt and are t-correcting. The density of decodable syndromes is approximately 1t! [13]. We denote by DecodeH the decoding algorithm associated with a Goppa Code of parity check matrix H.

In order to establish the security of the CFS signature and the pro-posed SAS, we introduce some problems on coding theory.

Definition 3. Goppa Bouned Decoding Problem (GBD): Given a random(n−k)×n binary matrix H, a syndrome s∈F2n−k, output a word e∈F2n of weight wt(e)≤n−klog2⁡n such that s=HeT.

The associated decision problem of GBD is NP-complete [28].

Definition 4. Multiple Goppa Bounded Decoding (MGBD): Given a random (n−k)×n binary matrix H, an arbitrary number c>0 and a syndrome s∈F2n−k , output a word e∈F2n of weight wt(e)≤cn−klog2⁡n such that s=HeT.

The associated decision problem of MGBD is conjectured to be NP-complete, too [29].

Definition 5. We say an algorithm A is (τ,ε)-solves MGBD(GBD) if A runs in time at most τ, and outputs a word e∈F2n of weight wt(e)≤cn−klog2⁡n (wt(e)≤n−klog2⁡n) with at least probability ε, such that s=HeT.

Lemma 1. There is no algorithm A which is (τ,ε)-solves MGBD and GBD.

Let Wn,t={e∈F2n|w(e)≤t}, l=⌊log2|Wn,t|⌋, To describe the CFS signature and the proposed SAS, we need a one to one function ϕ:Wn,t→{0,1}l. For the construction of such function ϕ and its inverse ϕ−1, refer to [30].

3.2 The CFS Signature

The basic idea of code-based cryptography is using a certain code which has efficient decoding algorithm with trapdoor information as private key and publishing the random look like variant of this code as public key.

The first code-based signature is the CFS signature which was introduced by Courtois, Finiasz and Sendrier at Asiacrypt 2001 [13]. The CFS signature is obtained by applying full hash domain approach to the Niederreiter public key cryptosystem. The CFS signature we will describe below is a minor modification of the original CFS signature, and this modified CFS signature enables us to prove its security more reasonable in random oracle [15,30]. The CFS signature consists of three algorithms which are described as follows:

SystemParameters: Two integers m,t∈N.

CFSKeyGen (1κ): CFSKeyGen (1κ) generates a [n, k, d]-binary Goppa code C (n=2m, k=n-mt, d = 2t+1) with parity check matrix H0, then C is a t-error correcting code, let its efficient decoding algorithm is DecodeH0. CFSKeyGen (1κ) generates a random (n−k)×(n−k) invertible matrix S and a random n×n permutation matrix P. Let H=SH0P, then H is a parity check matrix of the code C′ which is a permuted code of C. C′ is also a t-error correcting Goppa code, let its efficient decoding be DecodeH(obtained from S, P, DecodeH0). Finally, CFSKeyGen (1κ) outputs H as the public key, and the corresponding private key is DecodeH.

Sign: Let h:{0,1}∗→{0,1}n−k be a hash function. Let r=⌈log2(t!)⌉. To sign a message m, Sign does

1.    choose s randomly from {0,1}r;

2.    x=DecodeH(h(m‖s));

3.    if no x was found go to 1.

Let z=ϕ(x) then the signature on m is (z,s).

Verification: Let x=ϕ−1(z). The signature is valid if and only if HxT=h(m‖s) holds.

Security of the CFS Signature: The security of the CFS signature is based on two assumptions: One is the intractability of GBD as stated in Lemma1; the other is the intractability of the Permuted Goppa Code Distinguish (PGD) which we will describe below.

Definition 6. Permuted Goppa Code Distinguish Problem (PGD): Given H generated by CFSKeyGen (1κ) as the public key in the CFS signature, the Permuted Goppa Code Distinguish Problem is to distinguish H from a parity check matrix of a random linear code.

Definition 7. We say an algorithm A is(τ,ε)-solves PGD if A runs in time at most τ, and can distinguish H from a parity check matrix of a random linear code with probability at least 12+ε.

Lemma 2 ( [13,15]). There is no algorithm A which is (τ,ε)-solves PGD.

Because of Lemma 2, we can apply Lemma 1 to permuted Goppa code. In fact, we have

Definition 8. Permuted Goppa Code Bounded Decoding (PGBD): Given H generated by CFSKeyGen (1κ) as the public key in the CFS signature, an arbitrary number c>0 and a syndrome s∈F2n−k, the Permuted Goppa Code Bounded Decoding Problem is to output a word e∈F2n of weight wt(e)≤cn−klog2⁡n(=ct, since n−k=mt, n=2m) such thats=HeT. We say an algorithm A is (τ,ε)-solves PGBD, if A runs in time at mostτ, and can output the demanding vectore with at least probability ε.

Lemma 3 ( [13]). There is no algorithm A which is (τ,ε)-solves PGBD.

4  The Proposed Code-Based SAS

In this section, we propose a sequential aggregate signature based on CFS signature, and also prove the security of the proposed SAS.

4.1 The Proposed SAS

We firstly introduce some notations for vectors. We write a vector as x and its length |x|. The elements of x are x1,x2,⋯,x|x|. For a vector x, x|ab denotes the subvector contains elements xa,xa+1,⋯,xb. Suppose z∈{0,1}l, where l=⌊log2|Wn,t|⌋, if needed, n−k−l 0’s can be padded to z to obtain an n−k dimension vector z¯=(00⋯0⏟n−k−l‖z). Meanwhile, for a vector z=(00⋯0⏟n−k−l‖z), the unpadding of z is denoted by z^=x.Henceforward, we denote by M the message vector whose elements are m1,m2,⋯,mi, and denote by H the public key vector whose elements are H1,H2,⋯,Hi.

The proposed SAS consists of three algorithms which are described below:

SystemParameters: Two integers m,t∈N.

KeyGen (1κ): For each user Ui (1≤i≤n), KeyGen (1κ) generates the key pair (Hi,DecodeHi) (Hi is the public key, and the corresponding private key is DecodeHi) just as CFSKeyGen (1κ) does in the CFS signature.

AggSign: The inputs are a secret key DecodeHi, a message mi∈{0,1}∗, and a sequential aggregate-so-far signature σ′=(z′,s1,s2,⋯,si−1) on messages M(message vector whose elements are m1,m2,⋯,mi−1) under public keys H(public key vector whose elements are H1,H2,⋯,Hi−1). Let h:{0,1}∗→{0,1}n−k be a hash function. Let r=⌈log2(t!)⌉. To sign, AggSign does

1.    choose si randomly from {0,1}r;

2.    x=DecodeHi(h(H‖Hi,M‖mi,si)⊕z′¯;

3.    if no x was found, go to 1.

Let z=ϕ(x), then the sequential aggregate signature on messages M(whose elements are m1,m2,⋯,mi−1) under public keys H( whose elements are H1,H2,⋯,Hi−1) is σ=(z,s1,s2,⋯,si).

AggVerify: The input is a sequential aggregate signature σ=(z,s1,s2,⋯,si) on messages M under public keys H. To verify, let i=|H|=|M|, set zi=z. Then for j=i,i−1,⋯,1, compute mj−1=Hj(ϕ−1(zj))T⊕(h(H|1j,M|1j,sj) and set zj−1=mj−1^. Accept if z0=0.

Correctness of the proposed scheme. From the process of AggVerify, we know that

z0=H1(ϕ−1(z1))T⊕h(H1,m1,s1)^(1)

On the other hand, if the sequential signature is computed correctly, from the process AggSign we have,

z1=ϕ(DecodeH1(h(H1,m1,s1)⊕0)(2)

which implies H1(ϕ−1(z1))T⊕h(H1,m1,s1)=0. Hence, if the sequential aggregate signature is valid, we have z0=0.

4.2 Security of the Proposed SAS

In this section, we prove the security of the proposed SAS in the random oracle model, we will prove the security of our scheme based on the assumption in lemma 3.

To make the proof easier, we firstly prove the following lemma.

Lemma 4. There is a forger A (τ,qh,qs,N,ε)-breaks the proposed SAS, if and only if there is an forger B(τ′,qh,qs,N′,ε)-breaks the proposed SAS with the target public key is the last key in the key sequence.

Proof: The lemma can be immediately obtained by the observation that during the AggVerify phase of our scheme, supposing σ=(z,s1,s2,⋯,si) on messages M under public keys H, each sequential aggregate signature on M|1j under H|1j (1≤j≤i) can also be achieved.

Henceforward, we suppose that matrix-vector multiplication, exclusive or of vectors and the computation of ϕ and ϕ−1 take unit time. The security of our scheme is obtained from the following theorem.

Theorem 1. If there is a (τ,qh,qs,N,ε) forger A to break the proposed SAS, then there exists an algorithm (τ′,ε′) B to solve the Permuted Goppa Code Bounded Syndrome Decoding of Problem (PGBD) for c=2, with

ε′≥(1/12r2r)N(qs+1)−qsε,τ′≤τ+(qH+NqS+N)(3N+1)+3N+2(3)

where r=⌈log2(t!)⌉.

Proof: If A is (τ,qh,qs,N,ε) forger to break the proposed SAS. From Lemma 4, we can assume, without loss of any generality, that the forgery aggregate signature generated by A has the target public key is the last key i.e., the N-th key in the public key sequence.

Below we will show that if there is an algorithm A is (τ,qh,qs,N,ε) forger to break the proposed SAS, we can construct an algorithm B which is (τ′,ε′)-solves PGBD for c=2, which contradicts the assumption in lemma 3. The algorithm B is constructed as follows:

B is given a parity check matrix H of a random [n, k, d]-binary permuted Goppa code (n=2m, k=n-mt, d = 2t+1), a challenge syndrome y∈{0,1}n−k, B’s goal is to find x∈{0,1}n with wt(x)≤2t such that HxT=y. B sends H as the target public key to A. B runs A and answers its oracle queries as follows.

Hash queries: The random hash function h has two properties: i.e., the property that the outputs of h are random and the property that one output from t! outputs is decodable. B simulates the hash function as follows.

B maintains a list of tuples <H(j),M(j),s(j),w(j),z(j),c1(j),c2(j)> as the hash queries’ list. We call this list the h-list. When A queries the hash oracle at point <H,M,s> B responds as below:

1.    If the query <H,M,s> is already on the h-list, then B finds the entry <H,M,s,w,z,c1,c2> and outputs w as the answer to the query, i.e., w=h(H,M,s).

2.    Otherwise set i=|H|=|M|, r=⌈log2(t!)⌉, B runs the hashing algorithm on input <H|1i - 1,M|1i - 1> to obtain the corresponding entry <H|1i - 1,M|1i - 1,s′,w′,z′,c1′,c2′> with c1′=0 on the h-list. If i=1, B sets z′←0. B must now choose elements along with H,M,s in a new entry on the h-list. Firstly, B chooses a random vector z0∈{0,1}n with weight wt(z0)≤t, and B generates a random coin c1∈{0,1}, such that Pr[c1=0]=1t!. B chooses a random vector w0∈{0,1}n−k.

2.1 c1′=1: B sets w←w0, z←∗, c2←∗ (∗ is a placeholder value.).

2.2 c1′=0: If i<N and c1=1, B sets w←w0, z←∗, c2←∗. If i<N and c1=0, B sets w←Hiz0T⊕ϕ(z′)¯, and sets z←z0, c2←∗. If i=N, B generates another coin c2∈{0,1} such that Pr[c2=0]=1t!−1. If i=N, c1=1 and c2=1, B sets w←w0, z←∗. If i=N, c1=1 and c2=0, B sets w←Hz0T⊕ϕ(z′)¯⊕y, z←z0. If i=N, c1=0, B sets w←Hz0T⊕ϕ(z′)¯, z←z0 and c2←∗.

3. Finally, B adds <H,M,s,w,z,c1,c2> to the h-list, and responds to the query as w=h(H,M,s).

In all cases, B’s response, w, is indistinguishable from the random oracle.

Aggregate signature queries: A supplies a sequential aggregate signature σ′=(z′,s1,s2,⋯,sN−1) on messages M|1N−1 under keys H|1N−1. A requests a sequential aggregate signature on message M (MN=m), under keys H (HN=H). Firstly, B uses AggVerify to ensure that σ′ is the correct sequential aggregate signature on M|1N−1 under keys H|1N−1. If σ′ is incorrect, B responds with a placeholder value ∗. Otherwise, B runs the hash algorithm on (H, M) to obtain <H,M,s,w,z,c1,c2>. If c1=0, B responds to the query with σ←(ϕ(z),s1,s2,⋯,s), we will show later that σ is the correct sequential aggregate signature on (H, M). Otherwise, B reports failure and terminates.

B’s output:At last, algorithm A halts and produces a correct forgery sequential aggregate signature σ∗=(z∗,s1,s2,⋯,sN) on (H∗,M∗), where HN∗=H, and (H∗,M∗) is not queried to the aggregate signature queries. B now runs the hash algorithm on (H∗,M∗,sN), and obtains <H∗,M∗,s,w,z,c1,c2>. If c1=1 and c2=0, B then computes x=z⊕ϕ−1(z∗) and outputs x, we will show later that HxT=y with wt(x)≤2t.

This completes the description of algorithm B.

Claim 1. If A makes a valid sequential aggregate signature query on(H, M) with HN=H, supplying a correct sequential aggregate signature σ′=(z′,s1,s2,⋯,sN−1) on messages M|1N−1 under keys H|1N−1, then either B reports failure and halts or B’s outputσ←(ϕ(z),s1,s2,⋯,s) is the correct sequential aggregate signature on (H, M).

Proof: Firstly, we introduce some notations. For each j, 1≤j≤N, B’s hash algorithm associates with input (H|1j, M|1j) a tuple <H1j,M1j,s(j),w(j),z(j),c1(j),c2(j)>. If B does not abort, then c1(j)=0, c2(j)=∗ for 1≤j≤N. It is reasonable to assume that (H|1j, M|1j) is queried to the hash query before it is signed, for the hash function is random oracle. Hence, from the hash algorithm, we obtain that z=z(N),z′=ϕ(z(N−1)), s=s(N) and s(j)=sj (1≤j≤N−1). Also from the hash algorithm, we know that

z′=ϕ(z(N−1))=h(H1N,M1N,s)⊕HzT(4)

z(j)=ϕ−1(h(H1j+1,M1j+1,s(j+1))⊕Hj+1(z(j+1))T)(5)

z(j)=ϕ−1(h(H1j+1,M1j+1,s(j+1))⊕Hj+1(z(j+1))T)(1≤j≤N−2)(6)

H1(z(1))T⊕h(H1,m1,s(1))=0

The last equation shows that σ←(ϕ(z),s1,s2,⋯,s) is a valid sequential aggregate signature on (H, M).

Claim 2: If A outputs a valid nontrivial forgery sequential aggregate signature σ∗=(z∗,s1,s2,⋯,sN) on(H∗,M∗), then B either reports failure and halts or outputs the correct solution x such that HxT=y withwt(x)≤2t.

Proof: We use the same notations introduced in Claim 1. If B does not abortion, then c1(N)=0, c2(N)=0. Hence, from the hash algorithm, we know that

h(H∗,M∗,sN)=H(z(N))T⊕ϕ(z(N−1))¯⊕y(7)

Thus,

H(ϕ−1(z∗))T=h(H∗,M∗,sN)⊕ϕ(z(N−1))=H(z(N))T⊕ϕ(z(N−1))⊕y⊕ϕ(z(N−1))=H(z(N))T⊕y(8)

And hence, we can obtain that if we set x=z(N)⊕ϕ−1(z∗), then HxT=y with wt(x)≤2t.

It remains to show that the success probability ε′ that B outputs x is at least (1/12r2r)N(qs+1)−qsε. We define three events as below:

E1: B does not abort during the qs aggregate signature queries phase.

E2: A outputs a valid and nontrivial forgery sequential aggregate signature.

E3: B does not abort during the output phase.

Then B succeeds in giving the correct solution if all of the above events happen, i.e., ε′=Pr[E1∧E2∧E3]=Pr[E1]⋅Pr[E2|E1]⋅Pr[E3|E1∧E2].

On the other hand, we have the following three claims.

Claim 3. Pr[E1]=(12r)(N−1)qs.

Proof: If B does not abort during each aggregate signature query, then all c1(j)=0(1≤j≤N−1), which implies the probability that B does not abort during each signature query is (12r)(N−1). Hence, the probability that B does not abort during the qs signature queries is Pr[E1]=(12r)(N−1)qs.

Claim 4. Pr[E2|E1]≥ε.

Proof: Trivially.

Claim 5. Pr[E3|E1∧E2]=(12r)N .

Proof: If B does not abort during the output phase, then all c1(j)=0(1≤j≤N−1), c2(N)=0 which implies the probability that B does not abort during the output phase is (12r)(N−1).12r=(12r)N . Hence, Pr[E3|E1∧E2]=(12r)N.

Combine the results of the above claims, we obtain immediately that ε′≥(1/12r2r)N(qs+1)−qsε.

The running ting τ′ of B equal to the running time τ plus the time of B’s time to respond A’s qH hash queries and qs aggregate signature queries, each hash query involves at most N matrix-vector multiplication, at most N+1 exclusive or of vectors and at most N computation of the function ϕ. Each aggregate signature query needs at most N hash queries, at most N computation of ϕ and ϕ−1, N exclusive or of vectors. At last, in order to give x, B needs one exclusive or of two vectors and N hash queries. Then, the total time of B’s is at most

τ+(qH+NqS+N)(3N+1)+3N+2(9)

5  Efficiency Comparisons

We now compare the efficiency between our scheme and the original CFS scheme without aggregate in N users setting. To achieve security, for the CFS signature, [31] suggests the parameters: m=22, t=9, n=222, and for each signature (z,s), one needs about 182 and 19 bits to store z and s respectively. So in order to store N signatures, the total bits needed in the CFS scheme is (182 + 19)N = 201 N, while one needs only 182 + 19 N bits to store the signatures by using the sequential aggregate signatures we proposed. Hence, one can save about (1−19201)≈90% storage when N is big. It is not difficult to see that the signature generation and verification are of the same time. We give the comparison in Tab. 2.

6  Conclusions and Open Problems

In this paper, we propose the first code based sequential aggregate signature, and prove the security of the scheme in the random oracle model. We note that the length of the aggregate signature in our scheme is not constant. It is an open problem to construct code based sequential aggregate signatures with constant length. It is also an interesting problem to construct code based aggregate signatures using the Schnorr-Lyubashevsky Framework [18,20].

Funding Statement: This work was supported in part by the National Natural Science Foundation of China under Grant 62072240, by the Natural Science Foundation of Jiangsu Province under Grant BK20210330 and by the National Key Research and Development Program of China under Grant 2020YFB1804604.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

References

 1.  S. Kent, C. Lynn and K. Seo, “Secure border gateway protocol (secure-BGP),” IEEE J. Selected Areas in Comm, vol. 18, no. 4, pp. 582–92, 2000. [Google Scholar]

 2.  D. Boneh, C. Gentry, B. Lynn and H. Shacham, “Aggregate and verifiably encrypted signatures from bilinear maps,” in Advances in Cryptology, EUROCRYPT 2003. Proc.: Lecture Notes in Computer Science (LNCS 2656), Warsaw, Poland, pp. 416–432, 2003. [Google Scholar]

 3.  A. Lysyanskaya, S. Micali, L. Reyzin and H. Shacham, “Sequential aggregate signatures from trapdoor permutations,” in Advances in Cryptology, EUROCRYPT 2004. Proc.: Lecture Notes in Computer Science (LNCS 3027), Interlaken, Switzerland, pp. 74–90, 2004. [Google Scholar]

 4.  A. Boldyreva, C. Gentry, A. O’Neill and D. Yum, “Ordered multisignatures and identity-based aggregate signatures with applications to secure routing,” in Proc. of the 14th ACM Conf. on Computer and Communications Security, CCS 2007, Alexandria, Virginia, USA, pp. 276–285, 2007. [Google Scholar]

 5.  X. Cheng, J. Liu and X. Wang, “Identity-based aggregate and verifiably encrypted signatures from bilinear pairing,” in Int. Conf. on Computational Science and Its Applications, ICCSA 2005. Proc.: Lecture Notes in Computer Science (LNCS 3483), Singapore, pp. 1046–1054, 2005. [Google Scholar]

 6.  C. Gentry and Z. Ramzan, “Identity-based aggregate signatures,” in Public Key Cryptography, PKC 2006. Proc.: Lecture Notes in Computer Science (LNCS 3958), New York City, NY, USA, pp. 257–273, 2006. [Google Scholar]

 7.  S. Lu, R. Ostrovsky, A. Sahai, H. Shacham and B. Waters, “Sequential aggregate signatures and multisignatures without random oracles,” in Advances in Cryptology, EUROCRYPT 2006. Proc.: Lecture Notes in Computer Science (LNCS 4004), St. Petersburg, Russia, pp. 465–485, 2006. [Google Scholar]

 8.  J. Xu, Z. Zhang and D. Feng, “ID-Based aggregate signatures from bilinear pairings,” in Cryptology and Network Security, 4th Int. Conf., CANS 2005. Proc.: Lecture Notes in Computer Science (LNCS 3810), Xiamen, China, pp. 110–119, 2005. [Google Scholar]

 9.  P. W. Shor, “Polynomial-tme algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM J. Computing, vol. 26, pp. 1484–1509, 1997. [Google Scholar]

10. National Institute of Standards and Technology, “NIST post quantum standardization process,” 2017. [Online]. Available: https://csrc.nist.gov/Projects/Post-Quantum-Cryptography. [Google Scholar]

11. R. J. McEliece, “A Public-key cryptosystem based on algebraic coding theory,” Jet propulsion Laboratory DSN Progress Report, vol. 42-44, pp. 114–116, 1978. [Google Scholar]

12. H. Niederreiter, “Knapsack-type crytosystems and algebraic coding theory,” Prob. Contr. Inform. Theory, vol. 15, no. 2, pp. 157–166, 1986. [Google Scholar]

13. N. Courtois, M. Finiasz and N. Sendrier, “How to achieve a McEliece-based digital signature scheme,” in Advances in Cryptology, ASIACRYPT 2001. Proc.: Lecture Notes in Computer Science (LNCS 2248), Gold Coast, Australia, pp. 157–174, 2001. [Google Scholar]

14. M. Bellare and P. Rogaway, “Random oracles are practical: A paradigm for designing efficient protocols,” in Proc. of the 1st ACM Conf. on Computer and Communications Security, CCS 1993, Fairfax, Virginia, USA, pp. 62–73, 1993. [Google Scholar]

15. L. Dallot, “Towards a concrete security proof of courtois, finiasz and sendrier signature scheme,” in Research in Cryptology, Second Western European Workshop, WEWoRC 2007. Proc.: Lecture Notes in Computer Science (LNCS 4945), Bochum, Germany, pp. 65–77, 2008. [Google Scholar]

16. J. Buchmann, C. Coronado, M. Doring, D. Engelbert, C. Ludwig et al., “Post-quantum signatures,” 2004. [Online]. Available: https://eprint.iacr.org/2004/297.pdf. [Google Scholar]

17. P. Cayrel and M. Meziani, “Post-quantum cryptography: Code-based signatures,” in Advances in Computer Science and Information Technology, AST/UCMA/ISA/ACN 2010. Proc.: Lecture Notes in Computer Science (LNCS 6059), Miyazaki, Japan, pp. 82–89, 2010. [Google Scholar]

18. Y. Song, X. Huang, Y. Mu, W. Wu and H. Wang, “A Code-based signature scheme from the lyubashevsky framework,” Theoretical Computer Science, vol. 835, pp. 15–30, 2020. [Google Scholar]

19. Z. Li, C. Xing and S. L. Yeo, “A new code based signature scheme without trapdoors,” Cryptology ePrint Archive, Report 2020/1250, 2020. [Google Scholar]

20. M. Baldi, F. Chiaraluce and P. Santini, “Code-based signatures without trapdoors through restricted vectors,” Cryptology ePrint Archive, Report 2021/294, 2021. [Google Scholar]

21. M. Baldi, J. C. Deneuville, E. Persichetti and P. Santini, “Cryptanalysis of a code-based signature scheme based on the schnorr-lyubashevsky framework,” IEEE Communications Letters, vol. 25, no. 9, pp. 2829–2833, 2021. [Google Scholar]

22. R. Bansarkhani and J. Buchmann, “Towards lattice based aggregate signatures,” in“ Progress in Cryptology, AFRICACRYPT 2014. Proc.: Lecture Notes in Computer Science (LNCS 8469), Marrakesh, Morocco, pp. 336–355, 2014. [Google Scholar]

23. Y. Zhang, Y. Hu and M. Jiang, “Lattice- based sequential aggregate signatures with lazy verification,” the Journal of China Universities of Posts and Telecommunications, vol. 22, no. 6, pp. 36–44, 2015. [Google Scholar]

24. G. Xu, Y. Cao, S. Xu, K. Xiao, X. Liu et al., “A novel post-quantum blind signature for log system in blockchain,” Computer Systems Science and Engineering, vol. 41, no. 3, pp. 945–958, 2022. [Google Scholar]

25. A. Alghafis, H. M. Waseem, M. Khan and S. S. Jamal, “A hybrid cryptosystem for digital contents confidentiality based on rotation of quantum spin states,’’ Physica A: Statistical Mechanics and its Applications, vol. 554(C), pp. 123908, 2020. [Google Scholar]

26. H. M. Waseem, A. Alghafis and M. Khan, “An efficient public Key cryptosystem based on dihedral group and quantum spin states,” IEEE Access, vol. 8, pp. 71821–71832, 2020. [Google Scholar]

27. A. Alghafis, H. M. Waseem, M. Khan, S. S. Jamal, M. Amin et al., “A novel digital contents privacy scheme based on quantum harmonic oscillator and schrodinger paradox,” Wireless Networks, 2020. https://doi.org/10.1007/s11276-020-02363-7. [Google Scholar]

28. M. Finiasz, “Nouvelles constructions utilisant des codes correcteurs derreurs en cryptographie ‘a clef publique,” Ph.D dissertation, INRIA C Ecole Polytechnique, France, 2004. [Google Scholar]

29. N. Sendrier, “Code-based one way functions,” 2007. [Online]. Available: http://ecrypt-ss07.rhul.ac.uk/Slides/Thursday/sendrier-samos07.pdf. [Google Scholar]

30. R. Overbeck and N. Sendrier, “Code based cryptography,” in D. J. Bernstein, J. Buchmann, E. Dahmen, (Eds.Post-Quantum Cryptography, Berlin, Heidelberg, Germany: Springer, pp. 95–145, 2009. [Google Scholar]

31. M. Finiasz and N. Sendrier, “Security bounds for the design of code-based cryptosystems,” in Advances in Cryptology, ASIACRYPT 2009. Proc.: Lecture Notes in Computer Science (LNCS 5912), Tokyo, Japan, pp. 88–105, 2009. [Google Scholar]

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.