Private inference control

ABSTRACT

Access control can be used to ensure that database queries pertaining to sensitive information are not answered. This is not enough to prevent users from learning sensitive information though, because users can combine non-sensitive information to discover something sensitive. Inference control prevents users from obtaining sensitive information via such "inference channels", however, existing inference control techniques are not private - that is, they require the server to learn what queries the user is making in order to deny inference-enabling queries.

We propose a new primitive - private inference control (PIC) -which is a means for the server to provide inference control without learning what information is being retrieved. PIC is a generalization of private and symmetrically-private information retrieval (PIR/SPIR). While it is straightforward to implement access control using PIR (simply omit sensitive information from the database), it is nontrivial to implement inference control efficiently. We measure the efficiency of a PIC protocol in terms of its communication complexity, its round complexity, and the work the server performs per query. Under existing cryptographic assumptions, we give a PIC scheme which is simultaneously optimal, up to logarithmic factors, in the work the server performs per query, the total communication complexity, and the number of rounds of interaction. We also present a scheme requiring more communication but sufficient storage of state by the server to facilitate private user revocation. Finally, we present a generic reduction which shows that one can focus on designing PIC schemes for which the inference channels take a particularly simple threshold form.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 2: William Aiello , Yuval Ishai , Omer Reingold, Priced Oblivious Transfer: How to Sell Digital Goods, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.119-135, May 06-10, 2001
• 3: Leland L. Beck, A security machanism for statistical database, ACM Transactions on Database Systems (TODS), v.5 n.3, p.316-3338, Sept. 1980 [doi>10.1145/320613.320617]
• 4: Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, One-way functions are essential for single-server private information retrieval, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.89-98, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301277]
• 5: Amos Beimel , Yuval Ishai , Tal Malkin, Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.55-73, August 20-24, 2000
• 6: Mihir Bellare , Oded Goldreich, On Defining Proofs of Knowledge, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.390-420, August 16-20, 1992
• 7: M. Blum. Three applications of the oblivious transfer: Part i: Coin fippinf by telephone; part ii: How to exchange secrets; part iii: How to send electronic mail. Department of EECS,University of California,Berkeley,CA,1981.
• 8: D. Boneh, G. DiCrescenzo, R. Ostrovsky and G. Persiano. Searchable public key encryption. To appear in Advances in Cryptology -Eurocrypt 2004.http://eprint.iacr.org/2003/195/
• 9: Christian Cachin , Jan Camenisch , Joe Kilian , Joy Müller, One-Round Secure Computation and Secure Autonomous Mobile Agents, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.512-523, July 09-15, 2000
• 10: C. Cachin, S. Micali and M.Stadler. Computationally private information retrieval with polylo arithmic communication. In Advances in Cryptology -Eurocrypt '99.
• 11: Silvana Castano , Maria Grazia Fugini , Giancarlo Martella , Pierangela Samarati, Database security, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 12: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 13: Ronald Cramer , Victor Shoup, Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.45-64, May 02, 2002
• 14: G. Di Crescenzo, T. Malkin and R. Ostrovsky. Single database private information retrieval implies oblivious transfer. In Advances in Cryptology -Eurocrypt '00.
• 15: Irit Dinur , Kobbi Nissim, Revealing information while preserving privacy, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.202-210, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773173]
• 16: Danny Dolev , Cynthia Dwork , Moni Naor, Nonmalleable Cryptography, SIAM Journal on Computing, v.30 n.2, p.391-437, 2000 [doi>10.1137/S0097539795291562]
• 17: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 18: Csilla Farkas , Sushil Jajodia, The inference problem: a survey, ACM SIGKDD Explorations Newsletter, v.4 n.2, p.6-11, December 2002 [doi>10.1145/772862.772864]
• 19: E. Goh. How to search eficiently on encrypted compressed data. In the Cryptology ePrint Archive,Report 2003/216, October 7,2003.http://eprint.iacr.org/2003/216/
• 20: Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, Protecting data privacy in private information retrieval schemes, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.151-160, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276723]
• 21: O. Goldreich. Secure Multi-Party Computation, 1998. Available at http://philby.ucs.edu/
• 22: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 23: T. F. Keefe , Bhavani Thuraisingham , W. T. Tsai, Secure Query-Processing Strategies, Computer, v.22 n.3, p.63-70, March 1989 [doi>10.1109/2.16229 ]
• 24: 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
• 25: H.Lipmaa.An Oblivious Transfer Protocol with Log-Squared Total Communication, http://eprint.iacr.org/2004/063/
• 26: Moni Naor , Benny Pinkas, Oblivious transfer and polynomial evaluation, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.245-254, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301312]
• 27: Moni Naor , Benny Pinkas, Oblivious Transfer with Adaptive Queries, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.573-590, August 15-19, 1999
• 28: P. Paillier. Public-key cryptosystems based on composite degree residuaosity classes. In Advances in Cryptology -Eucrocrypt 1999, pp.223--238.
• 29: M.Rabin.How to exchange secrets by oblivious transfer. Tech report TR 81,Aiken Computation Lab, 1981.
• 30: Xiaolei Qian , Mark E. Stickel , Peter D. Karp , Teresa F. Lunt , Thomas D. Carvey, Detection and Elimination of Inference Channels in Multilevel Relational Database Systems, Proceedings of the 1993 IEEE Symposium on Security and Privacy, p.196, May 24-26, 1993
• 31: Pierangela Samarati , Latanya Sweeney, Generalizing data to provide anonymity when disclosing information (abstract), Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.188, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275508]
• 32: 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]
• 33: 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
• 34: Jessica Staddon, Dynamic inference control, Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13-13, 2003, San Diego, California [doi>10.1145/882082.882103]
• 35: J. F. Traub , Y. Yemini , H. Woźniakowski, The statistical security of a statistical database, ACM Transactions on Database Systems (TODS), v.9 n.4, p.672-679, Dec. 1984 [doi>10.1145/1994.383392]
• 36: D. Woodruff and J. Staddon. Private Inference Control IACR print, http://eprint.iacr.org/2004/130/
• 37: A. C. Yao. Protocols for secure computations. In proc.of 23rd FOCS, 1982, pp.160--164.16.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Security, Theory

Keywords:
inference control, oblivious transfer, private information retrieval