2012 год

Silvio Micali (1954) и Shafi Goldwasser (1958)


«За новаторские работы, которые легли в основу применения теории сложности в криптографии и предоставили новые методы эффективной проверки математических доказательств теории сложности»

Страна: США

Образование: Silvio Micali - Доктор философии в области информатики, Калифорнийский университет (Беркли), 1982

Shafi Goldwasser - Доктор философии в области информатики, Калифорнийский университет (Беркли), 1984


О лауреатах

Криптографическая система, разработанная Goldwasser и Micali в 1982 году, является первой схемой вероятностного шифрования с открытым ключом, доказуемо стойкая при стандартных криптографических предположениях. Однако, криптосистема GM является неэффективной, так как зашифрованный текст может быть в сотни раз длиннее, чем шифруемое сообщение. Для доказательства свойств стойкости криптосистемы Goldwasser и Micali ввели широко используемое понятие семантической стойкости - свойству, благодаря которому все элементы открытого текста, которые можно эффективно вычислить по заданному зашифрованному тексту, можно эффективно вычислить и без него.


Ключевые слова: Goldwasser-Micali cryptosystem, Zero-knowledge proof, Blum-Goldwasser cryptosystem, Pseudorandom functions, Peppercoin


Краткая библиография

1.

Goldwasser, S. and S. Micali, “Probabilistic Encryption,” Journal of Computer and System Sciences(JCSS), Vol. 28, Num. 2, pp. 270-299, April 1984.

Это первая статья, которая вводит формальные описания безопасности криптографических систем и применяет их шифрованию с открытым ключом и другим фундаментальным алгоритмам.
2.

Blum, M. and S. Micali, “How to generate Cryptographically Strong Sequences of Pseudo-Random Bits,” SIAM Journal on Computing (SICOMP), Vol. 13, Num. 4, pp. 850-864, November 1984.

Эта статья была первой, официально определившей понятие вычислительно непредсказуемых последовательностей и продемонстрировавшая, как детерминистически и эффективно генерировать такие последовательности.
3.

Chor, B., S. Goldwasser, S. Micali, and B. Awerbuch, “Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults,” Proceedings of 26th Annual Symposium on the Foundations of Computer Science (FOCS 1985), pp. 383-395, October 1985.

В отчёте обсуждается, как передавать секретный ключ таким образом, чтобы участники обмена не могли смухлевать.
4.

Goldreich, O., S. Goldwasser, and S. Micali, “How to Construct Random Functions,” Journal of the ACM (JACM), Vol. 33, Num. 4, pp. 792-807, October 1986.

Статья вводит семейство эффективно вычислимых функций, выходные значения которых неотличимы от значений случайных функций.
5.

Goldwasser, S., S. Micali, and C. Rackoff; “The Knowledge Complexity of Interactive Proof-Systems,” SIAM Journal on Computing (SICOMP), Vol. 18, Num. 1, pp. 186-200, February 1989.

В этом документе вводятся понятия интерактивных доказательств, зависимости сложности доказательства от имеющихся данных и парадоксальное понятие доказательства с нулевым разглашением.