All things DKG!

<aside> 🗒️ Aims to survey the myriad of DKG protocols for the various key settings

</aside>

Related work survey

Paper	Network Model	Fault tolerance	Adaptive adversary	Discrete log key	Comm. Complexity	Comp. Complexity	Round Complexity	Cryptographic Assumptions	Setup Assumptions	Notes
Pedersen DKG	Sync.	1/2	❌	✅	$O(n\mathcal{B}(\kappa t))$	$O(nt^3)$	$O(\mathcal{R})$	DDH	CRS	Untitled (https://hermitsage.notion.site/f0546908a19242448ed5a2c82e998f12)
JF-DKG	Sync.	1/2	❌	✅	$O(n\mathcal{B}(\kappa t))$	$O(nt^3)$	$O(\mathcal{R})$	DDH	CRS	Untitled (https://hermitsage.notion.site/f0546908a19242448ed5a2c82e998f12)
Canetti et al. DKG	Sync.	1/2	✅	✅	$O(n\mathcal{B}(\kappa t))$	$O(nt^3)$	$O(\mathcal{R})$	DDH	CRS	Untitled (https://hermitsage.notion.site/e19312e27ffb4994b599ebdb4d93c353)
Foque-Stern DKG	Sync.	1/2	⁉️	✅	$O(n\mathcal{B}(\kappa n))$	$O(n^3)$	$O(\mathcal{R})$	DCR, RO	PKI	Untitled (https://hermitsage.notion.site/d07cf63fa14a49ad87e33bd5e9e23b06)
Neji et al.	Sync.	1/2	❌	✅	$O(n\mathcal{B}(\kappa ))$	$O(nt^3)$	$O(\mathcal{R})$	CDH	CRS, PKI	Untitled (https://hermitsage.notion.site/a793823816e84a04a2a25cead93787a8)
Aggregatable DKG	Sync.	1/2	❌	❌	$O(\log{n}\mathcal{B}\left(\kappa n\right)+n\mathcal{B}\left(\kappa\right))$	$O(n^2\log^2{n})$	$O(\mathcal{R}+\log{n})$	SXDH, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/a77a39159fe44f24add31fbb190c604c)
ETHDKG	Sync.	1/2	❌	✅	$O(n\mathcal{B}(\kappa n))$	$O(n+t^2)$	$O(\mathcal{R})$	DDH, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/03fb580d9e924677a5aabf6a14b56b3e)
NIDKG	Sync.	1/2	❌	✅	$O(n\mathcal{B}(\kappa n))$	$O(n^3)$	$O(\mathcal{R})$	DDH, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/e735529baf1447eba0b5e0c9e2adf73c)
Canny and Sorkin - Practical Large scale DKG	Sync.	$1/2-\varepsilon$	❌	✅	$O(n\log^3{n} + \mathcal{B}(\log{n}))$	$O(n^2\log{n})$	$O(\mathcal{R})$	RO	CRS, PKI	Untitled (https://hermitsage.notion.site/73f7167557184f4e8c9cac8c48ac74a9)
Synchronous DKG without broadcasts	Sync.	1/2	❌	✅	$O(\kappa n^3\log{n})$	$O(nt^3)$	$O(1)$	DDH, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/7aaf1027dc6140e582113835605825ae)
Hybrid-DKG	Weak Sync.	1/3	❌	✅	$O(\kappa n^4)$	$O(n^4)$	$O(n)$	RO	CRS, PKI	Untitled (https://hermitsage.notion.site/1400941790fe4c0a8e2137389faae72d)
Asynchronous DKG	Async.	1/3	⁉️	✅	$O(\kappa n^4)$	$O(n^4)$	$O(n)$	DDH, RO	PKI	Untitled (https://hermitsage.notion.site/6ffe28dad3194d0a80ec0d15472a02a2)
Reaching consensus for DKG	Async.	1/3	❌	❌	$O(\kappa n^3\log{n})$	$O(n^3)$	$O(1)$	SXDH, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/9992f8921c564cc2a3d8a4903f8558db)
Gao et al. DKG	Async.	1/3	❌	❌	$O(\kappa n^3)$	$O(n^3)$	$O(1)$	SXDH, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/56b563d3fd4d47c0ba4ec03b9efead10)
Practical ADKG	Async.	1/3	❌	✅	$O(\kappa n^3)$	$O(n^4)$	$O(\log{n})$	DDH, DCR, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/2f443c9cc9044118aaa63615b1e39d44)

Notes

Fouque-Stern DKG (‣) claims adaptive security. It proves static security and sketches adaptive security. Is it still an adaptively secure DKG?
Pedersen DKG and JF-DKG (‣) both have a worst-case computation cost of $O(nt^3)$. This comes from all nodes $(n)$ have to verify $(2t)$ dealer complaints (in the first half, honest nodes are complaining against Byzantine dealers, and in the second half, the Byzantine nodes are complaining against honest dealers), each of which contains $t$ individual complaints, and each verification operation costs $t+1$ computations.
Pedersen DKG and JF-DKG (‣) have a worst-case communication complexity of $O(n\mathcal{B}(\kappa t))$ since each dealer has to post the commitments to the polynomials (size $O(\kappa t)$).
Neji DKG (‣) has a worst-case communication complexity of $O(n\mathcal{B}(\kappa))$. In their disputation protocols, $n-2$ nodes need to post some values.
Neji DKG (‣) has a worst-case computation complexity of $O(nt^3)$ since $n-2$ nodes verify $2t^2$ dealer complaints, in each of which there are $O(t)$ computation operations.

Problems 🧰

Different access structures
Separate parties from stake
Zero-knowledge circuit to make DKG publicly verifiable (GOAL: use in mainstream production systems)
Arbitrum is an L2 solution to execute contracts, Holy-grail DKG is a proposed L2 solution to perform DKG

Secret Sharing

Paper	Network Model	Fault tolerance	Adaptive adversary	Scalar secret	Comm. Complexity	Comp. Complexity	Round Complexity	Cryptographic Assumptions	Setup Assumptions	Notes
Feldman VSS	Sync.	1/2	✅	✅	$O(\mathcal{B}(\kappa t) + t\mathcal{B}(\kappa) + n\kappa)$	$O(nt)$	$O(1)$	DL		Untitled (https://hermitsage.notion.site/077bc422f2144385aa806cc14b16ee40)
Pedersen VSS	Sync.	1/2	✅	✅	$O(\mathcal{B}(\kappa t) + t\mathcal{B}(\kappa) + n\kappa)$	$O(nt)$	$O(1)$	DL	CRS	Untitled (https://hermitsage.notion.site/7d2368c8eabb4288823f325e5673519d)
Hybrid VSS	Weak Sync.	1/3	❌	✅	$O(\kappa n^2 +\mathcal{B}(1))$	$O(n^2)$	$O(\mathcal{R})$	DL, RO	CRS, PKI	Hybrid-VSS (Untitled (https://hermitsage.notion.site/1400941790fe4c0a8e2137389faae72d))
Cachin et al. - Async VSS	Async.	1/3	❌	✅	$O(\kappa n^3 )$	$O(n^2 )$	$O(1 )$	DL	PKI	Untitled (https://hermitsage.notion.site/8d99e2b4cd2c403a97471e55c28c7fd4)
eAVSS	Async.	1/3	✅	✅	$O(\kappa n^2 )$	$O(n^2 )$	$O(1 )$	DL, SXDH, q-SDH	CRS, PKI	Untitled (https://hermitsage.notion.site/b860080b34c54bfb90bbd73956366568)
VSSR	Weak Sync.	1/3	❌(/✅)	✅	$O(\kappa n^3 )$	$O(n^2 )$	$O(1 )$	DL, SXDH, q-SDH, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/9caea8674c3c40338e0d7d5e8712b001)
hbACSS	Async.	1/3	❌(/✅)	✅	$O(\kappa n^2\log{n} )$	$O(n^2 )$	$O(1 )$	DL, SXDH, q-SDH, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/de503bbd26f84b85b16342099c9d698c)
eVSS	Sync.	1/2	✅	✅	$O( t\mathcal{B}(\kappa) + n\kappa)$	$O(nt)$	$O(1)$	DL, SXDH, q-SDH	CRS, PKI	eVSS (Untitled (https://hermitsage.notion.site/bc91bf8576ac4bd4b4c66f213da6917c))
HAVEN	Async.	1/3	✅	✅	$O(\kappa n^2\log{n} )$	$O(n^2 )$	$O(1)$	DL, Bulletproof?	CRS, PKI	Untitled (https://hermitsage.notion.site/53725d1cabd94af797917a5dcf1a04b3)
Schoenmakers PVSS	Sync.	1/2	❌	❌	$O(\mathcal{B}(\kappa n) )$	$O(n^2t )$	$O(\mathcal{R} )$	DDH, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/c3501c34b0ce49b2903ef7835fc01b06)
Heidaravand et al. - HV09	Sync.	1/2	❌	❌	$O(\mathcal{B}(\kappa n) )$	$O(n^2t )$	$O(\mathcal{R} )$	SXDH	CRS, PKI	Untitled (https://hermitsage.notion.site/d50ca8e8ae164d1c89a3c558d1e946b1)
SCRAPE	Sync.	1/2	❌	❌	$O(\mathcal{B}(\kappa n) )$	$O(n^2 )$	$O(\mathcal{R} )$	SXDH	CRS, PKI	Untitled (https://hermitsage.notion.site/ba03ecbb9c6345489fa81ce3c7f76fff)
NIDKG	Sync.	1/2	❌	✅	$O(\mathcal{B}(\kappa n) )$	$O(n^2 )$	$O(\mathcal{R} )$	DDH, RO	CRS, PKI	Untitled (https://hermitsage.notion.site/e735529baf1447eba0b5e0c9e2adf73c)
Eurocrypt Gentry et al.
Towards Scalable threshold cryptosystems

Implementation Survey

Implementation	Language	Networking core	Network
https://github.com/anoma/ferveo	Rust	Tendermint	Sync.
https://github.com/dfinity/ic/tree/master/rs/crypto/internal/crypto_lib/threshold_sig/bls12_381/src/dkg	Rust	ICC	P. Sync.
https://github.com/kobigurk/aggregatable-dkg	Rust	🚫	🚫
https://github.com/drand/drand	Golang	Custom	Sync.
https://github.com/PhilippSchindler/ethdkg	Solidity	Ethereum	Sync.
https://github.com/orbs-network/dkg-on-evm	Solidity	Ethereum	Sync.
https://www.nongnu.org/dkgpg/	C	Custom	Sync.
https://github.com/gnosis/dkg	Golang	🚫	🚫
https://github.com/corestario/HERB	Golang	Cosmos	Sync.