Graceful service degradation (or, how to know your payment is late)

ABSTRACT

When distributing digital content over a broadcast channel it's often necessary to revoke users whose access privileges have expired, thus preventing them from recovering the content. This works well when users make a conscious decision to leave the system or have misbehaved, but numerous cases exist in which the revocation is in error and users are consequently left with the often onerous burden of getting reinstated. We introduce a gradual form of revocation that we call service degradation that enables the content distributor to provide "cues" to the user in the form of degraded system performance. The cues alert the user to their impending revocation and allow them to take the necessary action to remain in the system. Our protocols build on techniques for broadcast encryption and spam-fighting to provide the appropriate form of service for this previously ignored class of users.

REFERENCES

• 1: M. Abadi, M. Burrows, M. Manasse and T. Wobber. Moderately hard, memory-bound functions. Proceedings of the 10th Annual Network and Distributed Systems Security Symposium, 2003.
• 2: Michel Abdalla , Yuval Shavitt , Avishai Wool, Key management for restricted multicast using broadcast encryption, IEEE/ACM Transactions on Networking (TON), v.8 n.4, p.443-454, Aug. 2000 [doi>10.1109/90.865073]
• 3: A. Andoni and J. Staddon. Graceful Service Degradation (or, How to Know your Payment is Late) (Full Version). Available at http://www.mit.edu/ andoni and http://www.parc.com/jstaddon
• 4: Nuttapong Attrapadung , Kazukuni Kobara, Broadcast encryption with short keys and transmissions, Proceedings of the 3rd ACM workshop on Digital rights management, October 27-27, 2003, Washington, DC, USA [doi>10.1145/947380.947388]
• 5: S. Berkovits. How to broadcast a secret. Advances in Cryptology --- Eurocrypt '91, volume 547 of LNCS, pages 535--541. Springer-Verlag, 1991.
• 6: R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, B. Pinkas. Multicast security: A taxonomy and efficient constructions. IEEE INFOCOM, 1999.
• 7: Directory of Online Schools, http://www.directoryofonlineschools.com
• 8: Y. Dodis and N. Fazio. Public key broadcast encryption for stateless receivers. ACM CCS Workshop on Digital Rights Management 2002.
• 9: C. Dwork, A. Goldberg and M. Naor. On memory-bound functions for fighting spam. Advances in Cryptology -- Crypto 2003.
• 10: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 11: Constantinos Dovrolis , Dimitrios Stiliadis, Relative differentiated services in the Internet: issues and mechanisms, Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.204-205, May 01-04, 1999, Atlanta, Georgia, United States
• 12: E. Engelking. Are you in favor of Microsoft's new XP licensing program? Tech Republic, May 4, 2001. http://techrepublic.com.com/5100-6270-1032935.html
• 13: Amos Fiat , Moni Naor, Broadcast encryption, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.480-491, January 1994, Santa Barbara, California, United States
• 14: C. Gentry, Z. Ramzan. RSA Accumulator Based Broadcast Encryption. 7th Information Security Conference, 2004.
• 15: Dani Halevy , Adi Shamir, The LSD Broadcast Encryption Scheme, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.47-60, August 18-22, 2002
• 16: Markus Jakobsson , Ari Juels, Proofs of Work and Bread Pudding Protocols, Proceedings of the IFIP TC6/TC11 Joint Working Conference on Secure Information Networks: Communications and Multimedia Security, p.258-272, September 20-21, 1999
• 17: Keyhole, http://www.keyhole.com
• 18: Noam Kogan , Yuval Shavitt , Avishai Wool, A Practical Revocation Scheme for Broadcast Encryption Using Smart Cards, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.225, May 11-14, 2003
• 19: Ravi Kumar , Sridhar Rajagopalan , Amit Sahai, Coding Constructions for Blacklisting Problems without Computational Assumptions, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.609-623, August 15-19, 1999
• 20: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 21: Moni Naor , Benny Pinkas, Efficient Trace and Revoke Schemes, Proceedings of the 4th International Conference on Financial Cryptography, p.1-20, February 20-24, 2000
• 22: Dalit Naor , Moni Naor , Jeffrey B. Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.41-62, August 19-23, 2001
• 23: R. L. Rivest , A. Shamir , D. A. Wagner, Time-lock Puzzles and Timed-release Crypto, Massachusetts Institute of Technology, Cambridge, MA, 1996
• 24: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 25: Doug R. Stinson, On Some Methods for Unconditionally Secure Key Distributionand Broadcast Encryption, Designs, Codes and Cryptography, v.12 n.3, p.215-243, Nov. 1997 [doi>10.1023/A:1008268610932]
• 26: U. C. Berkeley Extension Online. http://learn.berkeley.edu
• 27: D.M. Wallner, E.J. Harder, R.C. Agee. RFC 2627 -- Key management for multicast: Issues and architectures. Available at http://www.rfc-archive.org.
• 28: Chung Kei Wong , Mohamed Gouda , Simon S. Lam, Secure group communications using key graphs, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.68-79, August 31-September 04, 1998, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Formal models of communication

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Commercial services
      H.3.7 Digital Libraries
          Subjects: Dissemination

General Terms:
Algorithms, Security, Theory

Keywords:
broadcast encryption, copyright protection, degradation scheme, moderately-hard functions, revocation scheme