Victor Shoup's Research Papers

  1. A New Broadcast Primitive for BFT Protocols, with Manu Drijvers, Tim Gretler, Yotam Harchol, Tobias Klenze, Ognjen Maric, Stefan Neamtu, Yvonne-Anne Pignolet, Rostislav Rumenov, and Daniel Sharifi. October 2024. [arxiv]

  2. Blue fish, red fish, live fish, dead fish. August 2024. [eprint]

  3. A Theoretical Take on a Practical Consensus Protocol. May 2024. [eprint]

  4. Asynchronous Consensus without Trusted Setup or Public-Key Cryptography, with Sourav Das, Sisi Duan, Shengqi Liu, Atsuki Momose, and Ling Ren. May 2024. Extended abstract in ACM CCS 2024. [eprint]

  5. BoLD: Fast and Cheap Dispute Resolution, with Mario M. Alvarez, Henry Arneson, Ben Berger, Lee Bousfield, Chris Buckland, Yafah Edelman, Edward W. Felten, Daniel Goldman, Raul Jordan, Mahimna Kelkar, Akaki Mamageishvili, Harry Ng, Aman Sanghi, and Terence Tsao. April 2024. Extended abstract in AFT 2024. [arxiv]

  6. MiniCast: Minimizing the Communication Complexity of Reliable Broadcast, with Thomas Locher. April 2024. [eprint]

  7. Sing a song of Simplex. December 2023. Extended abstract in DISC 2024. [eprint]

  8. Fast batched asynchronous distributed key generation, with Jens Groth. July 2023. Extended abstract in Eurocrypt 2024. [eprint]

  9. The many faces of Schnorr. June 2023. [eprint]

  10. vetKeys: How a Blockchain Can Keep Many Secrets, with Andrea Cerulli, Aisling Connolly, Gregory Neven, and Franz-Stefan Preiss. April 2023. [eprint]

  11. Lightweight Asynchronous Verifiable Secret Sharing with Optimal Resilience, with Nigel Smart. April 2023. Also in J. Cryptology 37(3), 2024. [eprint]

  12. Proof of history: what is it good for? (An opinion piece). May 2022. [pdf]

  13. Design and analysis of a distributed ECDSA signing service, with Jens Groth. April 2022. Revised February 2023. [eprint] [pdf]

  14. On the security of ECDSA with additive key derivation and presignatures, with Jens Groth. October2021, revised April 2022. Extended abstract in Eurocrypt 2022. [eprint] [pdf]

  15. Internet Computer Consensus, with Jan Camenisch, Manu Drijvers, Timo Hanke, Yvonne-Anne Pignolet, and Dominic Williams. May 2021. Extended abstract in PODC 2022. [eprint] [pdf]

  16. Arithmetic Software Libraries, originally writen January 2020, to be published in revised form in Computational Cryptography. [pdf]

  17. Bootstrapping for HElib, with Shai Halevi. Eurocrypt 2015; revised October 2020; also in J. Cryptology 34(7), 2021. [pdf]

  18. Design and implementation of HElib: a homomorphic encryption library, with Shai Halevi. November 2020. [pdf]

  19. Security analysis of SPAKE2+. March 12, 2020. Full length version of extended abstract in TCC 2020. [pdf]

  20. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme, with Shai Halevi and Yuriy Polyakov. Topics in Cryptology -- CT-RSA 2019. [pdf]

  21. Doing Real Work with FHE: The Case of Logistic Regression, with L.H. Crawford, Craig Gentry, Shai Halevi and Daniel Platt. Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 2018. [pdf]

  22. Faster Homomorphic Linear Transformations in HElib, with Shai Halevi. Crypto 2018. [pdf]

  23. Implementing BP-obfuscation using graph-induced encoding, with Shai Halevi, Tzipora Halevi, Noah Stephens-Davidowitz. ACM CCS 2017. [pdf]

  24. Algorithms in HElib, with Shai Halevi. Eurocrypt 2014. [pdf]

  25. Practical and employable protocols for UC-Secure circuit evaluation over Zn, with J. Camenisch and R. Enderlein. Full version of extended abstract at ESORICS 2013. [pdf]

  26. Practical chosen ciphertext secure encryption from factoring, with D. Hofheinz and E. Kilz. J. Cryptology 26(1), pp. 102-118, 2012. [pdf]

  27. A Framework for Practical Universally Composable Zero-Knowledge Protocols, with J. Camensisch and S. Krenn. Asiacrypt 2011. [pdf]

  28. GNUC: A New Universal Composability Framework, with D. Hofheinz. Preprint, June 6, 2011; updated, Dec. 11, 2012; J. Cryptology (2013). [pdf]

  29. Anonymous Credentials on Java Card, with P. Bichsel, J. Camenisch, and T. Gross. In Proc. 21st Fraunhofer SIT-Smartcard Workshop 2011. [pdf]

  30. Credential authenticated identification and key exchange, with J. Camenisch, N. Casati, and T. Gross. Full length version of extended abstract in Proc. CRYPTO 2010. [pdf]

  31. Simple and efficient public-key encryption from computational Diffie-Hellman in the standard model, with K. Haralambiev, T. Jager, and E. Kiltz. Full length version of extended abstract in Proc. PKC 2010. [pdf]

  32. Anonymous credentials on a standard Java Card, with P. Bichsel, J. Camenisch, and T. Gross. In ACM CCS 2009. [pdf]

  33. A new and improved paradigm for hybrid encryption secure against chosen-ciphertext attack, with Y. Desmedt, R. Gennaro, and K. Kurosawa. J. Cryptology 23(1):91-120, 2010. [pdf]

  34. A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks, with J. Camenisch and N. Chandran. Full length version of extended abstract in Proc. Eurocrypt 2009. [pdf]

  35. Efficient constructions of composable commitments and zero-knowledge proofs, with Y. Dodis and S. Walfish. Full length version of extended abstract in Proc. CRYPTO 2008. [pdf]

  36. The Twin Diffie-Hellman problem and applications, with D. Cash and E. Kiltz. Full length version of extended abstract in Proc. EUROCRYPT 2008. Also in J. Cryptology 22(4):470-504, 2009. [pdf]

  37. Stateful public-key cryptosystems: how to encrypt with one 160-bit exponentiation, with M. Bellare and T. Kohno. Full lengh version of extended abstract in Proc. ACM CCS 2006. [pdf]

  38. Sequences of games: a tool for taming complexity in security proofs, manuscript, Nov. 30, 2004. Revised, May 27, 2005; Jan. 18, 2006. [pdf]

  39. A note on an encryption scheme of Kurosawa and Desmedt, with R. Gennaro, manuscript, August 10, 2004. Revised, May 18, 2005. [pdf]

    This result was published as part of the extended abstract "Tag-KEM/DEM: A new framework for hybrid encryption and a new analysis of Kurosawa-Desmedt KEM", by Abe, Gennaro, Kurosawa, and Shoup, in Proc. Eurocrypt 2005. [pdf]

  40. Anonymous identification in ad-hoc groups, with Y. Dodis, A. Kiayias, and A. Nicolosi. Full lengh version of extended abstract in Proc. Eurocrypt 2004. [pdf]

  41. A secure signature scheme from bilinear maps, with Dan Boneh and Ilya Mironov, in Proc. RSA-CT 2003. [pdf] [ps]

  42. Practical Verifiable Encryption and Decryption of Discrete Logarithms, with J. Camenisch. Full length version of extended abstract in Proc. Crypto 2003. Updated, August 22, 2003. [pdf] [ps]

  43. Efficient computation modulo a shared secret with application to the generation of shared safe-prime products, with J. Algesheimer and J. Camenisch. Full length version of the extended abstract in Proc. Crypto 2002. [pdf] [ps]

  44. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack, with R. Cramer, manuscript, December 17, 2001. Updated, August 14, 2003. SIAM Journal of Computing 33:167-226, 2003. [pdf] [ps]

  45. Universal hash proofs and a paradigm for chosen ciphertext secure public key encryption, with R. Cramer. Full length version of the extended abstract in Proc. Eurocrypt 2002. [pdf] [ps]

  46. A proposal for an ISO standard for public key encryption (version 2.1), manuscript, December 20, 2001. [pdf] [ps]

    Older versions: [version 2.0 pdf] [version 2.0 ps] [version 1.1 pdf] [version 1.1 ps] [version 1.0 pdf] [version 1.0 ps]

  47. Secure and efficient asynchronous broadcast protocols, with C. Cachin, K. Kursawe, and F. Petzold, manuscript, March 7, 2001. Full length version of the extended abstract in Proc. Crypto 2001. [pdf] [ps]

  48. Optimistic asynchronous atomic broadcast. with K. Kursawe, manuscript, March 6, 2001. Revised version, April 19, 2002. Full length version of the extended abstract in ICALP 2005. [pdf] [ps]

  49. OAEP reconsidered, manuscript, November 16, 2000. Revised September 18, 2001. Full length version of the extended abstract in Proc. Crypto 2001. [pdf] [ps]

  50. Factorization in Z[x]: the searching phase, with J. Abbott and P. Zimmermann, in Proc. 2000 International Symposium on Symbolic and Algebraic Computation. [pdf] [ps]

  51. ACE: The Advanced Cryptographic Engine, with T. Schweinberger, manuscript, March 2000. Revised, August 14, 2000. [pdf] [ps]

  52. Random oracles in Constantinople: practical asynchronous Byzantine agreement using cryptography, with C. Cachin and K. Kursawe. Full length version of the extended abstract in Proc. 2000 Principles of Distributed Computing. Revised, August 14, 2000. [pdf] [ps]

  53. Algorithms for exponentiation in finite fields, with S. Gao, J. von zur Gathen, and D. Panario, Journal of Symbolic Computation 29:879-889, 2000. [pdf] [ps]

  54. A composition theorem for universal one-way hash functions, in Proc. Eurocrypt 2000; this is a revised version of IBM Research Report RZ 3147 (June 21 1999). [pdf] [ps]

  55. Using hash functions as a hedge against chosen ciphertext attack, in Proc. Eurocrypt 2000; this is a revised version of IBM Research Report RZ 3139 (June 21 1999). [pdf] [ps]

  56. Practical threshold signatures, in Proc. Eurocrypt 2000; this is a revised version of IBM Research Report RZ 3121 (April 1999). [pdf] [ps]

  57. On formal models for secure key exchange (version 4), November 15, 1999 revision of IBM Research Report RZ 3120 (April 1999). [pdf] [ps]

  58. Signature schemes based on the Strong RSA Assumption, with R. Cramer, ACM Transactions on Information and System Security (ACM TISSEC) 3(3):161-185, 2000; extended abstract in Proc. 6th ACM Conf. on Computer and Communications Security, 1999. [pdf] [ps]

  59. Why chosen ciphertext security matters, IBM Research Report RZ 3076, November, 1998. This is an expository paper. [pdf] [ps]

  60. Efficient Computation of Minimal Polynomials in Algebraic Extension of Finite Fields, in Proc. 1999 International Symposium on Symbolic and Algebraic Computation. This is a revision with corrections of the November, 1998 version. [pdf] [ps]

  61. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, with R. Cramer, in Proc. Crypto '98. [pdf] [ps]

  62. Optimistic fair exchange of digital signatures, with N. Asokan and M. Waidner, IEEE Journal on Selected Areas in Communications 18(4):593-610, 2000; extended abstract in Proc. Eurocrypt '98. [pdf] [ps]

  63. Securing threshold cryptosystems against chosen ciphertext attack, with R. Gennaro, IBM Research Report RZ 2974, 1997. J. Cryptology 15(2):75-96, 2002. Extended abstract in Proc. Eurocrypt '98. [pdf] [ps]

  64. Fast polynomial factorization over high algebraic extensions of finite fields, with E. Kaltofen, in Proc. 1997 International Symposium on Symbolic and Algebraic Computation. [pdf] [ps]

  65. Private information storage, with R. Ostrovsky, in Proc. 29th ACM Symposium on Theory of Computation, pp. 294-303, 1997. [pdf] [ps]

  66. Lower bounds for discrete logarithms and related problems, in Proc. Eurocrypt '97, pp. 256-266, 1997. This is a revision of the conference version. [pdf] [ps]

  67. On fast and provably secure message authentication based on universal hashing, in Proc. Crypto '96, pp. 313-328, 1996. This contains some corrections to the conference version. [pdf] [ps]

  68. On the security of a practical identification scheme, J. Cryptology 12(4):247-260, 1999; extended abstract in Proc. Eurocrypt '96, pp. 344-353, 1996. [pdf] [ps]

  69. Session-key distrubution using smart cards, with A. Rubin, in Proc. Eurocrypt '96, pp. 321-31, 1996. [pdf] [ps]

  70. A note on session-key distrubution using smart cards, manuscript, 1996. This contains some corrections and modifications to the previous paper. [pdf] [ps]

  71. Subquadratic-time factorization of polynomials over finite fields, with E. Kaltofen, Mathematics of Computation 67(223):1179-1197, 1998; extended abstract in Proc. 27th ACM Symposium on Theory of Computation, 1995. [pdf] [ps]

  72. A new polynomial factorization algorithm and its implementation, Journal of Symbolic Computation 20:363-397, 1995. [pdf] [ps]

  73. Constructing nonresidues in finite fields and the Extended Riemann Hypothesis, with J. Buchmann, Mathematics of Computation 65(215):1311-1326, 1996; extended abstract in Proc. 23rd ACM Symposium on Theory of Computation, pp. 72-79, 1991. [pdf] [ps]

  74. Fast construction of irreducible polynomials over finite fields, Journal of Symbolic Computation 17:371-391, 1994; extended abstract in Proc. 4th Annual Symposium on Discrete Algorithms, pp. 484-492, 1993. [pdf] [ps]

  75. Counting the number of points on elliptic curves of characteristic greater than three, with F. Lehmann, M. Mauerer, and V. Mueller, in Proc. First Algorithmic Number Theory Symposium, pp. 60-70, 1994. [pdf] [ps]

  76. Primality testing with fewer random bits, with R. Peralta, Computational Complexity 3:355-367, 1993. [pdf] [ps]

  77. Factoring polynomials over finite fields: asymptotic complexity vs. reality, in Proc. IMACS Symposium, Lille, France, 1993. [pdf] [ps]

  78. Computing Frobenius maps and factoring polynomials, with J. von zur Gathen, Computational Complexity 2:187-224, 1992; extended abstract in Proc. 24th ACM Symposium on Theory of Computing, pp. 97-105, 1992. [pdf] [ps]

  79. Searching for primitive roots in finite fields, Mathematics of Computation 58:369-380, 1992; extended abstract in Proc. 22nd ACM Symposium on Theory of Computation, pp. 546-554, 1990. [pdf] [ps]

  80. Smoothness and factoring polynomials over finite fields, Information Processing Letters 39:39-42, 1991. [pdf] [ps]

  81. A fast deterministic algorithm for factoring polynomials over finite fields of small characteristic, in Proc. 1991 International Symposium on Symbolic and Algebraic Computation, pp. 14-21, 1991. The results in this paper were later published in the paper ``Computing Frobenius maps and factoring polynomials'' above. [pdf] [ps]

  82. Lower bounds for polynomial evaluation and interpolation problems, with R. Smolensky, Computational Complexity, 6:301-311, 1997; preliminary version in Proc. 31st Annual Symposium on Foundations of Computer Science, pp. 378-383, 1991. [pdf] [ps]

  83. On the deterministic complexity of factoring polynomials over finite fields, Information Processing Letters 33:261-267, 1990. [pdf] [ps]

  84. Instance-hiding proof systems, with D. Beaver, J. Feigenbaum, R. Ostrovsky, preprint, 1993. This paper subsumes "Hiding instances in zero-knowledge proof systems," with D. Beaver and J. Feigenbaum, in Proc. Crypto '90, pp. 309-321, 1990. [pdf] [ps]

  85. Factoring polynomials using fewer random bits, with E. Bach, Journal of Symbolic Computation 9:229-239, 1990. [pdf] [ps]

  86. New algorithms for finding irreducible polynomials over finite fields, Mathematics of Computation 54:435-447, 1990; extended abstract in Proc. 29th Annual Symposium on Foundations of Computer Science, pp. 283-290, 1988. [pdf] [ps]

  87. Removing Randomness from Computational Number Theory, Ph. D. Thesis, University of Wisconsin, 1989. [pdf] [ps]

Victor Shoup's home page