Victor Shoup's Research Papers

  1. 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]

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

  3. 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]

  4. 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]

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

  6. 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]

  7. 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]

  8. 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]

  9. 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]

  10. 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]

  11. 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]

  12. 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]

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

  14. 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]

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

  16. 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]

  17. 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]

  18. 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]

  19. 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]

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

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

  22. 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]

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

  24. 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]

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

  26. 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]

  27. 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]

  28. 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]

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

  30. 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]

  31. 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]

  32. 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]

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

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

  35. 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]

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

  37. 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]

  38. 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]

  39. 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]

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

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

  42. 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]

  43. 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]

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

  45. 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]

  46. 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]

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

  48. 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]

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

  50. 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]

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

Victor Shoup's home page