Adaptively Secure Broadcast in Resource-Restricted Cryptography.

Broadcast protocols enable a set of $n$ parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP '83), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial $ω(n)$ communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform "after the fact" removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple protocol showing near tightness of our first bound. 1) We demonstrate a tradeoff between resiliency and communication for protocols secure against $n-o(n)$ static corruptions. For example, $Ω(n\cdot {\sf polylog}(n))$ messages are needed when the number of honest parties is $n/{\sf polylog}(n)$ ; $Ω(n\sqrt{n})$ messages are needed for $O(\sqrt{n})$ honest parties; and $Ω(n^2)$ messages are needed for $O(1)$ honest parties. Complementarily, we demonstrate broadcast with $O(n\cdot{\sf polylog}(n))$ total communication facing any constant fraction of static corruptions. 2) Our second bound considers $n/2 + k$ corruptions and a weakly adaptive adversary that cannot remove messages "after the fact." We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to $k$ other parties. This rules out, for example, broadcast facing 51% corruptions in which all non-sender parties have sublinear communication locality.Broadcast protocols enable a set of $n$ parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP '83), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial $ω(n)$ communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform "after the fact" removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple protocol showing near tightness of our first bound. 1) We demonstrate a tradeoff between resiliency and communication for protocols secure against $n-o(n)$ static corruptions. For example, $Ω(n\cdot {\sf polylog}(n))$ messages are needed when the number of honest parties is $n/{\sf polylog}(n)$; $Ω(n\sqrt{n})$ messages are needed for $O(\sqrt{n})$ honest parties; and $Ω(n^2)$ messages are needed for $O(1)$ honest parties. Complementarily, we demonstrate broadcast with $O(n\cdot{\sf polylog}(n))$ total communication facing any constant fraction of static corruptions. 2) Our second bound considers $n/2 + k$ corruptions and a weakly adaptive adversary that cannot remove messages "after the fact." We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to $k$ other parties. This rules out, for example, broadcast facing 51% corruptions in which all non-sender parties have sublinear communication locality.

arXiv:2309.01466Sep 4, 20230 citations

Design of quantum cryptography systems for passiveoptical networks

Paul D. Townsend, Simon J. D. Phoenix, Keith J. Blow +1 more

Quantum cryptography has been shown to be an effective technique for the secure distribution of cryptographic keys on point-to-point communication links. The authors describe adaptations of the existing quantum cryptography protocols and equipment configurations that allow secure key distribution to be performed on a variety of multiuser passive optical network (PON) architectures. These adaptations enable the network controller on the PON to distribute individual secret keys to each user on the network, and hence to securely encrypt and authenticate subsequent data transmissions broadcast on the network.Quantum cryptography has been shown to be an effective technique for the secure distribution of cryptographic keys on point-to-point communication links. The authors describe adaptations of the existing quantum cryptography protocols and equipment configurations that allow secure key distribution to be performed on a variety of multiuser passive optical network (PON) architectures. These adaptations enable the network controller on the PON to distribute individual secret keys to each user on the network, and hence to securely encrypt and authenticate subsequent data transmissions broadcast on the network.

Electronics LettersOct 27, 199475 citations

Broadcast protocols enable a set of

n

parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP '83), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial

ω(n)

communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform "after the fact" removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple protocol showing near tightness of our first bound. 1) We demonstrate a tradeoff between resiliency and communication for protocols secure against

n-o(n)

static corruptions. For example,

Ω(n\cdot {\sf polylog}(n))

messages are needed when the number of honest parties is

n/{\sf polylog}(n)

;

Ω(n\sqrt{n})

messages are needed for

O(\sqrt{n})

honest parties; and

Ω(n^2)

messages are needed for

O(1)

honest parties. Complementarily, we demonstrate broadcast with

O(n\cdot{\sf polylog}(n))

total communication facing any constant fraction of static corruptions. 2) Our second bound considers

n/2 + k

corruptions and a weakly adaptive adversary that cannot remove messages "after the fact." We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to

k

other parties. This rules out, for example, broadcast facing 51% corruptions in which all non-sender parties have sublinear communication locality.