A Revocation Scheme Preserving Privacy

  • Łukasz Krzywiecki
  • Przemysław Kubiak
  • Mirosław Kutyłowski
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4318)


We introduce a scheme for anonymous user exclusion in an encrypted broadcast communication. It allows a broadcaster to change the transmission key with a single message broadcasted to N users so that all but z excluded users can retrieve the new key, and volume of the message is \(O{\mathcal ({\it z})}\). Our scheme is based on Shamir’s secret sharing method based on polynomials with dynamic coefficients and shares that evolve in time. No explicit ID’s and pseudonyms are used.


key broadcasting exclusion protocol anonymity 


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Fiat, A., Naor, M.: Broadcast encryption. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 480–491. Springer, Heidelberg (1994)Google Scholar
  2. 2.
    Naor, M., Pinkas, B.: Efficient trace and revoke schemes. In: Frankel, Y. (ed.) FC 2000. LNCS, vol. 1962, pp. 1–20. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  3. 3.
    Matsuzaki, N., Anzai, J., Matsumoto, T.: Light weight broadcast exclusion using secret sharing. In: Clark, A., Boyd, C., Dawson, E.P. (eds.) ACISP 2000. LNCS, vol. 1841, pp. 313–327. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  4. 4.
    Yoo, E.S., Jho, N.S., Cheon, J.H., Kim, M.H.: Efficient broadcast encryption using multiple interpolation methods. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 87–103. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  5. 5.
    Tzeng, W.G., Tzeng, Z.J.: A public-key traitor tracing scheme with revocation using dynamic shares. In: Kim, K.-c. (ed.) PKC 2001. LNCS, vol. 1992, pp. 207–224. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  6. 6.
    Dodis, Y., Fazio, N., Kiayias, A., Yung, M.: Scalable public-key tracing and revoking. In: PODC, pp. 190–199. ACM Press, New York (2003)Google Scholar
  7. 7.
    Dodis, Y., Fazio, N.: Public key trace and revoke scheme secure against adaptive chosen ciphertext attack. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 100–115. Springer, Heidelberg (2002)CrossRefGoogle Scholar
  8. 8.
    Kim, C.H., Hwang, Y.H., Lee, P.J.: Practical pay-tv scheme using traitor tracing scheme for multiple channels. In: Lim, C.H., Yung, M. (eds.) WISA 2004. LNCS, vol. 3325, pp. 264–277. Springer, Heidelberg (2005)CrossRefGoogle Scholar
  9. 9.
    Watanabe, Y., Numao, M.: Multi-round secure-light broadcast exclusion protocol with pre-processing. In: Snekkenes, E., Gollmann, D. (eds.) ESORICS 2003. LNCS, vol. 2808, pp. 85–99. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  10. 10.
    Cichoń, J., Krzywiecki, Ł., Kutyłowski, M., Wlaź, P.: Anonymous distribution of broadcast keys in cellular systems. In: Burmester, M., Yasinsac, A. (eds.) MADNES 2005. LNCS, vol. 4074, pp. 96–109. Springer, Heidelberg (2006)Google Scholar
  11. 11.
    Barth, A., Boneh, D., Waters, B.: Privacy in encrypted content distribution using private broadcast encryption. In: Di Crescenzo, G., Rubin, A. (eds.) FC 2006. LNCS, vol. 4107, pp. 52–64. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  12. 12.
    Boneh, D., Shen, E., Waters, B.: Strongly unforgeable signatures based on computational Diffie-Hellman. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 229–240. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  13. 13.
    Borzȩcki, P., Kabarowski, J., Kubiak, P., Kutyłowski, M., Zagórski, F.: Kleptographic weaknesses in Benaloh-Tuinstra protocol. In: ICSNC. IEEE Comp. Soc. Press, Los Alamitos (to appear, 2006)Google Scholar
  14. 14.
    Anonymity bibliography, Available from:
  15. 15.
    Naccache, D., Stern, J.: A new public-key cryptosystem. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 27–36. Springer, Heidelberg (1997)Google Scholar
  16. 16.
    Chaum, D., Antwerpen, H.V.: Undeniable signatures. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 212–216. Springer, Heidelberg (1990)Google Scholar
  17. 17.
    Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis. Springer, New York, Berlin (1980)Google Scholar
  18. 18.
    Bao, F., Deng, R.H., Zhu, H.: Variations of Diffie-Hellman problem. In: Qing, S., Gollmann, D., Zhou, J. (eds.) ICICS 2003. LNCS, vol. 2836, pp. 301–312. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  19. 19.
    von zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 1st edn. Cambridge University Press, Cambridge (1999)zbMATHGoogle Scholar
  20. 20.
    Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392–407. Springer, Heidelberg (2000)CrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Łukasz Krzywiecki
    • 1
  • Przemysław Kubiak
    • 1
  • Mirosław Kutyłowski
    • 1
  1. 1.Institute of Mathematics and Computer ScienceWrocław University of Technology 

Personalised recommendations