Aarhus Universitets segl

Formalizing Delayed Adaptive Corruptions and the Security of Flooding Networks

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

Many decentralized systems rely on flooding protocols for message dissemination. In such a protocol, the sender of a message sends it to a randomly selected set of peers. These peers again send the message to their randomly selected peers, until every network participant has received the message. This type of protocols clearly fail in face of an adaptive adversary who can simply corrupt all peers of the sender and thereby prevent the message from being delivered. Nevertheless, flooding protocols are commonly used within protocols that aim to be cryptographically secure, most notably in blockchain protocols. While it is possible to revert to static corruptions, this gives unsatisfactory security guarantees, especially in the setting of a blockchain that is supposed to run for an extended period of time. To be able to provide meaningful security guarantees in such settings, we give precise semantics to what we call δ -delayed adversaries in the Universal Composability (UC) framework. Such adversaries can adaptively corrupt parties, but there is a delay of time δ from when an adversary decides to corrupt a party until they succeed in overtaking control of the party. Within this model, we formally prove the intuitive result that flooding protocols are secure against δ -delayed adversaries when δ is at least the time it takes to send a message from one peer to another plus the time it takes the recipient to resend the message. To this end, we show how to reduce the adaptive setting with a δ -delayed adversary to a static experiment with an Erdős-Rényi graph. Using the established theory of Erdős-Rényi graphs, we provide upper bounds on the propagation time of the flooding functionality for different neighborhood sizes of the gossip network. More concretely, we show the following for security parameter κ, point-to-point channels with delay at most Δ, and n parties in total, with a sufficiently delayed adversary that can corrupt any constant fraction of the parties: If all parties send to Ω(κ) parties on average, then we can realize a flooding functionality with maximal delay O(Δ· log (n) ) ; and if all parties send to Ω(κn) parties on average, we can realize a flooding functionality with maximal delay O(Δ).

OriginalsprogEngelsk
TitelAdvances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings : 42nd Annual International Cryptology Conference, CRYPTO 2022, Procerdings
Antal sider31
ForlagSpringer, Cham
Udgivelsesår2022
Sider400-430
ISBN (trykt)978-3-031-15978-7
ISBN (Elektronisk)978-3-031-15979-4
DOI
StatusUdgivet - 2022
Begivenhed42nd Annual International Cryptology Conference, CRYPTO 2022 - Santa Barbara, USA
Varighed: 15 aug. 202218 aug. 2022

Konference

Konference42nd Annual International Cryptology Conference, CRYPTO 2022
LandUSA
BySanta Barbara
Periode15/08/202218/08/2022
SerietitelLecture Notes in Computer Science
Nummer13508

Se relationer på Aarhus Universitet Citationsformater

ID: 297245002