Formalizing Delayed Adaptive Corruptions and the Security of Flooding Networks

TY - GEN

T1 - Formalizing Delayed Adaptive Corruptions and the Security of Flooding Networks

AU - Matt, Christian

AU - Nielsen, Jesper Buus

AU - Thomsen, Søren Eller

PY - 2022

Y1 - 2022

N2 - 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(Δ).

AB - 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(Δ).

KW - adaptive adversaries

KW - blockchain

KW - corruption models

KW - flooding networks

KW - peer-to-peer networks

KW - universal composability

UR - http://www.scopus.com/inward/record.url?scp=85141721716&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-15979-4_14

DO - 10.1007/978-3-031-15979-4_14

M3 - Article in proceedings

SN - 978-3-031-15978-7

T3 - Lecture Notes in Computer Science

SP - 400

EP - 430

BT - Advances in Cryptology – CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Proceedings

PB - Springer, Cham

T2 - 42nd Annual International Cryptology Conference, CRYPTO 2022

Y2 - 15 August 2022 through 18 August 2022

ER -