Victor Shoup's Research Papers

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

  2. The Twin Diffie-Hellman problem and applications, with D. Cash and E. Kiltz. Full length version of extended abstract in Proc. EUROCRYPT 2008. [pdf]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Victor Shoup's home page