Victor Shoup
Research Subjects
Victor Shoup has a total of 24 co-authors. Here are the top co-authors by number of shared publications:
- Sourav Das
University of Illinois at Urbana-Champaign
2 shared publications - Amit Agarwal
University of Illinois Urbana-Champaign
1 shared publication - Atsuki Momose
University of Illinois at Urbana-Champaign, Urbana, IL, USA
1 shared publication - Babak Poorebrahim Gilkalaye
Category Labs, New York, USA
1 shared publication - Daniel Sharifi
DFINITY Foundation
1 shared publication - Guru-Vamsi Policharla
Commonware, Inc., Palo Alto, California, USA
1 shared publication
Latest Publications
- Open Access
- 14 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 1447-1461
BTX and SimpleBTE: Efficient Batched Threshold Encryption
- 14 November 2026
- Published by Association for Computing Machinery (ACM)
- p. 1447-1461
Open AccessBTX and SimpleBTE: Efficient Batched Threshold Encryption
- Open Access
- 3 August 2026
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 3 (2)
Back to the future: simple threshold decryption secure against adaptive corruptions
We present a practical, non-interactive threshold decryption scheme. It can be proven CCA secure with respect to adaptive corruptions in the random oracle model under the decisional Diffie-Hellman assumption. Our scheme, called TDH2a, is a minor modification of the TDH2 scheme presented by Shoup and Gennaro at Eurocrypt 1998, which was proven secure against static corruptions under the same assumptions. The design and analysis of TDH2a are based on a straightforward extension of the simple information-theoretic argument underlying the security of the Cramer-Shoup encryption scheme presented at Crypto 1998. We also present another variant, TDH2abc, which offers a higher degree of backward compatibility with TDH2, allowing one to effectively "hot swap" TDH2abc in to replace TDH2 in a "live" system, without changing the public encryption key, so that any extant ciphertexts remain decryptable.
- 3 August 2026
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 3 (2)
Open AccessBack to the future: simple threshold decryption secure against adaptive corruptions
We present a practical, non-interactive threshold decryption scheme. It can be proven CCA secure with respect to adaptive corruptions in the random oracle model under the decisional Diffie-Hellman assumption. Our scheme, called TDH2a, is a minor modification of the TDH2 scheme presented by Shoup and Gennaro at Eurocrypt 1998, which was proven secure against static corruptions under the same assumptions. The design and analysis of TDH2a are based on a straightforward extension of the simple information-theoretic argument underlying the security of the Cramer-Shoup encryption scheme presented at Crypto 1998. We also present another variant, TDH2abc, which offers a higher degree of backward compatibility with TDH2, allowing one to effectively "hot swap" TDH2abc in to replace TDH2 in a "live" system, without changing the public encryption key, so that any extant ciphertexts remain decryptable.
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 155-166
Towards Reliable Broadcast with Optimal Communication and Round Complexity
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 155-166
Open AccessTowards Reliable Broadcast with Optimal Communication and Round Complexity
- 28 April 2025
- Published by Springer Nature
- p. 96-115
MiniCast: Minimizing the Communication Complexity of Reliable Broadcast
- 28 April 2025
- Published by Springer Nature
- p. 96-115
MiniCast: Minimizing the Communication Complexity of Reliable Broadcast
- Open Access
- 8 April 2025
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 2 (1)
The many faces of Schnorr: a toolkit for the modular design of threshold Schnorr signatures
Recently, a number of highly optimized threshold signing protocols for Schnorr signatures have been proposed. While these proposals contain important new techniques, some of them present and analyze these techniques in very specific contexts, making it less than obvious how these techniques can be adapted to other contexts, or combined with one another. The main goal of this paper is to abstract out and extend in various ways some of these techniques, building a toolbox of techniques that can be easily combined in different ways and in different contexts. To this end, we present security results for various “enhanced” modes of attack on the Schnorr signature scheme in the non-distributed setting, and we demonstrate how to reduce the security in the distributed threshold setting to these enhanced modes of attack in the non-distributed setting. This results in a very modular approach to protocol design and analysis, which can be used to easily design new threshold Schnorr protocols that enjoy better security and/or performance properties than existing ones.
- 8 April 2025
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 2 (1)
Open AccessThe many faces of Schnorr: a toolkit for the modular design of threshold Schnorr signatures
Recently, a number of highly optimized threshold signing protocols for Schnorr signatures have been proposed. While these proposals contain important new techniques, some of them present and analyze these techniques in very specific contexts, making it less than obvious how these techniques can be adapted to other contexts, or combined with one another. The main goal of this paper is to abstract out and extend in various ways some of these techniques, building a toolbox of techniques that can be easily combined in different ways and in different contexts. To this end, we present security results for various “enhanced” modes of attack on the Schnorr signature scheme in the non-distributed setting, and we demonstrate how to reduce the security in the distributed threshold setting to these enhanced modes of attack in the non-distributed setting. This results in a very modular approach to protocol design and analysis, which can be used to easily design new threshold Schnorr protocols that enjoy better security and/or performance properties than existing ones.
- Open Access
- 2 December 2024
- Published by Association for Computing Machinery (ACM)
- p. 3242-3256
Asynchronous Consensus without Trusted Setup or Public-Key Cryptography
Byzantine consensus is a fundamental building block in distributed cryptographic problems. Despite decades of research, most existing asynchronous consensus protocols require a strong trusted setup and expensive public-key cryptography. In this paper, we study asynchronous Byzantine consensus protocols that do not rely on a trusted setup and do not use public-key cryptography such as digital signatures. We give an Asynchronous Common Subset (ACS) protocol whose security is only based on cryptographic hash functions modeled as a random oracle. Our protocol has O(κn3) total communication and runs in expected O(1) rounds. The fact that we use only cryptographic hash functions also means that our protocol is post-quantum secure. The minimal use of cryptography and the small number of rounds make our protocol practical. We implement our protocol and evaluate it in a geo-distributed setting with up to 128 machines. Our experimental evaluation shows that our protocol is more efficient than the only other setup-free consensus protocol that has been implemented to date. En route to our asynchronous consensus protocols, we also introduce new primitives called asynchronous secret key sharing and cover gather, which may be of independent interest.
- 2 December 2024
- Published by Association for Computing Machinery (ACM)
- p. 3242-3256
Open AccessAsynchronous Consensus without Trusted Setup or Public-Key Cryptography
Byzantine consensus is a fundamental building block in distributed cryptographic problems. Despite decades of research, most existing asynchronous consensus protocols require a strong trusted setup and expensive public-key cryptography. In this paper, we study asynchronous Byzantine consensus protocols that do not rely on a trusted setup and do not use public-key cryptography such as digital signatures. We give an Asynchronous Common Subset (ACS) protocol whose security is only based on cryptographic hash functions modeled as a random oracle. Our protocol has O(κn3) total communication and runs in expected O(1) rounds. The fact that we use only cryptographic hash functions also means that our protocol is post-quantum secure. The minimal use of cryptography and the small number of rounds make our protocol practical. We implement our protocol and evaluate it in a geo-distributed setting with up to 128 machines. Our experimental evaluation shows that our protocol is more efficient than the only other setup-free consensus protocol that has been implemented to date. En route to our asynchronous consensus protocols, we also introduce new primitives called asynchronous secret key sharing and cover gather, which may be of independent interest.
- Open Access
A New Broadcast Primitive for BFT Protocols
Byzantine fault tolerant (BFT) protocol descriptions often assume application-layer networking primitives, such as best-effort and reliable broadcast, which are impossible to implement in practice in a Byzantine environment as they require either unbounded buffering of messages or giving up liveness, under certain circumstances. However, many of these protocols do not (or can be modified to not) need such strong networking primitives. In this paper, we define a new, slightly weaker networking primitive that we call abortable broadcast. We describe an implementation of this new primitive and show that it (1) still provides strong delivery guarantees, even in the case of network congestion, link or peer failure, and backpressure, (2) preserves bandwidth, and (3) enforces all data structures to be bounded even in the presence of malicious peers. The latter prevents out-of-memory DoS attacks by malicious peers, an issue often overlooked in the literature. The new primitive and its implementation are not just theoretical. We use them to implement the BFT protocols in the IC (Internet Computer), a publicly available blockchain network that enables replicated execution of general-purpose computation, serving hundreds of thousands of applications and their users.
Open AccessA New Broadcast Primitive for BFT Protocols
Byzantine fault tolerant (BFT) protocol descriptions often assume application-layer networking primitives, such as best-effort and reliable broadcast, which are impossible to implement in practice in a Byzantine environment as they require either unbounded buffering of messages or giving up liveness, under certain circumstances. However, many of these protocols do not (or can be modified to not) need such strong networking primitives. In this paper, we define a new, slightly weaker networking primitive that we call abortable broadcast. We describe an implementation of this new primitive and show that it (1) still provides strong delivery guarantees, even in the case of network congestion, link or peer failure, and backpressure, (2) preserves bandwidth, and (3) enforces all data structures to be bounded even in the presence of malicious peers. The latter prevents out-of-memory DoS attacks by malicious peers, an issue often overlooked in the literature. The new primitive and its implementation are not just theoretical. We use them to implement the BFT protocols in the IC (Internet Computer), a publicly available blockchain network that enables replicated execution of general-purpose computation, serving hundreds of thousands of applications and their users.
- Open Access
- 6 June 2024
- Published by Springer Nature in Journal of Cryptology
- Vol. 37 (3) , 1-58
Lightweight Asynchronous Verifiable Secret Sharing with Optimal Resilience
We present new protocols for Asynchronous Verifiable Secret Sharing for Shamir (i.e., threshold $$t<n$$ ) sharing of secrets. Our protocols: Use only “lightweight” cryptographic primitives, such as hash functions; Can share secrets over rings such as $${\mathbb {Z}}/(p^k)$$ as well as finite fields $$\mathbb {F}_q$$ ; Provide optimal resilience, in the sense that they tolerate up to $$t < n/3$$ corruptions, where n is the total number of parties; Are complete, in the sense that they guarantee that if any honest party receives their share then all honest parties receive their shares; Employ batching techniques, whereby a dealer shares many secrets in parallel and achieves an amortized communication complexity that is linear in n, at least on the “happy path”, where no party provably misbehaves.- 6 June 2024
- Published by Springer Nature in Journal of Cryptology
- Vol. 37 (3) , 1-58
Open AccessLightweight Asynchronous Verifiable Secret Sharing with Optimal Resilience
We present new protocols for Asynchronous Verifiable Secret Sharing for Shamir (i.e., threshold $$t<n$$ ) sharing of secrets. Our protocols: Use only “lightweight” cryptographic primitives, such as hash functions; Can share secrets over rings such as $${\mathbb {Z}}/(p^k)$$ as well as finite fields $$\mathbb {F}_q$$ ; Provide optimal resilience, in the sense that they tolerate up to $$t < n/3$$ corruptions, where n is the total number of parties; Are complete, in the sense that they guarantee that if any honest party receives their share then all honest parties receive their shares; Employ batching techniques, whereby a dealer shares many secrets in parallel and achieves an amortized communication complexity that is linear in n, at least on the “happy path”, where no party provably misbehaves. - 29 April 2024
- Published by Springer Nature
- p. 370-400
Fast Batched Asynchronous Distributed Key Generation
- 29 April 2024
- Published by Springer Nature
- p. 370-400
Fast Batched Asynchronous Distributed Key Generation
- 4 December 2008
- Published by Cambridge University Press (CUP)
- p. 306-326
Probabilistic primality testing
A Computational Introduction to Number Theory and Algebra - December 2008
- 4 December 2008
- Published by Cambridge University Press (CUP)
- p. 306-326
Probabilistic primality testing
A Computational Introduction to Number Theory and Algebra - December 2008