Early Stopping for Any Number of Corruptions

Julian Loss; Jesper Buus Nielsen

doi:10.1007/978-3-031-58734-4_16

Early Stopping for Any Number of Corruptions

Julian Loss^*
, Jesper Buus Nielsen

^*Corresponding author af dette arbejde

Institut for Datalogi

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

3 Citationer (Scopus)

Abstract

Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first early stopping byzantine broadcast protocol that tolerates up to t=n-1 malicious corruptions and terminates in O(min{f²,t+1}) rounds for any execution with f≤tactual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all either require honest majority or tolerate only up to t=(1-ϵ)n malicious corruptions while requiring either trusted setup or strong number theoretic hardness assumptions. As our key contribution, we show a novel tool called a polariser that allows us to transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority.

Originalsprog	Engelsk
Titel	Advances in Cryptology – EUROCRYPT 2024 : 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Redaktører	Marc Joye, Gregor Leander
Antal sider	32
Vol/bind	III
Forlag	Springer
Publikationsdato	2024
Sider	457-488
ISBN (Trykt)	9783031587337
DOI	https://doi.org/10.1007/978-3-031-58734-4_16
Status	Udgivet - 2024
Begivenhed	43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques - Zurich, Schweiz Varighed: 26 maj 2024 → 30 maj 2024 https://eurocrypt.iacr.org/2024/

Konference

Konference	43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques
Land/Område	Schweiz
By	Zurich
Periode	26/05/2024 → 30/05/2024
Internetadresse	https://eurocrypt.iacr.org/2024/

Navn	Lecture Notes in Computer Science
Vol/bind	14653
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-031-58734-4_16

Biblioteksadgang?

Tjek tilgængelighed hos det Kgl. Bibliotek

Andre filer og links

Link to publication in Scopus

Citationsformater

@inproceedings{6516786ae4b74ef8a361173575503d9e,

title = "Early Stopping for Any Number of Corruptions",

abstract = "Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first early stopping byzantine broadcast protocol that tolerates up to t=n-1 malicious corruptions and terminates in O(min\{f2,t+1\}) rounds for any execution with f≤tactual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all either require honest majority or tolerate only up to t=(1-ϵ)n malicious corruptions while requiring either trusted setup or strong number theoretic hardness assumptions. As our key contribution, we show a novel tool called a polariser that allows us to transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority.",

author = "Julian Loss and Nielsen, \{Jesper Buus\}",

year = "2024",

doi = "10.1007/978-3-031-58734-4\_16",

language = "English",

isbn = "9783031587337",

volume = "III",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "457--488",

editor = "Marc Joye and Gregor Leander",

booktitle = "Advances in Cryptology – EUROCRYPT 2024",

address = "Netherlands",

note = "43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT ; Conference date: 26-05-2024 Through 30-05-2024",

url = "https://eurocrypt.iacr.org/2024/",

}

Loss, J & Nielsen, JB 2024, Early Stopping for Any Number of Corruptions. i M Joye & G Leander (red), Advances in Cryptology – EUROCRYPT 2024: 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. bind III, Springer, Lecture Notes in Computer Science, bind 14653, s. 457-488, 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Schweiz, 26/05/2024. https://doi.org/10.1007/978-3-031-58734-4_16

Early Stopping for Any Number of Corruptions. / Loss, Julian; Nielsen, Jesper Buus.
Advances in Cryptology – EUROCRYPT 2024: 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. red. / Marc Joye; Gregor Leander. Bind III Springer, 2024. s. 457-488 (Lecture Notes in Computer Science, Bind 14653).

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Early Stopping for Any Number of Corruptions

AU - Loss, Julian

AU - Nielsen, Jesper Buus

PY - 2024

Y1 - 2024

N2 - Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first early stopping byzantine broadcast protocol that tolerates up to t=n-1 malicious corruptions and terminates in O(min{f2,t+1}) rounds for any execution with f≤tactual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all either require honest majority or tolerate only up to t=(1-ϵ)n malicious corruptions while requiring either trusted setup or strong number theoretic hardness assumptions. As our key contribution, we show a novel tool called a polariser that allows us to transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority.

AB - Minimizing the round complexity of byzantine broadcast is a fundamental question in distributed computing and cryptography. In this work, we present the first early stopping byzantine broadcast protocol that tolerates up to t=n-1 malicious corruptions and terminates in O(min{f2,t+1}) rounds for any execution with f≤tactual corruptions. Our protocol is deterministic, adaptively secure, and works assuming a plain public key infrastructure. Prior early-stopping protocols all either require honest majority or tolerate only up to t=(1-ϵ)n malicious corruptions while requiring either trusted setup or strong number theoretic hardness assumptions. As our key contribution, we show a novel tool called a polariser that allows us to transfer certificate-based strategies from the honest majority setting to settings with a dishonest majority.

UR - https://www.scopus.com/pages/publications/85193589144

U2 - 10.1007/978-3-031-58734-4_16

DO - 10.1007/978-3-031-58734-4_16

M3 - Article in proceedings

AN - SCOPUS:85193589144

SN - 9783031587337

VL - III

T3 - Lecture Notes in Computer Science

SP - 457

EP - 488

BT - Advances in Cryptology – EUROCRYPT 2024

A2 - Joye, Marc

A2 - Leander, Gregor

PB - Springer

T2 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques

Y2 - 26 May 2024 through 30 May 2024

ER -