Rethinking accountable privacy supporting services: extended abstract

ABSTRACT

As privacy concerns among consumers rise, service providers will increasingly want to provide services that support privacy enhancing technologies. At the same time, providers of commercial services require the security of identifying misbehaving users. For instance, users that do not pay their bill can be held accountable for their behavior. We propose a scheme that permits privacy support while retaining accountability. In our proposed scheme an honest user may enjoy full anonymity, but dishonest users who do not pay their bill have their identity revealed. In contrast to existing revocable anonymity systems, our proposed scheme requires less trust in an external authority, while simultaneously making accountability easier (and less costly) to achieve. We contribute the concept of a time capsule, that is, a verifiable encryption with timed and revocable decryptability.

REFERENCES

• 1: M. Abdalla, M. Bellare, D. Catalano, E. Kiltz, T. Kohno, T. Lange, J. Malone-Lee, G. Neven, P. Paillier, and H. Shi. Searchable encryption revisited: Consistency properties, relation to anonymous ibe, and extensions. In V. Shoup, editor, Advances in Cryptology -- CRYPTO 2005, volume 3621 of Lecture Notes in Computer Science, pages 205--222. Springer Verlag, 2005.
• 2: Giuseppe Ateniese , Jan Camenisch , Marc Joye , Gene Tsudik, A Practical and Provably Secure Coalition-Resistant Group Signature Scheme, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.255-270, August 20-24, 2000
• 3: D. Boneh, X. Boyen, and H. Shacham. Short group signatures. In M. K. Franklin, editor, Advances in Cryptology CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 41--55. Springer Verlag, 2004.
• 4: F. Boudot. Efficient proofs that a committed number lies in an interval. In B. Preneel, editor, Advances in Cryptology EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 431--444. Springer Verlag, 2000.
• 5: Stefan A. Brands, An Efficient Off-line Electronic Cash System Based On The Representation Problem., CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1993
• 6: Stefan A. Brands, Restrictive blinding of secret-key certificates, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1995
• 7: Stefan A. Brands, Secret-key certificates, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1995
• 8: S. Brands. Rapid demonstration of linear relations connected by boolean operators. In W. Fumy, editor, Advances in Cryptology -- EUROCRYPT '97, volume 1233 of Lecture Notes in Computer Science, pages 318--333. Springer Verlag, 1997.
• 9: Stefan A. Brands, Rethinking Public Key Infrastructures and Digital Certificates: Building in Privacy, MIT Press, Cambridge, MA, 2000
• 10: Jan Camenisch , Susan Hohenberger , Markulf Kohlweiss , Anna Lysyanskaya , Mira Meyerovich, How to win the clonewars: efficient periodic n-times anonymous authentication, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180431]
• 11: J. Camenisch, S. Hohenberger, and A. Lysyanskaya. Compact E-cash. In R. Cramer, editor, Advances in Cryptology -- Eurocrypt 2005, volume 3494 of Lecture Notes in Computer Science, pages 302--321. Springer, 2005.
• 12: J. Camenisch, M. Kohlweiss, A. R. Durán, and C. Sheedy. Public key encryption with oblivious keyword search and its application to data retention. IBM Research Report RZ 3708, IBM Research, May 2008. http://domino.research.ibm.com/library/cyberdig.nsf/index.html.
• 13: Jan Camenisch , Anna Lysyanskaya, An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.93-118, May 06-10, 2001
• 14: J. Camenisch and A. Lysyanskaya. A signature scheme with efficient protocols. In S. Cimato, C. Galdi, and G. Persiano, editors, Security in Communication Networks, Third International Conference, SCN 2002, volume 2576 of Lecture Notes in Computer Science, pages 268--289. Springer Verlag, 2003.
• 15: J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In M. K. Franklin, editor, Advances in Cryptology -- CRYPTO 2004, volume 3152 of Lecture Notes in Computer Science, pages 56--72. Springer Verlag, 2004.
• 16: J. Camenisch and M. Michels. Proving in zero-knowledge that a number n is the product of two safe primes. Technical Report RS-98-29, BRICS, Departement of Computer Science, University of Aarhus, Nov. 1998.
• 17: J. Camenisch and M. Michels. Proving in zero-knowledge that a number n is the product of two safe primes. In J. Stern, editor, Advances in Cryptology -- EUROCRYPT '99, volume 1592 of Lecture Notes in Computer Science, pages 107--122. Springer Verlag, 1999.
• 18: Jan Camenisch , Markus Michels, Separability and Efficiency for Generic Group Signature Schemes, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.413-430, August 15-19, 1999
• 19: J. Camenisch and V. Shoup. Practical verifiable encryption and decryption of discrete logarithms. In D. Boneh, editor, Advances in Cryptology -- CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 126--144, 2003.
• 20: Jan Camenisch , Markus Stadler, Efficient Group Signature Schemes for Large Groups (Extended Abstract), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.410-424, August 17-21, 1997
• 21: J. L. Camenisch. Group Signature Schemes and Payment Systems Based on the Discrete Logarithm Problem. PhD thesis, ETH Zürich, 1998. Diss. ETH No. 12520, Hartung Gorre Verlag, Konstanz.
• 22: A. Chan, Y. Frankel, and Y. Tsiounis. Easy come -- easy go divisible cash. In K. Nyberg, editor, Advances in Cryptology EUROCRYPT '98, volume 1403 of Lecture Notes in Computer Science, pages 561--575. Springer Verlag, 1998.
• 23: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 24: D. Chaum. Blind signatures for untraceable payments. In D. Chaum, R. L. Rivest, and A. T. Sherman, editors, Advances in Cryptology -- Proceedings of CRYPTO '82, pages 199--203. Plenum Press, 1983.
• 25: David Chaum, Security without identification: transaction systems to make big brother obsolete, Communications of the ACM, v.28 n.10, p.1030-1044, Oct. 1985 [doi>10.1145/4372.4373]
• 26: David Chaum , Jan-Hendrik Evertse, A secure and privacy-protecting protocol for transmitting personal information between organizations, Proceedings on Advances in cryptology---CRYPTO '86, p.118-167, January 1987, Santa Barbara, California, United States
• 27: David Chaum , Torben P. Pedersen, Wallet Databases with Observers, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.89-105, August 16-20, 1992
• 28: D. Chaum and E. van Heyst. Group signatures. In D. W. Davies, editor, Advances in Cryptology -- EUROCRYPT '91, volume 547 of Lecture Notes in Computer Science, pages 257--265. Springer-Verlag, 1991.
• 29: Ronald Cramer , Ivan Damgård , Berry Schoenmakers, Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.174-187, August 21-25, 1994
• 30: I. Damgård and E. Fujisaki. An integer commitment scheme based on groups with hidden order. http://eprint.iacr.org/2001, 2001.
• 31: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 32: Yair Frankel , Yiannis Tsiounis , Moti Yung, Fair Off-Line e-cash Made Easy, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.257-270, October 18-22, 1998
• 33: Atsushi Fujioka , Tatsuaki Okamoto , Kazuo Ohta, A Practical Secret Voting Scheme for Large Scale Elections, Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.244-251, December 13-16, 1992
• 34: Eiichiro Fujisaki , Tatsuaki Okamoto, Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.16-30, August 17-21, 1997
• 35: Shafi Goldwasser , Silvio Micali , Ronald L. Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, v.17 n.2, p.281-308, April 1988 [doi>10.1137/0217017]
• 36: M. Green and S. Hohenberger. Blind identity-based encryption and simulatable oblivious transfer. In ASIACRYPT, pages 265--282, 2007.
• 37: Aggelos Kiayias , Moti Yung, Secure scalable group signature with dynamic joins and separable authorities, International Journal of Security and Networks, v.1 n.1/2, p.24-45, September 2006 [doi>10.1504/IJSN.2006.010821]
• 38: A. Kiayias, M. Yung, and Y. Tsiounis. Traceable signatures. In C. Cachin and J. Camenisch, editors, Advances in Cryptology -- EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 571--589. Springer, 2004.
• 39: Moni Naor , Benny Pinkas , Reuban Sumner, Privacy preserving auctions and mechanism design, Proceedings of the 1st ACM conference on Electronic commerce, p.129-139, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337028]
• 40: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 41: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 42: C. P. Schnorr. Efficient signature generation for smart cards. Journal of Cryptology, 4(3):239--252, 1991.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Security

Keywords:
accountability, anonymous credential systems, cryptographic protocols, privacy, time capsule, verifiable encryption