infrastructures possible. Such infrastructures will usher automation in a large number of application domains such as transportation, manufacturing, smart-grid and urban life (e.g. Smart-city).

Because of their control capabilities and pervasive data acquisition, securing such smart-infrastructures is a critical requirement. Even though many security techniques are available, their application to smart infrastructures is not straightforward, especially when such infrastructures are based on networks that include mobile devices, and for safety reasons, they have to meet real-time requirements. We refer to such networks as time-critical networks.

An example is a vehicular network in which events from vehicles, such as sudden brake of a vehicle, have to be communicated promptly to the other vehicles in the network so that they can timely react to the events. Scalability is also crucial as many envisioned time-critical networks involve huge numbers of devices and systems. A key security technique for any comprehensive solution is represented by authentication as it is critical for establishing trust and securing communications among parties in a network. Authentication techniques have been widely investigated. However, to meet the real-time and scalability requirements of large scale time-critical networks, we need techniques that are far more efficient than the currently available ones. It is critical that devices in such a network should be able to respond and/or to initiate a large number of authentications in a small time-frame.

To address such a requirement, in this paper we develop a series of fast digital signatures, supported by hardwareacceleration, to enable real-time authentication in time-critical networks. We introduce a generic signature framework, referred to as Structure-free and Compact Real-time Authentication (SCRA), that can be instantiated with any secure aggregate signature. We then develop specific SCRA instantiations from Condensed-RSA [30], BGLS [7], NTRU [27] and PASSSign [18], and demonstrate that these SCRA schemes are significantly more computationally efficient than their counterparts in modern CPUs. We also computationally parallelize SCRA across thousands lightweight threads commonly supported by modern GPUs. We use several optimizations and show that the performance can be higher compared to the performance obtained when the CPU is used. Finally, we apply similar optimizations to SoCs commonly used by car manufacturers and IoT deployments.

We outline the advantages and limitations of authentication mechanisms that are most relevant to our work.

1) Message Authentication Codes and Standard Digital Signatures: Symmetric crypto-based authentication mechanisms rely on Message Authentication Code (MAC) [28]. Despite their computational efficiency, these methods are not practical for broadcast authentication in large-scale distributed systems, as they require pairwise key distribution among all signers and verifiers. They also cannot achieve non-repudiation and public verifiability. Digital signatures (e.g., RSA [35], ECDSA [3]) rely on the Public Key Infrastructures (PKIs) [28], which makes them publicly verifiable and scalable for large systems. Hence, they are considered as a primary authentication mechanism for large-scale delayaware systems. For instance, the vehicular WAVE architecture mandates the use of PKI mechanisms to sign critical messages [2]. Despite their scalability, standard digital signature schemes require several expensive operations such as modular exponentiation and pairing (e.g., BLS [8]). Therefore, they are not suitable for time-critical authentication. It has been shown that they introduce significant delays, which are unacceptable in time-critical networks such as vehicular networks [33].

2) Delayed Key Disclosure and Amortized Signatures: Delayed key disclosure methods [32] are efficient as they introduce an asymmetry between signer and verifier via a time factor. However, these methods require packet buffering, and therefore cannot achieve immediate verification (which is vital for delay-aware authentication). Signature amortization (e.g., [25]) computes a signature over a set of messages instead of individual messages. Hence, the cost of signature generation and verification is amortized over multiple messages. However, these methods require packet buffering and introduce packet loss risk due to the use of hash chains.

3) Specialized Signatures: One-Time Signatures (OTSs) (e.g., [34]) offer fast signature generation and verification. However, they incur very large signature and public key sizes, and also public keys must be renewed frequently. Various customizations of traditional signatures (along with cryptographic pairing [8]) and OTSs for time-critical systems such as vehicular networks (e.g., [16]) and smart-grids have been proposed. However, these schemes still suffer from computational inefficiency (due to heavy use of pairings) or public key distribution issues (OTSs).

The offline-online signatures (e.g., [31]) pre-compute a token for each message to be signed at the offline-phase, and then use it to compute a signature on a message very efficiently at the online-phase. Despite their merits, offline-online signatures incur significant storage overhead (i.e., linear with respect to the number of messages to be signed). Moreover, they require heavy computation for applications with high message throughput, since the signer depletes pre-computed tokens rapidly and is forced to regenerate them at the onlinephase. Hence, offline-online signatures are not suitable for time-critical networks with high message throughput.

Our prior work Rapid Authentication (RA) [41] is an efficient offline-online signature, which leverages the already available pre-defined message structures in certain applications (e.g., smart-grid) to reduce the computational and storage overhead of RSA-type offline-online constructions. Despite its advantages, RA is only suitable for applications that have a predefined message structure with a limited number of message components. Moreover, RA requires pre-computed tokens (i.e., one-time masking signatures) to be stored/renewed per item as in traditional offline-online techniques. Hardware-Accelerated Authentication (HAA) [39] exploits hardware acceleration to speed up RA in various settings. HAA demonstrates the benefit of hardware acceleration to reduce the end-to-end delay of digital signature schemes. In particular, HAA shows the performance advantages offered by GPUs for offline-online signatures to batch regenerate tokens as they are depleted.

We develop a new suite of delay-aware signatures that we refer to as Structure-Free and Compact Authentication (SCRA) to enable fast authentication for time-critical networks.

1) Main Idea: SCRA is based on the observation that the signature aggregation operation of some signature schemes is several magnitudes of times faster than that of their signature generation. We leverage this fact to shift the expensive operations of signature generation phase to the key generation phase. That is, at the key generation (offline), we compute a set of signatures on the bit-structures of a hash output domain. Later, we can combine these pre-computed signatures very efficiently based on the hash of each message without enforcing a message format (e.g., unlike [41]) or storage/regeneration of a token per-message (e.g., unlike offline-online signatures (e.g., RA [9], [41]) that incurs linear storage and re-computation overhead). This simple but elegant strategy enables SCRA to achieve very fast signature generation, a low end-to-end cryptographic delay, small-constant signature sizes with a constantsize private/public key. Figure 1 further outlines our main idea.

2) Properties: We outline below the relevant properties of our schemes.

• Generic and Simple Design: SCRA can be instantiated from any aggregate signature. We prove that SCRA is EU-CMA-secure if its base scheme is IA-EU-CMA secure (see Section II). We show that SCRA is at least a magnitude times faster than standard signatures as shown in Table I even without optimization.

• Highly Fast Signing, Low Delay and Compactness:W e develop several instantiations of SCRA offering performance trade-offs with different computational overhead, signature and key sizes.

-SCRA-C-RSA is constructed from C-RSA [30], which transforms the highly costly exponentiation of RSA signing into a few modular exponentiations, followed by already efficient signature verification. Therefore, SCRA-C-RSA offers the lowest end-to-end delay among all of its counterparts (e.g., 7 and 18 times faster than ECDSA and RSA, respectively) with a signature size of standard RSA. This makes SCRA-C-RSA an ideal choice for time-critical applications with a reasonable signature size. -SCRA-BGLS is constructed from BGLS [7], which reduces the signing cost from an exponentiation to a few modular It is important to mention that we use the NTRU scheme that is secure against transcript attacks [13]. Signatures are aggregated using the lattice based aggregation technique described in [15]. The lattice based sequential aggregate signature is proven to be secure in the random oracle security model [4]. Due to its moderate signature and key sizes and low end-to-end delay, SCRA-NTRU is ideal for time-critical applications. -SCRA-NTRUPASS is based on the PASS [18] signature scheme. It is also a lattice based cryptographic scheme based on the partial Fourier recovery problem.

• Performance Enhancements via Hardware-Acceleration: We improve the performance of SCRA by developing various hardware-acceleration and software-optimizations, which enable significant speed improvements (see Section VI).

We first introduce our notation and definitions, followed by our system and threat model. We then give our security model, in which we clarify the security properties of the SCRA schemes.

|S| denotes the cardinality of set S. {x i } l i=0 denotes (x 0 ,..., x l ). x $ ← S denotes that variable x is randomly and uniformly selected from set S. ||, |x| and {0, 1} * denote the concatenation operation, the bit length of variable x and the set of binary strings of any finite length, respectively.

Definition 1: A signature scheme SGN is a tuple of three algorithms (Kg, Sig, Ve r ) defined as follows:

-(sk, PK) ← SGN.Kg(1 κ ): Given the security parameter 1 κ , the key generation algorithm returns a private/public key pair (sk, PK) as the output.

s ← SGN.Sig(m, sk): The signing algorithm takes a message m ∈{ 0, 1} * and a private key sk as the input, and returns a signature s as the output. -{0, 1}←SGN.Ve r (m, s, PK): The verification algorithm takes a message m ∈{0, 1} * , signature σ and public key PK as the input. It returns a bit: 1 means valid and 0 means invalid. SCRA relies on aggregate signatures [7], which can aggregate multiple signatures into a single compact signature. SCRA uses a single-signer aggregate signature (e.g., [30]

Our system model follows the traditional PKC-based broadcast authentication model (e.g., [41]), in which a signer computes a digital signature on a message and broadcasts a message-signature pair to the verifiers. This model is compatible with our target time-critical applications. For instance, in vehicular networks, a vehicle or road infrastructure broadcasts authenticated messages to the surrounding entities as described in vehicular communication standards [2]. Our threat model reflects how a standard digital signature-based broadcast authentication works. That is, an adversary A can observe message-signature pairs computed under a private key. A also can actively intercept, modify, inject and replay messages transmitted over the network. A aims at producing existential forgeries against the digital signatures computed by signers.

The security notion for a signature is Existential Unforgeability under Chosen Message Attacks (EU-CMA).

Definition 3: The EU-CMA experiment for SGN is as follows:

-Setup. Algorithm B runs (sk, PK) ← SGN.Kg (1 κ ) and provides PK to the adversary A . -Queries. A queries B on any message m j of her choice for j = 1,...,q s . B replies to each query with a signature s j ← SGN.Sig(m j , sk). -Fo rge r y. A outputs a forgery (m * , s * ) and wins the EU-CMA experiment, if SGN.Ve r (PK, m * , s * ) = 1a n d m * was not queried to B . SGN is (t, q s , )-EU-CMA secure, if no A in time t making at most q s queries has an advantage with probability .

SCRA is constructed from a single-signer aggregate signature that achieves the signature immutability (described in detail below). The basic security notion for aggregate signatures is Aggregate-EU-CMA (A-EU-CMA) [7], [20], which captures the homomorphic properties of aggregate signatures. Later, the security of aggregate signatures has evolved to capture improved security properties such as signature immutability. Intuitively, signature immutability refers to the difficulty of computing new valid aggregated signatures from a set of other aggregated signatures [29]. To describe Immutable-A-EUCMA (IA-EU-CMA) [26], [43] security, we first define the aggregate signature extraction argument as below.

1) Aggregate Signature Extraction: The L-aggregate signature extraction problem, referred as AE problem, means that for a given aggregate signature s ← ASig.Agg(γ 1 ,...,γ L ) computed on L individual data items, it is difficult to extract the individual signatures (γ 1 ,...,γ L ) provided that only s is known to the extractor. Moreover, it is difficult to extract any aggregate signature subset s from a given aggregate signature s [42]. The AE problem was first introduced by Boneh et al. in [7] for the security of BGLS signatures, but as an intractability assumption without a proof. Coron and Naccache [10] later showed that Boneh's AE problem for BGLS scheme is equivalent to the Computational Diffie Hellman Assumption (CDH) [21]. Yavuz et al. [43] analyzed the log truncation problem for forward-secure and aggregate signatures [26], and produced formal proofs with AE argument for only the DLP-based schemes [43]. A related problem in the context of one-way accumulators for RSA have been considered in [6], which extends to other aggregate RSA variants (e.g., C-RSA [29]).

Definition 4: The AE experiment for a ASig is as follows [42]:

-Setup. Algorithm B runs (sk, PK) ← ASig.Kg (1 κ ) and provides PK to the adversary A . -Queries. A queries B on any batch message comprised of L individual messages -→ m j = (m j,1 ,...,m j,L ) of her choice for j = 1,...,q s . B replies to each query j with an aggregate signature s j ← ASig.Agg(γ j,1 ,...,γ j,L ), where {γ j,i ← ASig.Sig(m j,i , sk)

-→ m * is a subset of previously queried or some combination of previously queried batch messages: ∃I ⊆ {1,...,q s }: -→ m * ⊆| | k∈I -→ m k . This implies that -→ m * itself as a batch query never has been queried directly to B (but individual data items in -→ m * have been queried as an element of different batch queries before, but not individually), 3. The extraction is non-trivial: If -→ m * is combined with any previously queried or a combination of previously queried batch messages, the combination is not equal to one of the previously queried batch message itself:

. ASig is (t, q s , )-AE secure, if no A in time t making at most q s queries has an advantage with probability .

We now provide the definition of Immutable-A-EUCMA (IA-EU-CMA) security [26], [43] as below:

Definition 5: The IA-EU-CMA experiment for a ASig is as follows [42]:

-Setup. Algorithm B runs (sk, PK) ← ASig.Kg (1 κ ) and provides PK to the adversary A . -Queries. A queries B on any batch message comprised of L individual messages -→ m j = (m j,1 ,...,m j,L ) of her choice for j = 1,...,q s . B replies to each query j with an aggregate signature s j ← ASig.Agg(γ j,1 ,...,γ j,L ), where {γ j,i ← ASig.Sig(m j,i , sk)} L i=1 . -Fo rge r y. A outputs a forgery ( -→ m * ,γ * ) and wins the experiment IA-EU-CMA,i f 1. The forgery is valid as

-→ m * is a subset of previously queried or some combination of previously queried batch messages: ∃I ⊆ {1,...,q s }: -→ m * ⊆|| k∈I -→ m k , 3. Batch query -→ m * has not been queried previously as -→ m * ⊆{ -→ m j } q s j =1 . This implies one of the two conditions: (i) At least one item m * ⊆ -→ m * has never been queried to B , or (ii) the AE experiment wining conditions 2-3 hold as described in Definition 4. ASig is (t, q s , )-IA-EU-CMA-secure, if no A in time t making at most q s queries has an advantage at least with probability .

In this section, we present our proposed schemes. We first describe the SCRAdigital signature framework. We then provide several instantiations of the generic SCRA, each offering a unique performance benefit compared to the others.

SCRA can transform any aggregate signature into a signerefficient signature scheme, whose signing operation is as fast as just the aggregation (i.e., simple modular addition or multiplication) of a small set of pre-computed signatures. SCRA has several advantages over the state-of-the-art signatures: (i) SCRA is a magnitude(s) of times more efficient with respect to signature generation than standard signatures (e.g., RSA [35], ECDSA [3], BGLS [7]). (ii) Unlike messageformatted signature schemes [41], SCRA does not require any pre-defined message formats. (iii) Unlike offline-online signatures [31], [37], [41], SCRA does not require linearsized token storage. (iv) SCRA offers compact signature and public key sizes, and therefore is more scalable than one-time signatures (e.g., [34]).

The detailed description of SCRA is given in Algorithm 1. We further elaborate as follows:

Let (sk , PK ) ← ASig.Kg(1 κ ) be a ASig key pair and H : {0, 1} * →{ 0, 1} d be an ideal hash function (i.e., H behaves as a Random Oracle (RO) [4]), where d-bit denotes the output length of the cryptographic hash function.

We apply a divide-andconquer strategy over the hash output H :{ 0, 1} * →{ 0, 1} d . That is, a d-bit hash output can be interpreted as integers ( j 1 ,..., j L ), where each j i is a b-bit integer such that b • L = d. We then compute a signature on each b-bit integer j with its corresponding index i as mi, j ← i || j ||P, γ i, j ← ASig.Sig( mi, j , sk ), i = 1,...,L, j = 0,...,2 b -1, where P is a random padding. The index (i, j ) will enable the signer to select the corresponding pre-computed signature from the table in the online phase for a given message, and therefore ensure the correctness of the scheme. Moreover, the index i enforces the order of the bit chunks in the online phase.

The random padding P is added to ensure that, for practical applications, the input of hash function remains larger than d as required.

We construct a pre-computed sub-message/signature table

, which supports very efficient signature generation. is constant-size (e.g., unlike [9], [31]) and imposes no structure/length constraints on the online messages to be signed (e.g., unlike [41]).

2) Signature Generation: Given m ∈{ 0, 1}

An ideal aggregate signature to instantiate SCRA must achieve very efficient signature aggregation and IA-EU-CMA security. We identified three signatures to instantiate SCRA: Condensed-RSA (C-RSA) [30] based on RSA [35], BGLS [7] based on pairing and aggregate-NTRU signatures [15], [36] based on NTRU [13]. We summarize important operations of our SCRA instantiations in Algorithms 2-5. For the sake of brevity, we only give the dominant signature operations that are performed in each algorithm. The rest of the SCRA operations are as described in Algorithm 1 and are not repeated. Moreover, we only give the private/public keys of each instantiation without describing key generation steps and parameters in detail. We refer interested readers to C-RSA [30], BGLS [7] and NTRU [15], [36] for the details.

SCRA-C-RSA is based on Condensed-RSA (C-RSA) [30] and therefore it obtains the highest computational efficiency benefit from SCRA among all instantiations. That is, C-RSA is by default a verifier efficient signature scheme but its signature generation is expensive (i.e., an exponentiation under a large modulo). Since the SCRA significantly reduces the signing cost, SCRA-C-RSA achieves the lowest end-to-end delay among all instantiations with a moderate signature size (e.g., 2KB RSA signature size). SCRA-C-RSA is described in Algorithm 2.

SCRA-BGLS is based the BGLS signatures [7], and therefore has the smallest signature/key size among all instantiations (e.g., 320 bits). The SCRA strategy also significantly increases the signature efficiency of BGLS. However, since BGLS has an expensive signature verification due to cryptographic pairing operations, SCRA-BGLS has a larger end-toend cryptographic delay compared to our other instantiations. SCRA-BGLS is described in Algorithm 3.

SCRA-NTRU is based on NTRU aggregate signature [15]. Note that SCRA-NTRU achieves the highest signing efficiency among all instantiations (it is even more efficient than SCRA-C-RSA at the signer side). It also has a low end-toend delay, which is comparable to SCRA-C-RSA but slightly 3: mi, j ← i || j ||P, γ i, j ← ASig.Sig( mi, j , sk ), i = 1,...,L, j = 0,...,2 b -1. 4: sk ← (sk , ) and PK ← (PK , P),w h e r e ← ( mi, j ,γ i, j ) for i = 1,...,L, j = 0,...,2 b -1. σ ← SCRA.Sig(m, sk): Given a message m ∈{0, 1} * , compute its signature as follows:

1: (M * 1 ,...,M * L ) ← H (m||r ),w h e r er ←{0, 1} κ and

i ||P, and fetch corresponding signature γ i of m i from table , i = 1,...,L. 3: s ← ASig.Agg(γ 1 ,...,γ L ) and σ = (r, s). {0, 1}←SCRA.Ver (m,σ,PK):G i v e nm ∈{0, 1} * , verify its signature σ under PK as follows:

Algorithm 2 SCRA Instantiation With Condensed-RSA [30]: SCRA-C-RSA (sk, PK) ← SCRA-C-RSA.Kg(1 κ ):G i v e n1 κ , generate C-RSA and SCRA-C-RSA parameters as follows: 1: Randomly generate two large primes ( p, q) and computes n = p • q. The public and secret exponents (e, d) ∈ Z * n satisfies e • d ≡ 1modφ(n),w h e r eφ(n) = ( p -1)(q -1).S e tsk ← (n, d) and PK ← (n, e).L e tH be a full domain hash function (e.g., [5]) defined as

(please refer to [7] for details). Finally, H :{0, 1} * → G 1 is a Full Domain Hash [19] modeled as RO [4].

1: Set sk = x and PK = g x 2 ∈ G 2 [7], where

, return 1, else return 0. Note: We implement SCRA-BGLS on an elliptic curve E, in which modular exponentiation and multiplication correspond point scalar multiplication and point addition on E [17], respectively. less efficient, since NTRU aggregate signature verification algorithm in [15] is less efficient than that of SCRA-NTRU and a low end-to-end delay but with a larger signature size. SCRA-NTRUPASS is based on the PASS [18] signature scheme. It provides similar performance to SCRA-NTRUin terms of both latency and storage but the lattice based scheme is more practical to use. This means that SCRA-NTRUPASS is secure for usage even with smaller parameters as it is based on the partial Fourier recovery problem rather than the approximate CVP problem for SCRA-NTRU.

We now present our security analysis for SCRA schemes. Theorem 1: SCRA is (t, q s , )-EU-CMA secure, if the underlying ASig is (t , q s , )-IA-EU-CMA secure, where t = O(t)+(ASGN +RO(.))•q s .RO(.) and ASGN denote the cost of Algorithm 4 SCRA Instantiation With Lattice-Based Sequential Aggregate Signatures [15]: SCRA-NTRU (sk, PK) ← SCRA-NTRU.Kg(1 κ ): We use lattice-based sequential aggregate signature schemes AggSign and AggVerify as described in [15], that is secure in the random oracle model [4]. Let AggSign and AggVerify are functions as described in [15]. 1: Set f A : B n → R n as a family of preimage-sampleable trapdoor function NTRUSign [27], where

, T is the trapdoor and B n is the domain of f A . ω i represents the list of i partial aggregate signatures. 2: Compute γ i, j ← NT RUSign(sk, H ( mi, j )), i = 1,...L, j = 0,...,2 b -1, set ( , sk, PK) as in Algorithm 1.

1: σ ← SCRA-NTRU.Sig(m, sk): Execute Algorithm 1 SCRA.Sig Step 1-2, and obtain γ i of m i from , i = 1,...,L.

Compute s ← AggSign(T,γ i ,ω i-1 ) for i = 1,...,L.S e tσ as in Algorithm 1 SCRA.Sig Step 3. [15], that is secure in the random oracle model [4]. Let AggSign and AggVerify are functions as described in [15]. 1: Set f A : B n → R n as a family of preimage-sampleable trapdoor function PASSSign [18], where sk is a polynomial L ∞ norm equal to 1(coefficients are chosen independently from the set [-1, 0, 1]), PK ← A = F • sk , T is the trapdoor and B n is the domain of f A . ω i represents the list of i partial aggregate signatures. 2: Compute γ i, j ← PASSSign(sk, H ( mi, j )), i = 1,...L, j = 0,...,2 b -1, set ( , sk, PK) as in Algorithm 1.

1: σ ← SCRA-NTRUPASS.Sig(m, sk): Execute Algorithm 1 SCRA.Sig Step 1-2, and obtain γ i of m i from , i = 1,...,L.

Compute s ← AggSign(T,γ i ,ω i-1 ) for i = 1,...,L.S e tω as in Algorithm 1 SCRA.Sig Step 3. Proof: Suppose that A breaks (t, q s , )-EU-CMA secure SCRA. We construct a simulator F , which breaks (t , q s , )-IA-EU-CMA secure ASig by using A as a subroutine with the experiment below: Setup: F is provided with two oracles as below:

1. A random oracle h ← RO(m), which returns h $ ←{0, 1} d if m ∈{ 0, 1} * has not been queried before, else it returns the same answer h for the given m.T h a ti s ,t h e cryptographic hash function H in SCRA is modeled as a random oracle. Queries: A queries F on m j ∈{ 0, 1} * for j = 1,...,q s . For each query j , F performs the following operations:

1. F queries RO(.) on (m j ||r j ), and receives an answer as -→ M * is comprised of L data items and therefore it cannot be a trivial combination of previously asked batch queries. Hence, the IA-EU-CMA-secure ASig is broken.

If the above conditions hold, F wins in the IA-EU-CMA experiment against ASig.O t h e r w i s e ,F aborts. The probability that F wins in the IA-EU-CMA experiment is identical to that of A winning in the EU-CMA experiment. Note that H is modeled as a random oracle, and therefore the probability that H is not target collision-resilient or subset-resilient [34] is a negligible probability in terms of κ (i.e., 1/2 d/2 ). For each query of A , F performs a query to RO(.) and another query to O. Hence, the execution time of F is that of A plus (ASGN + RO(.)) • q s . We now prove that the SCRA-C-RSA and SCRA-BGLS schemes are secure in Theorem 2 and Theorem 3, respectively. Remark that, for the sake of brevity, we refer to the generic proof in Theorem 1 for common steps, and only emphasize the scheme-specific steps in these theorems.

Theorem 2: SCRA-C-RSA is (t, q s , )-EU-CMA secure, if the underlying C-RSA is (t , q s , )-IA-EU-CMA secure, where

Proof: Suppose that A breaks (t, q s , )-EU-CMA secure SCRA. We construct a simulator F , which breaks (t , q s , )-IA-EU-CMA secure C-RSA by using A as a subroutine as follows: Setup: F is given RO(.) and O sk as in Theorem 1 Setup Phase. By Algorithm 2, (sk = n, d , PK = n, e ) and hash function used by O is H :{ 0, 1} * → Z n that behaves as a RO. F gives PK ← (PK , P) to A ,w h e r eP $ ←{ 0, 1} d as in Algorithm 2. Queries: A queries F on m j ∈{ 0, 1} * for j = 1,...,q s . For each query j , F queries O on (1|| m j,1 ||P,...,L|| m j,L ||P) ← RO(m j ||r j ) as in Theorem 1 Query Phase and gets s j ← L i=1 H (i || m j,i ||P) d mod n as in Algorithm 2. F returns σ j = (s j , r j ). Forgery: A outputs a forgery (m * ,σ * = s * , r * ) and checks the EU-CMA experiment winning conditions (i)-(ii) as in Theorem 1 Forgery Phase. If they hold, then F returns a C-RSA forgery for IA-EU-CMA experiment as ( -→ M * , s * ) as in Theorem 1 Forgery Phase and proceeds as follows:

2) Non-triviality: F checks if one these conditions hold:

i) At least one data item ( j || m * j ||P) ∈ -→ M * has never been queried to O.T h i si m p l i e st h a tIA-EU-CMAsecure C-RSA is broken, since by the validity condition, there is a signature as s = H ( j || m * j ||P) d mod n, which was not obtained from O. ii) The signature extraction occurs as defined in Theorem 1 Non-triviality condition (b). That is, individual signatures {s * j = H ( j || m * j ||P) d mod n} L j =1 have never been individually queried to O, but all were part of a batch query k ∈ I -→ M k . This implies IA-EU-CMA-secure C-RSA is broken by the signature extraction argument as in [30] and [42]) (see Section II-C). The non-triviality holds as in Theorem 1.

The success probability is as in Theorem 1 and the probability that H produces a collision is 1/2 |n|/2 . For each query of A , F performs a query to RO(.) and O, which requires a H computation, followed by an exponentiation/multiplication under n for each item in (1|| m j,1 ||P,...,L|| m j,L ||P). Hence, the execution time of F is that of A plus [RO(.)+L •(Expn+

Proof: Suppose that A breaks (t, q s , )-EU-CMA secure SCRA. We construct a simulator F , which breaks (t , q s , )-IA-EU-CMA secure BGLS by using A as a subroutine with the experiment below: Setup: F is given RO(.) and O sk as in Theorem 1 Setup Phase. By Algorithm 3, (sk = x, PK = g x 2 ∈ G 2 ) and H : {0, 1} * → G 1 is a RO. F gives PK ← (PK , P) to A as in Algorithm 3. Queries: A queries F on m j ∈{ 0, 1} * for j = 1,...,q s . For each query j , F queries O on (1|| m j,1 ||P,...,L|| m j,L ||P) ← RO(m j ||r j ) as in Theorem 1 Query Phase and gets s j ← L i=1 H ( mi, j ) x ∈ G 1 as in Algorithm 3. F returns σ j = (s j , r j ). Forgery: A outputs a forgery (m * ,σ * = s * , r * ) and checks EU-CMA experiment winning conditions (i)-(ii) as in Theorem 1 Forgery Phase. If they hold then F returns a BGLS forgery for IA-EU-CMA experiment as ( -→ M * , s * ) as in Theorem 1 Forgery Phase and proceed as follows:

holds. Therefore, BGLS forgery is valid.

2) Non-triviality: F checks if one of these conditions hold.

(i) At least one data item ( j || m * j ||P) ∈ -→ M * has never been queried to O.T ha t i s ,IA-EU-CMA-secure BGLS is broken, since by validity condition, there is a signature as e(s , g 2 ) = e(H ( j || m * j ||P), g x 2 ∈ G 2 ), which was not obtained from O. (ii) The signature extraction occurs as defined in Theorem 1 Non-triviality condition (b). That is, individual signatures e(s * j , g 2 ) = e(H ( j || m * j ||P), g x 2 ∈ G 2 ), j = 1,...,L have never been individually queried to O, but all were part of a batch query k ∈ I -→ M k . This implies IA-EU-CMA-secure BGLS is broken by the signature extraction argument as in [10] (see Section II-C). The non-triviality of signature extraction holds as in Theorem 1. The success probability analysis is as in Theorem 1 and the probability that H produces a collision is 1/2 |Gfoot_0 |/2 . For each query of A , F performs a query to RO(.) and an another query to O, which requires a H computation, followed by an exponentiation and multiplication in G 1 for each item in (1|| m j,1 ||P,...,L|| m j,L ||P). Hence, the execution time of

Remark 1: The formal proof of SCRA-NTRUand SCRA-NTRUPASS follow a similar logic and therefore will not be repeated here. At the same time, we note that despite the existence of an A-EU-CMA analysis, IA-EU-CMA proof and analysis for signature extraction argument are not currently available for NTRU signatures. Hence, a full formal reduction requires this gap to be filled first, which is out of the scope of this paper.

In this section, we present the performance results of our experiments. We first compare the results of the SCRA with the state-of-the-art algorithms on a modern powerful CPU. We then provide results for the GPU implementations of SCRA-C-RSA and SCRA-NTRU as compared to their CPU counterparts. For the GPU, we used an Nvidia Tesla K40c card, which is comprised of 2880 computing cores with 12GB of GDDR5 device memory and 288GB/sec memory bandwidth. Our base system is equipped with an Intel Core i7-6700K 4.0GHz Quad-Core Processor and 16GB DDR4 2400 MT/s. This infrastructure represents a datacenter setting. We also implemented SCRA on a System-on-Chip (SoC). We used an Nvidia Tegra K1 SoC, which has a 4-Plus-1 quadcore ARM Cortex A15 CPU with clock rate of 2.3 Ghz and an embedded GPU with 192 computing cores. Such SoCs represent smaller scale systems that are widely used in IoT deployments. We open sourced the source code for the research and academic community to use and evaluate. 1 We summarize the results in Table I. Table I also provides the implementation details, parameters and key/table sizes. Table I shows the clear superiority of SCRA in terms of signature generation efficiency and end-to-end cryptographic delay (i.e., the sum of signature generation and verification times) using a powerful CPU. That is, the signature generation of SCRA instantiations are 24, 18 and 516 times faster than their non-SCRA counterparts for RSA, BGLS, and NTRU, respectively. This indicates that SCRA is an ideal choice for a very high-throughput signature generation, especially for resource-limited devices in IoT deployments. Similarly, SCRA-C-RSA and SCRA-NTRU offer 18 and 7 times lower end-to-end crypto delay compared to RSA and NTRU, respectively, making them ideal choices for time-critical authentication. In addition to their computational efficiency, the SCRA schemes are also compact, since the signature and public key sizes remain the same with their base signature scheme (the transmission of |r |=κ is negligible). By comparing to each other, SCRA-C-RSA achieves the lowest end-to-end delay with a moderate signature size (e.g., 256 bytes), while SCRA-BGLS offers the smallest signature (20 bytes) but the highest end-to-end delay. SCRA-NTRU has the lowest signing delay (0.0018 msec), low end-to-end delay but with large signatures (e.g., 1587 bytes). Note that all SCRA schemes require storing a pre-computed table ,w h i c h introduces a constant-size extra storage overhead at the signer side e.g., 160 KB, 2 MB and 12.33 MB for SCRA-BGLS, SCRA-C-RSA and SCRA-NTRU respectively. This signer storage is plausible even for some embedded devices (e.g., Raspberry PI 2 [1]), and negligible for vehicular networks. Moreover, recall that, unlike offline-online signatures, the signer overhead of SCRA is constant and it does not require to regenerate tokens.

The offline stages of the algorithms take fairly minimal times of 2.45, 8.65 and 12.83 seconds for SCRA-BGLS, SCRA-C-RSA and SCRA-NTRU, respectively. The offline stage will only be required to execute once during the system deployment.

We have a trade-off between the space taken to store the signatures and the execution time of the signing and the verification stages. As described in 1, an d-bit hash output can be interpreted as integers ( j 1 ,..., j L ), where each j i is a b-bit integer such that b • L = d. The total number of signatures that need to be calculated and stored in the offline stage of an algorithm is thus L • 2 b . The total storage cost is thus L • 2 b • S where S is the size of one signature. This also implies that the number of aggregations to be performed during the online phase increases linearly with L.T a b l eI I provides for the SHA-256 hashing scheme various values of (L, b) parameters and corresponding size of the signature table for each SCRA instantiation.

One may observe that the smallest storage overhead can be attained with (L = 256, b = 1), wherein we store a signature for every bit in the hash output domain. However, this requires L = 256 signature aggregations in the online signature generation phase (e.g., 256 modular multiplications for SCRA-C-RSA), which may not be computationally efficient. Another end of the trade-off is (L = 16, b = 16), wherein only L = 16 online aggregations are required during the online phase. However, this requires substantially larger table sizes, which may be suitable for some real-life applications. We observed that (L = 32, b = 8) offers a highly favorable overall performance/storage performance, as shown in Table I and Table II. The size of the pre-computed tables for SCRA-BGLS, SCRA-C-RSA and SCRA-NTRUis 160 KB, 2 MB and 12.33 MB, respectively, for signature-sizes of 20, 256 and 1578 bytes, respectively. This will require 32 signatures to be aggregated in the online-signing phase of each SCRA scheme.

To accelerate SCRA, we leveraged the parallel processing and optimization capabilities of GPUs both on server and embedded in the SoCs. We have introduced several optimizations to parallelize the individual steps of SCRA algorithms. We used optimizations specific to the architecture of the GPU to harness the vast amount of available lightweight cores [11].

-SCRA RSA -Server: In the offline signature stage, for 8192 messages, we achieve x1.3 times more throughput with our GPU optimizations compared to the CPU only implementations. In the online signature stage, we achieve significantly high throughput gains, which can reach up to x5.3 times. In the verify stage, the gain is around x4.2 times. These results are reported in Figures 2 and3. In terms of execution time, the GPU can process a message in 0.367, 0.022, 0.031 milliseconds for the offline, online and verify stages of the algorithm, respectively. This is approximately x1.31, x5, x4 times faster than the corresponding CPU execution times. The GPU gives a worse performance than the CPU if a very small number of messages are processed. This is mainly due to the low clock speeds of the GPU cores as compared to the CPU and also due to the time to copy the data from the CPU memory to the GPU memory and vice-versa. Our experiments show that the online signature and signature verification stages are executed faster in the GPU than in the CPU for message batches greater than 128 and 256, respectively. -SCRA RSA -SoC: In the offline signature stage, for 8192 messages, we achieve x3.2 times higher throughput with our GPU optimizations compared to CPU only implementations. In the online signature stage, we achieve high throughput gains up to x5.2 times. In the verify stage, the gain is around x4.8 times. These results are reported in Figures 4 and5. Below we describe the techniques we adopted to achieve some of the performance speedups shown by above experiments.

1) Chinese Remainder Theorem (CRT): We leverage CRT [28] to accelerate SCRA on GPUs. We split a k-bit signature σ into two k/2 bit signatures σ 1 and σ 2 . σ 1 = M d mod p-1 mod p,σ 2 = M d mod q-1 mod q,w h e r eM is the message and ( p, q) are the primes used. Then, we use the mixed radix conversion algorithm [22] to combine the two parts and recover the signature σ as σ = σ 2 +[(σ 1σ 2 ).(q -1 mod p)].q These two parts are processed on separate threads in the GPU, which is significantly faster than the k-bit modular exponentiation.

2) Montgomery Multiplication: The modular multiplication is inefficient in the GPUs since it requires a trial division to determine the result and is not parallelizable. The Montgomery multiplication is suitable for implementation in a GPU, since it does not require a trial division and can be implemented in parallel on separate words of the message. That is, given a • b mod n, we first find two integers r -1 and n using the Extended Euclidean Algorithm such that rr -1nn = 1. We then transform a = ar mod n and b = br mod n. Later, we compute a • b mod n by using Montgomery reduction [28].

3) Batch Processing: The crypto operations for multiple messages are performed concurrently in the GPU. This requires that a batch of messages be passed to the GPU, instead of a single message.

To optimize the throughput on the GPU, each message component is divided into words of size 32/64 bits, depending on the GPU capabilities. Each operation being run on a single thread is run over words rather than over entire message components. We use standard multi-precision algorithms [12] to represent and perform operations between large integers.

Warps are set of threads (generally 32) that are considered as one single execution unit inside a CUDA block. To gain maximum throughput from the GPU, it is necessary to attain the maximum number of active warps per streaming multiprocessor which is 64 in our case. We achieve this by adjusting the number of threads per block to the optimal value. 6) Memory Latency vs GPU Occupancy: T h es i z eo ft h e shared memory can limit the number of active warps on the GPU at a particular point in time by reducing the occupancy of the Streaming Multiprocessors (SM). The other limiting factor in the performance output is the number of reads and writes on the global memory on the device. We identified a balance between the SM occupancy and the global memory read/write latency by testing various permutations of memory allocations among the shared and global memory.

We scan the bits of the exponent from the least significant bit to the most significant bit. At each step, we compute a zero window or a non-zero window [23]. With the binary squareand-multiply method, we can process these windows and reduce the number of modular multiplications, making the exponentiation algorithm faster.

-SCRA NTRU -Server: In the online signature stage, for 4096 messages, we achieve x0.79 times more throughput with our GPU optimizations compared to CPU only implementations. In the verify signature stage and offline stage, we achieve high throughput gains up to x6.5 and x30 times respectively. These results are reported in Figures 6 and7, respectively. The cryptographic operations for multiple messages are performed concurrently on the GPU. This requires that a batch of messages be passed to the GPU, instead of a single message for the signing and verification stage. We do not employ the GPU for the online stage of SCRA-NTRU because the signature aggregation technique is computationally expensive and deploying it on a GPU core provides little performance benefit. Due to these reasons, the CPU performs better than the GPU during the online stage of the protocol. -SCRA NTRU -SoC: In the online signature stage, for 1024 messages, we achieve x0.81 times more throughput with our GPU optimizations compared to CPU only implementations. In the verify sign stage and offline stage, we achieve high throughput gains upto x6.65 and x17.7 times respectively. These results are reported in Figures 8 and9 respectively. We summarize below the optimizations that have resulted in the performance gains shown by the previous experiments.

1) Batch Processing: Message components are processed in batches as in Section VI-A. As mentioned before, we do not use the GPU for the online stage of SCRA-NTRU.

2) Convolution Operations: The convolution operations in the NTRU in the signing and verification phase are accelerated by employing GPUs. The convolution operation between two n bit polynomials is divided into n cores for each operation where each core is responsible for calculating one bit of the resulting polynomial.

3) Fourier Transformations: Implementing the Fourier transformation on GPUs further accelerates the signing, verification and offline stages. Due to the use of faster convolution and Fourier transformation operations on GPUs, the verify stage of the protocol on GPUs is significantly faster than on CPUs.

In this paper, we developed a new series of delay-aware digital signatures for time-critical applications, which we refer to as Structure-Free Compact Authentication (SCRA). SCRA can transform any secure aggregate signature into a signer efficient signature via a novel constant-size pre-computation strategy. We proposed several instantiations of SCRA schemes based on Condensed-RSA, BGLS, and NTRU signatures, each offering a unique computation time, key and signature size trade-offs. Our implementations and performance comparison with the existing alternatives show that the SCRA schemes achieve significantly faster signature generation and lower end-toend delay. We also formally proved that SCRA schemes are secure (in ROM). Finally, we pushed the performance of SCRA schemes to their edge by fully implementing them on server-grade GPUs and SoCs, which indicated significant performance gains. All these properties make the SCRA schemes a suitable alternative for delay-aware authentication for timecritical applications.