Премия Тьюринга ($250 тыс.) считается аналогом Нобелевской премии в области информатики. Она вручается ежегодно с 1966 года, с тех пор её получали, например, Алан Перлис за обобщённые техники построения компиляторов (1966), Марвин Минский за новаторские работы в области ИИ (1969), Эдсгер Дейкстра за язык программирования АЛГОЛ и публикации о программировании (1972), Дональд Кнут за огромный вклад в анализ алгоритмов, разработку языков программирования, и за создание широко известной серии книг под общим названием «Искусство программирования» (1974), Никлаус Вирт за разработку языков программирования Эйлер, Algol-W, Модула и Паскаль (1984). Среди номинантов последних лет — известные криптологи Рональд Ривест, Ади Шамир и Леонард Адлеман за уникальный вклад по увеличению практической пользы систем шифрования с открытым ключом (2002), а также Винтон Серф и Роберт Кан за пионерскую работу по проблеме межсетевого обмена, включая разработку и реализацию основных интернет-протоколов и TCP/IP (2004).
Недавно объявлены номинанты премии Тьюринга за 2012 год. Как это часто бывало в последнее время, ими опять стали криптологи. Награду получат Сильвио Микали (Silvio Micali) и Шафи Гольдвассер (Shafi Goldwasser) за новаторские работы по вероятностному шифрованию (в том числе, за первую вероятностную криптосистему с открытым ключом) и работы по применению доказательств с нулевым разглашением в криптографических протоколах. Оба профессора сейчас преподают в Массачусетском технологическом институте.
Эти двое учёных известны как авторы криптосистемы Гольдвассер – Микали, представленной в 1983 году (оригинал работы, pdf). Это доказуемо стойкая криптосистема с довольно ограниченной сферой практического использования, потому что шифртекст может быть в сотни раз длиннее, чем шифруемое сообщение. Тем не менее, авторы системы впервые сформулировали понятие семантической стойкости и внесли немалый вклад в криптографическую науку.
Семантическая стойкость означает, что зашифрованный текст не допускает никакой утечки полезной информации об исходном тексте. Для сравнения, если взять обычную одностороннюю хэш-функцию и применить её для шифрования простых однобитовых инструкций (покупать/продавать), то содержание исходного сообщения легко можно будет увидеть по разнице шифртекста. Гольдвассер и Микали разработали схему вероятностного шифрования, в которой не допускается такой утечки. Нулевые биты в исходном тексте равномерно распределяются по множеству QRn, а единичные — равномерно распределяются по множеству Jn(1)\QRn, где Jn(1) — такое множество, что символ Якоби его элементов равен 1.
Церемония вручения премии Тьюринга за 2012 год состоится 15 июня в Сан-Франциско.
