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 for this work

Department of Computer Science

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

4 Citations (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.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2024 : 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Marc Joye, Gregor Leander
Number of pages	32
Volume	III
Publisher	Springer
Publication date	2024
Pages	457-488
ISBN (Print)	9783031587337
DOIs	https://doi.org/10.1007/978-3-031-58734-4_16
Publication status	Published - 2024
Event	43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques - Zurich, Switzerland Duration: 26 May 2024 → 30 May 2024 https://eurocrypt.iacr.org/2024/

Conference

Conference	43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques
Country/Territory	Switzerland
City	Zurich
Period	26/05/2024 → 30/05/2024
Internet address	https://eurocrypt.iacr.org/2024/

Series	Lecture Notes in Computer Science
Volume	14653
ISSN	0302-9743

Access to Document

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

Library access?

Check availability with the Royal Danish Library

Cite this

@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. in M Joye & G Leander (eds), Advances in Cryptology – EUROCRYPT 2024: 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. vol. III, Springer, Lecture Notes in Computer Science, vol. 14653, pp. 457-488, 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, 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. ed. / Marc Joye; Gregor Leander. Vol. III Springer, 2024. p. 457-488 (Lecture Notes in Computer Science, Vol. 14653).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › 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 -

Loss J, Nielsen JB. Early Stopping for Any Number of Corruptions. In Joye M, Leander G, editors, Advances in Cryptology – EUROCRYPT 2024: 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Vol. III. Springer. 2024. p. 457-488. (Lecture Notes in Computer Science, Vol. 14653). doi: 10.1007/978-3-031-58734-4_16