Практически оптимальные схемы разделения секрета

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 20:54, 27 сентября 2015.
Almost Optimum t-Cheater Identifiable Secret Sharing Schemes
Almost Optimum t-Cheater Identifiable Secret Sharing Schemes.png
Авторы Satoshi Obana[@: 1].
Опубликован 2011 г.
Сайт Homepage of Satoshi Obana
Перевели коллектив проекта «Gir»
Год перевода 2011 г.
Скачать оригинал

__NUMBEREDHEADINGS__

Аннотация. Во время Crypto '95 Куросава, Обана и Огата предложили схему разделения из способную определить до мошенников с вероятностью , при условии, что Размер доли , удовлетворяющий равенству соответствует наиболее эффективной схеме, известной до сих пор. В этой статье мы представляем новую схему разделения секрета из позволяющую идентифицировать мошенников. Предлагаемая схема обладает теми же параметрами безопасности что и схема Куросавы и соавт. Схема удивительно проста и размер ее долей равен что значительно меньше, чем у Куросавы и соавт. и практически оптимален, учитывая, что размер доли только на один бит больше, чем существующие границы. Кроме того, это первая схема, которая может определить мошенников и размер долей в которой не зависит от величин Мы также представляем схемы, которые могут идентифицировать до и мошенников, с долями, приблизительно равными и соответственно. Количество мошенников, которое могут идентифицировать последние две схемы, определяется теоретической верхней границы.
Ключевые слова: Разделение секрета, Мошенник, Идентификация, код Рида-Соломона.

Введение

Схема разделения секрета это криптографический метод, в котором секрет делится на доли среди участников таким образом, что только их коалиция может восстановить сам секрет. Это фундаментальная система, применяемая во многих криптографических протоколах, которая часто используется при проведении безопасных многосторонних вычислений. Из-за важности данного вопроса для криптографии, схемы активно изучались на протяжении более трех десятилетий с момента первых работ Шамира [1] и Блэкли [2].

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

Схемы разделения секрета, способные не только обнаружить мошенничество, но и выявить мошенников, предоставляющих неверные доли, также в настоящее время является актуальной тема в этой области. Рабин и Бен-Ор предложили схему разделения секрета k из n, способную идентифицировать мошенников [10]. Размер доли будет равен , где обозначает размер секрета[прим. 1]. В работе [11] Куросава, Обана и Огата показали, что, когда число мошенников , размер долей значительно снижается в сравнении с работой [10]. Размер долей в их схеме составляет, что до сих пор представляло наиболее эффективную схему, несмотря на тот факт, что длина их схемы в битах зависит линейно от числа мошенников.

В соответствии в определением, данным Куросавой и соавт. [11], нижняя граница размера доли определяется следующим образом:

,

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

В этой статье мы сначала представим эффективную пороговую схему разделения секрета из позволяющую идентифицировать до мошенников, при условии что Несмотря на то, что это условие такое же, как у Куросавы и соавт. [11], размер долей значительно уменьшается по сравнению с работой [11]. А именно, размер доли для первой схемы будет составлять и будет только на один бит больше, чем граница уравнения . Мы также представим такую схему, в которой определение вероятностей успеха осуществления обмана мошенниками возможно без учета размера секрета, что не осуществимо в первой схеме. Мы также покажем пороговые схемы из которые могут идентифицировать до мошенников, таких что и . Количество мошенников, которое могут определить эти две схемы, достигает теоретического предела, когда четно и для любого , соответственно. Размеры долей в схемах могут быть приближенно записаны как и , соответственно, которые также намного меньше, чем у Куросавы и соавт., несмотря на различие в возможностях идентификации мошенников.

Отметим, что по отношению к мошенничеству схемы разделения секрета тесно связаны с обеспечением безопасности передачи сообщений, как отмечается в работах [12][13]. Таким образом, мы считаем, что идеи, используемые для построения предлагаемых схем, помогают получить безопасную схему передачи сообщений.

Оставшаяся часть работы построена следующим образом. В разделе 2 дается краткий обзор моделей схем разделения секрета, способных выявлять мошенников, и мы обсуждаем связанные с ними работы. В разделе 3 мы представляем практически оптимальные схемы, которые могут идентифицировать до мошенников. В разделах 4 и 5, мы описываем эффективные схемы, которые могут идентифицировать до и соответственно. В разделе 6 мы обобщаем итоги нашей работы.

Предварительные сведения

Схемы разделения секрета

В моделях схем разделения секрета существует участников и дилер Модель состоит из двух алгоритмов: ShareGen и Reconst. Алгоритм генерации долей ShareGen на входе принимает секрет , а на выходе выдает список Каждый элемент списка называется долей и передается участнику В обычном случае алгоритм ShareGen осуществляется дилером. Алгоритм восстановления Reconst принимает список долей и выводит секрет

Перечень участников, имеющих право восстанавливать секрет, определяется структурой доступа то есть участники могут восстановить секрет, только в том случае, если (например, структура доступа для пороговой схемы разделения секрета из определяется как Схема разделения секрета называется совершенной, если выполняются следующие два условия для выхода алгоритма ShareGen, где вероятность берется случайным образом в ShareGen.

  1. если , то ,
  2. если , то для любых .

Отметим, что в данной работе рассматриваются только совершенные схемы разделения секрета.

Схемы разделения секрета с t мошенниками

Схема разделения секрета, способная идентифицировать мошенников впервые была представлена Рабином и Бен-Ором в работе [10]. Они рассматривали случай, в котором мошенники, не принадлежащие к структуре доступа, представляют неверные доли на фазе восстановления. Такие мошенники будут успешны, если они не могут быть идентифицированы в качестве мошенников на стадии восстановления секрета.

Как и в обычные схемы разделения секрета, эта модель состоит из алгоритмов ShareGen и Reconst. Алгоритм генерации долей ShareGen здесь такой же, что и в обычной схеме разделения секрета. Два типа алгоритмов восстановления секрета определяются в зависимости от того, идентификация мошенника делается индивидуально или по группам. Мы будем использовать алгоритмы и соответственно. Алгоритм восстановления секрета использует так называемую базовую долю список долей в качестве входных данных и выводит пару из секрета и перечня мошенников, то есть, если мошенники не обнаружены, алгоритм выводит пару где это восстановленный секрет. Если алгоритм обнаруживает мошенников, а секрет может быть восстановлен из достоверных долей, то алгоритм выводит (где и это набор мошенников, предоставляющих неверные доли), в противном случае (т.е. если секрет не может быть восстановлен из достоверных долей), он выводит где это специальный символ, указывающий, что обман был обнаружен и представляет собой набор мошенников. В алгоритме базовые доли являются основанием для определения, будет ли участник, обращающийся к мошенником. С другой стороны, алгоритм Reconst (pub) определяет мошенников без доверительных долей, он берет на входе перечень долей и выводит из секрета и списка мошенников. Мы требуем, чтобы алгоритмы ShareGen и Reconst удовлетворяли следующим условиям корректности:

для любых и , таких как

Безопасность модели может быть продемонстрирована при помощи следующей простой игры, определенной для любой пороговой схемы разделения секрета из и для любой (не обязательно полиномиально ограниченной) машины Тьюринга где представляет собой мошенников которые пытаются обмануть честных участников при





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

С другой стороны, в индивидуальной модели, вероятность успешного обмана определяется для каждой базовой доли. Таким образом, мы определим данную вероятность как , где

где первый аргумент из определяет базовые доли. Вероятности берутся по распределению и по случайным данным из ShareGen и Обратим внимание, что описанная игра неявно предполагает единовременное восстановление секрета; что в свою очередь значит, что все участники представляют свои доли алгоритму восстановления одновременно на фазе восстановления. Таким образом, так называемые "нападающие противники", пытающиеся реализовать свою долю после вскрытия долей честными участниками, не допускаются в этой модели.

Мошенников в этой модели можно разделить на два класса: критичные и некритичные. Некритичные мошенники только раскрывают свою информацию другим мошенникам или подделывают доли таким образом, что подделки не приводят к неверному восстановлению исходного секрета алгоритмом восстановления. С другой стороны, критичные мошенники представляют доли, которые приводят к неверному восстановлению исходного секрета. В этой работе мы сконцентрируемся на выявлении только критичных мошенников, так как основная цель мошенников в рассматриваемых моделях состоит в том, чтобы при восстановлении другими участниками получался недействительный секрет. Формальное определение критичных мошенников для групповой модели идентификации дается следующим образом:

TemplateDifinitionIcon.svg Определение «Определение 1.»
Пусть выводится из Участники представляющие доли алгоритму называются критичными мошенниками тогда и только тогда, когда существуют такие что выполнено

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

TemplateDifinitionIcon.svg Определение «Определение 2.»
Пусть выводится из Участники представляющие доли алгоритму называются критичными мошенниками по отношению к тогда и только тогда, когда существуют такие что

Исходя из этого определения, мы определяем безопасность схем разделения секрета, способных выявить мошенников, как для групповых, так и для индивидуальных моделей следующим образом:

TemplateDifinitionIcon.svg Определение «Определение 3.»
Пороговая схема разделения секрета называется схемой с групповой идентификацией, если для любого - набора или менее мошенников и для любых критичных мошенников
TemplateDifinitionIcon.svg Определение «Определение 4.»
Пороговая схема разделения секрета называется индивидуально идентифицирующей схемой, если для любого - набора или менее мошенников и для любых критичных мошенников и для любых честных участников

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

Также заметим, что идентифицирующая схема разделения секрета отличается от верифицирующей схемы (VSS) в том смысле, что в идентифицирующей схеме дилер не мошенничает в , тогда как в верифицирующей это возможно.

Предыдущие работы

В этом пункте мы кратко рассмотрим известные способы построения и оценки идентифицирующих схем разделения секрета и смежные вопросы.

Возможность выявления мошенников в схемах разделенея секретов впервые была изучена Мак-Элисом и Сарватом в работе [14]. В частности, они отметили, что список долей пороговой схемы разделения секрета Шамира представляет собой код Рида-Соломона. Поэтому, если при восстановлении секрета имеется долей, среди которых содержится недействительных долей, тогда алгоритм восстановления может идентифицировать всех мошенников с вероятностью равной 1. Однако это наблюдение не приводит к построению идентифицирующей схемы разделения секрета, так как для идентификации мошенников необходимо не менее долей.

идентифицирующие схемы разделения секрета с индивидуальной идентификацией мошенников описаны в различной литературе. Здесь мы кратко рассмотрим полученные ранее результаты. В работах [10][15], Рабин и Бен-Ор представили верифицирующую схему разделения. Особенности их схемы можно обобщить с помощью следующего предположения:

TemplateDifinitionIcon.svg Определение «Предположение 1 [10][15]
Существует пороговая идентифицирющая схема разделения секрета с индивидуальной идентификацией мошенников с параметрами и где это степень простого числа.

Карпентиери предложил схему, в которой размер долей уменьшен по сравнению с работами [10][15]:

TemplateDifinitionIcon.svg Определение «Предположение 2 [16]
Существует пороговая идентифицирющая схема разделения секрета с групповой идентификацией мошенников с параметрами и , где это степень простого числа.

Огата и Куросава предложили удобную схему, в которой размер доли не зависит от

TemplateDifinitionIcon.svg Определение «Предположение 3 [17]
Существует пороговая идентифицирющая схема разделения секрета с индивидуальной идентификацией мошенников с параметрами и где это степень простого числа.

Отметим, что схемы в работах [10][15] (предположение 1) и в работе [16] (предположение 2) безопасны даже тогда, когда мошенник знает доли участников, в то время, как схема из работы [17] (предположение 3) обеспечивает защиту от мошенников, которые знают не более долей.

Что касается схем с групповой идентификацией мошенников, Куросава, Обана и Огата представили эффективную схему, размер долей в которой зависит только от максимального количество мошенников [11]. Свойства их схемы можно обобщить следующим образом:

TemplateDifinitionIcon.svg Определение «Предположение 4 [11]
Если то существует пороговая идентифицирующая схема разделения секрета с групповой идентификацией мошенников с параметрами и где это степени простых чисел, [прим. 2].

В работе [11], Куросава и соавт. также определили нижнюю границу размера доли для пороговых идентифицирующих схем разделения секрета, как с индивидуальной, так и с групповой идентификацией, следующим образом:

TemplateDifinitionIcon.svg Определение «Предположение 5 [11]
Размер доли для пороговой идентифицирующей схемы разделения секрета ограничен снизу неравенством

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

Схемы с групповой идентификацией мошенников для Схемы с групповой идентификацией мошенников для t ⩽ b k − 1 3 c   {\displaystyle t\leqslant {\mathcal {b}}{\frac {k-1}{3}}{\mathcal {c}}~\,\!}

В этом разделе мы представляем две эффективные пороговые идентифицирующие схемы разделения секрета с групповой идентификацией мошенников при условии, что Первая схема практически оптимальна в отношении размеров долей, то есть размер долей в битах в схеме только на один бит больше нижней границы предположения 5. Вторая схема, даже в отношении размера долей немного сложнее, чем первая, и в частности хороша тем, что вероятности успешного обмана мошенниками определяются без учета размера секрета, что невозможно ни в первой схеме, ни в схеме из работы [11].

Как и в схеме из работы [11], предложенная схема использует код Рида-Соломона для выявления мошенников. Главное отличие между схемой из работы [11] и предлагаемой заключается в следующем. В работе [11], доля каждого из участников состоит из (1) доли для схемы разделения секрета Шамира, (2) доли схемы разделения секрета для ключей универсальных хэш-функции (см. работу [18] для определения,) и (3) хэш-значение доли (1) при ключе (2). Здесь, кода Рида-Соломона используется в (2), чтобы не позволить мошенникам изменять значение ключа, используемого для определения достоверности долей (как отмечалось в работе [14], схема разделения секрета является обобщенным кодом Рида-Соломона). Поскольку размер ключа для универсальной хэш-функции такой же, как у долей схемы из работы [11], он растет линейно с числом мошенников. С другой стороны, доля в предлагаемой схеме состоит только из (1) доли схемы Шамира для секрета, и (2) хэш-значение (1), вычисленного универсальной хэш-функцией Интересно, что ключ, используемый для вычисления хэш-значения, не явно распределяется среди участников и извлекается из хеш-значений на стадии восстановления, используя возможность коррекции ошибок в коде Рида-Соломона. Это стало возможным за счет выбора универсального хэш набора, на основе конечных многочленов. Поскольку в предлагаемой схеме размер хэш-значение равен мы отмечаем, что размер доли удовлетворяет равенству которое не зависит от Подробное описание первой схемы приведено в следующем разделе.

Практически оптимальная схема

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

Генерация долей: Принимая на входе секрет , алгоритм ShareGen выводит список долей следующим образом:

  1. Генерируется случайный многочлен такой степени что
  2. Генерируется случайный многочлен степени
  3. Вычисляется и выводится

Восстановление секрета и идентификация мошенников: Принимая на входе список из долей алгоритм Reconst выводит восстановленный секрет или перечень мошенников следующим образом:

  1. Восстанавливается из с помощью алгоритма коррекции ошибок обобщенного кода Рида-Соломона (например, алгоритм Берлекэмпа.)
  2. Проверяется справедливость равенства для Если , тогда вносится в список мошенников
  3. Если тогда восстанавливается из ( или более) долей таких, что при помощи интерполяции Лагранжа, и выводится , если , в противном случае алгоритм Reconst выводит Reconst также выход если

Безопасность предложенной схемы можно определить следующей теоремой.

TemplateTheoremIcon.svg Теорема Теорема 1.
Если то предлагаемая схема будет идентифицирующей схемой разделения секрета с групповой идентификацией мошенников и справедливо следующее
Доказательство

Во-первых, мы покажем, что схема является совершенной. Если точно известно, что не раскрывают никакой информации о секрете, так как каждая доля это доля из схемы разделения секрета Шамира. Далее, легко показать, что знание долей не дает никакой утечки информации о секрете, так как многочлен является полностью независимым от секрета

Далее мы покажем, что схема является идентифицирующей, для этого используются следующие два ключевых факта:

  1. это код Рида-Соломона с минимальным расстоянием Поэтому, если ( т.е. ), тогда может быть восстановлен даже при наличии подделок.
  2. Множество функций представляет собой класс универсальных хэш-функций <nath> GF(q) \rightarrow GF(q) ~\,\! </math> силы для любых и это подразумевает выполнение следующего равенства

Без ограничения общности можно считать, что являются мошенниками, совместно пытающимися обмануть других участников, подделывая (часть) своих долей. Предполагается, что является основным мошенником, которому известны (т.е. доли для ) и предоставляет ненастоящие доли такие, что . не распознается как мошенник, только если он предоставляет такую , что , потому что алгоритм Reconst может восстановить исходный секрет даже если долей поддельны. Кроме того, так как относятся к классу универсальных хэш-функций и отличается от любого из имеет место равенство:

где вероятность берется для случайного выбора Так выше приведенные рассуждения справедливы для любого критичного мошенника мы видим, что ни один критичный мошенник не может добиться успеха в обмане, не будучи обнаруженным с вероятностью не меньше чем


Следует отметить, что размер долей в предложенной схеме не зависит от , хотя существует неявное ограничение . Оно подобно ограничению для схемы Шамира, требующему чтобы

Схема со свободным выбором параметров

Как мы отмечали в предыдущем разделе, существует ограничение в первой схеме, что вероятность успешного обмана мошенниками должна быть меньше, чем Это ограничение не желательно, особенно в случае. Если мы хотим разделить секрет большого размера. Рассмотрим случай, когда мы хотим разделить секрет в 1 Мбит (т.е. ) при помощи первой схемы. В этом случае размер доли становится равным 2Mбит с уровнем безопасности , тогда как на деле достаточно будет Вторая схема применима в том случае, если вероятность успешного обмана мошенниками определяется вне зависимости от размера секрета, а размер долей в свою очередь можно разумно уменьшить. Например, когда мы разделяем секрет в 1Mбит при помощи второй схемы с параметром , размер долей становится равным (1М+282) бит.

Основная идея второй схемы аналогична подходу в первой схеме. В первой схеме мы используем следующий трюк для того, чтобы получить гибкость по параметрам и В первой схеме выбирается такой случайный многочлен из множества , чтобы было справедливо и для любых и , а это приводит к неравенству Во второй схеме, мы вводим понятие практически универсальной хэш-функции (например, в работе [18]), (где ) и заменяем вход ( для второй схемы) на , где инъективная функция. Использование реализует равенство с малой вероятностью, однако, ограничение может быть устранено, поскольку выбирается на основе параметров и представляет из себя множество универсальных хэш-функций , определенных в Алгоритм генерации долей и алгоритм восстановление секрета для второй схемы определяются следующим образом:

Генерирование долей: Принимая на входе секрет , алгоритм генерации долей ShareGen выводит список долей следующим образом:

  1. Генеруется случайный многочлен степени такой что
  2. Случайным образом генерируется и строится случайного многочлен степени такой, что
  3. Генерируется случайный многочлен степени такой, что
  4. Вычисляется , где и
  5. Вычисляется и выводится

Восстановление секрета и идентификация мошенников: Принимая на входе список долей , алгоритм восстановления секрета Reconst выводит исходный секрет или список обнаруженных мошенников следующим образом:

  1. Восстанавливается и из и соответственно, при использовании алгоритма коррекции ошибок Рида-Соломона.
  2. Проверяется равенство . Если тогда добавляется в список мошенников
  3. Вычисляется
  4. Если справедливо равенство для тогда добавляется в список мошенников
  5. Если тогда восстанавливается из ( или более) долей таких, что для этого использовуется интерполяция Лагранжа, и выводится если в противном случае Reconst выводит Reconst также выводит если выполняется

Безопасность предложенной схемы можно описать с помощью следующей теоремы. Обратим внимание, что вероятность успешного обмана может быть определена без учета за счет правильного выбора значения

TemplateTheoremIcon.svg Теорема Теорема 2.
Если тогда предлагаемая схема будет идентифицирующей схемой разделения секрета с такой групповой идентификацией мошенников, что
Доказательство

Как и в доказательстве теоремы 1, можно предположить, что являются мошенниками, которые пытаются совместно обмануть других участников, изменяя (части) свои доли. Предполагая, что является основным мошенником, предоставляющим доли такие, что Так как соответствует коду Рида-Соломона, способного исправлять до ошибок, мошенников не могут изменить значение Таким образом, не определяется как мошенник, только в том случае, если он предоставляет такие, что где равномерно и случайно распределено по Существует способа определения такой вероятности. В первом случае предполагается, что изменил свою долю таким образом, В этом случае вероятность успешного обмана для при выполненном вычисляется следующим образом (для простоты мы обозначим как )

где последнее неравенство непосредственно следует из того, что является множеством строго универсальных хэш-функций силы (см. доказательство теоремы 1.)

Теперь рассмотрим второй случай, когда изменяет свою долю таким образом, что В этом случае вычисляется следующим образом:

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


Обратим внимание на то, что в представленной схеме размер в битах долей примерно равен Таким образом, мы можем определить размер секрета и вероятность успешного обмана, затратив лишь дополнительных битов.

Схемы с групповой идентификацией для Схемы с групповой идентификацией для t ⩽ b k − 2 2 c   {\displaystyle t\leqslant {\mathcal {b}}{\frac {k-2}{2}}{\mathcal {c}}~\,\!}

В этом разделе мы покажем, что мы можем построить эффективную схему с групповой идентификацией мошенников, даже когда число мошенников не удовлетворяет неравенству Точнее, мы представляем схему с групповой идентификацией, алгоритм восстановления секрета в которой может распознать до мошенников. Отметим, что способность идентифицировать мошенников в данной схеме близка к оптимальной, так как является верхней теоретической границей для идентификации мошенников. Кроме того, размер доли в предложенной схеме значительно меньше, чем в работе [11], несмотря на различие в их идентификации мошенников.

Алгоритм генерации долей для данной схемы идентичен описанному в разделе 3.1. Для определения более чем мошенников алгоритм восстановления секрета проверяет согласованность всех возможных подмножеств для долей, входных для алгоритма. Здесь, последовательность из долей проверяется путем проверки принадлежности величин многочлену степени Идея здесь заключается в следующем. Допустим, что мошенников пытаются обмануть алгоритм восстановления, изменяя свои доли. Поскольку мы предполагаем, что то существует, по крайней мере неповрежденные доли, используемые в алгоритме восстановления. Таким образом, мы может гарантировать, что существует, по крайней мере, одно подмножество (размера ) последовательных долей (то есть тех долей, которые не содержат изменений) и любые подмножества размера содержат, по крайней мере, две неизмененных доли. Мы будем использовать эти факты, для определения мошенников, так как множество из долей, содержащее как измененные, так и неизменные доли, может быть последовательным только с очень малой вероятностью. Подробное описание предлагаемого алгоритма восстановления заключается в следующем:

Восстановления секрета и идентификация мошенников для : Принимая на входе список из долей алгоритм восстановления секрета Reconst выводит исходный секрет или перечень обнаруженных мошенников следующим образом.

  1. Если выводится где представляет из себя алгоритм восстановления для (т.е. алгоритм , представленный в 3.1.)
  2. В противном случае задается и шаги повторяются для всех подмножества и
    (а) Вычисляется где где является коэффициентом перед в многочлене построенном из значений
    (b) Если тогда (т.е. удаляется из списка мошенников.) Отметим, что если все доли не изменены после выбора случайного многочлена степени в алгоритме генерации долей.
  3. Если тогда восстанавливается из таких ( или более) долей что используя интерполяцию Лагранжа, и выводится если в противном случае Reconst выводит также выводит если

Безопасность предложенной схемы можно сформулировать в следующей теореме.

TemplateTheoremIcon.svg Теорема Теорема 3.
Если тогда предлагаемая схема будет идентифицирующей схемой разделения секрета с такой групповой идентификацией мошенников, что
Доказательство

Как и в доказательстве теоремы 1, можно предположить, что являются мошенниками, пытающимися совместно обмануть других участников заменой (части) их долей. Предположим, что является основным мошенником, предоставляющим недействительные доли такие, что Покажем, что вероятность успешного обмана для ограничена сверху равенством

Из доказательства теоремы 1, легко увидеть, что если тогда вероятность успешного обмана для ограничена сверху так как мы можем применить алгоритм коррекции ошибок Рида-Соломона для

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

Для подтверждения вышесказанного, мы сначала покажем, что вероятность выполнения равенства для заданного ограничена снизу для любого при и Без ограничения общности можно считать, что и являются мошенниками.

Для оценки мы будем анализировать структуру Здесь мы используем обозначение для величины и также для обозначения тех переменных которые контролируются мошенниками.

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

При известных долях, принадлежащих мошенникам, количество возможных кандидатов для становится равным так как распределено случайно, равномерно и независимо на множестве даже при известных мошенниках, и однозначно определяет многочлен

Теперь мы оценим верхнюю границу значений , для которых Для любого фиксированного уравнение можно переписать следующим образом:

где являются постоянными при фиксированных и . Легко увидеть, что существует не более значений для которых Таким образом, верхняя граница числа нулей в уравнении может быть оценена следующим образом:


Таким образом, нижняя граница для задается как

Из приведенного выше неравенства и того факта, что число подмножеств для таких, что и будет равняться в свою очередь вероятность успешного обмана задается следующим образом:

существует такое, что


Размер долей равняется и примерно записывается как при и


Хотя размер долей растет экспоненциально с ростом числа мошенников, в нашей схеме размер доли намного меньше по сравнению с моделью Куросавы и соавт. [11], в которой размер доли определяется как (отметим, что ) Даже по сравнению с теоретической нижней границей для уравнения , размер предложенной схемы в битах лишь на бит больше. С другой стороны, недостаток предлагаемого алгоритма восстановления заключается в его вычислительной неэффективности. На деле алгоритму восстановления для выявления мошенников требуется вычислить интерполяцию Лагранжа раз. Однако, в обычном случае, идентификация мошенников предложенной схемой по-прежнему возможна. Рассмотрим, например, случай, когда мы хотим обнаружить до 10 мошенников (т.е. ). Число необходимых интерполяций Лагранжа составляет что осуществимо даже на персональном компьютере.

Следует отметить, что для схемы, приведенной в разделе 3.2, может быть использована методика подбора.

Схемы с групповой идентификацией для Схемы с групповой идентификацией для t ⩽ b k − 1 2 c   {\displaystyle t\leqslant {\mathcal {b}}{\frac {k-1}{2}}{\mathcal {c}}~\,\!}

Схема, приведенная в разделе 4, имеет теоретическую верхнюю границу для количества мошенников, которое схема может определить, когда порог это четное число. Это справедливо потому, что выполнено для четных Если нечетное, тогда схема не сможет выявить мошенников. В этом разделе мы представляем схему с групповой идентификацией, способную выявить мошенников. Размер долей в предлагаемой схеме не настолько мал, как в схеме для однако, этот размер по-прежнему намного меньше, чем в работе [11].

Здесь мы рассмотрим схемы, представленные в предыдущем разделе, чтобы пояснить идею предложенной схемы для Алгоритм восстановления в схеме для обнаруживает мошенников, проверяя степень многочлена, восстановленного из точек. Используя эту технику, можно обеспечить, чтобы точки, содержащие поддельные доли не могли построить многочлен степени меньше или равной , и точки, содержащие неизменные доли могли построить многочлен степени меньше или равной К сожалению, эта техника не применима, когда так как любые доли содержат, по крайней мере, одну поддельную доли и мы не можем найти все множество честных долей (и, следовательно, не можем правильно определить мошенников.)

Чтобы поиск честных долей был возможен путем изучения последовательности из долей, в предлагаемой схеме доли определяются как где это доля схемы Шамира из а это значения для многочленов и при Тогда мы можем проверить последовательность из долей, проверяя равенство где и это коэффициенты при и в многочленах и соответственно, где и это восстановленные из долей. Так как в предложенной схеме требуется дополнительный элемент ( ), то размер долей становиться больше, чем в схеме для

Алгоритм генерации долей и алгоритм восстановления секрета в предложенной схеме описываются следующим образом, где для и справедливо и является инъективной функцией.

Генерация долей: Принимая на входе секрет алгоритм генерации долей выводит список долей следующим образом:

  1. Создается случайный многочлен степени такой, что
  2. Создается случайный многочлен такой, что
  3. Вычисляется и выводится

Восстановление секрета и идентификация мошенников: Принимая на входе список из долей алгоритм восстановления секрета выводит исходный секрет или перечень обнаруженных мошенников следующим образом.

  1. Если справедливо выводится где обозначает алгоритм восстановления секрета для (т.е. алгоритм из раздела 3.1.)
  2. В противном случае и повторяются следующие шаги для всех подмножеств при
    (а) Вычисляются и следующим образом:


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

Безопасность предложенной схемы можно описать с помощью следующей теоремы.

TemplateTheoremIcon.svg Теорема Теорема 4.
Если тогда предлагаемая схема будет идентифицирующей схемой разделения секрета с групповой идентификацией мошенников, и при этом
Доказательство

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

Как и в доказательстве теоремы 3, можно предположить, что являются мошенниками, совместно пытающимися обмануть других участников изменяя (часть) своих долей. Предполагаем, что является основным мошенником, предоставляющим недействительную долю такую что Покажем, что вероятность успешного обмана для ограничена сверху значением

Из доказательства теоремы 1, легко увидеть, что если тогда вероятность успешного обмана для ограничена сверху значением

Теперь мы покажем, что предложенный алгоритм восстановления может определить мошенников с вероятностью больше, чем