Verifiable Data Structure Streaming | Consiglio Nazionale delle Ricerche

Joint research project

Project leaders: Fabio Martinelli, Lu Chun Shien
Agreement: TAIWAN - NSTC - National Science and Technology Council
Call: CNR-MoST (ex NSC) 2016-2017
Department: Engineering, ICT and technologies for energy and transportation
Thematic area: Engineering, ICT and technologies for energy and transportation
Status of the project: New

Research proposal

Introduction: As cloud storage providers such as Dropbox and Amazon Cloud Drive are gaining popularity, users start to outsourcing their data to remote servers with the easy access to their data later on. Currently, many cloud services such as Dropbox, YouTube, and SoundCloud offer streaming service, where users are allowed to upload and retrieve their data in a streaming fashion.

A common feature shared by the above scenarios is a trusted server that provides the streaming service between the server and users. However, the server may behave maliciously or make accidental mistakes due to software/hardware error. Here, we define the problem of Verifiable Data Structure Streaming (VDSS) as the one, where the owner outsources his/her own data structure to an untrusted server in a streaming fashion. The user may later make query and update requests to the server and verify the correctness of the query result. In this sense, VDS can be a special case of VDSS;

Related Work. Schröder and Schröder [Schröder12] define the problem of VDS and proposed a solution, called Chameleon Authentication Tree (CAT). CAT has an inherent limitation that the tree structure and therefore its height need to be fixed during the tree construction. Thus, Schröder and Simkin [Schröder15] propose VeriStream to support the integrity guarantee of an unbound number of outsourced data. VeriStream still bases its effectiveness on CAT except that the tree can grow dynamically in VeriStream. Another line of related research is the one on Verifiable Databases (VDB). However, VDB mainly differs with VDS on the fact that the size of the data to be outsourced has been fixed in advance.

Research Challenge. In CAT, the owner needs O(log M) communication and computation costs for the Append, Update, and Query operations. Such overheads have been improved to O(log N) communication and computation costs for the append, update, and query operations in VeriStream. It still becomes a heavy burden on the owner's possibly resource-constrained device. Thus, one particular challenge is to reduce the burden on the outsourcing phase (Append operation). Here, we assume that Append operation will be executed more frequently and therefore deserves to be speedup.

Moreover, all of the current solutions rely on the asymmetric key cryptography and therefore need to conduct the energy- and time-consuming modular exponentiation. Thus, we look for a mechanism for VDS that uses only symmetric cryptographic primitives such as SHA-1 and AES. Due to their execution performance order of magnitudes faster than the heavyweight modular exponentiation, the performance of the VDS with only symmetric cryptographic primitives may have a significant improvement.

In addition, we not only consider outsourcing an array but also outsourcing a linked list to the server. Basically, the linked list differ with array in the fact that element insertion and deletion are allowed. However, the element insertion and deletion might globally modify the authentication structure. This might lead to the consequence that all of the verifying materials need to be downloaded to the owner, who then re-computes and then uploads the updated authentication structure to the server, which causes unrealistically huge communication cost.

System Model. The streaming feature in our setting still distinguishes our VDSS from VDS and VDB. VDSS consists of Verifiably Outsourcing an Array (VOA) and Verifiably Outsourcing a Linked List (VOLL) to an untrusted server, respectively. Formally, VOA supports Append(i, d), Query(i), and Update(i, d). On the other hand, VOLL has the same set of operations as VDS, except that two more operations Insert(i,d) and Delete(i) are supported.

Potential Solutions to VOA and VOLL.
Due to the lack of practical solutions in VOA and VOLL, we propose the following methods to achieve the practical efficiency especially for the resource-constrained data owner. The common framework of our proposed methods is our proposed Arithmetic Merkle tree (AMT), which is a variant of conventional Merkle tree. We first will describe how to construct AMT and its weakness in the hash collision. After that, we develop different schemes for VOA based on the use of AMT together with the homomorphic encryptions. Finally, we also develop different schemes for VOLL, one of which is based on specific VOA scheme.

Arithmetic Merkle Tree (AMT). Arithmetic Merkle tree (AMT) is a variant of conventional Merkle tree, where the leaf node stores the data item while the internal node is calculated by applying the cryptographic hash function to the concatenation of left children and right children nodes. With the consideration of only numeric data, AMT differs from the conventional Merkle tree on the hash function used; the cryptographic hash function is used in conventional Merkle tree whereas the sum operation is instead used in AMT.

Since the cryptographic hash function is replaced by the sum operation, AMT fails to achieve the collision-free property of the conventional Merkle tree. However, AMT possesses many useful properties such as the lightweight computation and local update. Here, the local update means that if the data of a leaf node needs to be changed, one does not need to re-calculate the entire tree as in the conventional Merkle tree; instead, only the nodes on the path from the corresponding leaf node to the root need to be re-calculated. The property of local update in AMT can be useful in our setting of dynamic streamed elements.

Research goals

The main objective of this project is to develop techniques for Verifiably Outsourcing an Array (VOA) and Verifiably Outsourcing a Linked List (VOLL). The designs of VOA and VOLL should meet the following requirements.

1. The computation and communication burden for the user need to be minimized because of the possibly resource-constrained user devices such as sensors and cellphones. In particular, due to the symmetric cryptographic techniques the order of magnitudes faster than asymmetric cryptographic techniques, it would be better to base the security of developed techniques on the symmetric cryptographic techniques.
2. The developed techniques need to have integrity guarantee of an unbound number of stream elements. The techniques with the support of a bound number of stream elements are unrealistic since, in reality, even the data owner cannot pre-determine the stream length. It would be better to conceive the data stream as an infinite one.
3. The security guarantee is better based on standard or popular security assumptions. Because the non-standard or non-popular hardness assumptions have not been well examined, the system built on top of such assumptions may be more vulnerable to further test or detailed examination on their security level.
4. The developed techniques need to be implementation-friendly, which means that the practitioner can implement the VDSS system by using off-the-shelf crypto libraries only.

Last update: 25/04/2024