Further Related Work Sample Clauses

Further Related Work. There is a large body of research on BA and related problems (sometimes colloquially referred to as “consensus”), and we focus here on the most closely re- lated works. We have already mentioned the works of [AD15,KMS14,GKLP18] who achieve BA in the PoW model without setup and run in O(nκ2), O(n), and O(κ) rounds, respec- tively. It should also be noted that we require stronger assumptions (namely a VDF and the random oracle model (ROM)) than the protocols in [AD15,GKLP18,GKO+20], who require only the ROM that can be queried at a bounded rate by any party, but (pos- sibly) weaker assumptions than required in the work of Xxxx et al. [KMS14], who also require some form of an unpredictable beacon in their protocol. The more recent work of Aggarwal et al. [AMSZ19] presents a setup-free solution in the PoW model that also runs in expected O(1) rounds, but assumes a static adversary (while we consider the much stronger adversarial model of adaptive corruptions). Another related work that focuses on the PoW model is by Xxxxx et al. [GKO+20]. They show how to achieve UC-secure BA and multi-party computation (MPC) protocols in the PoW model. Similar to [AD15], their BA takes O(nκ2) rounds. Although the above-mentioned prior works achieve BA without a PKI [AD15,KMS14,GKLP18], their techniques are not what we need to achieve O(1)-round BA. In fact, we notice that achieving O(1)-round BA protocols requires very particular techniques that have been studied [Rab83,FM88,KK06a,MV17,Mic17,ADD+19,ACD+19] in the classical setting for many years and this round reduction is very challenging to achieve.

Further Related Work. A significant amount of work has gone into understanding what happens when security properties are analyzed in the multi-key setting in a variety of differ- ent contexts. These include public key encryption [5], key establishment proto- cols [9, 16], signatures [39], message authentication codes [4, 21], tweakable block ciphers [27, 52], and hybrid encryption [20, 51]. Xxxxx et al. recently established impossibility results showing that a loss of a factor μ is inevitable when moving to the multi-key setting for a range of public-key primitives [2]. Most recently, Xxxxxxxxx and Terashima [47] introduced a new model in order to bridge gaps between standard and ideal model bounds to analyze settings where the xxxx- dard model bounds provide little assurance of security, like the multi-key setting. Other research on security of block ciphers in the multi-key setting includes the works by Xxxxxxxx et al. [1], Xxxxx and Luykx [40], Xxxxxxx [49], and Xxxxxx et al. [24]. However, there is no systematic treatment of the problem like that provided in our work.