[{"abstract":[{"lang":"eng","text":"In this paper, we present the first Asynchronous Distributed Key Generation (ADKG) algorithm which is also the first distributed key generation algorithm that can generate cryptographic keys with a dual (f,2f+1)-threshold (where f is the number of faulty parties). As a result, using our ADKG we remove the trusted setup assumption that the most scalable consensus algorithms make. In order to create a DKG with a dual (f,2f+1)- threshold we first answer in the affirmative the open question posed by Cachin et al. [7] on how to create an Asynchronous Verifiable Secret Sharing (AVSS) protocol with a reconstruction threshold of f+1<k łe 2f+1, which is of independent interest. Our High-threshold-AVSS (HAVSS) uses an asymmetric bivariate polynomial to encode the secret. This enables the reconstruction of the secret only if a set of k nodes contribute while allowing an honest node that did not participate in the sharing phase to recover his share with the help of f+1 honest parties. Once we have HAVSS we can use it to bootstrap scalable partially synchronous consensus protocols, but the question on how to get a DKG in asynchrony remains as we need a way to produce common randomness. The solution comes from a novel Eventually Perfect Common Coin (EPCC) abstraction that enables the generation of a common coin from n concurrent HAVSS invocations. EPCC's key property is that it is eventually reliable, as it might fail to agree at most f times (even if invoked a polynomial number of times). Using EPCC we implement an Eventually Efficient Asynchronous Binary Agreement (EEABA) which is optimal when the EPCC agrees and protects safety when EPCC fails. Finally, using EEABA we construct the first ADKG which has the same overhead and expected runtime as the best partially-synchronous DKG (O(n4) words, O(f) rounds). As a corollary of our ADKG, we can also create the first Validated Asynchronous Byzantine Agreement (VABA) that does not need a trusted dealer to setup threshold signatures of degree n-f. Our VABA has an overhead of expected O(n2) words and O(1) time per instance, after an initial O(n4) words and O(f) time bootstrap via ADKG."}],"day":"30","publication_status":"published","oa_version":"Preprint","page":"1751–1767","status":"public","date_updated":"2024-02-22T13:10:45Z","title":"Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures","external_id":{"isi":["000768470400104"]},"publication":"Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security","main_file_link":[{"url":"https://eprint.iacr.org/2019/1015","open_access":"1"}],"scopus_import":"1","citation":{"apa":"Kokoris Kogias, E., Malkhi, D., &#38; Spiegelman, A. (2020). Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. In <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i> (pp. 1751–1767). Virtual, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3372297.3423364\">https://doi.org/10.1145/3372297.3423364</a>","short":"E. Kokoris Kogias, D. Malkhi, A. Spiegelman, in:, Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, 2020, pp. 1751–1767.","ista":"Kokoris Kogias E, Malkhi D, Spiegelman A. 2020. Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. CCS: Computer and Communications Security, 1751–1767.","mla":"Kokoris Kogias, Eleftherios, et al. “Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.” <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>, Association for Computing Machinery, 2020, pp. 1751–1767, doi:<a href=\"https://doi.org/10.1145/3372297.3423364\">10.1145/3372297.3423364</a>.","ama":"Kokoris Kogias E, Malkhi D, Spiegelman A. Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. In: <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>. Association for Computing Machinery; 2020:1751–1767. doi:<a href=\"https://doi.org/10.1145/3372297.3423364\">10.1145/3372297.3423364</a>","chicago":"Kokoris Kogias, Eleftherios, Dahlia Malkhi, and Alexander Spiegelman. “Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.” In <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>, 1751–1767. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3372297.3423364\">https://doi.org/10.1145/3372297.3423364</a>.","ieee":"E. Kokoris Kogias, D. Malkhi, and A. Spiegelman, “Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures,” in <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>, Virtual, United States, 2020, pp. 1751–1767."},"date_published":"2020-10-30T00:00:00Z","_id":"10556","oa":1,"author":[{"first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"},{"first_name":"Dahlia","full_name":"Malkhi, Dahlia","last_name":"Malkhi"},{"first_name":"Alexander","full_name":"Spiegelman, Alexander","last_name":"Spiegelman"}],"type":"conference","year":"2020","publisher":"Association for Computing Machinery","doi":"10.1145/3372297.3423364","language":[{"iso":"eng"}],"isi":1,"publication_identifier":{"isbn":["978-1-4503-7089-9"]},"quality_controlled":"1","month":"10","conference":{"location":"Virtual, United States","name":"CCS: Computer and Communications Security","start_date":"2020-11-09","end_date":"2020-11-13"},"article_processing_charge":"No","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","acknowledgement":"We would like to thank Ittai Abraham for the discussions and guidance during the initial conception of the project, especially for HAVSS. Furthermore, we would like to thank the anonymous reviewers for pointing out the relevance of this work to MPC protocols.","department":[{"_id":"ElKo"}],"date_created":"2021-12-16T13:23:27Z"},{"main_file_link":[{"url":"https://patents.google.com/patent/US10581613B2/en","open_access":"1"}],"month":"03","application_date":"2017-06-09","title":"Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods","related_material":{"link":[{"url":"https://patents.google.com/patent/US20180359096A1/en","relation":"earlier_version"}]},"citation":{"chicago":"Ford, Bryan, Linus Gasse, Eleftherios Kokoris Kogias, and Philipp Jovanovic. “Cryptographically Verifiable Data Structure Having Multi-Hop Forward and Backwards Links and Associated Systems and Methods,” 2020.","ieee":"B. Ford, L. Gasse, E. Kokoris Kogias, and P. Jovanovic, “Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods.” 2020.","mla":"Ford, Bryan, et al. <i>Cryptographically Verifiable Data Structure Having Multi-Hop Forward and Backwards Links and Associated Systems and Methods</i>. 2020.","apa":"Ford, B., Gasse, L., Kokoris Kogias, E., &#38; Jovanovic, P. (2020). Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods.","short":"B. Ford, L. Gasse, E. Kokoris Kogias, P. Jovanovic, (2020).","ista":"Ford B, Gasse L, Kokoris Kogias E, Jovanovic P. 2020. Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods.","ama":"Ford B, Gasse L, Kokoris Kogias E, Jovanovic P. Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods. 2020."},"department":[{"_id":"ElKo"}],"date_created":"2021-12-16T13:28:59Z","applicant":["Ecole Polytechnique Federale de Lausanne"],"article_processing_charge":"No","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","extern":"1","_id":"10557","oa":1,"ipn":"10581613","author":[{"full_name":"Ford, Bryan","first_name":"Bryan","last_name":"Ford"},{"last_name":"Gasse","first_name":"Linus","full_name":"Gasse, Linus"},{"last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","full_name":"Kokoris Kogias, Eleftherios","first_name":"Eleftherios"},{"last_name":"Jovanovic","first_name":"Philipp","full_name":"Jovanovic, Philipp"}],"abstract":[{"text":"Data storage and retrieval systems, methods, and computer-readable media utilize a cryptographically verifiable data structure that facilitates verification of a transaction in a decentralized peer-to-peer environment using multi-hop backwards and forwards links. Backward links are cryptographic hashes of past records. Forward links are cryptographic signatures of future records that are added retroactively to records once the target block has been appended to the data structure.","lang":"eng"}],"day":"03","date_published":"2020-03-03T00:00:00Z","oa_version":"Published Version","year":"2020","date_updated":"2021-12-21T10:04:50Z","type":"patent","status":"public","ipc":" H04L9/3247 ; G06Q20/29 ; G06Q20/382 ; H04L9/3236","publication_date":"2020-03-03"}]