Abstract
In this work we study a new information theoretic problem, called online merging, that has direct applications for constructing publicstate accumulators and registrationbased encryption schemes. An {online merger} receives the sequence of sets {1}, {2}, … in an online way, and right after receiving {i}, it can repartition the elements 1,…,i into T₁,…,T_{m_i} by merging some of these sets. The goal of the merger is to balance the tradeoff between the maximum number of sets wid = max_{i ∈ [n]} m_i that coexist 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 publicstate accumulators (using collisionresistant hashing) and registrationbased encryptions (relying on more assumptions). Doing so, the width of an online merger translates into the size of the publicparameter 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 2approximate 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)}).
BibTeX  Entry
@InProceedings{mahmoody_et_al:LIPIcs.ITC.2023.15,
author = {Mahmoody, Mohammad and Qi, Wei},
title = {{Online Mergers and Applications to RegistrationBased Encryption and Accumulators}},
booktitle = {4th Conference on InformationTheoretic Cryptography (ITC 2023)},
pages = {15:115:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772716},
ISSN = {18688969},
year = {2023},
volume = {267},
editor = {Chung, KaiMin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18343},
URN = {urn:nbn:de:0030drops183432},
doi = {10.4230/LIPIcs.ITC.2023.15},
annote = {Keywords: Registrationbased encryption, Accumulators, Merkle Trees}
}
Keywords: 

Registrationbased encryption, Accumulators, Merkle Trees 
Collection: 

4th Conference on InformationTheoretic Cryptography (ITC 2023) 
Issue Date: 

2023 
Date of publication: 

21.07.2023 