Batch Decryption of Encrypted Short Messages and Its Application on Concurrent SSL Handshakes

  • Yongdong Wu
  • Feng Bao
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4318)


A public-key cryptosystem is usually used for key management, in particular to session key management. The paper presents a method for handling a batch of concurrent keys with homomorphic public-key cryptosystems such as RSA, Paillier and ElGamal. Theorematically, regardless Shacham and Boneh proved that it is impossible to provide batch RSA encryption of messages with a single certificate, the present result is positive when the messages are small. Practically, the present method is compliant to the de facto standard SSL/TLS handshake and increases the SSL system performance.


Batch Size Plain Text Connection Request Homomorphic Encryption Decryption Operation 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Fiat, A.: Batch RSA. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 75–88. Springer, Heidelberg (1990); See also Journal of Cryptology 10(2), 75–88 (1997)Google Scholar
  2. 2.
    Shacham, H., Boneh, D.: Improving SSL Handshake Performance via Batching. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 28–43. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  3. 3.
    Qi, F., Jia, W., Bao, F., Wu, Y.: Batching SSL/TLS Handshake Improved. In: Qing, S., Mao, W., López, J., Wang, G. (eds.) ICICS 2005. LNCS, vol. 3783, pp. 402–413. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  4. 4.
    Fouque, P.-A., Kunz-Jacques, S., Martinet, G., Muller, F., Valette, F.: Power Attack on Small RSA Public Exponent. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 339–353. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  5. 5.
    Catalano, D., Gennaro, R., Howgrave-Graham, N., Nguyen, P.Q.: Paillier’s Cryptosystem Revisited. In: ACM CCS, pp. 206–214 (2001)Google Scholar
  6. 6.
    Okamoto, T., Uchiyama, S.: A New Public-Key Cryptosystem as Secure as Factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 308–318. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  7. 7.
    Boneh, D., Joux, A., Nguyen, P.: Why Textbook ElGamal and RSA Encryption are Insecure. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 30–44. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  8. 8.
    Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 401–415. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  9. 9.
    Bao, F., Deng, R., Feng, P., Guo, Y., Wu, H.: Secure and Private Distribution of Online Video and several Related cryptographic Issues. In: Varadharajan, V., Mu, Y. (eds.) ACISP 2001. LNCS, vol. 2119, pp. 190–205. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  10. 10.
    Lemstra, A.K., Verheul, E.R.: Selecting Cryptographic Key Sizes. J. Cryptology 14(4), 255–293 (2001)MathSciNetGoogle Scholar
  11. 11.
    Brumley, D., Boneh, D.: Remote Timing Attacks are Practical. In: The 12th Usenix Security Symposium, pp. 1–13 (2003)Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Yongdong Wu
    • 1
  • Feng Bao
    • 1
  1. 1.System and Security DepartmentInstitute for Infocomm Research119613Singapore

Personalised recommendations