Cryptography for Efficiency: Authenticated Data Structures Based on Lattices and Parallel Online Memory Checking.
Charalampos Papamanthou, Roberto Tamassia · IACR Cryptology ePrint Archive · 2011
In this work, we initially design a new authenticated data structure for a dynamic table with n entries. We present the first dynamic authenticated table that is update-optimal, using a lattice-based construction. In particular, the update complexity is O(1), improving in this way the “a priori” O(logn) update bounds of previous constructions, such as the Merkle tree. Moreover, the space complexity of our authenticated data structure is O(n) and logarithmic bounds hold for other performance measures, such as proof complexity (number of group elements contained in the proof). To achieve this result, we establish and exploit a property that we call repeated linearity of lattice-based hash functions and show how the security of lattice-based digests can be guaranteed under updates. An one-time preprocessing stage of O(n logn) complexity is also required at setup. This is the first construction achieving a constant update bound without causing other complexities to increase beyond logarithmic. All previous solutions enjoying such a complexity bound for updates enforce Ω(n ) proof or query complexity. As an application, we provide the first construction of an authenticated Bloom filter, an update-intensive data structure that falls into our