Non-interactive distributed encryption: a new primitive for revocable privacy

ABSTRACT

In this paper we introduce and instantiate a new cryptographic primitive, called non-interactive distributed encryption, that allows a receiver to decrypt a ciphertext only if a minimum number of different senders encrypt the same plaintext. The new functionality can be seen as the dual of the functionality provided by threshold cryptosystems. It is shown that this primitive can be used to solve real-world problems balancing security and privacy needs. In particular it is used to solve the canvas cutters problem (introduced below), that might be of independent interest.

References

1. Masayuki Abe and Miyako Ohkubo. Provably secure fair blind signatures with tight revocation. In Colin Boyd, editor, ASIACRYPT, LNCS 2248, pages 583--602. Springer, 2001.
2. Man Ho Au, Willy Susilo, and Yi Mu. Constant-size dynamic -taa. In Roberto De Prisco and Moti Yung, editors, SCN, LNCS 4116, pages 111--125. Springer, 2006.
3. Joonsang Baek and Yuliang Zheng. Identity-based threshold decryption. In Feng Bao, Robert H. Deng, and Jianying Zhou, editors, Public Key Cryptography, volume 2947 of Lecture Notes in Computer Science, pages 262--276. Springer, 2004.
4. Paulo S. L. M. Barreto and Michael Naehrig. Pairing-friendly elliptic curves of prime order. In Bart Preneel and Stafford E. Tavares, editors, Selected Areas in Cryptography, volume 3897 of Lecture Notes in Computer Science, pages 319--331. Springer, 2005.
5. Mihir Bellare and Chanathip Namprempre. Authenticated encryption: Relations among notions and analysis of the generic composition paradigm. J. Cryptology, 21(4):469--491, 2008.
6. Dan Boneh, Xavier Boyen, and Shai Halevi. Chosen ciphertext secure public key threshold encryption without random oracles. In David Pointcheval, editor, CT-RSA, volume 3860 of Lecture Notes in Computer Science, pages 226--243. Springer, 2006.
7. Dan Boneh and Matthew K. Franklin. Identity-based encryption from the weil pairing. SIAM J. Comput., 32(3):586--615, 2003.
8. Eric Brier, Jean-Sébastien Coron, Thomas Icart, David Madore, Hugues Randriam, and Mehdi Tibouchi. Efficient indifferentiable hashing into ordinary elliptic curves. In Tal Rabin, editor, CRYPTO, volume 6223 of Lecture Notes in Computer Science, pages 237--254. Springer, 2010.
9. Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography. J. Cryptology, 18(3):219--246, 2005.
10. Jan Camenisch, Thomas Groß, and Thomas S. Heydt-Benjamin. Rethinking accountable privacy supporting services: extended abstract. In Elisa Bertino and Kenji Takahashi, editors, Digital Identity Management, pages 1--8. ACM, 2008.
11. Jan Camenisch, Susan Hohenberger, Markulf Kohlweiss, Anna Lysyanskaya, and Mira Meyerovich. How to win the clonewars: efficient periodic n-times anonymous authentication. In Ari Juels, Rebecca N. Wright, and Sabrina De Capitani di Vimercati, editors, ACM Conference on Computer and Communications Security, pages 201--210. ACM, 2006.
12. Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya. Balancing accountability and privacy using e-cash (extended abstract). In Roberto De Prisco and Moti Yung, editors, SCN, LNCS 4116, pages 141--155. Springer, 2006.
13. David Chaum. Untraceable electronic mail, return adresses, and digital pseudonyms. Comm. ACM Communications of the ACM, 24(2):84--88, 1981.
14. David Chaum, Amos Fiat, and Moni Naor. Untraceable electronic cash. In Shafi Goldwasser, editor, CRYPTO, LNCS 403, pages 319--327. Springer, 1988.
15. Benny Chor, Shafi Goldwasser, Silvio Micali, and Baruch Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In FOCS, pages 383--395. IEEE, 1985.
16. Cécile Delerablée and David Pointcheval. Dynamic threshold public-key encryption. In David Wagner, editor, CRYPTO, volume 5157 of Lecture Notes in Computer Science, pages 317--334. Springer, 2008.
17. Yvo Desmedt and Yair Frankel. Threshold cryptosystems. In Gilles Brassard, editor, CRYPTO, volume 435 of Lecture Notes in Computer Science, pages 307--315. Springer, 1989.
18. Augusto Jun Devegili, Michael Scott, and Ricardo Dahab. Implementing cryptographic pairings over barreto-naehrig curves. In Tsuyoshi Takagi, Tatsuaki Okamoto, Eiji Okamoto, and Takeshi Okamoto, editors, Pairing, volume 4575 of Lecture Notes in Computer Science, pages 197--207. Springer, 2007.
19. Yevgeniy Dodis. Efficient construction of (distributed) verifiable random functions. In Yvo Desmedt, editor, Public Key Cryptography, volume 2567 of Lecture Notes in Computer Science, pages 1--17. Springer, 2003.
20. C. C. F. Pereira Geovandro, Marcos A. Simplicio Jr., Michael Naehrig, and Paulo S. L. M. Barreto. A family of implementation-friendly bn elliptic curves. Journal of Systems and Software, 84(8):1319--1326, 2011.
21. Shafi Goldwasser and Silvio Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270--299, 1984.
22. Jaap-Henk Hoepman. Revocable privacy. ENISA Quarterly Review, 5(2):16--17, June 2009.
23. Lawrence Lessig. Code and other laws of cyberspace. Basic Books, 1999.
24. Keith M. Martin, Reihaneh Safavi-Naini, Huaxiong Wang, and Peter R. Wild. Distributing the encryption and decryption of a block cipher. Des. Codes Cryptography, 36(3):263--287, 2005.
25. Bruce Schneier. What our top spy doesn't get: Security and privacy aren't opposites. Wired, January 2008.
26. Adi Shamir. How to share a secret. Commun. ACM, 22(11):612--613, 1979.
27. Victor Shoup and Rosario Gennaro. Securing threshold cryptosystems against chosen ciphertext attack. In EUROCRYPT, pages 1--16, 1998.
28. Nigel P. Smart and Frederik Vercauteren. On computable isomorphisms in efficient asymmetric pairing-based systems. Discrete Applied Mathematics, 155(4):538--547, 2007.
29. Daniel J. Solove. Understanding Privacy. Harvard University Press, 2008.
30. Markus Stadler. Cryptographic Protocols for Revocable Privacy. PhD thesis, Swiss Federal Institute of Technology, Zürich, 1996.
31. Markus Stadler, Jean-Marc Piveteau, and Jan Camenisch. Fair blind signatures. In EUROCRYPT, pages 209--219, 1995.
32. Isamu Teranishi and Kazue Sako. k-times anonymous authentication with a constant proving cost. In Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, editors, Public Key Cryptography, volume 3958 of Lecture Notes in Computer Science, pages 525--542. Springer, 2006.
33. Eric R. Verheul and Henk C. A. van Tilborg. Binding ElGamal: A fraud-detectable alternative to key-escrow proposals. In EUROCRYPT, pages 119--133, 1997.
34. Samuel D. Warren and Louis D. Brandeis. The right to privacy {The implicit Made Explicit}. Harvard Law Review, IV(5):193--220, December 15 1890.
35. Hoeteck Wee. Threshold and revocation cryptosystems via extractable hash proofs. In Kenneth G. Paterson, editor, EUROCRYPT, volume 6632 of Lecture Notes in Computer Science, pages 589--609. Springer, 2011.

Index Terms

• Security and privacy

  • Cryptography

  • Human and societal aspects of security and privacy

  • Systems security

    • Operating systems security

• Social and professional topics

  • Computing / technology policy

    • Privacy policies