# Invalid Signatures Searching Bitwise Divisions-Based Algorithm for Vehicular Ad-Hoc Networks

Authors: Xin Ye; Gencheng Xu; Xueli Cheng; Jin Zhou; Zhiguang Qin
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

Vehicular ad-hoc networks (VANETs) are the crucial part of intelligent transportation systems (ITS), which are brought to enhance the security, efficiency, and comfort of transportation. VANETs have aroused extensive attention in the world recently. One of the challenges in practice is real time and low delay, which strongly requires VANETs to be efficient. Existing schemes have properly solved the problem which is how to aggregate the signatures and verify the aggregated signature. However, few solutions are proposed to pinpoint all invalid signatures if existing. The algorithms that can find all invalid signatures are not efficient enough. Following consideration of the above deficiencies of existing approaches, this paper proposes a factorial bitwise divisions (FBD) algorithm and its optimized version and early-stopping factorial bitwise divisions (EFBD) algorithm. Both algorithms are parallel-friendly. Compared with the binary-based batch verification algorithm, the experimental results demonstrate that the proposed algorithms achieve better performance in both theory and practice at low invalid signatures’ rate. Especially, in the parallel condition, when the number of invalid signatures is 1, the proposed algorithms cost only one aggregation-verification delay, while the comparison is more thanlog2n times.


---

## Body

## 1. Introduction

Vehicular ad-hoc networks (VANETs) were created by applying the principles of the mobile ad-hoc networks (MANETs), which is a spontaneous creation of wireless networks for data exchange in the vehicle domain. In the early 21st century, VANETs were considered direct implementation of the MANETs, and since then, because of the particularity of VANETs, they have developed into an independent field of study. By 2015, the focus was still on spontaneous networking, not to mention roadside units (RSUs) or cellular networks. The vehicle that joins the network becomes a wireless node or a wireless route. It allows vehicles spaced 100 to 300 meters from each other to form a decentralized and dynamic network automatically. When one vehicle is out of range and off the network, other vehicles can join and link to each other, creating new mobile networks [1–3]. Nowadays, VANETs have become an important part of the Internet of things (IoT) and they have a broad application prospect.Although it seems that VANETs own a lot of merits, there are still many problems to overcome to achieve a wide application. One of the obstacles is that VANETs require strong timeliness. Existing single verification methods can verify a signature one by one. However, in the area of heavy traffic, there are too many vehicles to be fully verified, which may lead to potential hazards. Batch verification and aggregate verification emerged at the right moment. In the batch verification mode, signatures are aggregated simultaneously at first; then, the aggregated signatures need to be verified. Compared with the validation process, the aggregation process takes very little time that it can be ignored. In this approach, if the aggregate signature can be verified, then all individual signatures are considered legal. However, all the individual signatures will be rejected when there exists one or more illegal signature, which will cause a great waste of time and cannot take full advantage of batch verification [4–6].In recent years, some researchers try to propose a few solutions to the aforementioned problem. Some just discard all signatures or verify them individually. Huang et al. [7, 8] use binary search to solve the problem. Indeed, it is easy to understand. Huang et al. [9] proposed a matrix-detection algorithm to reduce the escape probability of bad signatures, but it only applies to a batch of signatures which has less than four or odd number of bad signatures. However, the method still fails to achieve high efficiency. Ferng et al. [10] proposed a dynamic batch verification scheme. However, it cannot fully address the problem and has a relatively low efficiency. In addition, in the binary search algorithm, the number of layers is log2n which is not parallel-friendly. Therefore, binary search cannot have a relatively good performance in practice.To solve the problem, this paper proposes a factorial bitwise divisions’ algorithm (FBD) and an early-stopping factorial bitwise divisions’ (EFBD) algorithm. According to the index of each signature, they can be divided into a few groups; the details of the grouping strategy will be covered in Section4. Then, each group will be verified aggregately. If the aggregate validation passes, all signatures in this group are supposed to be legitimate. Therefore, in the later aggregate verification process, we can exclude all signatures in this group. In Section 4, we show that the size of each group is half the size of the input. Thus, half of the signatures are verified at least. Eventually, we will get a set including all illegitimate signatures and nn≥0 good signatures. The aforementioned algorithm is recursively executed until the input and output are completely same. Later, two algorithms execute differently. FBD will reorder each group, make them as the input, and recursively execute the algorithm, whereas EFBD will singly verify all signatures in the final output set when the size of the set is less than 2log2n. Our main contributions in this paper are as follows:(i)
Propose FBD and EFBD algorithms which are recursive and parallel-friendly for aggregate verification in VANETs and adopt a classical bitwise method(ii)
Through simulation experiments, the proposed algorithms are effective in a real application scenarioThe rest of this paper is organized as follows. InSection 2, we will introduce the related work, mainly about how the binary search algorithm works in batch verification. In Section 3, we describe some related concepts in VANETs and the problem definition of our work. Then, we present our proposed algorithms in Section 4 in detail. Time complexity analysis is described in Section 5. Experiments are performed and analyzed in Section 6. Finally, we will draw a conclusion of this paper in Section 7.


## 2. Related Works

In this section, we will cover several famous grouping strategies, especially the binary search algorithm.Heidari et al. [11] propose a novel population-based, nature-inspired optimization paradigm, which is called Harris Hawks Optimizer (HHO). Yang et al. [12] propose a general-purpose population-based optimization technique called Hunger Games Search (HGS). It has a simple structure, special stability features, and very competitive performance to realize the solutions of both constrained and unconstrained problems more effectively. Li et al. [13] propose a new stochastic optimizer called slime mould algorithm (SMA) which is based on the oscillation mode of slime mould in nature.To detect all invalid requests, Huang et al. [8] proposed a binary divisions’ detection (BDD) algorithm, which is based on the “divide-and-conquer” approach. It is shown in Algorithm 1. When BDD is applied in the signature verification process, it can easily and efficiently find all invalid signatures, and it is easy to understand. A full BDD tree is shown in Figure 1, where the dark red and dark purple grids represent the invalid signatures and the blue group of signatures indicates that all signatures in the group are valid, and the detecting branch should be terminated.Algorithm 1: Binary divisions’ detection algorithm.
Input: Nonempty SetA, start index i, end index jOutput: Set F(1)
function BDD (A,i,j)(2)
if Verify (A,i,j) then(3)
return∅(4)
end if(5)
ifi==j then(6)
returnAi(7)
end if(8)
F=F+BDDA,i,i+j/2(9)
F=F+BDDA,i,i+j/2+1,j(10)
returnF(11)
end functionFigure 1
Binary-based aggregate verification process of Huang et al. [8].The algorithm is described as follows. Firstly, aggregate the input and verify the aggregated signature. If the verification passes, it reveals all are valid, and the function returns an empty set; if not, it will divide the input into two batches. Then, treat each batch as the new input of the algorithm and call the BDD recursively. Once the input contains only one signature, the algorithm should be terminated. Eventually, the algorithm will return a set which exactly includes all invalid signatures.A randomly selected test was proposed by Guan et al. [14], the approach randomly chooses half of the signature and aggregates them into a batch. Bellare et al. [15] proposed a small exponent test, which also randomly selects 1, 2, 4, … signatures in each verification process. It improves the efficiency a little. Later, Hwang et al. [16] simplified the approach. Both are inefficient when we care about the exact invalid signatures.


## 3. Preliminaries

This section presents the basics related to signature verifications in VANETs. Note that this paper is based on popular and efficient schemes: certificateless signature (CLS) scheme and certificateless aggregate signature (CL-AS) scheme [4, 17]. The notations are listed in Table 1.Table 1
List of notations.
NotationDescriptionTATrusted authorityKGCKey generation centerRSURoadside unitpA secure prime numbersEAn elliptic curve:y2=x3+ax+b mod pPA generator of the additive groupFpThe finite field of the elliptic curvePKTA,αThe public key and private key of the TAPKKGC,βThe public key and private key of the KGCPKVi,ρiThe public key and private key of the vehiclePPKiPartial private key of the vehicleViσiThe signature of vehicleiPIDiPseudoidentity of the vehicleVi


### 3.1. Elliptic Curve Cryptography

As widely used in cryptographic, elliptic curve cryptography (ECC) is an excellent algorithm which has an extremely high efficiency and a relatively excellent security [18, 19]. It can use much fewer bits, less time, and memory to encrypt messages than RSA algorithm in the field of public key cryptography. Thanks to the excellent advantages, ECC can be perfectly applied to the application scenarios of VANETs [20]. We will make the following three definitions to describe ECC.Definition 1.
(elliptic curve definition). Assume thatFp is a finite field of the module p, where p is a large prime number. The elliptic curve over a finite field Fp can be defined as E:y2=x3+ax+bmodp, where a,b,x,y∈Fp and Δ=4a3+27b2≠0modp.Definition 2.
(addition of elliptic curves). Assume thatP=x1,y1∈E, where P is a point of the elliptic curve E, and −P=x1,−y1modp is the negative point of P. Suppose Q=x2,y2∈E, Q≠−P, and we can define a line l passes through P and Q and intersects the elliptic curve at a point R′=x3,y3, The symmetrical point about the x-axis with R′ is R=x3,−y3; then, we can define R=P+Q.Definition 3.
(elliptic curve discrete logarithm problem). Firstly, the discrete logarithm problem should be defined. Ifaandb are known, how to get k from the equation b=akmodp is a question. Assume that P1 is a point on the elliptic curve E on the finite field Fp, and select a random number k∈Zp∗. Then, we can calculate P2=k⋅P1. In this case, it is straightforward to calculate P2 according to Definition 2. However, given the description of elliptic curve discrete logarithm problem (ECDLP), it is scarcely possible to get k according the above equations.


### 3.2. System Model

In this section, we will try to describe the system model of VANETs in detail. As shown Figure2, there are four main participants: trusted authority (TA), key generation center (KGC), roadside unit (RSU), and vehicle, which can be divided into two layers: the upper layer includes TA and KGC, both are of more powerful computation, and the lower layer consists of RSUs and vehicles. The demonstration of each participant is as follows:TA: it is a fully trusted third party that is responsible for system initialization, user registration, system parameter generation, and system security implementation. If necessary, it can track malicious behavior and catch malicious nodes. In addition, it also has enough computing power and storage capacity.KGC: it is a partially trusted party used for generating partial private key. It can help vehicle generate partial secret key which contributes to its privacy security. It also has sufficient memory, processing, and computing capabilities the same as TA.RSU: it is a smart application device installed on the roadside, which is able to transmit and submit information to TA, KGC, vehicles, or other RSUs in a secure wired connection and plays the role of an intermediary agent. Unlike TA or KGC, RSU usually has limited computing power and storage capacity.Vehicle: it is the major and basic member in VANETs, which is generally equipped with a smart device which can perform the basic functions such as transmitting the vehicle’s messages and performing a simple calculation. In addition, vehicles commonly have limited computing power and storage capacity. The most obvious feature of the vehicle is that the network connection between vehicles is always in dynamic change.Figure 2
System model of VANETs.Note that TA and KGC are distinct entities in function and logical; however, the two usually are deployed on a single server in physics if the scale of VANETs is small.


### 3.3. Certificateless Aggregate Signature Scheme

Generally, a CLS scheme and a CL-AS scheme consist of the following seven algorithms [21, 22].Setup: the KGC and TA will execute a probabilistic algorithm, which needs a security parameterλ. Then, it generates an elliptic curve E, the public key PKTA and PKKGC, and the master secret key α and β, respectively. After the security parameters for ECC are generated, a number of system parameters which is used for ensuring the system in order are transmitted between each participant.ParitialPrivateKeyGeneration: in this algorithm, firstly, the vehicleVi transmits a tuple, which consists of a real identity and a partial pseudoidentity, to TA. Then, the TA generates a complete pseudoidentity with the tuple and sends it to the KGC for calculation. Eventually, the KGC transmits the partial private key to the vehicle Vi in a secure channel [23].VehicleKeyGeneration: the vehicleVi selects a random ρi∈Zq∗ as its secret key and calculates its public key PKVi=ρi⋅P.IndividualSign: this algorithm is used by each vehicleVi; after generating a message mi, the vehicle Vi tries to calculate a set of variables. Then, it sends the signature σ to the verifier.IndividualVerify: this algorithm is executed by the verifier such as RSU. When the inputs, including signatureσi, pseudoidentity PIDi, and current time Tcur, are received, the verifier will check the validity of the timestamp firstly. Then, the algorithm will output true if the signature is valid or false otherwise.AggregateSign: in this algorithm, generally, the aggregate signature generator is RSU in the system. For an aggregating setV of n vehicles V0,V1,…,Vn−1, the pseudoidentity PIDi of each vehicle Vi is the list PID, the corresponding public key PKVi of Vi, and message signature tuples m1,σ1,m2,σ2,…,mn,σn of Vi, respectively. The aggregate signature generator will generate signature σ; then, it will transmit the tuple including the signature, PID, and timestamp list T to the verifier.AggregateVerify: in general, this algorithm is executed by another RSU. It takes an aggregated setV of n vehicles V0,V1,…,Vn−1, the pseudoidentity PIDi of each vehicle Vi. The verifier will check the timestamp validity for each vehicle firstly. Then, it will output true if the signature is valid or false otherwise.To demonstrate the whole communication process, Figure3 shows the certificateless aggregate signature scheme.Figure 3
Certificateless aggregate signature scheme.As shown in Figure3, there are two main steps for CL-AS, aggregation and verification, which cause some delays in VANETs. For convenience, the delay brought by the aggregation of signatures is defined as Ta, while Tc is the total time in a cryptographic operation of the verification process. Without loss of generality, in the following algorithm, the tokens, rather than the actual number, will be used in the relevant calculation because different schemes adopt different algorithms and different time costs. Ta and Tc of different VENETs schemes are shown in Table 2 for reference. From the table, we can conclude that Ta is much smaller than Tc in whichever scheme. Even in some schemes, Tc is almost 1000 times of Ta. Therefore, in the following sections, Ta can be ignored and is not calculated.Table 2
Time cost of different schemes.
SchemeTa (ms)Tc (ms)Cui et al. [4]0.00181.3298Kamil et al. [5]0.06992.2899Kumar et al. [24]0.24574.5120Malhi et al. [25]5.206112.6330Zhao et al. [26]0.042417.7673


### 3.4. Problem Definition

Batch verification is widely used in VANETs [5, 9, 26]. There are two major research aspects about the batch verification: one is about the correctness and security of the encryption algorithm and how to aggregate the signatures into one and verify the aggregated one correctly and the other is about the strategy of grouping. An appropriate strategy will benefit the aggregation and verification process with significant time savings.This paper focuses on the latter one, the strategy of grouping, that is, how to divide all signatures into one or more batches to determine all invalid signatures as soon as possible. Here, the problem can be converted into a logical problem, given an input set whose size isnn≥1,n∈ℤ+. In the set, all n elements are either true or false, and assume that they are distributed randomly and testing an element is true or false costs much more time than other operations, such as AND. The number of false elements is x, and the number of true elements is n−x. The problem is how can we design an algorithm to determine exactly all false elements as efficiently as possible.In summary, the problem is as follows: given a signatures’ setA=σ1,σ2,,σ3,…,σn which includes a certain number of valid signatures and invalid signatures, find a set F only including all invalid signatures, i.e., A−F is verified true and minimized to F.


## 3.1. Elliptic Curve Cryptography

As widely used in cryptographic, elliptic curve cryptography (ECC) is an excellent algorithm which has an extremely high efficiency and a relatively excellent security [18, 19]. It can use much fewer bits, less time, and memory to encrypt messages than RSA algorithm in the field of public key cryptography. Thanks to the excellent advantages, ECC can be perfectly applied to the application scenarios of VANETs [20]. We will make the following three definitions to describe ECC.Definition 1.
(elliptic curve definition). Assume thatFp is a finite field of the module p, where p is a large prime number. The elliptic curve over a finite field Fp can be defined as E:y2=x3+ax+bmodp, where a,b,x,y∈Fp and Δ=4a3+27b2≠0modp.Definition 2.
(addition of elliptic curves). Assume thatP=x1,y1∈E, where P is a point of the elliptic curve E, and −P=x1,−y1modp is the negative point of P. Suppose Q=x2,y2∈E, Q≠−P, and we can define a line l passes through P and Q and intersects the elliptic curve at a point R′=x3,y3, The symmetrical point about the x-axis with R′ is R=x3,−y3; then, we can define R=P+Q.Definition 3.
(elliptic curve discrete logarithm problem). Firstly, the discrete logarithm problem should be defined. Ifaandb are known, how to get k from the equation b=akmodp is a question. Assume that P1 is a point on the elliptic curve E on the finite field Fp, and select a random number k∈Zp∗. Then, we can calculate P2=k⋅P1. In this case, it is straightforward to calculate P2 according to Definition 2. However, given the description of elliptic curve discrete logarithm problem (ECDLP), it is scarcely possible to get k according the above equations.


## 3.2. System Model

In this section, we will try to describe the system model of VANETs in detail. As shown Figure2, there are four main participants: trusted authority (TA), key generation center (KGC), roadside unit (RSU), and vehicle, which can be divided into two layers: the upper layer includes TA and KGC, both are of more powerful computation, and the lower layer consists of RSUs and vehicles. The demonstration of each participant is as follows:TA: it is a fully trusted third party that is responsible for system initialization, user registration, system parameter generation, and system security implementation. If necessary, it can track malicious behavior and catch malicious nodes. In addition, it also has enough computing power and storage capacity.KGC: it is a partially trusted party used for generating partial private key. It can help vehicle generate partial secret key which contributes to its privacy security. It also has sufficient memory, processing, and computing capabilities the same as TA.RSU: it is a smart application device installed on the roadside, which is able to transmit and submit information to TA, KGC, vehicles, or other RSUs in a secure wired connection and plays the role of an intermediary agent. Unlike TA or KGC, RSU usually has limited computing power and storage capacity.Vehicle: it is the major and basic member in VANETs, which is generally equipped with a smart device which can perform the basic functions such as transmitting the vehicle’s messages and performing a simple calculation. In addition, vehicles commonly have limited computing power and storage capacity. The most obvious feature of the vehicle is that the network connection between vehicles is always in dynamic change.Figure 2
System model of VANETs.Note that TA and KGC are distinct entities in function and logical; however, the two usually are deployed on a single server in physics if the scale of VANETs is small.


## 3.3. Certificateless Aggregate Signature Scheme

Generally, a CLS scheme and a CL-AS scheme consist of the following seven algorithms [21, 22].Setup: the KGC and TA will execute a probabilistic algorithm, which needs a security parameterλ. Then, it generates an elliptic curve E, the public key PKTA and PKKGC, and the master secret key α and β, respectively. After the security parameters for ECC are generated, a number of system parameters which is used for ensuring the system in order are transmitted between each participant.ParitialPrivateKeyGeneration: in this algorithm, firstly, the vehicleVi transmits a tuple, which consists of a real identity and a partial pseudoidentity, to TA. Then, the TA generates a complete pseudoidentity with the tuple and sends it to the KGC for calculation. Eventually, the KGC transmits the partial private key to the vehicle Vi in a secure channel [23].VehicleKeyGeneration: the vehicleVi selects a random ρi∈Zq∗ as its secret key and calculates its public key PKVi=ρi⋅P.IndividualSign: this algorithm is used by each vehicleVi; after generating a message mi, the vehicle Vi tries to calculate a set of variables. Then, it sends the signature σ to the verifier.IndividualVerify: this algorithm is executed by the verifier such as RSU. When the inputs, including signatureσi, pseudoidentity PIDi, and current time Tcur, are received, the verifier will check the validity of the timestamp firstly. Then, the algorithm will output true if the signature is valid or false otherwise.AggregateSign: in this algorithm, generally, the aggregate signature generator is RSU in the system. For an aggregating setV of n vehicles V0,V1,…,Vn−1, the pseudoidentity PIDi of each vehicle Vi is the list PID, the corresponding public key PKVi of Vi, and message signature tuples m1,σ1,m2,σ2,…,mn,σn of Vi, respectively. The aggregate signature generator will generate signature σ; then, it will transmit the tuple including the signature, PID, and timestamp list T to the verifier.AggregateVerify: in general, this algorithm is executed by another RSU. It takes an aggregated setV of n vehicles V0,V1,…,Vn−1, the pseudoidentity PIDi of each vehicle Vi. The verifier will check the timestamp validity for each vehicle firstly. Then, it will output true if the signature is valid or false otherwise.To demonstrate the whole communication process, Figure3 shows the certificateless aggregate signature scheme.Figure 3
Certificateless aggregate signature scheme.As shown in Figure3, there are two main steps for CL-AS, aggregation and verification, which cause some delays in VANETs. For convenience, the delay brought by the aggregation of signatures is defined as Ta, while Tc is the total time in a cryptographic operation of the verification process. Without loss of generality, in the following algorithm, the tokens, rather than the actual number, will be used in the relevant calculation because different schemes adopt different algorithms and different time costs. Ta and Tc of different VENETs schemes are shown in Table 2 for reference. From the table, we can conclude that Ta is much smaller than Tc in whichever scheme. Even in some schemes, Tc is almost 1000 times of Ta. Therefore, in the following sections, Ta can be ignored and is not calculated.Table 2
Time cost of different schemes.
SchemeTa (ms)Tc (ms)Cui et al. [4]0.00181.3298Kamil et al. [5]0.06992.2899Kumar et al. [24]0.24574.5120Malhi et al. [25]5.206112.6330Zhao et al. [26]0.042417.7673


## 3.4. Problem Definition

Batch verification is widely used in VANETs [5, 9, 26]. There are two major research aspects about the batch verification: one is about the correctness and security of the encryption algorithm and how to aggregate the signatures into one and verify the aggregated one correctly and the other is about the strategy of grouping. An appropriate strategy will benefit the aggregation and verification process with significant time savings.This paper focuses on the latter one, the strategy of grouping, that is, how to divide all signatures into one or more batches to determine all invalid signatures as soon as possible. Here, the problem can be converted into a logical problem, given an input set whose size isnn≥1,n∈ℤ+. In the set, all n elements are either true or false, and assume that they are distributed randomly and testing an element is true or false costs much more time than other operations, such as AND. The number of false elements is x, and the number of true elements is n−x. The problem is how can we design an algorithm to determine exactly all false elements as efficiently as possible.In summary, the problem is as follows: given a signatures’ setA=σ1,σ2,,σ3,…,σn which includes a certain number of valid signatures and invalid signatures, find a set F only including all invalid signatures, i.e., A−F is verified true and minimized to F.


## 4. The Proposed Bitwise Divisions’ Algorithm

In this section, factorial bitwise divisions’ (FBD) algorithm and early-stopping factorial bitwise divisions’ (EFBD) algorithm will be fully introduced. In addition, three theorems will be proved to support FBD and EFBD.


### 4.1. Description of FBD

FBD is a recursive algorithm, and the maximal recursion time islog2n. Note that the output set F equals to the input set A in the beginning. First of all, it will check whether all signatures are valid or not. If so, it will return the full set F, which means all signatures in the input set A are valid. And if the size of the set A is 1, it means that the algorithm has gone into the final layer and the algorithm will return (Algorithm 2).Algorithm 2: Factorial bitwise divisions’ algorithm.
Input: nonempty SetAOutput: setF(1)
functionFBDA(2)
ifA⋅size=1 then(3)
if Verify (A) then(4)
return∅(5)
else(6)
returnA(7)
end if(8)
end if(9)
GS00,S01,S10,S11,…=DivideByBitsA(10)
X=VerifyG(11)
F=F−X(12)
ifF⋅size=1 then(13)
returnF(14)
end if(15)
ifF=∅ then(16)
return∅(17)
end if(18)
ifF⋅size=A⋅size then(19)
choose two groupsSi1,Si0 on random bit(20)
F=F−FBDReorderSi0(21)
F=F−FBDReorderSi1(22)
else(23)
F=F−FBDF(24)
end if(25)
returnF(26)
end functionFigure4 shows the FBD algorithm flow which selects a sample to demonstrate the entire process. Function DivideByBits is utilized to divide the set A to 2log2n groups. It is a bitwise operation. For example, a signature whose index is 12 and the binary representation is 001010. Therefore, it is expected to be divided into groups S10,S21,S30,S41,S50,S60. The superscript represents that the group is divided by 0 or 1, and the subscript represents which bit is used to divide the set. All groups in G are verified and the set X includes all invalid groups. Then, we can filter F and make it smaller. Recursive boundary is the size of F is 1 or 0. If no signatures are filtered, then the algorithm randomly selects a certain bit and gets two original groups Si0,Si1 and reorders them and makes them as input to recursively call the algorithm. If some signatures are filtered, then use the output set F as an input to recursively call the algorithm until the filter does not work.Figure 4
Proposed factorial bitwise divisions’ algorithm flow.A few proofs will be necessary to demonstrate to support FBD and EFBD algorithms. Theorems1 and 2 prove the recursive boundary, and Theorem 3 proves that the result is correct. With the following four proofs, FBD and EFBD can work normally and efficiently.Theorem 1.
If the output setF is an empty set, then the algorithm is supposed to be terminated.Proof.
As described in the algorithm, if the output setF is an empty set, then all signatures are filtered and there exist no invalid signatures in set A. Therefore, the original proposition is correct.Theorem 2.
If the output setF has just one signature, then the algorithm is supposed to be terminated.Proof.
As the algorithm goes, if the output setF has only one invalid signature, it means that the number of both invalid and valid groups definitely is log2n. According to FBD, one valid group can half the size of F and log2n valid groups can cut the size of F to 1. Therefore, the algorithm can return the output set F and the original proposition is true.Theorem 3.
The output setF consists of all invalid signatures.Proof.
Assume that the output setF does not consist of all invalid signatures, which means that the algorithm has omitted certain invalid signatures. According to the algorithm, the only way to filter from the set F is that the group is verified as true. However, when there exist invalid signatures in a certain group, it will definitely not pass the verification, and the whole group will not be filtered which contradicts the assumption. Therefore, the original proposition is correct.Theorem 4.
In the output setF, if the number of invalid signatures is greater than that of valid signatures, then the scale of F will not be reduced.Proof.
Assume that the number of input setA is n,n=2k, the number of invalid signatures is x,x>n/2, and the number of valid signatures is n−x which is small than n/2. In the grouping of certain bit i, Si0 and Si1 can be seen as two boxes whose capacity is n/2. When the number of invalid signatures is greater than the capacity of one box, the other box surely has at least one invalid signature whatever the distribution is. Since both boxes have at least one invalid signature, then they will both be verified failed. Also, the inference is true for other bits. Eventually, all groups are false and no more signatures can be removed from the output set F. Therefore, the original proposition is correct.
Consider its contrapositive. In the output setF, if the scale of F can be reduced, then the number of valid signatures is greater than that of invalid signatures. Indeed it is true. However, it is converse. In the output set F, if the number of valid signatures is greater than that of invalid signatures, then the scale of F which can be reduced is obviously false. Unfortunately, it is exactly what FBD needs. It can easily find its counterexample which can be called repulsion number.
The filter will definitely be invalid and cannot filter any valid signatures. Then, the algorithm will reorder each group. The group can go back to FBD as the groupA recursively. Eventually, the algorithm will go to the recursive boundary which can be seemed as a single verification.


### 4.2. Description of EFBD

In FBD, it is usual that the majority of the output setF are invalid signatures. As FBD goes, it will branch to the final layer which is a waste of time. As an optimized algorithm for FBD, EFBD adopts single verification when the size of the set F is less than 2log2n. The algorithm is designed specially for parallel calculation, and 2log2n verifications can be calculated at a time. The specific algorithm is shown in Algorithm 3.Algorithm 3:Early stopping bitwise divisions’ algorithm.
Input: nonempty SetAOutput: setF(1)
function EFBD (A)(2)
ifA⋅size=1 then(3)
if Verify (A) then(4)
return∅(5)
else(6)
returnA(7)
end if(8)
end if(9)
GS00,S01,S10,S11,…=DivideByBitsA(10)
X=VerifyG(11)
F=F−X(12)
ifF⋅size=1 then(13)
returnF(14)
end if(15)
ifF=∅ then(16)
return∅(17)
end if(18)
ifF⋅size<=2log2n then(19)
return SingleVerify (F)(20)
end if(21)
ifF⋅size=A⋅size then(22)
choose two groupsSi1,Si0 on random bit(23)
F=F−EFBDReorderSi0(24)
F=F−EFBDReorderSi1(25)
else(26)
F=F−EFBDF(27)
end if(28)(29)
returnF(30)
end functionMost part of EFBD is completely consistent with FBD. The difference is that when the loop terminates, it will singly check each signature inF which will filter all valid signatures. Eventually, it will get a final set F including exactly all invalid signatures.Definition 4.
For two or more binary codes, if both 0 and 1 appear in every bit, then they are called repulsion numbers.If there exist false repulsion numbers, as EFBD algorithm goes, they will be divided into different groups no matter which bit is used to group. As a result, all groups will be verified false and the filter will be invalid.


## 4.1. Description of FBD

FBD is a recursive algorithm, and the maximal recursion time islog2n. Note that the output set F equals to the input set A in the beginning. First of all, it will check whether all signatures are valid or not. If so, it will return the full set F, which means all signatures in the input set A are valid. And if the size of the set A is 1, it means that the algorithm has gone into the final layer and the algorithm will return (Algorithm 2).Algorithm 2: Factorial bitwise divisions’ algorithm.
Input: nonempty SetAOutput: setF(1)
functionFBDA(2)
ifA⋅size=1 then(3)
if Verify (A) then(4)
return∅(5)
else(6)
returnA(7)
end if(8)
end if(9)
GS00,S01,S10,S11,…=DivideByBitsA(10)
X=VerifyG(11)
F=F−X(12)
ifF⋅size=1 then(13)
returnF(14)
end if(15)
ifF=∅ then(16)
return∅(17)
end if(18)
ifF⋅size=A⋅size then(19)
choose two groupsSi1,Si0 on random bit(20)
F=F−FBDReorderSi0(21)
F=F−FBDReorderSi1(22)
else(23)
F=F−FBDF(24)
end if(25)
returnF(26)
end functionFigure4 shows the FBD algorithm flow which selects a sample to demonstrate the entire process. Function DivideByBits is utilized to divide the set A to 2log2n groups. It is a bitwise operation. For example, a signature whose index is 12 and the binary representation is 001010. Therefore, it is expected to be divided into groups S10,S21,S30,S41,S50,S60. The superscript represents that the group is divided by 0 or 1, and the subscript represents which bit is used to divide the set. All groups in G are verified and the set X includes all invalid groups. Then, we can filter F and make it smaller. Recursive boundary is the size of F is 1 or 0. If no signatures are filtered, then the algorithm randomly selects a certain bit and gets two original groups Si0,Si1 and reorders them and makes them as input to recursively call the algorithm. If some signatures are filtered, then use the output set F as an input to recursively call the algorithm until the filter does not work.Figure 4
Proposed factorial bitwise divisions’ algorithm flow.A few proofs will be necessary to demonstrate to support FBD and EFBD algorithms. Theorems1 and 2 prove the recursive boundary, and Theorem 3 proves that the result is correct. With the following four proofs, FBD and EFBD can work normally and efficiently.Theorem 1.
If the output setF is an empty set, then the algorithm is supposed to be terminated.Proof.
As described in the algorithm, if the output setF is an empty set, then all signatures are filtered and there exist no invalid signatures in set A. Therefore, the original proposition is correct.Theorem 2.
If the output setF has just one signature, then the algorithm is supposed to be terminated.Proof.
As the algorithm goes, if the output setF has only one invalid signature, it means that the number of both invalid and valid groups definitely is log2n. According to FBD, one valid group can half the size of F and log2n valid groups can cut the size of F to 1. Therefore, the algorithm can return the output set F and the original proposition is true.Theorem 3.
The output setF consists of all invalid signatures.Proof.
Assume that the output setF does not consist of all invalid signatures, which means that the algorithm has omitted certain invalid signatures. According to the algorithm, the only way to filter from the set F is that the group is verified as true. However, when there exist invalid signatures in a certain group, it will definitely not pass the verification, and the whole group will not be filtered which contradicts the assumption. Therefore, the original proposition is correct.Theorem 4.
In the output setF, if the number of invalid signatures is greater than that of valid signatures, then the scale of F will not be reduced.Proof.
Assume that the number of input setA is n,n=2k, the number of invalid signatures is x,x>n/2, and the number of valid signatures is n−x which is small than n/2. In the grouping of certain bit i, Si0 and Si1 can be seen as two boxes whose capacity is n/2. When the number of invalid signatures is greater than the capacity of one box, the other box surely has at least one invalid signature whatever the distribution is. Since both boxes have at least one invalid signature, then they will both be verified failed. Also, the inference is true for other bits. Eventually, all groups are false and no more signatures can be removed from the output set F. Therefore, the original proposition is correct.
Consider its contrapositive. In the output setF, if the scale of F can be reduced, then the number of valid signatures is greater than that of invalid signatures. Indeed it is true. However, it is converse. In the output set F, if the number of valid signatures is greater than that of invalid signatures, then the scale of F which can be reduced is obviously false. Unfortunately, it is exactly what FBD needs. It can easily find its counterexample which can be called repulsion number.
The filter will definitely be invalid and cannot filter any valid signatures. Then, the algorithm will reorder each group. The group can go back to FBD as the groupA recursively. Eventually, the algorithm will go to the recursive boundary which can be seemed as a single verification.


## 4.2. Description of EFBD

In FBD, it is usual that the majority of the output setF are invalid signatures. As FBD goes, it will branch to the final layer which is a waste of time. As an optimized algorithm for FBD, EFBD adopts single verification when the size of the set F is less than 2log2n. The algorithm is designed specially for parallel calculation, and 2log2n verifications can be calculated at a time. The specific algorithm is shown in Algorithm 3.Algorithm 3:Early stopping bitwise divisions’ algorithm.
Input: nonempty SetAOutput: setF(1)
function EFBD (A)(2)
ifA⋅size=1 then(3)
if Verify (A) then(4)
return∅(5)
else(6)
returnA(7)
end if(8)
end if(9)
GS00,S01,S10,S11,…=DivideByBitsA(10)
X=VerifyG(11)
F=F−X(12)
ifF⋅size=1 then(13)
returnF(14)
end if(15)
ifF=∅ then(16)
return∅(17)
end if(18)
ifF⋅size<=2log2n then(19)
return SingleVerify (F)(20)
end if(21)
ifF⋅size=A⋅size then(22)
choose two groupsSi1,Si0 on random bit(23)
F=F−EFBDReorderSi0(24)
F=F−EFBDReorderSi1(25)
else(26)
F=F−EFBDF(27)
end if(28)(29)
returnF(30)
end functionMost part of EFBD is completely consistent with FBD. The difference is that when the loop terminates, it will singly check each signature inF which will filter all valid signatures. Eventually, it will get a final set F including exactly all invalid signatures.Definition 4.
For two or more binary codes, if both 0 and 1 appear in every bit, then they are called repulsion numbers.If there exist false repulsion numbers, as EFBD algorithm goes, they will be divided into different groups no matter which bit is used to group. As a result, all groups will be verified false and the filter will be invalid.


## 5. Performance Analysis

In this section, the performance and time complexity will be analyzed. In addition, our discussion is based on a parallel calculation. For convenience, we defineN=2log2n which equals to the number of groups in a bitwise partition. For BDD algorithm, it can calculate at most N nodes in the same layer at a time. However, it cannot execute cross-layer computing. For FBD and EFBD, they can also calculate N nodes at a time.If there exist no invalid signatures, then both algorithms need only one verification. Then, one invalid signature circumstance can be idealized. Time complexity of binary search is reproduced below:(1)On=1N+2N+2N+⋯+2N︸log2nitems=1+log2n×2N.In general,N is always greater than or equal to 2. Therefore, equation (1) can be further simplified:(2)On=1+log2n.According to the algorithm, the time complexity of FBD isOn=2log2n/N=1.Considering the worst case, that is, all signatures are invalid; BDD algorithm will branch on each leaf. Its time complexity is as follows:(3)n=1N+2N+4N+⋯+nN≥1N+2N+4N+⋯+nN≥2n−1N.Time complexity of FBD is as follows:(4)On=2log2nN+22log2n−1N+23log2n−2N+⋯+2log2nlog2n−log2n−1N=2log2nN+22log2nN+23log2nN+⋯+2log2nlog2nN−22N+23×2N+24×3N+⋯+2log2nlog2n−1N≤1+2+4+⋯+2log2n−1−2nlog2n−4n+4N=4n−4−2log2nN.


## 6. Simulation Analysis

In the simulation experiment, BDD, FBD, and EFBD are simulated to countTa and Tc, respectively, in different scales and invalid signatures. In addition, the parallel calculation is adopted and the scale N=2log2n.For different invalid signatures and scales, the performance of the three algorithms is shown in Tables3 and 4. The number of signatures is from 4 (22) to 128 (27) and the invalid signatures are 1, 2, 3, 4, and 5, respectively. Because the distribution of invalid signatures greatly influences the result, the simulation is repeated 1000 times and the result is equilibrated to avoid randomness.Table 3
Number ofTc used in different algorithms.
BDDFBDEFBD123451234512345433333133441111184444413456122331655555145681223332666661468101244564777771589111346712888888158111313578Table 4
Number ofTa used in different algorithms.
BDDFBDEFBD12345123451234542222211111333338333333444436788164444479111213714161920327788815192530321531343742641112131314313856667231596679871282023242627637710814015563115123155177As shown in Table3, when the number of signatures is 4, EFBD only uses 1Tc for the reason that it will use single verification when the size of the input set is less than or equal to N=2log2n. In addition, when the number of false nodes is 1, FBD and EFBD only need 1Tc because of their unique filtering structure. BDD has a relatively constant number because of its regular hierarchic execution. In comparison, FBD and EFBD have a high performance when the number of invalid signatures is less than 2 and 4, respectively. BDD has to go through log2n layers to find the invalid signatures. However, as described in Section 4, FBD and EFBD can be seen as a filter, and it can efficiently filter most of the valid signatures and get a set containing invalid signatures when there exist a few invalid signatures. In Table 4, although the number of Ta of our algorithms is bigger than that of BDD, Ta is defined as a much smaller time cost compared to Tc, which makes no difference in the circumstance.Furthermore, Figure5 shows the total time cost comparison among the three algorithms. It should be noted that the total time cost includes both aggregation time and verification time. In our work, Ta is 0.036 ms, and Tc is 2.2899 ms which is much bigger than Ta. Therefore, in Figure 5, the rank of different algorithms is the same as the rank in Table 3. From the figures, when the number of elements and the number of false elements are small, the two proposed algorithms are better than the BDD significantly. Actually, in a real scene, the number of elements and the number of false elements is small. Therefore, FBD and EFBD algorithm can achieve high efficiency in real application scenarios.Figure 5
Total time cost of different number of vehicles. (a)n = 4. (b) n = 8. (c) n = 16. (d) n = 32. (e) n = 64. (f) n = 128.
(a)(b)(c)(d)(e)(f)


## 7. Conclusion

To solve the problem that batch verification has low efficiency in the process of message verification, FBD and EFBD are proposed, and they are featured by parallel calculation and filtering. They show their high efficiency after simulation experiments. However, FBD and EFBD have relatively low efficiency performance in serial computing and only have high efficiency in parallel calculation. And, they cannot outperform BDD when invalid signatures are more than a certain number. According to the experiments, when the number of invalid signatures is more than 4, FBD and EFBD have low efficiency. In the future, FBD and EFBD can be simulated in a more real scene and some factors can be considered. Furthermore, they can be implemented in the hardware that supports parallel computing. Due to repulsion number problem, they can also be optimized to attain higher performance.



---

*Source: 9970851-2021-05-24.xml*