DRAGON: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive Consistency

Hanwen Feng; Zhenliang Lu; Qiang Tang

doi:10.1145/3662158.3662771

DRAGON: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive Consistency

Hanwen Feng, Zhenliang Lu^*, Qiang Tang

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

8 Citations (Scopus)

1 Downloads (CityUHK Scholars)

Abstract

Several distributed protocols, including distributed key generation (DKG) and interactive consistency (IC), depend on O (n) instances of Byzantine Broadcast or Byzantine Agreement among n nodes, resulting in O (n³) communication overhead.

In this paper, we provide a new methodology of realizing such broadcasts we call DRAGON: Decentralization at the cost of Representation after Arbitrary GrOupiNg. At the core of it, we arbitrarily group nodes into small "shards" and paired with multiple new primitives we call consortium-sender (dealer) broadcast (and secret sharing). The new tools enable a shard of nodes to to jointly broadcast (or securely contribute a secret) to the whole population only at the cost of one dealer (as if there is a representative).

With our new Dragon method, we construct the first two DKG protocols, both achieving optimal resilience, with sub-cubic total communication and computation. The first DKG generates a secret key within an Elliptic Curve group, incurring Õ (n^2·5λ) total communication and computation. The second DKG, while slightly increasing communication and computation by a factor of the statistical security parameter, generates a secret key as a field element, which makes it directly compatible with various off-the-shelf DLog-based threshold cryptographic systems. We also construct a first deterministic IC with sub-cubic communication.

© 2024 Copyright held by the owner/author(s).

Original language	English
Title of host publication	PODC '24
Subtitle of host publication	Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing
Publisher	Association for Computing Machinery
Pages	469-479
ISBN (Print)	979-8-4007-0668-4
DOIs	https://doi.org/10.1145/3662158.3662771
Publication status	Published - Jun 2024
Externally published	Yes
Event	43rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2024) - Nantes, France Duration: 17 Jun 2024 → 21 Jun 2024 https://www.podc.org/podc2024/

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference	43rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2024)
Place	France
City	Nantes
Period	17/06/24 → 21/06/24
Internet address	https://www.podc.org/podc2024/

Funding

This work was supported in part by research awards from Protocol Labs, Ethereum Foundation, Stellar Development Foundation, and SOAR Prize from the University of Sydney.

Research Keywords

distributed key generation
interactive consistency

Publisher's Copyright Statement

This full text is made available under CC-BY 4.0. https://creativecommons.org/licenses/by/4.0/

Access Output

10.1145/3662158.3662771

335448174.pdfFinal Published version, 863 KBLicence: CC BY

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Feng, H., Lu, Z., & Tang, Q. (2024). DRAGON: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive Consistency. In PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (pp. 469-479). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). Association for Computing Machinery. https://doi.org/10.1145/3662158.3662771

Feng, Hanwen ; Lu, Zhenliang ; Tang, Qiang. / DRAGON : Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive Consistency. PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 2024. pp. 469-479 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

@inproceedings{8082c329c0634994bfcae945344dfc6e,

title = "DRAGON: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive Consistency",

abstract = "Several distributed protocols, including distributed key generation (DKG) and interactive consistency (IC), depend on O (n) instances of Byzantine Broadcast or Byzantine Agreement among n nodes, resulting in O (n3) communication overhead.In this paper, we provide a new methodology of realizing such broadcasts we call DRAGON: Decentralization at the cost of Representation after Arbitrary GrOupiNg. At the core of it, we arbitrarily group nodes into small {"}shards{"} and paired with multiple new primitives we call consortium-sender (dealer) broadcast (and secret sharing). The new tools enable a shard of nodes to to jointly broadcast (or securely contribute a secret) to the whole population only at the cost of one dealer (as if there is a representative).With our new Dragon method, we construct the first two DKG protocols, both achieving optimal resilience, with sub-cubic total communication and computation. The first DKG generates a secret key within an Elliptic Curve group, incurring {\~O} (n2·5λ) total communication and computation. The second DKG, while slightly increasing communication and computation by a factor of the statistical security parameter, generates a secret key as a field element, which makes it directly compatible with various off-the-shelf DLog-based threshold cryptographic systems. We also construct a first deterministic IC with sub-cubic communication. {\textcopyright} 2024 Copyright held by the owner/author(s). ",

keywords = "distributed key generation, interactive consistency",

author = "Hanwen Feng and Zhenliang Lu and Qiang Tang",

year = "2024",

month = jun,

doi = "10.1145/3662158.3662771",

language = "English",

isbn = "979-8-4007-0668-4",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "469--479",

booktitle = "PODC '24",

address = "United States",

note = "43rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2024) ; Conference date: 17-06-2024 Through 21-06-2024",

url = "https://www.podc.org/podc2024/",

}

Feng, H, Lu, Z & Tang, Q 2024, DRAGON: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive Consistency. in PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, pp. 469-479, 43rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2024), Nantes, France, 17/06/24. https://doi.org/10.1145/3662158.3662771

DRAGON: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive Consistency. / Feng, Hanwen; Lu, Zhenliang; Tang, Qiang.
PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 2024. p. 469-479 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - DRAGON

T2 - 43rd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2024)

AU - Feng, Hanwen

AU - Lu, Zhenliang

AU - Tang, Qiang

PY - 2024/6

Y1 - 2024/6

N2 - Several distributed protocols, including distributed key generation (DKG) and interactive consistency (IC), depend on O (n) instances of Byzantine Broadcast or Byzantine Agreement among n nodes, resulting in O (n3) communication overhead.In this paper, we provide a new methodology of realizing such broadcasts we call DRAGON: Decentralization at the cost of Representation after Arbitrary GrOupiNg. At the core of it, we arbitrarily group nodes into small "shards" and paired with multiple new primitives we call consortium-sender (dealer) broadcast (and secret sharing). The new tools enable a shard of nodes to to jointly broadcast (or securely contribute a secret) to the whole population only at the cost of one dealer (as if there is a representative).With our new Dragon method, we construct the first two DKG protocols, both achieving optimal resilience, with sub-cubic total communication and computation. The first DKG generates a secret key within an Elliptic Curve group, incurring Õ (n2·5λ) total communication and computation. The second DKG, while slightly increasing communication and computation by a factor of the statistical security parameter, generates a secret key as a field element, which makes it directly compatible with various off-the-shelf DLog-based threshold cryptographic systems. We also construct a first deterministic IC with sub-cubic communication. © 2024 Copyright held by the owner/author(s).

AB - Several distributed protocols, including distributed key generation (DKG) and interactive consistency (IC), depend on O (n) instances of Byzantine Broadcast or Byzantine Agreement among n nodes, resulting in O (n3) communication overhead.In this paper, we provide a new methodology of realizing such broadcasts we call DRAGON: Decentralization at the cost of Representation after Arbitrary GrOupiNg. At the core of it, we arbitrarily group nodes into small "shards" and paired with multiple new primitives we call consortium-sender (dealer) broadcast (and secret sharing). The new tools enable a shard of nodes to to jointly broadcast (or securely contribute a secret) to the whole population only at the cost of one dealer (as if there is a representative).With our new Dragon method, we construct the first two DKG protocols, both achieving optimal resilience, with sub-cubic total communication and computation. The first DKG generates a secret key within an Elliptic Curve group, incurring Õ (n2·5λ) total communication and computation. The second DKG, while slightly increasing communication and computation by a factor of the statistical security parameter, generates a secret key as a field element, which makes it directly compatible with various off-the-shelf DLog-based threshold cryptographic systems. We also construct a first deterministic IC with sub-cubic communication. © 2024 Copyright held by the owner/author(s).

KW - distributed key generation

KW - interactive consistency

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85199032404&origin=recordpage

U2 - 10.1145/3662158.3662771

DO - 10.1145/3662158.3662771

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 979-8-4007-0668-4

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 469

EP - 479

BT - PODC '24

PB - Association for Computing Machinery

Y2 - 17 June 2024 through 21 June 2024

ER -

Feng H, Lu Z, Tang Q. DRAGON: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive Consistency. In PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery. 2024. p. 469-479. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). Epub 2024 Jun 17. doi: 10.1145/3662158.3662771

DRAGON: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive Consistency

Abstract

Publication series

Conference

Funding

Research Keywords

Publisher's Copyright Statement

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this