Argument of knowledge of a Goppa codeword and of a bounded error.pdf Рассматривается задача проверки утверждения об ошибке в искаженном кодовомслове кода Гоппы. Дополнительным условием является предоставление проверяющейстороне минимально необходимой информации о структуре кода, кодовом слове и весеошибки. Рассматриваются интерактивные протоколы (interactive proof system) ипротоколы доказательства знания (proof of knowledge) значений, из которых полученыэкземпляры привязки (commitment). Произвольный Доказывающий, который незнает компонентов кодового слова и коэффициентов полинома Гоппы, удовлетворяющихпроверяемым условиям, имеет только ничтожную вероятность успешно завершитьпротокол с честным Проверяющим.Рассматриваются протоколы аргумента, в которых как Проверяющий, так и Доказывающийрасполагают только полиномиальными ресурсами. Рассматривается схемазапрос - ответ, в которой запросом является значение переменной некоторого полиноманад конечным полем, а проверяемым условием - равенство нулю этого полинома.Рассматриваются условия, эквивалентные определению кодового слова кода Гоппыи утверждению о верхней границе веса ошибки. Также рассматриваются проверочныеполиномы, в которых компоненты кодового слова и коэффициенты полинома Гоппызаменяются ответами Проверяющего.Полученный протокол имеет свойство полноты (completeness), свойство корректности(soundness) в предположении о сложности задачи поиска логарифма в конечнойгруппе, является аргументом знания кодового слова и полинома Гоппы, имеет специальноесвойство нулевого разглашения в модели с честным проверяющим (specialhonest verifier zero knowledge). Ошибка корректности протокола экспоненциально мала,параметром безопасности является количество бит в двоичном представлении порядкагруппы.П р о т ок ол для сл ова кода Гоппы, полинома Гоппы и ош и бки ограниченноговесаОбщая информация Проверяющего и Доказывающего: порядок q и пара элементовгруппы (h, f ), дополнительные значения {aj } j =1...N, искаженное кодовое слово{wj}j=i...N, экземпляры привязки к коэффициентам полинома {V .}k=0...T и к компонентамкодового слова {Wj } j=1...N, верхняя граница веса ошибки S .Информация Доказывающего: коэффициенты полинома {д .} и дополнительныезначения {0 .}, компоненты кодового слова {b j} и дополнительные значения { ^ j }, такиечто Vfc = Ы*f вк, Wj = hbjf и g(z) = E l =0 zkgk, Е ^ 1 j = 0 (mod g (z)),|{j 1 bj = wj }| ^ S .Доказывающий демонстрирует знание значений {b j} и { g . }, из которых были полученыэкземпляры привязки {W j} и {V .}, а также справедливость утверждения овесе ошибки.1) Проверяющий выбирает запрос d Е Fq и пересылает его Доказывающему.2) Доказывающий выбирает { a . , }k=0...T, { в , П }j= 1...N, {Mt=0...N, {Ts}s=0...s Е Fq,получает коэффициенты {r t}, {ps}, экземпляры привязки {Uk}, {Q j}, {R t}, {P s}:N T dk - ak N T NX (ybj + e j ^ X (ygk + a k) d _ j П X (ygm + а т )аГ J=1 k=1 d a jj i=1,i=j m=0 = t=0 ^N SI I (ybj + e - ywj ) = Xj=1 s=0= h" fc f , Qj = he f , Rt = hrt h^' , Ps = hPs hTs.Доказывающий пересылает {Uk}, {Q j }, {R t}, {P s} Проверяющему.3) Проверяющий выбирает запрос с Е Fq и пересылает его Доказывающему.4) Доказывающий получает ответы и пересылает их Проверяющему:Ф k cgk + a k, Gk C$k + , ^ j cbj + ^ j, Ф^' c^j + nj ,N SA = X cVt, A' = X csTs.t=0 s=05) Проверяющий получает значения проверочных полиномов:N T ,fc _ N T Nг = . ^j . ф*- г - т П . г ' = П (% - cj=l k=l - aj j i=l,i=jm=0 j=l ®j).Проверяющий рассматривает демонстрацию как убедительную, еслиN Sh*k f &k VTc = U Л h^ W - = Qj Л hr f A П R - c' = 1 Л hr' f A П Ps- cS = 1.

Скачать электронную версию публикации