Single-bit re-encryption with applications to distributed proof systems

ABSTRACT

We examine the implementation of the distributed proof system designed by Minami and Kotz [17]. We find that, although a high-level analysis shows that it preserves confidentiality, the implementation of the cryptographic primitives contains a covert channel that can leak information. Moreover, this channel is present with any traditional choice of public key encryption functions.

To remedy this problem, we use the Goldwasser-Micali cryptosystem to implement single-bit re-encryption and show how to make it free of covert channels. We then extend the primitive to support commutative encryption as well. Using this primitive, we design a variant of the Minami-Kotz algorithm that not only is free of covert channels, but also has additional proving power over the original design.

REFERENCES

• 1: L. Bauer, S. Garriss, J. M. McCune, M. K. Reiter, J. Rouse, and P. Rutenbar. Device-enabled authorization in the Grey system. In J. Zhou and J. Lopez, editors, Information Security Conference, volume 3650 of Lecture Notes in Computer Science, pages 431--445, Singapore, Sept. 2005.
• 2: Lujo Bauer , Scott Garriss , Michael K. Reiter, Distributed Proving in Access-Control Systems, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.81-95, May 08-11, 2005 [doi>10.1109/SP.2005.9]
• 3: M. Bellare and P. Rogaway. Optimal asymmetric encryption. In A. De Santis, editor, Advances in Cryptology . EUROCRYPT, volume 950 of Lecture Notes in Computer Science, pages 92--111, Perugia, Italy, May 1994.
• 4: J. Boyar, K. Friedl, and C. Lund. Practical zero-knowledge proofs: Giving hints and using deficiencies. Journal of Cryptology, 4(3):185--206, Jan. 1991.
• 5: Ivan Damgård , Mats Jurik, A Generalisation, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.119-136, February 13-15, 2001
• 6: John DeTreville, Binder, a Logic-Based Security Language, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.105, May 12-15, 2002
• 7: Shawna Meyer Eikenberry , Jonathan P. Sorenson, Efficient algorithms for computing the Jacobi symbol, Journal of Symbolic Computation, v.26 n.4, p.509-523, Oct. 1998 [doi>10.1006/jsco.1998.0226]
• 8: Jun Furukawa , Kazue Sako, An Efficient Scheme for Proving a Shuffle, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.368-387, August 19-23, 2001
• 9: Shafi Goldwasser , Silvio Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.365-377, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802212]
• 10: S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270--299, 1984.
• 11: Dan Boneh , Philippe Golle, Almost entirely correct mixing with applications to voting, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586121]
• 12: Markus Jakobsson , Ari Juels , Ronald L. Rivest, Making Mix Nets Robust for Electronic Voting by Randomized Partial Checking, Proceedings of the 11th USENIX Security Symposium, p.339-353, August 05-09, 2002
• 13: Trevor Jim, SD3: A Trust Management System with Certified Evaluation, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.106, May 14-16, 2001
• 14: Ari Juels , Jorge Guajardo, RSA Key Generation with Verifiable Randomness, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.357-374, February 12-14, 2002
• 15: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
• 16: J. Massey and J. Omura. A new multiplicative algorithm over finite fields and its applicability in public key cryptography. Presented at the rump session of EUROCRYPT, Mar. 1983.
• 17: Kazuhiro Minami , David Kotz, Secure context-sensitive authorization, Pervasive and Mobile Computing, v.1 n.1, p.123-156, March 2005 [doi>10.1016/j.pmcj.2005.01.004]
• 18: Kazuhiro Minami , David Kotz, Secure Context-Sensitive Authorization, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, p.257-268, March 08-12, 2005 [doi>10.1109/PERCOM.2005.37]
• 19: C. Andrew Neff, A verifiable secret shuffle and its application to e-voting, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502000]
• 20: S. C. Pohlig and M. E. Hellman. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory, 24(1):106--110, Jan. 1978.
• 21: 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]
• 22: Jeroen van de Graaf , René Peralta, A Simple and Secure Way to Show the Validity of Your Public Key, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.128-134, August 16-20, 1987
• 23: Stephen A. Weis , Ronald L. Rivest, New foundations for efficient authentication, commutative cryptography, and private disjointness testing, Massachusetts Institute of Technology, Cambridge, MA, 2006
• 24: Marianne Winslett , Charles C. Zhang , Piero A. Bonatti, PeerAccess: a logic for distributed authorization, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102144]

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

General Terms:
Security

Keywords:
commutative encryption, covert channels, distributed proof systems, goldwasser-micali, re-encryption