Аннотация:Задача информационной защиты баз данных имеет один аспект, которому долгое время не уделялось должного внимания - дедуктивная безопасность. Располагая правом доступа к базе данных с зашифрованными записями и получая лишь ответы на запросы из некоторого ограниченного класса (например, осуществляющие сбор статистических данных), злоумышленник может попытаться решить задачу дедуктивного анализа и на основании полученных ответов предугадать также ответы на те запросы, которые находятся вне рамок его полномочий (например, выявить хотя бы частичные сведения о персональных данных). Для предотвращения угрозы такого рода в системах контроля доступом целесообразно предусмотреть механизм проверки дедуктивной безопасности запросов клиента. Ранее авторы предложили простейшую модель базы данных, каждая запись которой состоит из одного бита или нескольких битов, а угрозы состояли в раскрытии хотя бы одного или всех битов такой записи. Для этой модели было сформулировано требование дедуктивной безопасности запросов к базе данных, установлен критерий дедуктивной безопасности запросов, и показано, что задача проверки выполнимости этого критерия имеет большую вычислительную сложность. В данной заметке мы сформулировали и исследовали более общую задачу проверки свойств дедуктивной безопасности запросов к базам данных относительно более слабой угрозы раскрытия ответа на некоторый фиксированный запрос.