Search

In this work we study a new information theoretic problem, called online merging, that has direct applications for constructing public-state accumulators and registration-based encryption schemes. An {online merger} receives the sequence of sets {1}, {2}, … in an online way, and right after receiving {i}, it can re-partition the elements 1,…,i into T₁,…,T_{m_i} by merging some of these sets. The goal of the merger is to balance the trade-off between the maximum number of sets wid = max_{i ∈ [n]} m_i that co-exist at any moment, called the width of the scheme, with its depth dep = max_{i ∈ [n]} d_i, where d_i is the number of times that the sets that contain i get merged. An online merger can be used to maintain a set of Merkle trees that occasionally get merged. An online merger can be directly used to obtain public-state accumulators (using collision-resistant hashing) and registration-based encryptions (relying on more assumptions). Doing so, the width of an online merger translates into the size of the public-parameter of the constructed scheme, and the depth of the online algorithm corresponds to the number of times that parties need to update their "witness" (for accumulators) or their decryption key (for RBE). In this work, we construct online mergers with poly(log n) width and O(log n / log log n) depth, which can be shown to be optimal for all schemes with poly(log n) width. More generally, we show how to achieve optimal depth for a given fixed width and to achieve a 2-approximate optimal width for a given depth d that can possibly grow as a function of n (e.g., d = 2 or d = log n / log log n). As applications, we obtain accumulators with O(log n / log log n) number of updates for parties' witnesses (which can be shown to be optimal for accumulator digests of length poly(log n)) as well as registration based encryptions that again have an optimal O(log n / log log n) number of decryption updates, resolving the open question of Mahmoody, Rahimi, Qi [TCC'22] who proved that Ω(log n / log log n) number of decryption updates are necessary for any RBE (with public parameter of length poly(log n)). More generally, for any given number of decryption updates d = d(n) (under believable computational assumptions) our online merger implies RBE schemes with public parameters of length that is optimal, up to a constant factor that depends on the security parameter. For example, for any constant number of updates d, we get RBE schemes with public parameters of length O(n^{1/(d+1)})., LIPIcs, Vol. 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023), pages 15:1-15:23

Given 2n-to-n compression functions h₁,h₂,h₃, we build a new 5n-to-n compression function T₅, using only 3 compression calls: T₅(m₁, m₂, m₃, m₄, m₅) : = h₃(h₁(m₁, m₂)⊕ m₅ , h₂(m₃, m₄)⊕ m₅) ⊕ m₅ We prove that this construction matches Stam’s bound, by providing Õ(q²/2ⁿ) collision security and O(q³/2^{2n}+ nq/2ⁿ) preimage security (the latter term dominates in the region of interest, when q < 2^{n/2}). In particular, it provides birthday security for hashing 5 inputs using three 2n-to-n compression calls, instead of only 4 inputs in prior constructions. Thus, we get a sequential variant of the Merkle-Damgård (MD) hashing, where t message blocks are hashed using only 3t/4 calls to the 2n-to-n compression functions; a 25% saving over traditional hash function constructions. This time reduces to t/4 (resp. t/2) sequential calls using 3 (resp. 2) parallel execution units; saving a factor of 4 (resp. 2) over the traditional MD-hashing, where parallelism does not help to process one message. We also get a novel variant of a Merkle tree, where t message blocks can be processed using 0.75(t-1) compression function calls and depth 0.86 log₂ t, thereby saving 25% in the number of calls and 14% in the update time over Merkle trees. We provide two modes for a local opening of a particular message block: conservative and aggressive. The former retains the birthday security, but provides longer proofs and local verification time than the traditional Merkle tree. For the aggressive variant, we reduce the proof length to a 29% overhead compared to Merkle trees (1.29log₂ t vs log₂ t), but the verification time is now 14% faster (0.86log₂ t vs log₂ t). However, birthday security is only shown under a plausible conjecture related to the 3-XOR problem, and only for the (common, but not universal) setting where the root of the Merkle tree is known to correspond to a valid t-block message., LIPIcs, Vol. 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021), pages 24:1-24:23