# New Constructions of Existential Unforgeable Aggregate Signature Scheme from CSP

Authors: Bo Mi; Yongxing Zou; Darong Huang; Yang Liu; Lu Chen
Journal: Security and Communication Networks
 (2022)

---

## Abstract

In future, hundreds of years of mathematical problems that the security of public key cryptography algorithms rely on may be defeated by quantum algorithms. How can a digital signature scheme gracefully balance security and efficiency? This study uses the conjugate search problem and the left self-distributive system to combine and uses the RSA-like algorithm as the underlying structure to propose a new aggregated signature scheme. We, through the EUF game, under the random metaphor model, prove that the security of the scheme satisfies the adaptation unforgeability under selective message attack, the scheme can be finally reduced to the discrete logarithm problem or large prime number decomposition problem. In addition, we can achieve antiquantum attack and exhaustive attack by performing matrix calculations on the message, defining and changing the structure of the matrix by encoding, and setting thresholds for the matrix dimension and the length of the private key. In terms of efficiency, the message signature implementation is linear compared with the expansion rate in terms of storage and computing overhead, and the generation and verification of the final signature pair have nothing to do with the number of users. In addition, the length of the signature is fixed and the size is only the length of a single group, which effectively reduces the generation of public and private key pairs and saves a lot of storage space. The storage space and computational complexity are also effectively improved compared with other solutions.


---

## Body

## 1. Introduction

Throughout the ages, information security has played an important role in both ordinary life and military strategy. Cryptography provides the theory and technical support of information security and meets the four requirements of information security from the two aspects of data encryption and digital signature: confidentiality means information content cannot be accessed by unauthorized persons. Integrity means no information modification during transmission and storage. Authentication means identification and authentication service technology applied to both the entity and the information itself. Nonrepudiation means users cannot deny their existing actions and commitments [1–3]. Among them, data encryption can realize the confidentiality of data, and a digital signature can realize the integrity, authentication, and nonrepudiation of information. The digital signature is a digital simulation of a handwritten signature. With the advent of the information age, most standard protocols, and software support digital signatures, at present, many countries have legislation that stipulates that digital signatures and handwritten signatures have the same legal effect. In 1978, Rivest et al. realized the first public-key encryption scheme [4] for the large integer factorization problem, and at the same time, using this public-key encryption scheme, we realized the first digital signature scheme, namely, the famous RSA scheme. Since the proposal of this scheme, the research on digital signatures has always been one of the main research topics and hotspots in the field of cryptography. Digital signatures often involve multiuser scenarios: on the one hand, the signature itself needs to be signed by multiple users; on the other hand, although the signature is generated by a single user, security in a multiuser environment needs to be considered. Boneh et al. first proposed the concept of aggregated signatures in 2003 [5] and constructed the first aggregated signature scheme using pairings on elliptic curves. Roughly speaking, the aggregated signature σ is the synthesis of n different signatures by n users to different pairs of documents m1,m2,…,mn into a single signature σ, which reduces not only the storage space requirements for signatures but also the requirements for transmission network bandwidth. At the same time, the verification of multiple signatures is simplified into one verification, which reduces the workload of the verifier. Especially, in some computing resources and a large number of fast authentication situations at the same time, such as online ticket purchases, virtual currency, safety routing protocol, and vehicle ad hoc networks, whether it is the Spring Festival transport of 1.4 billion people in China or the routing topology in a certain area, it has a greater application demand for short-signed fast algorithms. In the direction of protecting user data privacy and communication security, even 6 G networks with endogenous security face many problems, such as AI-induced concerns about security and privacy issues, including data security, AI model and algorithm security, and malicious use of AI technology. Traditional computational complexity-based cryptographic mechanisms (such as encryption, authentication, authorization, signature, and privacy protection) will remain the primary method for maintaining network security and data privacy. However, due to the characteristics of 6 G networks, lightweight and efficient encryption and signature mechanisms are very popular. The combination of 6 G and blockchain, through the application of encryption algorithms such as aggregate signature and ring signature in the data structure, makes the data highly anonymous and improves the efficiency of authentication, which is also a promising solution. The achievement of these goals requires an efficient and secure signature algorithm as the underlying technical support. In the near future, quantum computers are expected to break the modern public key cryptosystem. Postquantum cryptography must be an important means to protect future information security. The past cryptosystems cannot be abandoned. How to migrate from public key cryptosystems to postquantum cryptosystems has become a hot topic.


### 1.1. Contributions

Given the problems of existing schemes such as excessive storage signature overhead, low signature verification efficiency, insufficient security, and inability to achieve antiquantum computing in the future, we propose a new scheme; the main contributions of this study are summarized as follows:(1)
This study uses the combination of RSA, CSP (conjugate search problem), and LD (left self-distributive system) to construct a new aggregated signature scheme, and we utilize the RSA-like as the underlying structure of the scheme, which can eventually be reduced to the DLP problem or the large prime number decomposition problem because the RSA algorithm is based on the large prime number decomposition problem.(2)
In terms of security, the proposed scheme satisfies that EUF-CMA can resist existential forgery attacks under adaptive selection messages. Through the EUF game, adversary A uses his scheme to attack the challenger as a subroutine, designs computational targets for adversaryB, and then defines the advantage that B can solve for a given RSA-like scheme to achieve the proof.(3)
In terms of efficiency, since all messages are encoded as low-dimensional matrices with a certain regularity, and with the help of the characteristics of the CSP-LD system, the signatures of all signers will be synthesized into the final unique signature through calculation.As a result, the signature storage and verification become more efficient. The overhead is greatly reduced, the expansion rate of message signature implementation is linear compared with the storage and computing overhead, and the length of the final aggregated signature is fixed, which saves the maximum amount of signed storage space without losing accuracy.(4)
What is more prominent is that the scheme we propose can customize the format of the encoded message matrix. By setting the system parameters to reach a certain threshold, it can achieve antiquantum attacks. Other problems using RSA or DLP include digital signature schemes based on pairing problems, neither can resist the quantum computer attack under Shor’s algorithm.


## 1.1. Contributions

Given the problems of existing schemes such as excessive storage signature overhead, low signature verification efficiency, insufficient security, and inability to achieve antiquantum computing in the future, we propose a new scheme; the main contributions of this study are summarized as follows:(1)
This study uses the combination of RSA, CSP (conjugate search problem), and LD (left self-distributive system) to construct a new aggregated signature scheme, and we utilize the RSA-like as the underlying structure of the scheme, which can eventually be reduced to the DLP problem or the large prime number decomposition problem because the RSA algorithm is based on the large prime number decomposition problem.(2)
In terms of security, the proposed scheme satisfies that EUF-CMA can resist existential forgery attacks under adaptive selection messages. Through the EUF game, adversary A uses his scheme to attack the challenger as a subroutine, designs computational targets for adversaryB, and then defines the advantage that B can solve for a given RSA-like scheme to achieve the proof.(3)
In terms of efficiency, since all messages are encoded as low-dimensional matrices with a certain regularity, and with the help of the characteristics of the CSP-LD system, the signatures of all signers will be synthesized into the final unique signature through calculation.As a result, the signature storage and verification become more efficient. The overhead is greatly reduced, the expansion rate of message signature implementation is linear compared with the storage and computing overhead, and the length of the final aggregated signature is fixed, which saves the maximum amount of signed storage space without losing accuracy.(4)
What is more prominent is that the scheme we propose can customize the format of the encoded message matrix. By setting the system parameters to reach a certain threshold, it can achieve antiquantum attacks. Other problems using RSA or DLP include digital signature schemes based on pairing problems, neither can resist the quantum computer attack under Shor’s algorithm.


## 2. Related Work

How to construct efficient and secure aggregated signatures has always been highly concerning for cryptographers. Hashimoto and Ogata [6] proposed the first unrestricted and compact aggregated signature scheme, in which the signature size is constant, and the generated pair signatures can have different information states and can aggregate any combination of signatures. Iwasaki et al. [7] extended from the two perspectives of structured signature and identity-based signature and constructed an identity-based structured aggregated signature scheme, and the security of the scheme will not be reduced due to the ability of the adversary. It can successfully defend against switching attacks (CCS 2007, Boldyreva et al. [8]) and reordering attacks (ISPEC 2007, Shao [9]). In recent years, the combination of signature scheme and blockchain technology [10–12], federated learning technology [13], 6G network [14], homomorphic learning [15], network routing protocol [16], edge computing [17], vehicular ad hoc networks [18], and software-defined vehicular network [19–21] by applying signature algorithms and encryption algorithms to the experimental scheme to further strengthen the security of the scheme and improve the privacy protection capability of the scheme is also a hot topic. In the blockchain, the digital signature is one of the three basic technologies, and its importance is self-evident. The blockchain mainly uses digital signatures to control permissions, identify the legal identity of transaction initiators, and prevent malicious nodes from impersonating. Coincidentally, the distributed and decentralized edge nodes inherent in the 6 G network allow blockchain technology to be used to improve the endogenous security performance of 6 G, based on blockchain technology to achieve what is considered a promising solution in the field of data security and privacy in 6 G networks. Data have a high level of anonymity by applying encryption algorithms such as aggregate signature signatures and ring signatures in the data structure. In edge computing, federated learning, and homomorphic learning, edge computing processes and applies data to the nearest computing facility to protect its privacy or federated learning uses other remote data and protects the privacy of remote data, and at the same time collaborative modeling, or the cloud computing model based on homomorphic encryption, solves the problem of users trusting cloud service providers not to steal or even user data and to achieve data confidentiality and computability. Verifying the identity legitimacy of a user or terminal based on a digital signature is both basic and necessary work. SDVN (software-defined virtual network) is a new type of VANET (vehicle ad hoc network), a promising networking paradigm, that can provide intelligent information exchange by separating network management and data transfer. For such applications that combine vehicles with networks, frequently changing topology networks, real-time routing calculations, and efficient service requests all play a crucial role in vehicle networks. Before designing a routing strategy for vehicles in these operations, it is undoubtedly a wise move to use an aggregated signature scheme that is fast and can protect its identity privacy to verify the legitimacy of vehicle units. Domestic Li et al. [22] constructed an efficient aggregated signature scheme under the certificateless public-key cryptosystem based on bilinear pairing, and the signature length of the scheme is only two group elements. Only 4 pair operations (of constant magnitude) and n scalar multiplication operations are required in signature verification, which has a fast signature verification algorithm and fast transmission efficiency. Zhou et al. [23] proposed two certificateless aggregated signature schemes that do not use bilinear mapping for different network environments. However, due to the long aggregate signature length of Scheme I, it can only be used in a network environment with high bandwidth and the final signature length is positively correlated with the number of users, Scheme II has a shorter signature length, and the length has nothing to do with the number of users and will be used in a network environment with low bandwidth. Whether the security proofs of these two schemes have existential unforgeability under adaptive chosen message attack remains to be further analyzed. At present, most aggregated signature schemes are constructed according to the pairings on elliptic curves. For example, Yang et al. [24], aiming at the problems of privacy leakage and low signature verification efficiency in VANET (vehicular ad hoc network), combined with identity-based cryptography and aggregated signature technology, designed a message authentication scheme for VANET to improve the security of the system and the efficiency of road traffic.However, there are still many deficiencies in the pairing-based scheme: one is that the hardware devices currently implemented are all oriented towards RSA and DLP (discrete logarithm problem), and the pairing-based cryptography scheme still has a long way to go before it can be applied in reality. Another is that the pairing problem was not introduced into cryptography for research until 2000. Unlike RSA and DLP problems, hundreds of years of research have made them well-understood in the cryptography community. Therefore, most of the current digital signature schemes are based on the discrete logarithm problem and the RSA problem. For example, many people learn from the ideas of Bellare and Neven [25] and propose RSA-based identity-based sequential signature schemes, which need to be further strengthened and improved in terms of the storage efficiency of signatures and whether they can achieve EUF-CMA (existential unforgeability under adaptive chosen message attack) security. What makes us more motivated is that almost no one aggregates signatures based on RSA.More importantly, with the development of quantum computers, the abovementioned mathematical problems that the security of public key cryptographic algorithms depends on can be solved by efficient quantum algorithms [26, 27]. As the underlying mathematical problems are solved, including discrete logarithms (elliptic curve versions) and large integer factorization, all these public key cryptographic algorithms will no longer be secure, which directly affects Diffie-Hellman, Elliptic Curve, RSA, and those currently used algorithms. In 2016–2017, NIST focused on the solicitation of the following three categories of postquantum cryptographic algorithms: encryption, key exchange, and digital signatures. Among the 69 “complete and suitable” candidate drafts, postquantum cryptographic algorithms constructed by the following 4 mathematical methods are mainly included lattice-based, code-based, multivariate-based, and hash-based. The scheme discussed in this study does not have a self-made wheel, but through the fusion of CSP and matrix, using the encoding of the message to achieve antiquantum attacks, the specific form is in the follow-up content.


## 3. Preliminaries

Before introducing definitions, let us review the concept of groups.When an algebraic system has a certain operationG,∗, ∗ is a binary operation. When ∗ satisfies the following properties, we call the algebraic system a group, in which G,∗ is simply denoted as G:(1)
Closedness: it means for∀a,b∈G satisfying a∗b∈G.(2)
Unitary: it means, for∀a∈G,∃e, there are existing a∗e=e∗a=a. At the same time, we call e the identity element of G,∗.(3)
Inverse element exists: it means, for∀a∈G,∃b∈G, there are existing a∗b=b∗a=e. Then, b is called the inverse of a, denoted as a−1.(4)
Associativity: it means∀a,b,c∈G satisfying a∗b∗c=a∗b∗c.An algebraic systemG,∗ is called a semigroup if it only satisfies closure and associativity. For example, multiplication and addition of real numbers. If the ∗ operation in an algebraic system G,∗ also satisfies the commutative law, that is, ∀a,b∈G has a∗b=b∗a, then G,∗ is called a commutative group, also called an Able group.Note that not all elements inG have inverses. At the same time, an=a∗∗∗a, n times, and a−n=b∗∗∗b, n times, where n>1.LetG−1 be the set of all invertible elements belonging to G, expressed as follows:(1)G−1=a∈G:∃b∈G,so thata∗b=b∗a=e.The so-called CSP problem can be roughly explained in the group: there is a groupG, where a∈G and x∈G−1; there must be an element b∈G; a and b are isomorphic so that b=xax−1; we say that, for the element x, a, and b are conjugated.Definition 1.
(conjugacy search problem, CSP). SupposeG is a noncommutative group, a and b are two elements belonging to G, denoted as a,b∈G, and the unknown x is an element in G−1, denoted as x∈G−1, satisfying b=xax−1. The so-called CSP (conjugate search problem) problem in the noncommutative group G refers to finding another x′ in G−1, denoted as x′∈G−1, so that b=x′ax′−1, where x′ does not need to be exactly the same as x.Lemma 1.
The same applies to transforminga and b into matrix form in the above search problem. For example, write a and b as the simplest two-dimensional upper triangular matrix:(2)a=a1a20a3,b=b1b20b3.Satisfyingb=xax−1,(3)b=b1b20b3=x1x20x3a1a20a31x1−x2x1x301x3.CSP (conjugate search problem) problem in the noncommutative groupG refers to finding another x′ in G−1, denoted as x′∈G−1, so that b=x′ax′−1, where x′ does not need to be exactly the same as x:(4)x′=x1′x2′0x3′.Theorem 1.
If the matrixA is invertible, then the inverse matrix of A is unique, and the proof is omitted.Definition 2.
(left self-distributive system, LD [28]). W is a nonempty subset and F is a complete and closed function satisfying F:W×W⟶W; we denote Fa,b as Fab. If F satisfies the following formula, then we call F⋅ a left self-distributive system or LD system for short:(5)FrFsp=FFrsFrp,∀p,r,s∈W.
If we considerFrs as a binary operation r∗s, the above expression becomes(6)r∗s∗p=r∗s∗r∗p.
The operator∗ is left self-distributive.Definition 3.
(CSP-LD system [29]). Assuming that G is a noncommutative group, the binary function F satisfies the following conjugation operations:(7)F:G−1×G⟶G,a,b⟶aba−1.
Then,F⋅ is a CSP-LD system.
The proof is as follows:(8)FrFsp=Frsps−1=rsps−1r−1=rsr−1⋅rpr−1⋅rs−1r−1=rsr−1⋅rpr−1⋅rsr−1−1=Frsr−1,rpr−1=FFrsFrp.
The CSP-LD system also has some very simple but very useful properties in the field of cryptography. A few are listed below, and readers can prove it by themselves.Property 1:Faa=a,a∈G−1Property 2:Fab=c⇔Fa−1c=b,a∈G−1,b∈GProperty 3:Fabc=FabFac,a∈G−1,b,c∈G
The power-law property ofF in the CSP-LD system will be described in detail below.Lemma 2.
Supposea and b are given and fixed, a∈G−1andb∈G. Then, for any three integers m,s,t, as long as m=s+t is satisfied, there must be the following formula:(9)Fabm=FabsFabt=FambFamb=FasFatb.The first proof of the formula is as follows:(10)Fabm=abma−1=ab⋯⋯ba−1=aba−1⋅aba−1⋯⋯aba−1=aba−1m=Famb.The second proof of the formula is as follows:(11)Famb=amba−m=asatba−ta−s=asFatba−s=FasFatb.The two formulas are of great help to our follow-up content. One satisfies the internal and external exchange of power, transforming the exponent of the variable into the exponent of the function, and the other satisfies the addition of the power law.Definition 4.
(security definition of EUF-CMA). Currently, there are two main types of attacks against digital signatures: key-only attacks and known-message attacks. A key-only attack means that the adversary only knows the signer's public key without any other message. Among the many known-message attacks, the attack method with the highest attack strength is called adaptively chosen message attacks. In this type of attack, the adversary uses the signer as a querier, which can query not only the challenger for messages that depend on the signer's public key but also the signed message that has already been queried. If a signature scheme still has signature unforgeability under this attack, in other words, the signature constructed by the adversary through this optional challenge is still illegal and cannot be verified, the scheme is said to have existential unforgeability under adaptive chosen message attack, which is referred to as EUF-CMA security [30, 31]. The advantage of the adversary A in the following experiments is negligible:(12)ExpSig,AEUFk:vk,sk←SigGenk,M,σ←ASignsk⋅vk.
LetQ denote that A accesses the message set of signature metaphor Signsk⋅.
Returns 1 ifVrfyvkM,σ=1^M∈≠Q, otherwise returns 0, where A has access to the signed idiom machine polynomial bounded qH degree. The specific meaning is whether the challenger can judge whether the signature σ of the message M comes from the message set of the signature metaphor Signsk⋅ visited by the adversary A through VrfyvkM,σ. If it returns 1, it means that the challenger believes that the signature σ of the message M is naturally generated by legal means. If it returns 0, it means that the challenger believes that the signature σ of the message M is generated by A accessing the metaphor Signsk⋅.
The advantage ofA is defined as follows:(13)AdvSig,AEUFk=PrEXPSig,AEUFk=1.
WhenAdvSig,AEUFk<neglk, which is a negligible function, then we say the scheme is EUF-CMA safe.


## 4. EUF-CMA Security Signature Scheme Based on CSP

We first review the basic process of the RSA algorithm and specifically prove why the classical RSA signature algorithm does not have the existence of unforgeability under the adaptive chosen message attack.The basic description of the RSA-like signature algorithm is as follows.(1)
Key generation is as follows:(14)GenRSAk:p,q←GenPrimek,N=pq,φn=p−1q−1,Choosee,for1<e<φnandφn,e=1,Calculated,ford⋅e≡1modφn,pk=n,e,sk=n,d.(2)
Signature is as follows:(15)SignskM:σ=Mdmodn.(3)
Verify is as follows:(16)VrfypkM,σ:Return1,ifσe=Mmodn,otherwise return0.Obviously, this signature algorithm is not antiforgery under the adaptive chosen message attack. When the attackerA performs a qH-bounded query, A can submit Mi=re⋅M for the signature query. At this point, the challenger answers, computes ui=Midmodn,i=1,2,…,q, and returns it to A. A forges the signature of message M and outputs M,σ=M,ui/r because of(17)ui≡reMdmodn≡rMdmodn.Therefore,σ=ui/r≡Mdmodn is the legal signature of M.According to the previous Definition4, EUF-CMA security definition, we can make the following analysis:(18)ExpSig,AEUFk:vk,sk←SigGenk,M,σ←ASignsk⋅vk.LetQ denote the message set of A accessing signature metaphor Signsk⋅, denoted as M∈Q, where A has access to the signed metaphor polynomial bounded qH times.At this time, the adversaryA has the message M and its corresponding signature σ after accessing the signature machine Signsk⋅. At the same time, A calculates M′=re⋅M, and the challenger calculates u′=M′dmodn and returns it to A. Then, A has another pair of signatures M,σ′=M,u′/r. Verified by the challenger for legitimacy,(19)σ′=u′r≡reMdrmodn≡rMdrmodn≡Mdmodn=σ.However, the adversaryA has not used M′ to access the signature metaphor, so M′∉Q. That is to say, the challenger believes that the message M signature σ′ is naturally generated through legal means. The advantage of A at this time is defined as follows:(20)AdvSig,AEUFk=PrEXPSig,AEUFk=1=1.How to solve this problem? The previous method is to use the FDH (global hash function) that the output bit length of the hash function is the same as the modulus bit length to ensure the security of the scheme [32], but the hash function itself is a relatively complex algorithm, and the so-called randomness itself is controversial. Because no algorithm is truly random, such as h=Hm, whose output is a pseudorandom process from m to h. In addition, using a hash function will reduce the efficiency of the scheme. Below, we will propose a new solution that satisfies EUF-CMA and prove that its security is improved based on the comparison above.


### 4.1. Definition of the RSA Problem (RSAP)

Given a positive integern (n is the product of two different odd prime numbers p,q), a positive integer egcde,p−1q−1=1, and an integer c, we find an integer m such that me≡cmodn. That is to say, the RSA problem is to find the root of e times in the case of modulo n (n is a composite integer).


### 4.2. The Difficult Problem of CSP Based on DDH

G is a noncommutative group. Suppose F is a function that satisfies the above CSP-LD system while having an adversary A. For any a∈G−1,b∈G, we perform the following two experiments in parallel:(21)ExperimentEXPF,ACSP−ddh−realExperimentEXPF,ACSP−ddh−randi←$T,X←Faib,i←$T;X←Faib,j←$T,Y←Fajb,j←$T;Y←Fajb,Z←Fai+jb,L←$T,Z←FaLb,b←AX,Y,Z,b←AX,Y,Z,Returnb.Returnb..For adversaryA, the advantage of successful attacks in a CSP system based on the DDH assumption is defined as follows:(22)AdvF,Acsp−ddh=PrEXPF,ACSP−ddh−real=1−PrEXPF,ACSP−ddh−rand=1.In other words, wheni,j,L are taken randomly from T, we can consider that Faib,Fajb,Fai+jb and Faib,Fajb,FaLb are computationally indistinguishable when distributed. At present, there is no specific statement in the academic community to judge whether the CSP-DDH problem is hard, but we know that, in a general cyclic group, the DLP problem and the DDH problem are equivalent. From the above CSP-LD system reasoning, we know that, on a noncommutative semigroup, the CSP problem and the CSP-DDH problem can be directly replaced by the DLP problem and the DDH problem. Therefore, by logical reasoning, we can conclude that in a general noncommutative semigroup, the CSP problem and the CSP-DDH problem are equivalents [27].


### 4.3. Digital Signature Scheme Based on CSP-LD System

Assuming thata and b are random numbers, a∈G−1andb∈G, which have been fixed for the system parameters. Assuming that G is a general noncommutative semigroup, the binary function F satisfies the following conjugate operations:(23)F:G−1×G⟶G,a,b⟶aba−1.We markFa,b=aba−1 as Fab.(1)
Key generation is as follows:(24)p,q←GenPrimek,N=pq,φn=p−1q−1,Choosee,for1<e<φnandφn,e=1,Calculated,ford⋅e≡1modφn,pk=n,e,sk=n,d.(2)
Signature is as follows:(25)SignskM:H=FaM,σ=Hdmodn.(3)
Verify is as follows:(26)VrfypkM,σ:Return1,ifσe=Hmodn,otherwise return0.Under the CSP-LD system, the above scheme RSA-CSP-LD is EUF-CMA safe if the GenRSA-related RSA problem is difficult. Compared with the predecessors using the global hash function FDH to mapM to prevent signature forgery, our scheme has a more compact security reduction.Theorem 2.
Specifically, assuming that there is an adversaryA that breaks the RSA-CSP-LD scheme with the advantage of ε, then there must be an adversary B that solves the RSA problem at least with the advantage of the following:(27)AdvBRSAk≥εkeqs.Proof.
The EUF game is as follows.
In this proof process, all references toG refer to a universal noncommutative group, F is the CSP-LD system function defined on G, and a∈G−1andb∈G are two fixed elements.(1)
The challenger runsKey generationk to get n,e,d and runs CSP-LD to get Fab. Adversary A gets the public key n,e.(2)
The adversaryA can ask the challenger Fa⋅b and the signature of the message; when A requests the signature of the message M, the challenger returns σ=FabMdmodn to A.(3)
A outputs a message-signature pair M,σ where A has not previously requested a signature for a message M. If σe=FabMmodn, the adversary attack is successful.
The following proves that the RSA-CSP-LD scheme can be reduced to the RSA problem.
The adversaryB knows n,e,y∗ where y∗ is uniformly random on Zn∗. Using A to attack RSA-CSP-LD as a subroutine, the goal is to calculate y∗1/emodn. Because if B can get σ such that σe≡y∗modn, then σ≡y∗1/emodn. Because of σe≡y∗modn, if y∗ is the value of FaM of a message M in the CSP-LD system, then σ is the signature of the message. M,σ is generated by adversary A, but FaM is generated by B, and B can be set to FaM=y∗. Since B does not know which message A generates a forged pair signature when generating y∗, B has to make a guess, where the jth query of A corresponds to the final forged result of A. Before the reduction, for the sake of generality, we assume that the adversary A will not issue the same query to FaM twice. If A requests the signature of M, we take that it has been asked FaM before.
The reduction process is as follows:(1)
B gives the public key n,e to A.(2)
Fa⋅ inquiry (at most qs times): B creates a list query, which is initially empty and the element type is a quadruple Mi,σi,yi,ci, indicating that B has set FaM=yi, σie≡yimodn. When A initiates a query (set to M), B will answer as follows:(a)
If there is already an itemMi,σi,yi,ci corresponding to M in query, we reply with yi.(b)
Otherwise,B randomly chooses a ci←0,1R and sets Prci=0=δ.Ifci=0, we return y∗.Otherwise, we select a random valueσi←Zn∗R, calculate yi≡σiemodn, take yi as the answer to this query, and store Mi,σi,yi,ci in the table query.(3)
Signature query (up toqs times): when A requests message M as a signature, B looks up Mi,σi,yi,ci in the list query such that Mi=M.Ifci≠0, we return σi.Otherwise,ci=0, interrupts.(4)
Output:A outputs (M, σ. B looks for M in the query list corresponding to the quadruple Mi,σi,yi,ci, if ci≠0, B interrupts.
In the above reduction process,ci is the guess of B. ci=0 corresponding to the message that M in the quadruple is the signature that A will eventually forge and the role of ci in the quadruple Mi,σi,yi,ci is an identifier.
The success ofB is determined by the following three events:π1:B does not break in A 's signature queryπ2:A produces a valid message-signature pair M,σπ3:π2 occurs and c is equal to 0 in the quadruplet M,σ,y,c corresponding to M.
Prπ1=1−δqs, Prπ2|π1=εK, and Prπ3|π2π1=Pr0|π2π1=δ. So, the success rate of B is Prπ3π1=Prπ1⋅Prπ2|π1⋅Prπ3|π2π1=1−δqs∈δ.
Considering1−δqs∈δ as a function of δ, when δ=1/qs+1 can be obtained, 1−δqs∈δ reaches the maximum, and the maximum value is εk/eqs+1≈εk/eqs. The proof is complete.
Compared to previous pair schemes, our scheme has a larger pair advantage in terms of efficiency, since all messages are encoded as low-dimensional matrices, and the scaling rate in terms of storage and computational overhead is linear compared to plaintext implementations. Horan K. et al. [33] mentioned that the CSP problem is in a general linear group GLdR (where R represents the real number field); if d>4, CSP can be proved to be antiquantum secure, so when we encode the message M as a matrix, it is necessary to keep its dimension greater than 4. Specifically, we assume that G is a general noncommutative semigroup, a∈G−1andb∈G, and the function FaM can be regarded as a pair of preprocessing for the message M. For any message M originating from the real domain R, we can encode bM as a 6-dimensional upper triangular matrix, denoted by M∈R6×6.
We use three pairs of random numbersm1,m2,m3,m4,m5,m6 to represent the message M, while satisfying certain properties: m1+m2=M,m3+m4=m5+m6=r, where r is a system random number. With these elements, we construct the matrix as follows:(28)M1=m1m2m2m1,M2=m3m4m4m3,M3=m5m6m6m5.
Combining the above three small matrices, the final encoding form of the messageM is as follows:(29)M=M1R1R20M2R300M3.
0 here also represents an all-zero matrix of 2 × 2.Rii=1,2,3 represents a random matrix uniformly sampled from the real number domain R2×2.
Next, we perform the encoding operation ona. We uniformly randomly sample a matrix from R6×6 to represent a, which can also be considered as 9 random matrices of 2 × 2, as expressed in the following form:(30)a=a1a2a3a4a5a6a7a8a9,forai=ai1ai2ai3ai4,i=1,2,…,9.
The probability that message spaceM communicates with elements in a is negligible. It can be understood in this way that a here is similar to a key for encrypting a message M, so there are the following operations:(31)H=FaM=aMa−1=aM1R1R20M2R300M3a−1,where H is the input parameter for the subsequent execution of the RSA algorithm, which can also be regarded as the encryption of the message M, where a can be understood as a symmetric key. In some specific cases, we can perform conflict tracking, use a to solve H, recover the message from M1, and recover the signer pair identity from M2 (assuming the user identity information is placed in it).
The security (antiforgery) ofFaM=aMa−1 proves the following.
First, we carry out the following operations:(32)detH∗−TH′=detadetM1∗−TM1′R1∗R2∗0M2∗−TM2′R3∗00M3∗−TM3′deta−1,where Ri∗,i=1,2,3 are random matrices. The representation of T is as follows:(33)T=tR1R20tR300t,among them(34)t=0110.
Ri,i=1,2,3 is randomly sampled from R2×2. The adversary is defined to launch a forgery attack according to the following algorithm, which is formally described as follows [34]:(35)Expπ,ACPAK:k←KeyGenK,M0,M1,H←AFk⋅,thereM0=M1,H′=FkH,andM0<H<M1,β←R0,1,H∗=εkMβ,β′=1,ifdetH∗−TH′,β′=0,otherwise,Output1,ifβ=β′,Output0,otherwise.
The adversary's advantage is defined as follows:(36)Advπ,ACPAK=PrExpπ,ACPAK=1−12.
We will try to expand the content of the if conditional statementdetH∗−TH’:(37)detH∗−TH′=detpdetMi∗−tMi′detp−1,i=1,2,3,among them(38)detMi∗−tMi′=a2i−1∗−a2i′2−a2i∗−a2i−1′2=m∗−m′a2i−1∗−a2i∗t−a2i′−a2i−1′n.
However, by borrowing the scheme of Li et al. [35], we can clarify a2i−1>a2i. So, the part of a2i−1∗−a2i∗t−a2i′−a2i−1′n always satisfies positive, and detpdetp−1=1. Therefore, for an attacking adversary, to distinguish whether the signed message is M0 or M1, he only needs to calculate detH∗−TH′ according to the sign of the returned value. If a positive value is returned, 1 is output, representing the guessed signature message as M∗=M1. If a negative value is returned, 0 is output, which means the guessed signature message is M∗=M0. Therefore, the advantage of the adversary is 1, which means that the scheme is not anticounterfeiting.
The advantage of our proposed scheme is that we are a probabilistic encryption scheme. There can be multiple encoding forms form′. First, a random even number ρ is selected to encrypt m′, and the following form is obtained:(39)H′=FaM′ρ=aM′ρa−1=aM1ρR1R20M2ρR300M3ρa−1=FaρM′.
According to the propertiesFabm=Famb of the CSP-LD system, we mentioned earlier, and the upper triangular matrix encoding form of M is(40)M=M1R1R20M2R300M3.
We can infer(41)Mρ=Mρ,i=1,2,3.
Therefore,(42)detH∗−TH′=detpdetMi∗−tMi′ρdetp−1,i=1,2,3=detMi∗−tMi′ρ,=m∗−m′ρa2i−1∗−a2i∗t−a2i′−a2i−1′nρ.
Becauseρ is an even number, the adversary always has a positive value when calculating detH∗−TH’, and it is impossible to determine whether the signature comes from M0 or M1.


## 4.1. Definition of the RSA Problem (RSAP)

Given a positive integern (n is the product of two different odd prime numbers p,q), a positive integer egcde,p−1q−1=1, and an integer c, we find an integer m such that me≡cmodn. That is to say, the RSA problem is to find the root of e times in the case of modulo n (n is a composite integer).


## 4.2. The Difficult Problem of CSP Based on DDH

G is a noncommutative group. Suppose F is a function that satisfies the above CSP-LD system while having an adversary A. For any a∈G−1,b∈G, we perform the following two experiments in parallel:(21)ExperimentEXPF,ACSP−ddh−realExperimentEXPF,ACSP−ddh−randi←$T,X←Faib,i←$T;X←Faib,j←$T,Y←Fajb,j←$T;Y←Fajb,Z←Fai+jb,L←$T,Z←FaLb,b←AX,Y,Z,b←AX,Y,Z,Returnb.Returnb..For adversaryA, the advantage of successful attacks in a CSP system based on the DDH assumption is defined as follows:(22)AdvF,Acsp−ddh=PrEXPF,ACSP−ddh−real=1−PrEXPF,ACSP−ddh−rand=1.In other words, wheni,j,L are taken randomly from T, we can consider that Faib,Fajb,Fai+jb and Faib,Fajb,FaLb are computationally indistinguishable when distributed. At present, there is no specific statement in the academic community to judge whether the CSP-DDH problem is hard, but we know that, in a general cyclic group, the DLP problem and the DDH problem are equivalent. From the above CSP-LD system reasoning, we know that, on a noncommutative semigroup, the CSP problem and the CSP-DDH problem can be directly replaced by the DLP problem and the DDH problem. Therefore, by logical reasoning, we can conclude that in a general noncommutative semigroup, the CSP problem and the CSP-DDH problem are equivalents [27].


## 4.3. Digital Signature Scheme Based on CSP-LD System

Assuming thata and b are random numbers, a∈G−1andb∈G, which have been fixed for the system parameters. Assuming that G is a general noncommutative semigroup, the binary function F satisfies the following conjugate operations:(23)F:G−1×G⟶G,a,b⟶aba−1.We markFa,b=aba−1 as Fab.(1)
Key generation is as follows:(24)p,q←GenPrimek,N=pq,φn=p−1q−1,Choosee,for1<e<φnandφn,e=1,Calculated,ford⋅e≡1modφn,pk=n,e,sk=n,d.(2)
Signature is as follows:(25)SignskM:H=FaM,σ=Hdmodn.(3)
Verify is as follows:(26)VrfypkM,σ:Return1,ifσe=Hmodn,otherwise return0.Under the CSP-LD system, the above scheme RSA-CSP-LD is EUF-CMA safe if the GenRSA-related RSA problem is difficult. Compared with the predecessors using the global hash function FDH to mapM to prevent signature forgery, our scheme has a more compact security reduction.Theorem 2.
Specifically, assuming that there is an adversaryA that breaks the RSA-CSP-LD scheme with the advantage of ε, then there must be an adversary B that solves the RSA problem at least with the advantage of the following:(27)AdvBRSAk≥εkeqs.Proof.
The EUF game is as follows.
In this proof process, all references toG refer to a universal noncommutative group, F is the CSP-LD system function defined on G, and a∈G−1andb∈G are two fixed elements.(1)
The challenger runsKey generationk to get n,e,d and runs CSP-LD to get Fab. Adversary A gets the public key n,e.(2)
The adversaryA can ask the challenger Fa⋅b and the signature of the message; when A requests the signature of the message M, the challenger returns σ=FabMdmodn to A.(3)
A outputs a message-signature pair M,σ where A has not previously requested a signature for a message M. If σe=FabMmodn, the adversary attack is successful.
The following proves that the RSA-CSP-LD scheme can be reduced to the RSA problem.
The adversaryB knows n,e,y∗ where y∗ is uniformly random on Zn∗. Using A to attack RSA-CSP-LD as a subroutine, the goal is to calculate y∗1/emodn. Because if B can get σ such that σe≡y∗modn, then σ≡y∗1/emodn. Because of σe≡y∗modn, if y∗ is the value of FaM of a message M in the CSP-LD system, then σ is the signature of the message. M,σ is generated by adversary A, but FaM is generated by B, and B can be set to FaM=y∗. Since B does not know which message A generates a forged pair signature when generating y∗, B has to make a guess, where the jth query of A corresponds to the final forged result of A. Before the reduction, for the sake of generality, we assume that the adversary A will not issue the same query to FaM twice. If A requests the signature of M, we take that it has been asked FaM before.
The reduction process is as follows:(1)
B gives the public key n,e to A.(2)
Fa⋅ inquiry (at most qs times): B creates a list query, which is initially empty and the element type is a quadruple Mi,σi,yi,ci, indicating that B has set FaM=yi, σie≡yimodn. When A initiates a query (set to M), B will answer as follows:(a)
If there is already an itemMi,σi,yi,ci corresponding to M in query, we reply with yi.(b)
Otherwise,B randomly chooses a ci←0,1R and sets Prci=0=δ.Ifci=0, we return y∗.Otherwise, we select a random valueσi←Zn∗R, calculate yi≡σiemodn, take yi as the answer to this query, and store Mi,σi,yi,ci in the table query.(3)
Signature query (up toqs times): when A requests message M as a signature, B looks up Mi,σi,yi,ci in the list query such that Mi=M.Ifci≠0, we return σi.Otherwise,ci=0, interrupts.(4)
Output:A outputs (M, σ. B looks for M in the query list corresponding to the quadruple Mi,σi,yi,ci, if ci≠0, B interrupts.
In the above reduction process,ci is the guess of B. ci=0 corresponding to the message that M in the quadruple is the signature that A will eventually forge and the role of ci in the quadruple Mi,σi,yi,ci is an identifier.
The success ofB is determined by the following three events:π1:B does not break in A 's signature queryπ2:A produces a valid message-signature pair M,σπ3:π2 occurs and c is equal to 0 in the quadruplet M,σ,y,c corresponding to M.
Prπ1=1−δqs, Prπ2|π1=εK, and Prπ3|π2π1=Pr0|π2π1=δ. So, the success rate of B is Prπ3π1=Prπ1⋅Prπ2|π1⋅Prπ3|π2π1=1−δqs∈δ.
Considering1−δqs∈δ as a function of δ, when δ=1/qs+1 can be obtained, 1−δqs∈δ reaches the maximum, and the maximum value is εk/eqs+1≈εk/eqs. The proof is complete.
Compared to previous pair schemes, our scheme has a larger pair advantage in terms of efficiency, since all messages are encoded as low-dimensional matrices, and the scaling rate in terms of storage and computational overhead is linear compared to plaintext implementations. Horan K. et al. [33] mentioned that the CSP problem is in a general linear group GLdR (where R represents the real number field); if d>4, CSP can be proved to be antiquantum secure, so when we encode the message M as a matrix, it is necessary to keep its dimension greater than 4. Specifically, we assume that G is a general noncommutative semigroup, a∈G−1andb∈G, and the function FaM can be regarded as a pair of preprocessing for the message M. For any message M originating from the real domain R, we can encode bM as a 6-dimensional upper triangular matrix, denoted by M∈R6×6.
We use three pairs of random numbersm1,m2,m3,m4,m5,m6 to represent the message M, while satisfying certain properties: m1+m2=M,m3+m4=m5+m6=r, where r is a system random number. With these elements, we construct the matrix as follows:(28)M1=m1m2m2m1,M2=m3m4m4m3,M3=m5m6m6m5.
Combining the above three small matrices, the final encoding form of the messageM is as follows:(29)M=M1R1R20M2R300M3.
0 here also represents an all-zero matrix of 2 × 2.Rii=1,2,3 represents a random matrix uniformly sampled from the real number domain R2×2.
Next, we perform the encoding operation ona. We uniformly randomly sample a matrix from R6×6 to represent a, which can also be considered as 9 random matrices of 2 × 2, as expressed in the following form:(30)a=a1a2a3a4a5a6a7a8a9,forai=ai1ai2ai3ai4,i=1,2,…,9.
The probability that message spaceM communicates with elements in a is negligible. It can be understood in this way that a here is similar to a key for encrypting a message M, so there are the following operations:(31)H=FaM=aMa−1=aM1R1R20M2R300M3a−1,where H is the input parameter for the subsequent execution of the RSA algorithm, which can also be regarded as the encryption of the message M, where a can be understood as a symmetric key. In some specific cases, we can perform conflict tracking, use a to solve H, recover the message from M1, and recover the signer pair identity from M2 (assuming the user identity information is placed in it).
The security (antiforgery) ofFaM=aMa−1 proves the following.
First, we carry out the following operations:(32)detH∗−TH′=detadetM1∗−TM1′R1∗R2∗0M2∗−TM2′R3∗00M3∗−TM3′deta−1,where Ri∗,i=1,2,3 are random matrices. The representation of T is as follows:(33)T=tR1R20tR300t,among them(34)t=0110.
Ri,i=1,2,3 is randomly sampled from R2×2. The adversary is defined to launch a forgery attack according to the following algorithm, which is formally described as follows [34]:(35)Expπ,ACPAK:k←KeyGenK,M0,M1,H←AFk⋅,thereM0=M1,H′=FkH,andM0<H<M1,β←R0,1,H∗=εkMβ,β′=1,ifdetH∗−TH′,β′=0,otherwise,Output1,ifβ=β′,Output0,otherwise.
The adversary's advantage is defined as follows:(36)Advπ,ACPAK=PrExpπ,ACPAK=1−12.
We will try to expand the content of the if conditional statementdetH∗−TH’:(37)detH∗−TH′=detpdetMi∗−tMi′detp−1,i=1,2,3,among them(38)detMi∗−tMi′=a2i−1∗−a2i′2−a2i∗−a2i−1′2=m∗−m′a2i−1∗−a2i∗t−a2i′−a2i−1′n.
However, by borrowing the scheme of Li et al. [35], we can clarify a2i−1>a2i. So, the part of a2i−1∗−a2i∗t−a2i′−a2i−1′n always satisfies positive, and detpdetp−1=1. Therefore, for an attacking adversary, to distinguish whether the signed message is M0 or M1, he only needs to calculate detH∗−TH′ according to the sign of the returned value. If a positive value is returned, 1 is output, representing the guessed signature message as M∗=M1. If a negative value is returned, 0 is output, which means the guessed signature message is M∗=M0. Therefore, the advantage of the adversary is 1, which means that the scheme is not anticounterfeiting.
The advantage of our proposed scheme is that we are a probabilistic encryption scheme. There can be multiple encoding forms form′. First, a random even number ρ is selected to encrypt m′, and the following form is obtained:(39)H′=FaM′ρ=aM′ρa−1=aM1ρR1R20M2ρR300M3ρa−1=FaρM′.
According to the propertiesFabm=Famb of the CSP-LD system, we mentioned earlier, and the upper triangular matrix encoding form of M is(40)M=M1R1R20M2R300M3.
We can infer(41)Mρ=Mρ,i=1,2,3.
Therefore,(42)detH∗−TH′=detpdetMi∗−tMi′ρdetp−1,i=1,2,3=detMi∗−tMi′ρ,=m∗−m′ρa2i−1∗−a2i∗t−a2i′−a2i−1′nρ.
Becauseρ is an even number, the adversary always has a positive value when calculating detH∗−TH’, and it is impossible to determine whether the signature comes from M0 or M1.


## 5. RSA-like Aggregate Signature Scheme Based on CSP-LD System

Before formally introducing the aggregate signature scheme, we need to make a formal specification of the paired element inG for a secure and valid pair.Specification 1: in a CSP-LD system, the representation of elements inG is uniqueSpecification 2: it is possible to efficiently convert an element inG to its regular formSpecification 3: the length ofFatb does not show any information about at.According to Definition3, we suppose a and b are random numbers, a∈G−1andb∈G, which are given and fixed for the system parameters, and we assume that G is a general noncommutative semigroup, and the binary function F satisfies the following conjugation operations:(43)F:G−1×G⟶G,a,b⟶aba−1.We denoteFa,b=aba−1 as Fab.Assuming that there are different usersp1,p2,…,pN, in a multiuser environment, the message M needs to be co-signed. Our RSA aggregate signature scheme based on the CSP-LD system consists of the following algorithms.(1–1) message encoding: the messageM is composed of mii=1,2,…,6 satisfying some certain property, m1+m2=Mandm3+m4=m5+m6=r, where r is a system random number, and an even number ρ is sampled from the random number in the real number domain. We construct the matrix as follows:(44)Miρ=m2∗i−1ρm2∗iρm2∗iρm2∗i−1ρ,i=1,2,3.Combining the above three submatrices, the final encoding form of the messageM is as follows:(45)Mρ=M1ρR1ρR2ρ0M2ρR3ρ00M3ρ.0 here also represents an all-zero matrix of 2 × 2.Rii=1,2,3 represents a random matrix uniformly sampled from the real number domain R2×2.(1–2) coding form ofa: we uniformly randomly sample a matrix from R6×6 for encoding, representing a, which can also be considered as 9 random matrices of 2 × 2, expressed in the following form:(46)a=a1a2a3a4a5a6a7a8a9,forai=ai1ai2ai3ai4,i=1,2,…,9.(1)
Key generation is as follows:(47)GenRSAk:si,i=1,2,…,N,p,q←GenPrimek,N=pq,φn=p−1q−1,Takee,satisfying1<e<jnandjn,e=1,Computed,satisfyingd⋅e≡1modφn,Calculatew,w=∑i=1Nsi,pk=n,e,w,sk=n,d,si.(2)
Signature is as follows:(48)SignskM:H=∑i=1NFasiρM,σ=Hdmodn.(3)
Verify is as follows:(49)VrfypkM,σ.Ifσe=FawρMmodn, we return 1; otherwise, we return 0.Proof of the correctness of the scheme: according to Lemma2, the CSP-LD system satisfies the following properties:(50)Famb=amba−m=asatba−ta−s=asFatba−s=FasFatb.Because ofw=∑i=13si, we get ∏i=13FasiρM=FawρM. On the question of whether the security is satisfied, we can infer from the previous point that since M is an upper triangular matrix, it satisfies(51)Mρ=Mρ,i=1,2,3.When the adversary tries to distinguishM0 or M1 by computing the determinant,(52)detH∗−TH′=detpdetMi∗−tMi′ρdetp−1,i=1,2,3=detMi∗−tMi′ρ=m∗−m′ρa2i−1∗−a2i∗t−a2i′−a2i−1′nρ.Because the value ofρ is an even number (it can be set to ρ=2), the adversary cannot determine whether the signature comes from M0 or M1 based on the value calculated by detH∗−TH’, so H satisfies the selection of plaintext antiforgery. According to the previous inference in Definition 4, the aggregated signature scheme proposed by us is still antiforgery under the adaptive chosen message attack.According to the algorithm proposed by Shor, a quantum computer withN qubits can perform 2N operations at a time. In theory, the key is the 1024 bit long RSA algorithm, which can be cracked in 1 second with a 512 bit quantum computer. At present, as long as the proposed scheme is set si to a 160 bit integer, it can resist the exhaustion-resistant attack [27].


## 6. Efficiency Analysis

Now, we compare the computational efficiency of the RSA aggregate signature scheme under the CSP-LD system with some other aggregate signature schemes. Still assume that there areN users signing messages M at the same time. For each signature, if the aggregation method is not used, the original RSA signature method without aggregation method needs to store a total of N pairs of M,σ1,…,M,σN signatures. While the scheme in [36] improves the efficiency by 50%, the signature they store is M,σ1,…,σN. In our scheme, no matter how many users there are, we only need to store a pair of signatures, namely, M,σ, which benefits from the advantages of the CSP-LD system. Compared with [36], our improved efficiency has a linear relationship with the value of N, and the larger the value, the greater the advantage of our scheme. Compared with the pairing-based scheme in [24], our advantage is even more obvious, since it is known that a pairing operation takes approximately 6–20 times the time of a modulo-exponential operation [25].In addition, since all messages are encoded as low-dimensional matrices, the scaling rate in terms of storage and computation overhead is linear compared to message signature implementations and the length of aggregated signatures is fixed, maximizing signature storage savings space without losing accuracy. In terms of security, our scheme is also indestructible to a large extent, and the strongest attack method against the signature scheme, the adaptive chosen message attack, is still existentially unforgeable. Moreover, by setting the system parameter thresholds on the matrix dimension and the length of the private key, antiquantum attacks, and exhaustive attacks can be achieved.Explanation of symbols in Table1: Exp represents a power of 1 operation, H represents a hash operation, P represents a bilinear pairing operation, and n represents the number of users. Assuming that the following three schemes all select the group G whose order is the same prime number q, if the system parameter k is 160 bits, the length of the group G is calculated as G=160bit. The details are shown in Table 1.Table 1
The efficiency comparison between our scheme and literature [24, 36].
AssumptionSignature lengthSignature algorithmVerification algorithmSaving rateLiterature 24Pairing3202nE+nHnH+3n−1P50%Literature 36RSA160nEn+1E50%Our schemeRSA160nE2EFixed lengthThe details of the security comparison between our scheme and literature are shown in Table2.Table 2
The security comparison between our scheme and [3, 6, 24].
EUF-CMAAntiquantum securityLiterature 24NoNoLiterature 36YesNoOur schemeYesYes


## 7. Conclusion

This study improves the RSA-like signature scheme by proposing new schemes that take advantage of CSP-LD systems to encode messages with the low-dimensional matrix. By flexibly changing the encoding structure, it can perfectly satisfy the antiforgery under the adaptive choice message attack (EUF-CMA) without using the global hash function. Setting the matrix dimension greater than the critical value can achieve the antiquantum attack, and controlling the length of the user'ssi element longer than a certain bit can resist exhaustive attacks. In the environment where N users sign a message, we implement the aggregated signature under the RSA structure according to the CSP-LD system, which greatly reduces the generation of public and private key pairs. Moreover, the final signature pair has nothing to do with the number of users, which saves a lot of storage space and improves computing efficiency. In the future, we look forward to combining the signature scheme with cutting-edge technologies such as blockchain technology, smart contracts [37], and machine learning [38] to improve the deployment of the scheme, learn from each other's strengths, and furthermore, improve efficiency and security.


### 7.1. The notations of this work

In this section, we explain all the specific characters in the study; the details are shown in Table3.Table 3
Notations.
NotationsDescriptionkThe system parametersp,qTwo large prime numbers are chosen at randompk, skThe public key and private keyσResult of signing the messageFabFunctions satisfying certain properties under the CSP-LD systemGA general noncommutative semigrouppiUsersMMessagemii=1,2,…,6They together according to certain rules to form a messageMrRandom numberρRandom even numbera9 random matrices of 2 × 2Mi,σi,yi,ciThe quadruple,σi, is the signature of Mi, yi is the query result of an adversary A to Mi, and ci is a random value of 0 1siUser ID numberwThe sum of allsitSpecial 0 and 1 matrixRi,i=1,2,3The randomly sampled matrices fromR2×2TThe upper triangular encoding matrixHRegarded as the encryption of the messageM under the function F


## 7.1. The notations of this work

In this section, we explain all the specific characters in the study; the details are shown in Table3.Table 3
Notations.
NotationsDescriptionkThe system parametersp,qTwo large prime numbers are chosen at randompk, skThe public key and private keyσResult of signing the messageFabFunctions satisfying certain properties under the CSP-LD systemGA general noncommutative semigrouppiUsersMMessagemii=1,2,…,6They together according to certain rules to form a messageMrRandom numberρRandom even numbera9 random matrices of 2 × 2Mi,σi,yi,ciThe quadruple,σi, is the signature of Mi, yi is the query result of an adversary A to Mi, and ci is a random value of 0 1siUser ID numberwThe sum of allsitSpecial 0 and 1 matrixRi,i=1,2,3The randomly sampled matrices fromR2×2TThe upper triangular encoding matrixHRegarded as the encryption of the messageM under the function F



---

*Source: 8954767-2022-11-09.xml*