## 1 Introduction  
In accordance with the dramatic increase in data volume, advances in information and communication technology (ICT) have facilitated the move from local data management to remote data outsourcing services. Although data outsourcing has several benefits in terms of its low cost, agility, scalibility, and ease of maintenance, it also has potential problems that users may overlook. Outsourcing data to third-party storage means that control of the data is delegated to the authority managing the remote repository. Unintended data breaches or losses are possible because third-party storage service may be less vigilant than the data owner. Data breaches and losses may lead to serious financial damage as well as wasteful efforts, and can happen for various reasons such as negligimanagement [1], improper operations [2], and poor resource utilization [3], among other reasons [4; 5]. Nonetheless, some remote storage service providers may even attempt to hide losses to protect their reputation [6]. Given the issues surrounding data outsourcing, there is an increasing need for a method of effectively and efficiently verifying the integrity of the data stored in a remote repository [7; 8; 9; 10; 11]. Of the various methods available for data integrity verification, Merkle tree [12] is a particularly well-known authenticated data structure. The verification of data integrity based on Merkle tree is implemented by a challenge-response protocol, where a prover provides a series of node values on the path from a leaf node (randomly chosen by a verifier) to the root node of the tree. The prover needs to generate the entire Merkle tree for the attested data, while the verifier can store the single value for the root node in the tree. In other words, this approach only requires the verifier to store and operate on a few number of hash values, and the prover to generate the proof by using the entire data blocks. Thanks to its lightweight computation and low memory requirements, Merkle tree-based authentication has been widely adopted to various systems including blockchain technologies [13; 14] such as Bitcoin [15]. Of particular note is that its efficiency increases significantly as the amount of data to be verified increases. When it comes to online authentication, however, adversarial entities can gather meaningful information from transcripts by repeatedly conducting integrity verification for the same data. In an extreme case, an eavesdropper who collects authentication information can illicitly obtain ownership of the data stored in a remote repository if this method is directly used for authenticating ownership [16; 17; 18]. To minimize this risk, we examine possible information leakage from Merkle tree-based online authentication. Based on an in-depth analysis, we present a new Merkle tree-based protocol which inserts random sources every time the proof generation is executed. This eliminates information leakage we have found, thus providing consistently reliable online authentication. The main contributions of this paper can be summarized as follows: (This work is an extended version of a conference paper published in ICWS 2017 [19]. In the earlier version, the proof generated by the prover was allowed to be extended but not shortened while this version provides both options for better flexibility. In addition, rigorous security analysis and a complete comparison with related work are provided in this version.) * We analyze potential information leakage during the online verification process. It includes partial information of the Merkle tree and size information, which weaken the security and reliability of authentication (Section 3). * We propose a leakage-resilient integrity verification protocol (Section 4). Through a rigorous security proof, we illustrate its effectiveness regardless of the number of executions without requiring additional trusted third-party (Section 5). * We evaluate efficiency of the proposed scheme by implementing it in a real-world application.