Секретность данных
БД, позволяющая получать агрегированную информацию о больших подмножествах некоторого множества объектов, называется статистической. Примерами могу служить БД переписи населения, налоговых деклараций либо пациентов госпиталя. Кроме обычных проблем предотвращения несанкционированного доступа к БД или ее модификации, в статистической БД существуют проблемы, связанные с тем, что допускаются запросы в виде: «Напечатать средний доход всех жителей Томска», но в тоже время запрещается доступ к данным о доходах, конкретного человека, например Иванова.
Не так просто запретить запросы, которые требуют информации, относящейся к единственной записи. Например, Петров может запросить средний доход для множества {Петров, Иванов}, из которого, зная свой собственный доход, он может вычислить доход Иванова. Не решает проблему также и требование, чтобы информация запрашивалась относительно множества, состоящего из m человек. Действительно, в этом случае Петров мог бы взять множество S из m-1 или более человек, доходы которых ему не нужно узнавать, и запросить средний доход этих людей вместе с Ивановым. Затем он получил бы средний доход для множества, включающего его самого и людей из множества S. Зная свой собственный доход, он смого бы теперь легко определить доход Иванова на основе двух ответов системы. Поэтому необходимо ввести огранечения на запросы, сильно пересекающиеся друг с другом и таким образом можно если не предотвратить раскрытие индивидуальных данных, но сделать это достаточно трудным делом.
Будем считать для простоты, что статистическая БД содержит единственный файл записей. Каждая запись состоит из нескольких полей. Пусть v = (v
Важным случаем линейных запросов является сумма по множеству S, где
а также средние, где
где p - число записей в S.
Способность компрометировать БД (т.е. вычислять значения отдельного
Существует теорема: Пусть допускаются линейные запросы, продуцирующие по меньшей мере m элементов (т.е. обрабатывают m записей), и никакие два запроса не могут иметь более k общих элементов (т.е. k общих записей). Предположим, что p элементов уже известны (т.е. для p записей конкретные значения поля известны), тогда для вычитания некоторого еще неизвестного элемента (значения поля в интересующей нас записи) необходимо сделать не менее 1+ (m-1-p) /k запросов.
Ограничения на структуру запроса.
Пусть ключ записи состоит из x полей и предполагается, что в запросе можно задать не более y полей ключа (т.е. выполняется поиск по частичному соответствию ключа). Тогда, если y < k, никакая функция, использующая только операции сложения, вычитания, умножения и деления, не позволит определить значение данного конкретной записи.
