A secure multidimensional point inclusion protocol

ABSTRACT

Signal processing in the encrypted domain combines typical signal processing operations and cryptographic primitives to ensure security in applications involving mutually distrusting participants. Several such applications reduce to a multidimensional point inclusion problem where two participants decide whether a point known to the first lies inside a region specified by the second. In a secure solution, neither party gains knowledge about the other's input. For instance, in biometric authentication the client can prove his identity without disclosing his biometric.

In this paper, we present a new primitive for securely solving the multidimensional point inclusion problem. Using this primitive, we first propose an efficient and provably secure protocol that solves the problem for an N-dimensional convex region bounded with hyperplanes. We subsequently extend the protocol to inclusion in multiple hyperellipsoidal regions. Considering possible reduction strategies such as input packing, we analyze the complexity of both protocols.

REFERENCES

• 1: Mikhail J. Atallah , Wenliang Du, Secure Multi-party Computational Geometry, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.165-179, August 08-10, 2001
• 2: F. Boudot. Efficient proofs that a committed number lies in an interval. In Advances in cryptology - EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 431--444. Springer-Verlag, 2000.
• 3: R. Brinkman, J. M. Doumen, and W. Jonker. Using secret sharing for searching in encrypted data. In Workshop on Secure Data Management in a Connected World (SDM 2004), volume 3178 of Lecture Notes in Computer Science, pages 18--27. Springer-Verlag, 2004.
• 4: Bernard Chazelle , Joel Friedman, Point location among hyperplanes and unidirectional ray-shooting, Computational Geometry: Theory and Applications, v.4 n.2, p.53-62, June 1994 [doi>10.1016/0925-7721(94)90009-4]
• 5: Ronald Cramer , Ivan Damgård , Jesper Buus Nielsen, Multiparty Computation from Threshold Homomorphic Encryption, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.280-299, May 06-10, 2001
• 6: Ivan Damgård , Eiichiro Fujisaki, A Statistically-Hiding Integer Commitment Scheme Based on Groups with Hidden Order, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.125-142, December 01-05, 2002
• 7: 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
• 8: Ivan Damgård , Mads Jurik, Client/Server Tradeoffs for Online Elections, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.125-140, February 12-14, 2002
• 9: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 10: Yvo G. Desmedt , Yair Frankel, Threshold cryptosystems, Proceedings on Advances in cryptology, p.307-315, July 1989, Santa Barbara, California, United States
• 11: B. Goethals, S. Laur, H. Lipmaa, and T. Mielikäinen. On private scalar product computation for privacy-preserving data mining. In C. Park and S. Chee, editors, 7th Annual International Conference in Information Security and Cryptology (ICISC 2004), volume 3506 of Lecture Notes in Computer Science, pages 104--120, Seoul, Korea, December 2004. Springer.
• 12: Maged Hamada Ibrahim, Two-Party Private Vector Dominance: The All-Or-Nothing Deal, Proceedings of the Third International Conference on Information Technology: New Generations, p.166-171, April 10-12, 2006 [doi>10.1109/ITNG.2006.136]
• 13: M. Johnson, P. Ishwar, V. Prabhakaran, D. Schonberg, and K. Ramchandran. On compressing encrypted data. IEEE Transactions on Signal Processing, 52(10):2992--3006, October 2004.
• 14: J. Matousek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Computational Geometry, 10:215--232, 1993.
• 15: P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology - EUROCRYPT 1999, volume 1592 of Lecture Notes in Computer Science, pages 223--238. Springer, 1999.
• 16: L. Pérez-Freire, P. Comesana, J. R. Troncoso-Pastoriza, and F. Pérez-González. Watermarking security: a survey. LNCS Transactions on Data Hiding and Multimedia Security I, 4300:41--72, October 2006.
• 17: Franco P. Preparata , Roberto Tamassia, Efficient point location in a convex spatial cell-complex, SIAM Journal on Computing, v.21 n.2, p.267-280, April 1992 [doi>10.1137/0221020]
• 18: Yingpeng Sang , Hong Shen, A Scheme for Testing Privacy State in Pervasive Sensor Networks, Proceedings of the 19th International Conference on Advanced Information Networking and Applications, p.644-648, March 25-30, 2005 [doi>10.1109/AINA.2005.60]
• 19: B. Schoenmakers and P. Tulys. Efficient binary conversion for paillier encrypted values. In Advances in Cryptology - EUROCRYPT 2006, volume 4004 of Lecture Notes in Computer Science, pages 522--537. Springer, 2006.
• 20: V. Shoup. Practical threshold signatures. In Advances in cryptology - EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 207--220. Springer, 2000.
• 21: Dawn Xiaodong Song , David Wagner , Adrian Perrig, Practical Techniques for Searches on Encrypted Data, Proceedings of the 2000 IEEE Symposium on Security and Privacy, p.44, May 14-17, 2000
• 22: P. Tuyls and J. Goseling. Capacity and examples of template protecting biometric authentication systems. In Proceedings of Biometric Authentication Workshop, volume 3087 of Lecture Notes in Computer Science, pages 158--170, Berlin, 2004. Springer-Verlag.
• 23: Rebecca Wright , Zhiqiang Yang, Privacy-preserving Bayesian network structure computation on distributed heterogeneous data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014145]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Algorithms, Performance, Security

Keywords:
computational geometry, homomorphic encryption, point inclusion, secure multiparty computation, signal processing in the encrypted domain