×

Discrete algorithms and methods for security of statistical databases related to the work of Mirka Miller. (English) Zbl 1410.68110

Summary: This article gives a survey of discrete and combinatorial algorithms and methods for database security related to the work of Mirka Miller. The main contributions of Mirka Miller and coauthors to the security of statistical databases include the introduction of Static Audit Expert and theorems determining time complexity of its combinatorial algorithms, a polynomial time algorithm for deciding whether the maximum possible usability can be achieved in a statistical database with a special class of answerable statistics, NP-completeness of similar problems concerning several other types of statistical databases, sharp upper bounds on the number of compromise-free queries in certain categories of statistical databases, and analogous results on applications of Static Audit Expert for the prevention of relative compromise.

MSC:

68P15 Database theory
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahlswede, R.; Aydinian, H., On security of statistical databases, SIAM J. Discrete Math., 25, 1778-1791 (2011) · Zbl 1237.68069
[2] Alfalayleh, M.; Brankovic, L., Quantifying privacy: a novel entropy-based measure of disclosure risk, (25th International Workshop on Combinatorial Algorithms, IWOCA 2014. 25th International Workshop on Combinatorial Algorithms, IWOCA 2014, Lect. Notes Comput. Sci., vol. 8986 (2015)), 24-36 · Zbl 1396.94058
[3] Batten, L. M., Public Key Cryptography: Applications and Attacks (2013), Wiley-IEEE Press: Wiley-IEEE Press New York · Zbl 1270.94001
[4] Brankovic, L.; Cvetković, D., The eigenspace of the eigenvalue −2 in generalized line graphs and a problem in security of statistical databases, Publ. Elektroteh. Fak. Univ. Beogr., Mat., 14, 37-48 (2003) · Zbl 1105.05041
[5] Brankovic, L.; Giggins, H., Statistical database security, (Security, Privacy, and Trust in Modern Data Management, Data-Centric Systems and Applications (2007), Springer), 167-181
[6] Brankovic, L.; Horak, P.; Miller, M., An optimization problem in statistical database security, SIAM J. Discrete Math., 13, 3, 346-353 (2000) · Zbl 0949.68115
[7] Brankovic, L.; Islam, M. Z.; Giggins, H., Privacy-preserving data mining, (Security, Privacy, and Trust in Modern Data Management, Data-Centric Systems and Applications (2007), Springer), 151-165
[8] Brankovic, L.; Lopez, M.; Miller, M.; Sebe, F., Triangle randomization for social network data anonymization, Ars Math. Contemp., 7, 461-477 (2014) · Zbl 1315.68118
[9] Brankovic, L.; Miller, M., An application of combinatorics to the security of statistical databases, Aust. Math. Soc. Gaz., 22, 4, 173-177 (1995) · Zbl 0851.68026
[10] Brankovic, L.; Miller, M.; Horak, P.; Wrightson, G., Usability of compromise-free statistical databases, (Proceedings of the International Working Conference on Scientific and Statistical Database Management. Proceedings of the International Working Conference on Scientific and Statistical Database Management, Melbourne, Australia, January 29-30 (1997)), 144-154
[11] Brankovic, L.; Miller, M.; Širáň, J., Towards a practical auditing method for the prevention of statistical database compromise, (Proceedings of the Seventh Australasian Database Conference. Proceedings of the Seventh Australasian Database Conference, Melbourne, Australia, January 29-30 (1996)), 177-184
[12] Brankovic, L.; Miller, M.; Širáň, J., Graphs, 0-1 matrices, and usability of statistical databases, Congr. Numer., 120, 169-182 (1996) · Zbl 0901.05071
[13] Brankovic, L.; Miller, M.; Širáň, J., On range query usability of statistical databases, Int. J. Comput. Math., 79, 12, 1265-1271 (2002) · Zbl 1008.62005
[14] Brankovic, L.; Širáň, J., 2-compromise usability in 1-dimensional statistical databases, (Computing and Combinatorics. Computing and Combinatorics, Lect. Notes Comput. Sci., vol. 2387 (2002), Springer: Springer Berlin), 448-455 · Zbl 1077.68625
[15] Casino, F.; Domingo-Ferrer, J.; Patsakis, C.; Puig, D.; Solanas, A., A k-anonymous approach to privacy preserving collaborative filtering, J. Comput. Syst. Sci., 81, 1000-1011 (2015)
[16] Chin, F. Y.; Ozsoyoglu, G., Auditing and inference control in statistical databases, IEEE Trans. Softw. Eng., 8, 6, 574-582 (1982) · Zbl 0491.68102
[17] Demetrovics, J.; Katona, G. O.H.; Miklos, D., On the security of individual data, (Foundations of Information and Knowledge Systems. Foundations of Information and Knowledge Systems, Lect. Notes Comput. Sci., vol. 2942 (2004)), 49-58 · Zbl 1202.68136
[18] Domingo-Ferrer, J., Inference Control in Statistical Databases (2002), Springer: Springer Berlin · Zbl 1051.68637
[19] Domingo-Ferrer, J., A survey of inference control methods for privacy-preserving data mining, (Privacy-Preserving Data Mining Models and Algorithms. Privacy-Preserving Data Mining Models and Algorithms, Adv. Database Syst., vol. 34 (2008), Springer), 53-80
[20] Domingo-Ferrer, J.; Muralidhar, K., New directions in anonymization: Permutation paradigm, verifiability by subjects and intruders, transparency to users, Inf. Sci., 337-338, 11-24 (2016)
[21] Estivill-Castro, V.; Brankovic, L., Data swapping: Balancing privacy against precision in mining for logic rules, (Data Warehousing and Knowledge Discovery. Data Warehousing and Knowledge Discovery, Lect. Notes Comput. Sci., vol. 1676 (1999)), 389-398
[22] Giggins, H.; Brankovic, L., Statistical disclosure control: To trust or not to trust, (Proceedings of the International Symposium on Computer Science and its Applications (2008), IEEE Computer Society), 108-113
[23] Giggins, H.; Brankovic, L., VICUS - a noise addition technique for categorical data, (Proceedings of the Tenth Australasian Data Mining Conference, AusDM 2012. Proceedings of the Tenth Australasian Data Mining Conference, AusDM 2012, Conferences in Research and Practice in Information Technology (CRPIT), vol. 134 (2012)), 139-148
[24] Griggs, J. R., Concentrating subset sums at \(k\) points, Bull. Inst. Comb. Appl., 20, 65-74 (1997) · Zbl 0876.05096
[25] Griggs, J. R., Database security and the distribution of subset sums in \(R^m\), (Graph Theory and Combinatorial Biology. Graph Theory and Combinatorial Biology, Bolyai Soc. Math. Stud., vol. 7 (1997)), 223-252 · Zbl 0934.05121
[26] Hardjono, T.; Seberry, J., Applications of smartcards for anonymous and verifiable databases, Comput. Secur., 14, 465-472 (1995)
[27] Hardjono, T.; Zheng, Y.; Seberry, J., Database authentication revisited, Comput. Secur., 13, 573-580 (1994)
[28] Horak, P.; Brankovic, L.; Miller, M., A combinatorial problem in database security, Discrete Appl. Math., 91, 1-3, 119-126 (1999) · Zbl 0924.68067
[29] Islam, M. Z.; Brankovic, L., A framework for privacy preserving classification in data mining, (Proceedings of the 2nd Workshop on Australasian Information Security, vol. 32 (2004), Data Mining and Web Intelligence, and Software Internationalisation), 163-168
[30] Islam, M. Z.; Brankovic, L., DETECTIVE: a decision tree based categorical value clustering and perturbation technique for preserving privacy in data mining, (Proceedings of the 3rd IEEE International Conference on Industrial Informatics, INDIN 2005 (2005)), 701-708
[31] Islam, M. Z.; Brankovic, L., Privacy preserving data mining: a noise addition framework using a novel clustering technique, Knowl.-Based Syst., 24, 1214-1223 (2011)
[32] Kelarev, A. V.; Yi, X.; Cui, H.; Rylands, L.; Jelinek, H. F., A survey of state-of-the-art methods for securing medical databases, AIMS Med. Sci., 5, 1-22 (2017)
[33] Liu, D.; Bertino, E.; Yi, X., Privacy of outsourced k-means clustering, (Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security. Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security, ASIA CCS 2014 (2014)), 123-133
[34] Mathieson, L.; King, T.; Brankovic, L., 2-compromise: usability in 1-dimensional statistical database, Research Gate (2008), available online at
[35] Miller, M., A model of statistical database compromise incorporating supplementary knowledge, (Databases in the 1990’s (1991)), 258-267
[36] Miller, M.; Cooper, J., Security considerations for present and future medical databases, Int. J. Med. Inform., 41, 39-46 (1996)
[37] Miller, M.; Roberts, I.; Simpson, J., Application of symmetric chains to an optimization problem in the security of statistical databases, Bull. Inst. Comb. Appl., 2, 47-58 (1991) · Zbl 0850.68184
[38] Miller, M.; Roberts, I.; Simpson, J., Prevention of relative compromise in statistical databases using audit expert, Bull. Inst. Comb. Appl., 10, 51-62 (1994) · Zbl 0811.68076
[39] Miller, M.; Seberry, J., Relative compromise of statistical databases, Aust. Comput. J., 21, 2, 56-61 (1989)
[40] Miller, M.; Seberry, J., Audit expert and statistical database security, (Databases in the 1990’s (1991)), 149-174
[41] Mishra, V.; Stranieri, A.; Miller, M.; Ryan, J., Knowledge based regulation of statistical databases, WSEAS Trans. Inf. Sci. Appl., 3, 2, 239-244 (2006)
[42] Pacheco, F.; Cooper, J.; Bomba, D.; Morris, S.; Miller, M.; Brankovic, L., Education issues in health informatics, Healthc. Inform., 4, 101-105 (1995)
[43] Pacheco, F.; Cooper, J.; Bomba, D.; Morris, S.; Miller, M.; Brankovic, L., Value added networks (VANs) and their benefit to a health information system, Healthc. Inform., 4, 141-144 (1995)
[44] Pieprzyk, J.; Hardjono, T.; Seberry, J., Fundamentals of Computer Security (2003), Springer-Verlag: Springer-Verlag Berlin · Zbl 1011.68034
[45] Rao, F.-Y.; Samanthula, B.; Bertino, E.; Yi, X.; Liu, D., Privacy-preserving and outsourced multi-user k-means clustering, (Proceedings of the IEEE Conference on Collaboration and Internet Computing, CIC 2015 (2015)), 80-89
[46] Skinner, G.; Chang, E.; McMahon, M.; Aisbett, J.; Miller, M., Shield privacy hippocratic security method for virtual community, (IECON Proceedings (Industrial Electronics Conference) (2004)), 472-479
[47] Skinner, G.; Miller, M., Managing privacy, trust, security, and context relationships using weighted graph representations, WSEAS Trans. Inf. Sci. Appl., 3, 2, 283-290 (2006)
[48] Slamet, S.; Sugeng, K. A.; Miller, M., Sum graph based access structure in a secret sharing scheme, J. Prime Res. Math., 2, 113-119 (2006) · Zbl 1131.94021
[49] Stanley, R. P., Weyl groups, the hard Lefshetz theorem, and the Sperner property, SIAM J. Algebraic Discrete Methods, 1, 168-184 (1980) · Zbl 0502.05004
[50] Yi, X.; Paulet, R.; Bertino, E., Private Information Retrieval (2013), Morgan and Claypool: Morgan and Claypool United States · Zbl 1375.68011
[51] Yi, X.; Paulet, R.; Bertino, E., Homomorphic Encryption and Applications (2014), Springer: Springer New York · Zbl 1308.68014
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.