04.04.2013

Премию Тьюринга 2012 присудили за вероятностное шифрование

Премия Тьюринга ($250 тыс.) считается аналогом Нобелевской премии в области информатики. Она вручается ежегодно с 1966 года, с тех пор её получали, например, Алан Перлис за обобщённые техники построения компиляторов (1966), Марвин Минский за новаторские работы в области ИИ (1969), Эдсгер Дейкстра за язык программирования АЛГОЛ и публикации о программировании (1972), Дональд Кнут за огромный вклад в анализ алгоритмов, разработку языков программирования и за создание широко известной серии книг под общим названием "Искусство программирования" (1974), Никлаус Вирт за разработку языков программирования Эйлер, Algol-W, Модула и Паскаль (1984). Среди номинантов последних лет - известные криптологи Рональд Ривест, Ади Шамир и Леонард Адлеман за уникальный вклад по увеличению практической пользы систем шифрования с открытым ключом (2002), а также Винтон Серф и Роберт Кан за пионерскую работу по проблеме межсетевого обмена, включая разработку и реализацию основных интернет-протоколов и TCP/IP (2004).

Недавно объявлены номинанты премии Тьюринга за 2012 год. Как это часто бывало в последнее время, ими опять стали криптологи. Награду получат Сильвио Микали (Silvio Micali) и Шафи Гольдвассер (Shafi Goldwasser) за новаторские работы по вероятностному шифрованию (в том числе, за первую вероятностную криптосистему с открытым ключом) и работы по применению доказательств с нулевым разглашением в криптографических протоколах. Оба профессора сейчас преподают в Массачусетском технологическом институте.

Эти двое учёных известны как авторы криптосистемы Гольдвассер-Микали, представленной в 1983 году. Это доказуемо стойкая криптосистема с довольно ограниченной сферой практического использования, потому что шифртекст может быть в сотни раз длиннее, чем шифруемое сообщение. Тем не менее, авторы системы впервые сформулировали понятие семантической стойкости и внесли немалый вклад в криптографическую науку.

Семантическая стойкость означает, что зашифрованный текст не допускает никакой утечки полезной информации об исходном тексте. Для сравнения, если взять обычную одностороннюю хэш-функцию и применить её для шифрования простых однобитовых инструкций (покупать/продавать), то содержание исходного сообщения легко можно будет увидеть по разнице шифртекста. Гольдвассер и Микали разработали схему вероятностного шифрования, в которой не допускается такой утечки. Нулевые биты в исходном тексте равномерно распределяются по множеству QRn, а единичные - равномерно распределяются по множеству Jn(1)\QRn, где Jn(1) - такое множество, что символ Якоби его элементов равен 1.

Церемония вручения премии Тьюринга за 2012 год состоится 15 июня в Сан-Франциско.

Источники:

1. xakep.ru