Смешивающиеся решетки и исчезающие потайные ходы: Фреймворк для безопасной короткой подписи и прочее

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 10:31, 5 декабря 2015.
Two-Output Secure Computation with Malicious Adversaries
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Abhi Shelat[@: 1] and
Chih-Hao Shen[@: 2]
Опубликован 2010 г.
Сайт Department of Computer Science
Перевели Egor Zorin
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Мы представляем фреймворк для адаптивной безопасности, основанный на случайно генерируемых решетках из стандартной модели.Наш подход основан на семействе решеток Агравал-Бонех-Бойена, которое предоставляет надежные и точечные потайные ходы успешно используемые как в моделировании так и на практике. Мы расширили эту идею для того чтобы рассмотреть не только симуляцию закрытия потайных ходов в специально созданных для этого условиях, но и в том небольшом количестве случаев, когда данная ситуация может возникнуть в реальности. В общих чертах, мы построили довольно большое и компактно представимое семейство зависящих от входных данных "cмесией" решеток, которые создаются вместе с потайными ходами "исчезающими" при использовании некоторого секретного подмножества, на которое как мы думаем будет нацелен злоумышленник. Технически, мы настраиваем структуру решеток таким образом, чтобы получить "естественное" представление для произвольной выборки из размеров подмножества. Наш фреймворк не нацелен на какую-то определенную задачу. Он позволяет как получать безопасные цифровые подписи, так и реализовывать шифрование основанное на идентификационных данных, которое является простым, компактным и весьма элегантным.

Введение

Благодаря комбинации из математической элегантности, простоты реализации, доказанного снижения безопасности, и успехах в эффективности, приближающих их к дискретно-логарифмическому и основанном на факторизации подходах, к решеткам в криптографии вновь возобновился интерес. Так же основанная на решетках криптография позволяет надеяться на то, что она будет устойчива к появлению квантовых компьютеров, в то время как дискретно-логарифмический и основанный на факторизации подходы гарантированно не смогут противостоять им. Можно выделить несколько примеров наиболее важных криптосистем и образований, основанных на решетках.[1] [2] [3] [4] [5] [6] [7] [8]


Контакты авторов материала

  1. University of Virginia, Charlottesville, VA 22904, E-mail: shelat@virginia.edu
  2. University of Virginia, Charlottesville, VA 22904, E-mail: shench@virginia.edu

Примечание

Литература

  1. Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC (1996)
  2. Ajtai, M.: Generating hard instances of the short basis problem. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, p. 1. Springer, Heidelberg (1999)
  3. Micciancio, D., Goldwasser, S.: Complexity of lattice problems: a cryptographic perspective. Kluwer Series on Engineering and Computer Science (2002)
  4. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on gaussian measures. In: FOCS (2004)
  5. Aharonov, D., Regev, O.: Lattice problems in NP ∩ coNP. Journal of the ACM 52(5), 749–765 (2005)
  6. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC (2005)
  7. Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 145–166. Springer, Heidelberg (2006)
  8. Micciancio, D., Regev, O.: Worst-case to average-case reductions based on Gaussian measures. SIAM Journal of Computing 37(1), 267–302 (2007)