В докладе будет рассмотрено понятие differential privacy, являющееся наиболее успешной попыткой теоретической формализации понятия privacy. Данное понятие позвляет давать сильные теоретико-информационные гарантии privacy пользователям, чьи личные данные хранятся в базе данных, при условии, что над базой данных выполняются операции, сохраняющие differential privacy. Поскольку гарантии являются теоретико-информационными, они действительны относительно произвольного противника, вне зависимости от его априорной информации.
Введение понятия differential privacy в работе Dwork, McSherry, Nissim и Smith (TCC, 2006) дало начало новой области теоретической информатики, посвященной изучению алгоритмов, сохраняющих differential privacy. Мы рассмотрим некоторые современные темы и задачи в этой области. Особенное внимание будет уделено механизму smooth sensitivity, введенному в работе Nissim, Raskhodnikova и Smith (STOC 2007) и его приложениям при анализе структуры графов с сохранением privacy (совместная работа докладчика с Behoora, Karwa, Raskhodnikova и Smith).