## 3 Information Leakage Analysis of Merkle Tree-Based Authentication Schemes
### Previous Schemes and Their Vulnerabilities
#### 3.2.4 Merkle Tree-Based Authentication with Transmission in Encrypted Form  
[PERSON] et al. [32] employed a Merkle tree-based approach for online authentication in a smart grid system. To avoid information leakage, they combined it with a secure encryption algorithm. Specifically, the prover (i.e., a smart meter) and verifier (i.e., a neighborhood gateway) engage in a Diffie-Hellman key agreement protocol, followed by AES encryption to preserve the privacy of the authentication proof generated by the prover. (Inspired by [PERSON] et al. 's work [32], we can employ secure encryption algorithms to obfuscate communication between the prover and verifier. In [32], a Merkle tree is used for sender identification instead of data authentication, in which the Merkle tree is constructed from random elements chosen by \(\mathcal{P}\) and then \(\mathcal{V}\) validates the origin of the received power measurement (in a way that guarantees only one who can construct the valid Merkle tree is \(\mathcal{P}\)). However, in their research, the main purpose of exploiting secure key agreement and encryption algorithms was to minimize side effects caused by side channels during Merkle tree-based online authentication.) The overall data authentication process for Merkle tree-based data authentication using encrypted channels is described in Algorithm 2. (This algorithm requires key agreement and encryption of communications. Compared to adopting full SSL/TLS, it is more efficient since it requires Diffie-Hellman key agreement and efficient encryption algorithms such as AES, which will be analyzed in Section 6.) ```
Multiplicative cyclic group \(\mathbb{G}\) of large prime order \(p\) with generator \(g\) Key size of symmetric key encryption/decryption algorithm \(x\) according to security parameter \(\lambda\) Cryptographic hash function \(\mathcal{H}_{0}:\mathbb{G}\rightarrow\{0,1\}^{x(\lambda)}\) Secure symmetric key encryption/decryption algorithm \(SE/SD:\{0,1\}^{x(\lambda)}\times\{0,1\}^{|\textbf{m}|}\rightarrow\{0,1\}^{| \textbf{m}|}\)  for \(|m|\in\mathbb{N}\)  Merkle tree construction \(MTGen(\mathcal{H},B,M)\) over message \(M\) with block size \(B\) and cryptographic hash function \(\mathcal{H}\)  Proof (subbing path) generation \(prf\gets PrfGen(MT_{M},chal)\) for challenged index \(chal\)  on Merkle tree \(MT_{M}\)  Verification of proof \(1/0\gets Vr_{f}Prf(MT_{M}^{\text{\emph{\emph{\emph{\emph{\emph{\emph{\emph{\emph{\emph{\emph{\emph{\emph{\emph{\emph{\emph{\emph



this approach requires the verifier to construct a new Merkle tree for every authentication request, rendering pre-computation of the Merkle tree and its reuse on the verifier side impossible. Therefore, dynamically changing the size of the data blocks and hash functions for each authentication attempt significantly reduces efficiency from the verifier's perspective. Another approach is to insert dummy data into the ciphertext. While this can obfuscate information by increasing the size of data, it also increases the computational and communication overhead for both sides. With regard to efficiency, it requires higher computation cost for data encryption and decryption during data verification than in Merkle tree-based authentication, which is another practical drawback of this approach. (Detailed analysis can be found in Section 6.) ## 4 Randomized Online Authentication

In this section, we present a probabilistic authentication protocol by exploiting Merkle tree without a reduction in verification coverage. Before describing the proposed protocol, the adversarial model and its goals are summarized in the following subsections. ### Adversarial Model

We consider adversaries who are able to collect valid proofs of data authentication from public channels. This adversary can be either (1) a passive attacker eavesdropping on communications between valid prover \(\mathcal{P}\) and verifier \(\mathcal{V}\) without intervention, or (2) an adaptive online adversary.