A security machanism for statistical database

ABSTRACT

The problem of user inference in statistical databases is discussed and illustrated with several examples. It is assumed that the database allows “total,” “average,” “count,” and “percentile” queries; a query may refer to any arbitrary subset of the database. Methods for protecting the security of such a database are considered; it is shown that any scheme which gives “statistically correct” answers is vulnerable to penetration. A precise definition of compromisability (in a statistical sense) is given. A general model of user inference is proposed; two special cases of this model appear to contain all previously published strategies for compromising a statistical database. A method for protecting the security of such a statistical database against these types of user inference is presented and discussed. It is shown that the number of queries required to compromise the database can be made arbitrarily large by accepting moderate increases in the variance of responses to queries. A numerical example is presented to illustrate the application of the techniques discussed.

REFERENCES

• 1: BORUCH, R.F. Maintaining confidentiality in educational research: A systematic analysis. Am. Psychol. 26 (1971), 413-430.
• 2: CAMPBELL, D.T., BORUCH, R.F., SCHWARTZ, R.D., AND STEINBERG, J. Confidentiality-preserving modes of access to files and to interfile exchange for useful statistical analysis. Eval. Quart. 1, 2 (May 1977), 266-269.
• 3: Francis Y. Chin, Security in statistical databases for queries with small counts, ACM Transactions on Database Systems (TODS), v.3 n.1, p.92-104, March 1978 [doi>10.1145/320241.320250]
• 4: Richard Conway , David Strip, Selective partial access to a database, Proceedings of the annual conference, p.85-89, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805537]
• 5: DALENIUS, T. Towards a methodology for statistical disclosure control. Stirtryck ur Statistisk tidskrift 15 (1977}, 429-444.
• 6: DALENIUS, T., AND REINS, S.P. Data-swapping--A technique for disclosure control. Comput. Sci. Tech. Rep. 39, Brown Univ., Providence, R.I., July I978.
• 7: DAVIDA, G.I., AND KAM, J.B. Data security: Theory and practice. Rep. TR-CS-76-2, Coll. Engineering and Applied Science, Univ. Wisconsin, Milwaukee, WIN., 1976.
• 8: DAVIDA, G.I., LINTON, D.J., SZELAG, C.R., AND WELLS, D.L. Data base security. IEEE Trans. Softw. Eng. SE-4, 6 (Nov. 1978), 531-533.
• 9: DEMmLO, R.A., DOBKIN, D., AND LIPTON, R.J. Combinatorial inference. In Foundations of Secure Computation, R. A. DeMiUo et al., Eds. Academic Press, New York, 1978, pp. 27-35.
• 10: DEMILLO, R.A., DOBKIN, D., AND LIPTON, R.J. Even databases that lie can be compromised. IEEE Trans. Softw. Eng. SE-4, 1 (Jan. 1978), 73-75.
• 11: DENNING, D.E. Are statistical data bases secure? Proc. AFIPS 1978 NCC, vol. 47, AFIPS Press, Arlington, Va., pp. 525-530.
• 12: DENNING, D.E. Secure statistical databases with random sample queries. Rep. CSD-TR~302, Dep. Computer Science, Purdue Univ., W. Lafayette, Ind., April 1979.
• 13: DENNING, D.E. Complexity results relating to statistical confidentiality. Computer Science and Statistics: 12th Ann. Symp. Interface, Waterloo, Canada, May 1979.
• 14: Dorothy E. Denning , Peter J. Denning , Mayer D. Schwartz, The tracker: a threat to statistical database security, ACM Transactions on Database Systems (TODS), v.4 n.1, p.76-96, March 1979 [doi>10.1145/320064.320069]
• 15: David Dobkin , Anita K. Jones , Richard J. Lipton, Secure databases: protection against user influence, ACM Transactions on Database Systems (TODS), v.4 n.1, p.97-106, March 1979 [doi>10.1145/320064.320068]
• 16: FELLEGI, I.P., AND PHILLIPS, J.L. Statistical confidentiality: Some theory and applications to data dissemination. Ann. Econ. Soc. MeaN. 3, 2 (April 1974), 399-409.
• 17: HANSEN, M.H. Insuring confidentiality of individual records in data storage and retrieval for statistical purposes. Proc. AFIPS 1971 FJCC, vol. 39, AFIPS Press, Arlington, Va., pp. 579-585.
• 18: HOFFMAN, L.J., AND MILLER, W.F. Getting a personal dossier from a statistical data bank. Datamation 16, 5 (May 1970), 74-75.
• 19: HocG, R.V., AND CRAIG, A.T. introduction to Mathematical Statistics. Macmillan, New York, 1970.
• 20: John B. Kam , Jeffrey D. Ullman, A model of statistical database their security, ACM Transactions on Database Systems (TODS), v.2 n.1, p.1-10, March 1977 [doi>10.1145/320521.320525]
• 21: NARGUNDKAR, M.S., AND SAVELAND, W. Random rounding to prevent statistical disclosure. Proc. Am. Stat. Assoc., Soc. Stat. Sect. (1972), 382-385.
• 22: SC~IL6RER, J. Disclosure from statistical databases: Quantitative aspects of trackers. Inst. Medizinische Statistik und Dokumentation, Univ. Giessen, Giessen, W. Germany, March 1979.
• 23: SC~II~6RER, J. Security of statistical databases: Multidimensional transformation. Rep. TB- IMSD 2/78, Inst. Medizinische Statistik und Dokumentation, Univ. Giessen, Giessen, W. Germany, March 1979.
• 24: SCHL6RER J. Union tracker and open statistical databases. Rep. TB-IMSD 1/78, Inst. Medizinische Statistik und Dokumentation, Univ. Giessen, Giessen, W. Germany, June 1978.
• 25: C. T. Yu , F. Y. Chin, A study on the protection of statistical data bases, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509432]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General
          Subjects: Security, integrity, and protection**

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
      H.2.8 Database applications
          Subjects: Statistical databases

General Terms:
Design, Security

Keywords:
compromisability, data security, database inference, privacy protection, statistical databases, statistical queries