Арифметический кодекс: теория и практика

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:47, 27 сентября 2015.
The Arithmetic Codex: Theory and Applications
Two-Output Secure Computation with Malicious Adversaries.png
Авторы Ronald Cramer[@: 1]
Опубликован 2011 г.
Сайт Ronald Cramer's webpage
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал


Аннотация. Мы определяем понятие арифметического кодекса (или кодекса, для краткости) и, в особом случае, арифметическое разделение секрета. Это понятие включает и обобщает в единых математических рамках все известные схемы разделения секрета из области защищенных многопользовательских вычислений, например, так называемые (сильно) мультипликативные линейные схемы разделения секрета.

Эти схемы впервые были исследованы в качестве абстрактных примитивов Крамером, Дамгардом и Морером в конце 90х. Они показали, что «Фундаментальные теоремы информационно-теоретических безопасных многопользовательских вычислений», поворотный результат, полученный в 1988 Бен-Ором, Голдвассером и Вигдерсоном и, независимо от них в то же время, Чомом, Крепё и Дамгардом, содержит проверку, использующую данный примитив в черном ящике: из этого примитива, представленного в виде черного ящика, можно выгрузить набор отдельных суб-протоколов на основе которых можно построить общую безопасность вычислений. Они также показали, когда и как мультипликативные (но не сильно мультипликативные) схемы сводятся к обычным, что дает злоумышленникам неограниченные преимущества.

В 2006 Чен и Крамер продемонстрировали «асимптотически хорошую» версию Фундаментальных Теорем, где размер сетей неограничен и злоумышленник атакует конкретную часть сети, в то время как информативная часть примитивов разделения сектертов является константой. Их результат основывается на правильном выборе алгебраических геометрических кодов, в комбинации с более ранней работой Крамера, Дамгарда и Морера.

В 2007 этот асимптотический результат получил неожиданное применение в двухсторонней криптографии, через работу Ишаи, Кушилевица, Островского и Сахаи («Многопользовательские вычисления в целом»). Это первое применение не брало в расчет выполнимость в схеме, но скоро появились другие варианты обеспечения безопасности двухсторонней криптографии и информационной теории (корреляционные экстракторы).

Наше определение арифметического разделения секрета – не просто объединение ради объединения. Во-первых, оно описывает эти схемы в терминах выделенного «представления» К-алгебр, таким образом выводя на поверхность надежные математические структуры. Во-вторых, оно определяет новые типы специальных схем разделения секрета. И, в-третьих, появились новые криптографические применения. Помимо приведения нескольких элементарных примеров и предоставления обзора базовой теории и основных областей применения, мы обсуждаем создание арифметических схем разделения секрета на основе новой алгебраически-геометрической парадигмы, которую мы также рассмотрим. Этот разговор в основном основан на нескольких недавних совместных работах Начо Каскудо (CWI) и Чаопиня Сина (NTU). Но частично он также основан на недавних совместных работах Ивана Дамгарда (Университет Архуса) и Валерио Пастро (Университет Архуса)

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

  1. CWI, Amsterdam & Mathematical Institute, Leiden University, The Netherlands, http://www.cwi.nl/~cramer