Dynamic Fully Homomorphic encryption-based Merkle Tree for lightweight streaming authenticated data structures

Fully Homomorphic encryption-based Merkle Tree (FHMT) is a novel technique for streaming authenticated data structures (SADS) to achieve the streaming verifiable computation. By leveraging the computing capability of fully homomorphic encryption, FHMT shifts almost all of the computation tasks to the server, reaching nearly no overhead for the client. Therefore, FHMT is an important technique to construct a more efficient lightweight ADS for resource-limited clients. But the typical FHMT cannot support the dynamic scenario very well because it cannot expend freely since its height is fixed. We now present our fully dynamic FHMT construction, which is a construction that is able to authenticate an unbounded number of data elements and improves upon the state-of-the-art in terms of computational overhead. We divided the algorithms of the DFHMT with the following phases: initialization, insertion, tree expansion, query and verification. The DFHMT removes the drawbacks of the static FHMT. In the initialization phase, it is not required for the scale of the tree to be determined, and the scale of the tree can be adaptively expanded during the data-appending phase. This feature is more suitable for streaming data environments. We analyzed the security of the DFHMT, and point out that DFHMT has the same security with FHMT. The storage, communication and computation overhead of DFHMT is also analyzed, the results show that the client uses simple numerical multiplications and additions to replace hash operations, which reduces the computational burden of the client; the length of the authentication path in DFHMT is shorter than FHMT, which reduces storage and communication overhead. The performance of DFHMT was compared with other construction techniques of SADS via some tests, the results show that DFHMT strikes the performance balance between the client and server, which has some performance advantage for lightweight devices.