LRCoin: Leakage-resilient Cryptocurrency Based on Bitcoin for Data Trading in IoT

BY KEYHUNTER 05.03.2025
LRCoin: Leakage-resilient Cryptocurrency Based on Bitcoin for Data Trading in IoT

Currently, the number of Internet of Thing (IoT) devices making up the IoT is more than 11 billion and this number has been continuously increasing. The prevalence of these devices leads to an emerging IoT business model called Device-as-a-service (DaaS), which enables sensor devices to collect data disseminated to all interested devices. The devices sharing data with other devices could receive some financial reward such as Bitcoin. However, side-channel attacks, which aim to exploit some information leaked from the IoT devices during data trade execution, are possible since most of the IoT devices are vulnerable to be hacked or compromised. Thus, it is challenging to securely realize data trading in IoT environment due to the information leakage such as leaking the private key for signing a Bitcoin transaction in Bitcoin system. In this paper, we propose LRCoin, a kind of leakage-resilient cryptocurrency based on bitcoin in which the signature algorithm used for authenticating bitcoin transactions is leakage-resilient. LRCoin is suitable for the scenarios where information leakage is inevitable such as IoT applications. Our core contribution is proposing an efficient bilinear-based continual-leakage-resilient ECDSA signature. We prove the proposed signature algorithm is unforgeable against adaptively chosen messages attack in the generic bilinear group model under the continual leakage setting. Both the theoretical analysis and the implementation demonstrate the practicability of the proposed scheme.

Index Terms—Blockchain, Leakage Resilient Signature, Data Trading, The Generic Bilinear Group Model.

1 INTRODUCTION

The Internet of Thing (IoT) has emerged as an area of incredible potential and impact. According to Gartner Inc. [1], more than 11 billion IoT devices have been connected to the IoT network in 2018. The number of these devices is continuously increasing and is expected to be 20 billion by 2020. The application of IoT pervades everywhere from smart home, smart cities, manufacturing, commerce, education to supply chain, logistics and almost anything we can imagine [2] – [7]. The opportunities presented by IoT raise an emerging IoT business model pattern Device-as-a-service (DaaS). We can employ the sensor devices to collect data which would be vended to all interested users or devices. For example, the owner of personal weather station not only uses the IoT devices to control his household heating, but share the data to neighborhood for obtaining financial incentives.

However, most of these IoT devices are easy to be hacked or compromised by various cyber attacks such as a side channel attack. Due to this attack, the secret key in IoT devices might be leaked and then adversaries could successfully forge valid signatures to transfer bitcoins from those devices to other accounts. Actually, ten thefts of over 10,000 BTC each and more than 34 crimes of stealing accidents over 1000 BTC each since 2011 happened [8]. It was reported by Kaspersky labs that about one million infections per month of malware designed to search for secret keys and steal bitcoins were detected [8]. Dubbed Satori IoT Botnet exploits zero-day to zombify Huawei Routers and was found infecting more than 200,000 IP addresses in just 12 hours [9]. Cisco’s Talos cyber intelligence units discovered an advanced piece of IoT botnet malware, dubbed VPNFilter, that was designed with versatile capabilities to gather intelligence, interfere with internet communications, as well as conduct destructive cyber attack operations. The malware infected over 500,000 devices in at least 54 countries, most of which are small and home offices routers and internet-connected storage devices from Linksys, MikroTik, NETGEAR, and TP-Link. Some network-attached storage devices were targeted by the malware as well [10]. To sum up, the security of IoT devices was degraded due to a variety of factors, and the increasing IoT applications based on Bitcoin leads to an urgent need for more secure bitcoin transactions [11].

Blockchain was firstly introduced by Satoshi Nakamoto in Bitcoin white paper [12]. A blockchain is a hash-based data structure. Each block has a block header, a hash pointer to the previous block and a Merkle hash tree (MHT) that digests of transactions in the block. A blockchain makes use of two well-known cryptographic techniques, namely digital signatures and hash functions. A digital signature is employed to provide the integrity, non-repudiation and authentication of bitcoin transactions. A hash function is used to compute a hash value of the previous block and make the blocks as a chain. The decentralization of blockchain benefits IoT in many applications such as access control to data [13], data trading [14], and key management [15] – [18] in IoT etc.

Related Work. Noyen et al. [14] discussed how sensing-as-a-service can benefit from Bitcoin and described the process of exchanging data for cash via Bitcoin. Zhou et al. [20] presented distributed data vending on blockchain by combining data embedding and similarity learning. This approach brings the trade-off between the effectiveness of data retrieval and leakage risk from indexing the data. Leiba et al. [21] introduced a fair protocol for data trading based on Bitcoin script language and double ECDSA. In practically, the script language operator was disabled for Bitcoin transaction. Kopp et al. [22] presented KopperCoin, a distributed file storage system with financial incentives. Later, Kopp et al. proposed privacy-preserving distributed file storage system with financial incentives [23], which takes advantages of ring signatures and one-time addresses to realize a privacy-preserving payment mechanism. However, these solutions provide no confidentiality and reliability of data in the context of side channel attacks.

Our Contributions. Blockchain is subject to side-channel attacks due to the openness of its deployment. As a consequence, information leakage especially secret key leakage is possible in various IoT applications. In this paper, we propose a new kind of cryptocurrency named LRCoin which is secure even part of the signing key of a user is exposed. LRCoin can be used in the applications where secret key leakage is inevitable such as the payment of data trading in IoT. We propose a concrete construction of an efficient bilinear pairing-based continual leakage-resilient ECDSA signature algorithm as the building block for signing transactions in LRCoin. The proposed signature algorithm is proven unforgeable against adaptively chosen messages attack in the presence of continual leakage setting. The security proof is conducted in the generic bilinear group model to bypass the impossible results that achieving continual leakage-resilience cryptographic protocols whose secret key is uniquely determined by the corresponding public key. We also implement the proposed signature algorithm on laptops and phones respectively, which demonstrates that its efficiency is comparable with that of the original ECDSA signature.

2 Data Trading Model in IoT

Data trading [24], [25] is the exchange of bitcoin for data collected by IoT devices between data seller and data buyer. The market is to establish a platform for data seller to use blockchains as infrastructures to sell the data. The data buyer can retrieve data from blockchain and complement the payment. In this section, we introduce the data trading model in IoT and the key components. The participants involved in data trading model in IoT include Data Sellers, Trade Market (Blockchain Network, Storage Server), Data Buyers, as shown in Fig. 1.

Data seller: A data seller is a user who owns the data and wants to sell the data.

Trade market: The trade market is composed of blockchain network and storage server. The blockchain network provides data sellers and data buyers a trading platform. The storage server provides data sellers and data buyers an intermediate facility to upload data and download data respectively.

Data buyer: A data buyer submits Purchase Transactions to the trade market to match the corresponding Sale Transactions. A data buyer generates a payment transaction for data she wants to buy and downloads the data from the storage server.

Sale Transaction: A data seller constructs a Sale Transaction with the topic that he has some data to sell and then broadcasts the transaction to the trade market and uploads the data to the storage server. A sale transaction consists of the topic of the data, the intended price of selling the data etc.

Purchase Transaction: A data buyer constructs a purchase transaction with the topic of the data that she wants to buy and then broadcasts the transaction to data market. A purchase transaction consists of the topic of the data, the intended price of buying the data etc.

3 Preliminaries

In this section, we recall some preliminaries used in this paper, including bilinear maps, leakage-resilient models and the security model for continual leakage-resilient digital signatures.

3.1 Bilinear Maps

Let $G = \langle g \rangle$, $G_T = \langle g_T \rangle$ be two multiplicative cyclic groups of prime order $p$ with $k$ bits. A map [26] $e : G \times G \rightarrow G_T$ is called a bilinear map if the follow conditions holds.

Bilinearity. For all $u, v \in G$ and $a, b \in \mathbb{Z}_p$, $e(u^a, v^b) = e(u, v)^{ab}$.

Non-Degeneracy. $e(g, g) \neq 1_{G_T}$, the identity element of $G_T$.

Efficient Computation. $e(u, v)$ can be computed in polynomial time.

3.2 Stateful Signatures

In order to achieve continual leakage resilience when a significant bits of secret key are leaked during each round of computations, it is necessary to let the secret key stateful. That is, the secret key must be refreshed after each round of signature computation. Otherwise, the secret key would eventually be completely exposed. Galindo and Vivek [27] suggested to split the secret key into two parts and reserve them on two distinct parts of a device memory. Specifically, they divide a signature computation into two steps. In each step, the memory in use is divided into two parts called the active part and the passive part. The active part of the memory is the memory being accessed by the computation while other parts of the memory are the passive part. It is assumed that information leakage is only possible in the active part at any specified time.

There are four polynomial-time algorithms namely KeyGen, Sign1, Sign2, Verify in a stateful signature scheme. Different from the key generation of traditional digital signatures which generates a single secret key, the key generation algorithm in a stateful signature outputs two initial secret states ((S_0, S_0′)). The two signing algorithms Sign1, Sign2 are executed sequentially to generate a signature on a message (m). A bit more specific, the (i)-th round of the signature computation is performed as follows.

[ \text{Sign}1(S{i-1}, m_i, r_i) \rightarrow (S_i, w_i), ] [ \text{Sign}2(S{i-1}’, w_i, r_i’) \rightarrow (S_i’, \sigma_i), ]

where (r_i) and (r_i’) denote the random values used in Sign1 and Sign2 respectively, (w_i) denotes the state information delivered to Sign2 by Sign1. Then the secret state is updated from ((S_{i-1}, S_{i-1}’)) to ((S_i, S_i’)). The signature of (m_i) is (\sigma_i).

The formal definition of a stateful signature (\Pi = (\text{KeyGen}, \text{Sign1}, \text{Sign2}, \text{Verify})) is as follows.

  • KeyGen((k)): On input a security parameter (k), it outputs a key pair ((pk, (S_0, S_0′))) where (pk) is public key and ((S_0, S_0′)) are two shares of the secret key.
  • Sign1((S_{i-1}, m_i)): On input the first part of the ((i-1))-th secret key (S_{i-1}) and message (m_i), it selects a randomness (r_i) and updates (S_{i-1}) into (S_i) and computes the state information (w_i), which would be passed onto Sign2.
  • Sign2((S_{i-1}’, w_i)): On input the second part of the ((i-1))-th secret key (S_{i-1}’) and state information (w_i), it chooses a randomness (r_i’) and updates (S_{i-1}’) into (S_i’) and computes the (i)-th signature (\sigma_i).
  • Verify((pk, \sigma_i, m_i)): On input the public key (pk), signature (\sigma_i) and message (m_i), it outputs a bit (b = 1) meaning valid, or (b = 0) meaning invalid.

3.3 Existential Unforgeability with Leakage

A cryptographic primitive is called leakage-resilient if it is secure even the adversary additionally obtains some side-channel information, that is leakage. A variety of leakage models ([31, 32, 33]) have been proposed to model side-channel attacks and formalize the security for diverse cryptographic primitives. In 2004, Miclai and Reyzin ([32]) gave a leakage model namely “only computation leaks information (OCLI)”, saying that only the secret memory which is involved in computation at that time leaks information. And they noted that the leakage amount during each computation is bounded. Otherwise, the adversary continually obtains leakage from many computations, and finally the adversary is able to obtain the full knowledge of the secret key. In 2009, Akavia et al. ([34]) introduced a general leakage model called “bounded-memory leakage model”. In this model, an adversary is allowed to adaptively choose an efficiently computable a leakage function (f) and send it to a leakage oracle. The adversary obtains (f(sk)) from the leakage oracle where (sk) denotes the secret key of the target user. However, the overall output length of all the leakage functions is bounded by a parameter (\lambda), which is smaller than the secret key (sk). But this model does not cover the continuous memory leakage, which could been given rise to due to various side channel attacks. In 2010, Zvika et al. ([29]) and Dodis et al. ([30]) formalized a “continual-memory leakage model”. This model is similar to the OCLI model except that in this model the leakage is assumed from the entire secret memory whether or not the memory is involved in computation.

Galindo and Vivek ([27]) presented an approach to model the leakage in a signature generation by allowing an adversary (A) to access to a leakage oracle (\Omega_{\text{leak}}^{\cdot}). It not only gives (A) signatures of messages choosen by (A) but also allows (A) to obtain leakage from the current signature computation. More precisely, let (\lambda) be the leakage parameter, and (A) is allowed to adaptively select two efficiently computed leakage functions (f_i(\cdot) \rightarrow {0, 1}^\lambda) and (h_i(\cdot) \rightarrow {0, 1}^\lambda) during every round of signature generation. Specifically, the inputs of leakage functions (f_i) and (h_i) are a part of the secret key respectively, and the outputs of leakage are denoted as (\Lambda_i = f_i(\cdot), \Lambda_i’ = h_i(\cdot)). Galindo and Vivek noted that (A) can determine (h_i) after seeing (\Lambda_i). But for simplicity, they only define the leakage model in which (f_i) and (h_i) are specified along with the message (m_i) when they are sent to the leakage oracles.

The property of unforgeability of a stateful signature scheme (\Pi = (\text{KeyGen}, \text{Sign1}, \text{Sign2}, \text{Verify})) with continual leakage is defined by the following game between a challenger (C) and an adversary (A).

  • Setup. The challenger (C) runs the key generation algorithm KeyGen((k)) to obtain a public pair key (pk) and the initial secret key ((S_0, S_0′)). (pk) is given to (A). (C) sets a counter (i = 1) and a set of (\omega = \emptyset) where (i) denotes the (i)-th round of the signature query and (\omega) is the set of messages which have been signed by querying the Sign-Leak oracle below.
  • Sign-Leak Queries. Given with the public parameter (pk) the adversaries (A) can query a Sign-Leak Oracle (A^{\Omega_{\text{leak}}^\cdot_{S_i-1}(m_i, f_i, h_i)}) at most (q) numbers of signatures of messages ((m_1, m_2, …, m_q) \in {0, 1}^*) adaptively chosen by (A) ((i < q)). When (A) queries the Sign-Leak Oracle, If (|f_i| \neq \lambda) or (|h_i| \neq \lambda) the oracle would return ⊥ and then abort. Otherwise the oracle would response (A) with a signature (\sigma_i) by computing

[ \text{Sign}1(S{i-1}, m_i) \rightarrow (S_i, w_i) \quad \text{and} \quad \text{Sign}2(S{i-1}’, w_i) \rightarrow (S_i’, \sigma_i). ]

During each such signature computation, the adversaries (A) could also get some knowledge about the internal secret key from the leakage functions (f_i) and (h_i) functioning by (\Lambda_i = f_i(S_{i-1}, r_i)) and (\Lambda_i’ = h_i(S_{i-1}’, r_i, w_i)). After each such query, the counter (i) is increased to (i + 1) and the messages set is enlarged by (\omega \cup m_i). Eventually the Sign-Leak Oracle returns ((\sigma_i, \Lambda_i, \Lambda_i’)) to the adversary (A).

  • Output. Finally, (A) gives a pair ((m, \sigma)). If there exists (1) (\text{Verify}(pk, m, \sigma) = 1) and (2) (m \not\in \omega) then the experiment returns (b = 1) meaning that (A) has won the game. Otherwise the experiment returns (b = 0) meaning that (A) has failed to forge a signature.

We define (Pr^\cdot_{\text{A}}) as the probability of (A) wins in the above game. The probability (Pr^\cdot_{\text{A}}) is taken over the coin tosses of (A) and KeyGen.

Definition 1. A signature scheme II is ((e, \tau, q))-existentially unforgeable under adaptively chosen message attacks with continual leakage if for all ((e, \tau, q))-adversaries (A) where (\tau) is the most running time of (A) and (Pr[A,{\text{for}}]{\text{t}}) is at least (\epsilon) and (q) is the most number of queries to oracle, the probability (Pr(b = 1)) in the experiment Sign-Leak_{\text{II}}(A, k, \lambda)) is negligible (as a function of the security parameter (k)).

3.4 Generic Bilinear Group Model

The “generic algorithm” was first proposed by Shoup, in which the group elements are encoded as unique binary strings and the special properties of the encodings of the group elements are not exploited. This model was extended to the generic bilinear group ([27]) where a bilinear map is involved.

The specific details about the generic bilinear group model have been formalized by Galindo in ([27]), where representations of bilinear group elements in (G) and (G_T) are given by random bijective maps (\sigma : Z_p \rightarrow \Xi) and (\sigma_T : Z_p \rightarrow \Xi_T). (\Xi) and (\Xi_T) are sets of bit strings respectively. There are oracles (O, O_T, O_e) that can compute the group operations in (G) and (G_T) and the evaluation of the bilinear map (e). These oracles accept the representations in (\Xi) and (\Xi_T) as inputs and generate such representations as outputs, which are defined as follows:

[ O(\sigma(a), \sigma(b)) = \sigma(a + b \mod p) \ O_T(\sigma_T(a), \sigma_T(b)) = \sigma_T(ab \mod p) \ O_e(\sigma(a), \sigma(b)) = \sigma(ab \mod p) ]

The generator (g) of the group (G) satisfies (g = \sigma(1)) and the generator (g_T) of (G_T) satisfies (g_T = e(g, g) = \sigma_T(1)). Since the representation of (g) is public, thus, users can efficiently generate random elements in both (G) and (G_T).

We extend the generic bilinear group model ([27]) slightly to the asymmetric pairing setting denoted as (G_1 \times G_2 \rightarrow G_T) where (G_1 \neq G_2). Representations of group elements in (G_1, G_2) and (G_T) are given by random bijective maps (\sigma_1 : Z_p \rightarrow \Xi_1, \sigma_2 : Z_p \rightarrow \Xi_2) and (\sigma_T : Z_p \rightarrow \Xi_T), respectively. Moreover, the generator (P_1) of (G_1) satisfies (P_1 = \sigma_1(1)), and the generator (P_2) of (G_2) satisfies (P_2 = \sigma_2(1)), and the generator (P_T) of (G_T) satisfies (P_T = e(P_2, P_1) = \sigma_T(1)). The adversary (A) has accesses to these generic group oracles, namely (O_1, O_2, O_T). Let (\tau_1, \tau_2) and (\tau_T) be the number of queries of (A) to group oracles (O_1, O_2) and (O_T). We define the query form of (A) and the response form of generic group oracles as follows. Let the inputs of the (i^{th}) query of (A) to (O_T) be of the form ((X_i, Y_i)), where (X_i) and (Y_i) are representations in (\Xi_T). And let the response of the generic group oracle (O_T) to the (i^{th}) query be the representation (Z_i), such that (Z_i = X_i \times Y_i). For convenience, all the above mentioned representations, including inputs and outputs are denoted as (R_1, R_2, \ldots, R_{3\tau_T}), meaning that ((X_1, Y_1, Z_1, X_2, Y_2, Z_2, \ldots) = (R_1, R_2, R_3, R_4, R_5, R_6, \ldots)). The query form of (A) to (O_1, O_2) and their response form are similar to (O_T), except the response of (O_1) and (O_2) is (Z_i = X_i + Y_i). Three tables (L_T, L_1, L_2) defined below are maintained to reserve these group element representations obtained from (O_1, O_2) and (O_T).

[ L_T = {R_1, R_2, R_3, R_4, R_5, R_6, \ldots R_{3\tau_T} : 1 \leq i \leq \tau_T} \ L_1 = {R_1, R_2, R_3, R_4, R_5, R_6, \ldots R_{3\tau_1} : 1 \leq i \leq \tau_1} \ L_2 = {R_1, R_2, R_3, R_4, R_5, R_6, \ldots R_{3\tau_2} : 1 \leq i \leq \tau_2} ]

Since (A) can also query group oracles with representations not previously appeared in the above tables, called independent representations, we introduce another three tables in order to maintain the consistencies of the representations of the group elements.

[ Q_T = {Q_1, Q_2, Q_3, Q_4, Q_5, Q_6, \ldots Q_i : 1 \leq t \leq 2\tau_T} \ Q_1 = {Q_1, Q_2, Q_3, Q_4, Q_5, Q_6, \ldots Q_i : 1 \leq t \leq 2\tau_1} \ Q_2 = {Q_1, Q_2, Q_3, Q_4, Q_5, Q_6, \ldots Q_i : 1 \leq t \leq 2\tau_2} ]

where (Q_1, Q_2, \ldots, Q_i) are received by generic bilinear group oracles in order. It is clear that if the total query number to oracle (O_T) is (\tau_T), then (t \leq 2\tau_T) because the number of independent inputs is at most twice of the number of queries. The same conclusions apply to oracles (O_1) and (O_2).

Lemma 1. An observer of the interactions between (A) and generic bilinear group oracles can determine, for each representations, a sequence of integers, namely (a_i = (a_{i1}, a_{i2}, \ldots, a_{it})) with the property that (R_i = \sum_{j=1}^{t} a_{ij} Q_j) in group (G_1) and (G_2) or (R_i = \prod_{j=1}^{t} Q_{ij}) in group (G_T). We call (a_i) the combination of (R_i) in generic bilinear group (G_1, G_2) and (G_T).

Brown ([28]) proved this lemma in a single group (G), and it holds naturally in (G_1, G_2) and (G_T). Thus, lemma 1 holds.

If there exist two different combinations (a_j \neq a_k) satisfying (R_j = R_k), we call that a collision appeared in tables (L_1, L_2), and (L_T). When a collision is found in (L_T), the observer can conclude

[u^{a_j – a_k} = 1 \mod p]

Similarly, when a collision appears in (L_1) or (L_2), the observer has

[(a_j – a_k) \cdot u = 0 \mod p]

With these equations, the observer is able to infer some knowledge of the set (u). Let (r_i \in Z_p) be the unique unknown value such that (\sigma_T(r_i) = R_i), then the observer can obtain some information (r_i) where (r_i = a_i \cdot u) in (G_1) and (G_2) or (r_i = u^{a_i}) in (G_T).

Lemma 2 ([28]). Suppose there are at most (m) oracle queries, the probability of a collision occurring in a generic bilinear group for (Z_p) is at most (3^{(n + 1)} / p).

4 Our Construction

4.1 Basic Idea

To make the original ECDSA signature scheme continual-leakage-resilient, we apply the techniques due to Galindo et al. ([27]). That is, instead of managing a single secret key, the secret key is divided into two shares which are stored in different parts of the memory. The signing algorithm is divided into two steps as well. We deal with the continual leakage of the secret key by refreshing the two shares of the secret key after each signature round regularly to keep the internal secret key stateful.

4.2 Detailed construction

The details of the proposed leakage- resilient pairing-based ECDSA signature are as follows, in which $i$ denotes the $i$th round of signing.

Setup($k$): On input a security parameter $k$, this algorithm randomly picks a pairing friendly curve $C$ defined on the finite field $\mathbb{Z}_p$ and outputs the corresponding bilinear pairing generic groups $G_1$, $G_2$, and $G_T$, and a bilinear map $e: G_1 \times G_2 \rightarrow G_T$. The operations of $G_1$ and $G_T$ are denoted as $+$ and $\times$ respectively. This algorithm chooses a base point $P_1$ of $G_1$ and a base point $P_2$ of $G_2$, and computes $P_T = e(P_1,P_2)$. $H: {0,1}^* \rightarrow \mathbb{Z}_p$ denotes a secure hash function and $f(R) = R \mod p$ denotes an almost invertible reduction function where $R \in G_T$ is defined in [25]. The system parameters are denoted as $para = (G_1,G_2,G_T,P_1,P_2,P_T,e,p,C,H,f)$.

KeyGen($k$, para): On input the security parameter $k$ and the system parameters $para$, this algorithm randomly picks two integers $d,l_0 \in \mathbb{Z}_p$, and computes $S_0 = l_0 P_1, S’_0 = (d-l_0)P_1$ and $Q = P_T$. The public key is $pk = (P_1,P_2,P_T,Q)$ while the initial secret key is $sk = (S_0,S’_0)$.

Sign$i$(S${i-1}$, m$_i$): On input the first part of the $(i-1)$th secret key, to sign a message $m_i$, this algorithm randomly selects integer $l_i,t_i \in {0,p-1}$ and computes $S_i = S_{i-1} + l_i P_1$, $R_s = P_T^{t_i}$, $r_s = f(R_s)$, $h_s = H(m_i)$, and $w_i = t_i P_1 + h_s r_s S_i$.

Sign$3$(S${i-1}$, h$_s$, r$_s$, w$_i$): On input the second part of the $(i-1)$th secret key, this algorithm computes $S’i = S’{i-1} – l_i P_1$, and $s_i = w_i + h_s r_s S_i$. The signature on the message $m_i$ is $\sigma_i = (r_s,s_i)$.

Verify(pk, m$_i$, $\sigma_i$): On input a message-signature pair $(m_i, \sigma_i)$ where $\sigma_i = (r_s,s_i)$, this algorithm computes $h_b = H(m_i)$ and $R_b = e(s_i,S’_i) \times Q^{-h_b r_s}$. Output a bit 0 to indicate the signature is valid if $f(R_b) = r_s$. Otherwise, output 0 meaning the signature is invalid.

5 SECURITY PROOF

In this section, we prove the security of our construction against adaptive chosen message attack under continual leakage setting in the generic bilinear group model via a sequence of games. To do this, we firstly prove the security of our scheme denoted as $\Pi$ against ($\Gamma$-time,0-query) adversary called a passive adversary under no leakage environment through a game $G_1$. Then, we prove security against a ($\Gamma$-time,$\tau$-query) adversary called an active adversary under no leakage setting through a game $G_2$. It is clear that the attack power of the adversaries in $G_2$ is stronger than that of in $G_1$. More precisely, except the generic group oracles $O_1$, $O_2$ and $O_T$, $A$ can also query a signing oracle to obtain polynomial signatures of messages. Next, we prove security against an active adversary under the continual-leakage setting through a game $G_3$. In this game, the adversary $A$ can not only obtain the representations of group elements and signatures of messages but also can get some leaked knowledge of the internal secret key.

5.1 Proof under no leakage setting

We firstly provide the unforgeability proof of our scheme against a passive adversary, and then, we give a proof against an active adversary in this part.

Against a passive adversary.

Theorem 1. If there exists an ($\epsilon,\tau,0$)-adversary $A$ that can forge a valid signature of our scheme $\Pi$ in the generic bilinear group model, then we can construct an ($\epsilon’$, $\tau’$)-hash-inverter $I_H$ where

$$\epsilon’ \geq \frac{\epsilon – 9(\tau’ + 1)/p}{\tau’}.$$

Proof. In order to construct a hash inverter $I_H$, we use the adversary $A$ as a sub-routine.

In the generic bilinear group model, the functions $\sigma_T$, $\sigma_1$ and $\sigma_2$ behave randomly. Just like hash functions are controlled by the challenger in the random oracle model, $\sigma_T$ is controlled by $I_H$ in the generic bilinear group model. With this simulation, we describe the response of $I_H$ to group oracle queries as follows.

Query to $O_T$: Upon receiving an independent input $R_i = Q_j$ for some $i,j$ from $A$, the oracle $O_T$ selects a random $u_j \in \mathbb{Z}p \setminus {r_1,\ldots,r{i-1}}$ and sets $\sigma_T(u_j) = Q_j$. $O_T$ adds $Q_j$ into the table $Q_T$ and adds $u_j$ to $u$. If $O_T$ receives a dependent input $R_i = R_k$ for some $k < i$, it sets $r_i = r_k$. Before $O_T$ outputs the response $Z_{3i}$, it first computes $a_{3i} = a_i + a_{i+1}$ where $a_i$ and $a_{i+1}$ can be determined from $A$’s two inputs. Then it computes $r_{3i} = \prod_{j=1}^{i} u_{3i-j}$. Next, it compares $r_{3i}$ with ${r_1,\ldots,r_{3i-1}}$, which are already in the table $L_T$. If $r_{3i} = r_k$ for some $k < 3i$, then $O_T$ responds with $R_k$. If $r_{3i} \neq r_k$ for all $k < 3i$ then $O_T$ selects randomly $R_{3i} \in \mathbb{Z}T \setminus {r_1,\ldots,r{3i-1}}$ and appends it into the table $L_T$.

Query to $O_1$ and $O_2$: $A$’s queries to generic group oracles $O_1$ and $O_2$ are similar to queries to $O_T$. A difference is that $O_1$ and $O_2$ computes the pre-image as $r_{3i} = a_{3i} u = \sum_{j=1}^{i} a_{3i-j} \cdot Q_j$.

Description of game $G_1$: We describe a reduction game from an ($\epsilon,\tau,0$)-adversary $A$ to a ($\epsilon’,\tau’$)-hash-inverter $I_H$ of the hash function $H$. More precisely, if $A$ can forge a signature in probability $\epsilon$, then $I_H$ can invert $H$ in probability $\epsilon’$.

The input to $I_H$ is a random element $h \in [0,p-1]$ as a challenge, and the goal of $I_H$ is to find $M$ such that $H(M) = h$. To find $M$, $I_H$ invokes the adversary $A$ and let it interact with a modified simulation of generic group oracle $O_T$. When $A$ is invoked, it makes some queries to generic group oracles. In the end, $A$ outputs $(M,(r_s,s))$, where $M$ is an arbitrary message and $(r_s,s)$ is a signature for $M$ valid under the public key $Q$. Initially, we assume without loss generality that the first independent representation in table $Q_1$ is the base point $P_1$ in $G_1$ and $P_1 = Q_1 = \sigma_1(1)$. And the first independent representation in table $Q_2$ is the base point $P_2$ in $G_2$ and $P_2 = Q_1 = \sigma_2(1)$. In the table $Q_T$, the first independent representation is the signer’s public key $Q$ and $Q = Q_1 = \sigma_T(X)$ where $X$ denotes the discrete logarithm of the signer’s secret key.

To make sure the output message $M$ of $A$ is the answer of the inverter $I_H$, we introduce the following trick. We conduct a modified simulation of the generic bilinear group oracle $O_T$. Moreover, we ensure that the modified version of the oracle $O_T$, from $A$’s perspective, is indistinguishable from the standard version. Therefore, $A$ would operate as if it were communicating with a true generic group oracle.

Useful information for enthusiasts:

Contact me via Telegram: @ExploitDarlenePRO