УСТРОЙСТВО АУТЕНТИФИКАЦИИ, СПОСОБ АУТЕНТИФИКАЦИИ И ПРОГРАММА Российский патент 2016 года по МПК H04L9/32 G06F21/60 

Область техники, к которой относится изобретение

Настоящее раскрытие относится к устройству аутентификации, способу аутентификации и программе.

Уровень техники

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

Цифровая подпись используется для установления автора электронного документа. В соответствии с этим, цифровая подпись должна обладать возможностью ее генерирования только автором электронного документа. Если злонамеренная третья сторона получит возможность генерировать такую цифровую подпись, такая третья сторона может выдать себя за автора электронного документа. Таким образом, электронный документ будет подделан злоумышленной третьей стороной. Различные мнения были выражены в отношении защиты цифровой подписи для предотвращения такой подделки. В качестве схемы цифровой подписи, которая в настоящее время широко используются, известны, например, схемы, в которых используются схема подписи RSA и схема подписи DSA.

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

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

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

Среди этих задач другие задачи, кроме задачи поиска сечения на алгебраической поверхности, известны, как NP-трудно решаемые. В качестве варианта применения, например, в непатентной литературе 1 и в непатентной литературе 2, упомянутых ниже, раскрыты схемы аутентификации с открытым ключом на основе задачи декодирования синдрома. Кроме того, в непатентной литературе 3, упомянутой ниже, раскрыта схема аутентификации с открытым ключом на основе задачи ядра с перестановками. Кроме них, также предложена схема аутентификации с открытым ключом на основе задачи ограниченных линейных уравнений, схема аутентификации с открытым ключом на основе задача восприятия с перестановками и т.п.

Список литературы

Непатентная литература

Непатентная Литература 1: Jacques Stern, A New Identification Scheme Based on Syndrome Decoding, CRYPTO 1993, p13-21

Непатентная литература 2: Jacques Stern, A New Paradigm for Public Key Identification, IEEE Transactions on Information Theory, 1996, p13-21

Непатентная литература 3: Adi Shamir, An Efficient Identification Scheme Based on Permuted Kernels (Extended Abstract), CRYPTO 1989, p606-609

Раскрытие изобретения

Техническая задача

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

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

Существующая схема аутентификации с открытым ключом представляет собой схемы, в которых контролер подтверждает для проверяющего “знание значения s, которое удовлетворяет y = F (s) для данного y”, используя одну пару ключей (открытый ключ y, секретный ключ s). В соответствии с этим, если было выполнено взаимодействие, которое было принято при проверке, не было возможности предотвратить знание проверяющим информации о том, что “контролер, который выполнил взаимодействие, использовал значение s”. Кроме того, в конфигурации с параллельным повторением схемы аутентификации с открытым ключом этого типа, если устойчивость к коллизии не была гарантирована для F, не было известно, был ли абсолютно гарантирован достаточный уровень безопасности для активной атаки, или нет. Фактически, устойчивость к коллизиям не гарантируется для функции F, используемой в схемах аутентификации с открытым ключом, описанных выше.

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

Решение задачи

В соответствии с аспектом настоящего раскрытия, для достижения описанной выше цели предусмотрено устройство аутентификации, которое включает в себя модуль хранения ключей для хранения L (L≥2) секретных ключей s_i(i = от 1 до L) и L открытых ключей y_i, которые удовлетворяют уровню y_i = F (s_i) в отношении набора F многочленов нескольких переменных n-го порядка (n≥2), и модуль выполнения интерактивного протокола для выполнения проверяющим интерактивного протокола для проверки знания (L-1) секретных ключей s_i, удовлетворяющих условию y_i=F(s_i). Модуль выполнения интерактивного протокола не допускает во время выполнения интерактивного протокола проверяющим знания проверяющим, какой секретный ключ S_i был использован.

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

Далее, модуль выполнения интерактивного протокола может дополнительно включать в себя модуль передачи сообщения для передачи проверяющему сообщений Cmt_i, каждое из которых соответствует каждому из L секретных ключей S_i. В этом случае модуль приема вызовов принимает вызов Ch_i, указывающий схему проверки, выбранную из k (k≥2) схем проверки с помощью проверяющего, в соответствии с каждым сообщением Cmt_i, переданным модулем передачи сообщения.

Далее, в случае сообщения Cmt_i=(c_{i, 1}, …, c_{i, N}) модуль передачи сообщения может вычислить новое сообщение Cmt'=Н(Cmt₁, …, Cmt_L) с использованием односторонней функции H и передать это сообщение Cmt' проверяющему, а модуль передачи ответа может передавать, вместе с ответом Rsp_i, элемент сообщения Cmt_i, о том, что проверяющий не может осуществить восстановление, даже когда используется ответ Rsp_i.

Кроме того, модуль хранения ключей может не хранить один секретный ключ s_i0(1≤i₀≤L) среди L секретных ключей S_i. В этом случае модуль выполнения интерактивного протокола выполняет, на основе алгоритма фальсификации, обработку, относящуюся к секретному ключу S_i0, которая должна подлежит выполнению в интерактивном протоколе.

Кроме того, в соответствии с другим аспектом настоящего раскрытия, для достижения описанной выше цели предусмотрено устройство аутентификации, которое включает в себя модуль хранения ключей для хранения L секретных ключей S_i(i=1-L) и L открытых ключей y_i, которые удовлетворяют условию y_i=F(s_i) в отношении набора F многочленов нескольких переменных n-го порядка (n≥2), модуль приема вызовов для приема Q наборов (Q≥2) из L вызовов CH_i ^(j)(j=1-Q) от проверяющего, модуль выбора вызовов для произвольного выбора одного набора из L вызовов CH_i ^(j) из Q наборов из L вызовов CH_i ^(j), принятых модулем приема вызовов, модуль генерирования ответов для генерирования с использованием секретных ключей s_i L ответов Rsp_i соответственно для L вызовов CH_i ^(j), выбранных модулем выбора вызовов, и модуль передачи ответа для передачи L ответов Rsp_i, генерируемых модулем генерирования ответа, проверяющему.

Кроме того, модуль выполнения интерактивного протокола может дополнительно включать в себя модуль передачи сообщений для передачи в проверочное устройство сообщений Cmt_i соответственно соответствующих L секретным ключам S_i. В этом случае модуль приема вызовов принимает вызов Chi_i ^(j), указывающий схему проверки, выбранную из k (k≥2) схем проверки проверяющим в соответствии с каждым сообщением Cmt_i, переданным модулем передачи сообщения.

Кроме того, в случае сообщения Cmt_i=(c_{i, 1}, …, c_{i, N}), модуль передачи сообщения может рассчитать новое сообщение Cmt'=H(Cmt₁, …, Cmt_L) с использованием односторонней функции H и передать это сообщение Cmt' проверяющему, а модуль передачи ответа может передать, вместе с ответом Rsp_i, элемент сообщения Cmt_i, который проверяющий не может восстановить, даже при использовании этого ответа Rsp_i.

Кроме того, в соответствии с другим аспектом настоящего раскрытия для достижения описанной выше цели предусмотрен способ аутентификации, который включает в себя этап генерирования ключей для генерирования L (L≥2) секретных ключей S_i (i = от 1 до L) и L открытых ключей y_i, которые удовлетворяют условию y_i=F(s_i), относительно набора F многочленов нескольких переменных n-го порядка (n≥2), и этап выполнения интерактивного протокола для выполнения, с помощью проверяющего, интерактивного протокола для подтверждения знания (L-1) секретных ключей S_i, которые удовлетворяют условию y_i=F(s_i). Этап выполнения интерактивного протокола не допускает, чтобы во время выполнения интерактивного протокола с помощью проверяющего, проверяющий знал, какой секретный ключ S_i был использован.

Кроме того, в соответствии с другим аспектом настоящего раскрытия для достижения описанной выше цели предусмотрена программа, обеспечивающая реализацию компьютером функции хранения ключей, состоящей в хранении L (L≥2) секретных ключей S_i (i = от 1 до L) и L открытых ключей y_i, которые удовлетворяют условию y_i=F(s_i) относительно набора F многочленов нескольких переменных n-го порядка (n≥2), и функции исполнения интерактивного протокола, состоящей в выполнении с помощью проверяющего интерактивного протокола для подтверждения знания (L-1) секретных ключей s_i, которые удовлетворяют условию y_i=F(s_i). Функция исполнения интерактивного протокола не допускает, чтобы во время выполнения интерактивного протокола с помощью проверяющего, проверяющий знал, какой секретный ключ S_i был использован.

Кроме того, в соответствии с другим аспектом настоящего раскрытия, для достижения описанной выше цели предусмотрен способ аутентификации, который включает в себя этап генерирования ключей для генерирования L секретных ключей s_i (i = от 1 до L) и L открытых ключей y_i, которые удовлетворяют условию y_i=F(s_i) относительно набора F многочленов нескольких переменных n-го порядка (n≥2), этап приема вызовов для приема Q наборов (Q≥2) из L вызовов Ch_i ^(j) (j = от 1 до Q) для проверяющего, этап выбора вызовов, на котором произвольно выбирают один набор из L вызовов Ch_i ^(j) из Q наборов L вызовов Ch_i ^(j), которые были приняты на этапе приема вызовов, этап генерирования ответа для генерирования с использованием секретных ключей s_i L ответов Rsp_i соответственно для L вызовов Chp_i ^(j), выбранных на этапе выбора вызовов, и этап передачи ответов для передачи проверяющему L ответов Rsp_i, сгенерированных на этапе генерирования ответов.

Кроме того, в соответствии с другим аспектом настоящего раскрытия для достижения описанной выше цели предусмотрена программа, обеспечивающая реализацию компьютером функции хранения ключей, состоящей в хранении L секретных ключей S_i (i = от 1 до L) и L открытых ключей y_i, удовлетворяющих условию y_i=F(s_i) относительно многочленов F нескольких переменных n-го порядка (n≥2), функции приема вызовов, состоящей в приеме Q наборов (Q≥2) из L вызовов Ch_i ^(j) (j = от 1 до Q) от проверяющего, функции выбора вызовов, состоящей в произвольном выборе одного набора из L вызовов Ch_i ^(j) из Q наборов из L вызовов Ch_i ^(j), принятых функцией приема вызовов, функции генерирования ответа, состоящей в генерировании с использованием секретных ключей S_i L ответов Rsp_i соответственно для L вызовов Ch_i ^(j), выбранных функцией выбора вызовов, и функции передачи ответов, состоящей в передаче L ответов Rspi, сгенерированных функцией генерирования ответов, проверяющему. В соответствии с другим вариантом осуществления настоящего раскрытия, предусмотрен считываемый компьютером носитель записи, на котором записана программа.

Полезные результаты изобретения

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

Краткое описание чертежей

На фиг.1 показана пояснительная схема для описания структуры алгоритма схемы аутентификации с открытым ключом;

на фиг.2 показана пояснительная схема для описания n-ходовой схемы аутентификации открытого ключа;

на фиг.3 показана пояснительная схема для описания интерактивного протокола схемы аутентификации с открытым ключом SSH10a;

на фиг.4 показана пояснительная схема для описания интерактивного протокола схемы аутентификации с открытым ключом SSH10b;

на фиг.5 показана пояснительная схема для описания конфигурации порядкового повторения интерактивного протокола;

на фиг.6 показана пояснительная схема для описания конфигурации с параллельным повторением интерактивного протокола;

на фиг.7 показана пояснительная схема для описания алгоритма фальсификации против интерактивного протокола схемы аутентификации с открытым ключом SSH10a;

на фиг.8 показана пояснительная схема для описания алгоритма фальсификации против интерактивного протокола схемы аутентификации с открытым ключом SSH10b;

на фиг.9 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a;

на фиг.10 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a (модифицированный пример 1);

на фиг.11 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a (модифицированный пример 2);

на фиг.12 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a (модифицированный пример 3);

на фиг.13 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10b;

на фиг.14 показана пояснительная схема для описания способа применения настоящего способа №1 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10b (модифицированный пример);

на фиг.15 показана пояснительная схема для описания способа применения настоящего способа №2 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a;

на фиг.16 показана пояснительная схема для описания способа применения настоящего способа №2 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10a (модифицированный пример);

на фиг.17 показана пояснительная схема для описания способа применения настоящего способа №2 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10b;

на фиг.18 показана пояснительная схема для описания способа применения настоящего способа №2 к интерактивному протоколу схемы аутентификации с открытым ключом SSH10b (модифицированный пример);

на фиг.19 показана пояснительная схема для описания способа уменьшения величины передаваемых данных в интерактивном протоколе схемы аутентификации с открытым ключом SSH10a;

на фиг.20 показана пояснительная схема для описания способа уменьшения величины передаваемых данных в интерактивном протоколе схемы аутентификации с открытым ключом SSH10b; и

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

Осуществление изобретения

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

Порядок пояснений

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

Далее, со ссылкой на фиг.7, будет описан алгоритм фальсификации против интерактивного протокола схемы аутентификации с открытым ключом SSH10a. Затем, со ссылкой на фиг.8, будет описан алгоритм фальсификации против интерактивного протокола схемы аутентификации с открытым ключом SSH10b. После, со ссылкой на фиг.9-12, будут описаны способы применения способа, в соответствии с первым вариантом осуществления (настоящий способ №1) настоящего раскрытия для интерактивного протокола схемы аутентификации с открытым ключом SSH10a. Затем способы применения настоящего способа №1 для интерактивного протокола схемы аутентификации с открытым ключом SSH10b будут описаны со ссылкой на фиг.13 и 14.

Потом способы применения способа, в соответствии со вторым вариантом осуществления (настоящий способ №2) настоящего раскрытия, для интерактивного протокола схемы аутентификации с открытым ключом SSH10a, будут описаны со ссылкой на фиг.15 и 16. Затем способы применения настоящего способа №2 для интерактивного протокола для схемы аутентификации с открытым ключом SSH10b будут описаны со ссылкой на фиг.17 и 18. Затем способы уменьшения количества передаваемых данных при интерактивных протоколах, в соответствии с настоящими вариантами осуществления, будут описаны со ссылкой на фиг.19 и 20. Затем пример конфигурации аппаратных средств в устройстве обработки информации, выполненного с возможностью реализации интерактивных протоколов, в соответствии с настоящими вариантами осуществления, будет описан со ссылкой на фиг.21. И, наконец, технические идеи, в соответствии с вариантом осуществления, будут сведены вкратце, и будут кратко описаны эффекты, полученные в результате технических идей.

Содержание описания

1: Введение

1-1: Структура алгоритма схемы аутентификации с открытым ключом

1-2: Схема аутентификации N-ходового открытого ключа

1-3: Интерактивный протокол схемы аутентификации с открытым ключом SSH10a

1-4: Интерактивный протокол схемы аутентификации с открытым ключом SSH10b

1-5: Конфигурация повторения интерактивного протокола

1-6: Алгоритм фальсификации против схемы аутентификации с открытым ключом SSH10a

1-7: Алгоритм фальсификации против схемы аутентификации с открытым ключом SSH10b

2: Первый вариант осуществления (настоящий способ №1)

2-1: Общий обзор

2-2: Применение для схемы аутентификации с открытым ключом SSH10a

2-3: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример 1)

2-4: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример 2)

2-5: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример 3)

2-6: Применение для схемы аутентификации с открытым ключом SSH10b

2-7: Применение для схемы аутентификации с открытым ключом SSH10b (модифицированный пример)

3: Второй вариант осуществления (настоящий способ №2)

3-1: Общий обзор

3-2: Применение для схемы аутентификации с открытым ключом SSH10a

3-3: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример)

3-4: Применение для схемы аутентификации с открытым ключом SSH10b

3-5: Применение для схемы аутентификации с открытым ключом SSH10b (модифицированный пример)

4: Приложение

4-1: Расширение схемы

4-2: Схема неинтерактивной аутентификации с открытым ключом

4-3: Способ уменьшения объема вычислений

5: Конфигурация аппаратных средств

6: Краткая сводка

1: Введение

Перед подробным описанием вариантов осуществления настоящего раскрытия, вкратце будет описана структура алгоритма схемы аутентификации общего открытого ключа и схемы аутентификации n-ходового открытого ключа.

1-1: Структура алгоритма схемы аутентификации с открытым ключом

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

Общий обзор

Схема аутентификации с открытым ключом представляет собой схему аутентификации, где человек (контролер) убеждает другого человека (проверяющего), что она является сама по себе контролером, путем использования открытого ключа pk и секретного ключа sk. Например, открытый ключ pk_A контролера A делают известным для проверяющего. С другой стороны, контролер секретно распоряжается секретным ключом sk_A контролера A. В соответствии со схемой аутентификации с открытым ключом, лицо, которое знает секретный ключ sk_A, соответствующий открытому ключу pk_A, само по себе считается контролером A.

В случае, когда контролер A пытается доказать проверяющему B, что она сама по себе не является контролером, контролер A может выполнить интерактивный протокол с проверяющим B и доказать, что она знает секретный ключ sk_A, соответствующий открытому ключу pk_A. Затем, в случае, когда проверяющий B подтверждает с помощью интерактивного протокола, что контролер A знает секретный ключ sk_A, легитимность контролера A (что она является сама по себе контролером), является доказанной.

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

Первое условие состоит в том, чтобы уменьшить по возможности в максимально возможной степени вероятность фальсификации, установленной во время выполнения интерактивного протокола фальсификатором, который не имеет секретный ключ sk. Удовлетворение этого первого состояния называется ″прочностью″. Другими словами, при использовании прочного интерактивного протокола фальсификатор, не имеющий секретный ключ sk, не устанавливает фальсификация с не пренебрежимо малой вероятностью. Второе условие состоит в том, что, даже если будет выполнен интерактивный протокол, не допускается утечка информации для проверяющего В секретного ключа sk_A контролера A. То, что такое второе условие удовлетворяется, называется “нулевым знанием”.

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

Модель

В модели схемы аутентификации с открытым ключом присутствуют два объекта, а именно, контролер и проверяющий, как показано на фиг.1. Контролер генерирует пару из открытого ключа pk и секретного ключа sk, уникальную для контролера, используя алгоритм Gen генерирования ключа. Затем контролер выполняет интерактивный протокол с проверяющим, используя пару из секретного ключа sk и открытого ключа pk, генерируемую путем использования алгоритма Gen генерирования ключа. В это время контролер выполняет интерактивный протокол, используя алгоритм P контролера. Как описано выше, в интерактивном протоколе, контролер подтверждает для проверяющего, используя алгоритм P контролера, что он обладает секретным ключом sk.

С другой стороны, проверяющий выполняет интерактивный протокол, используя алгоритм V проверяющего, и проверяет, обладает или нет контролер секретным ключом, соответствующим открытому ключу, который контролер опубликовал. Таким образом, проверяющий представляет собой объект, который проверяет, обладает или нет контролер секретным ключом, соответствующим открытому ключу. Как описано выше, модель схемы аутентификации с открытым ключом выполнена из двух объектов, а именно, для контролера и проверяющего, и трех алгоритмов, а именно, алгоритма Gen генерирования ключа, алгоритма P контролера и алгоритма V проверяющего.

Кроме того, выражения ″контролер″ и ″проверяющий″ используются в следующем описании, но эти выражения строго означают объекты. Поэтому, субъект, который выполняет алгоритм Gen генерирования ключа и алгоритм P контролера, представляет собой устройство обработки информации, соответствующее объекту ″контролер″. Аналогично, субъект, который выполняет алгоритм V проверяющего, представляет собой устройство обработки информации. Конфигурация аппаратных средств этих устройств обработки информации показана, например на фиг.21. Таким образом, алгоритм Gen генерирования ключа, алгоритм P контролера и алгоритм V проверяющего выполняет CPU 902 на основе программы, записанной в ROM 904, RAM 906, в модуль 920 накопителя, на съемный носитель 928 записи и т.п.

Алгоритм Gen генерирования ключа

Алгоритм Gen генерирования ключа используется контролером. Алгоритм Gen генерирования ключа представляет собой алгоритм, предназначенный для генерирования пары из открытого ключа pk и секретного ключа sk, уникальный для контролера. Открытый ключ pk, сгенерированный алгоритмом Gen генерирования ключа публикуют. Кроме того, опубликованный открытый ключ pk используется проверяющим. С другой стороны, контролер секретно распоряжается секретным ключом sk, сгенерированным алгоритмом Gen генерирования ключа. Секретный ключ sk, которым секретно распоряжаются, используется для доказательства для проверяющего обладания секретным ключом sk, соответствующим открытому ключу рk. Формально, алгоритм Gen генерирования ключа представлен, как формула (1), показанная ниже, как алгоритм, который принимает параметр 1^λ безопасности (λ представляет собой целое число, равное 0 или больше), в качестве входных данных, и выводит секретный ключ sk и открытый ключ pk.

Выражение 1

$$\left(sk,pk\right)\leftarrow Gen\left(1^{\lambda }\right)\dots \left(1\right)$$

Алгоритм P контролера

Алгоритм P контролера используется контролером. Алгоритм P контролера представляет собой алгоритм для обеспечения обладания секретным ключом sk, соответствующим открытому ключу pk. Алгоритм P контролера определен, как алгоритм, который принимает открытый ключ pk и секретный ключ sk контролера и вводит, и выполняет интерактивный протокол с проверяющим.

Алгоритм V проверяющего

Алгоритм V проверяющего используется проверяющим. Алгоритм V проверяющего представляет собой алгоритм для проверки, в интерактивном протоколе, обладает ли контролер секретным ключом sk, соответствующим открытому ключу pk. Алгоритм V проверяющего определен, как алгоритм, который принимает открытый ключ рk контролера, как вход, и затем выводит 0 или 1 (1 бит) после выполнения интерактивного протокола с контролером. Кроме того, предполагается, что в случае вывода 0, контролер является нелегитимным, и в случае вывода 1, предполагается, что контролер является легитимным.

Приложение

Как описано выше, схема аутентификации с открытым ключом должна удовлетворять двум условиям, то есть прочности и нулевому знанию, для обеспечения безопасности. Однако, для того, чтобы контролер убедился, что она содержит секретный ключ sk, необходимо, чтобы контролер выполнил процедуру, зависящую от секретного ключа sk, уведомил проверяющего о результате и обеспечил, чтобы проверяющий выполнил проверку на основе предоставления содержания. Выполнение процедуры, зависящей от секретного ключа sk, необходимо для гарантирования прочности. С другой стороны, необходимо, чтобы отсутствовали какие-либо утечки информации о секретном ключе sk для проверяющего, даже когда проверяющий будет уведомлен о результате процедуры. В соответствии с этим, алгоритма Gen генерирования ключа, алгоритм P контролера и алгоритм V проверяющего разработаны так, чтобы они удовлетворяли этим условиям.

Выше была описана структура алгоритма схемы аутентификации с открытым ключом.

1-2: Схема аутентификации N-ходового открытого ключа

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

Как описано выше, схема аутентификации с открытым ключом представляет собой схему аутентификации, предназначенную для доказательства для проверяющего, в интерактивном протоколе, что контролер обладает секретным ключом sk, соответствующим открытому ключу pk. Кроме того, чтобы гарантировать безопасность схемы аутентификации с открытым ключом, должны удовлетворяться два состояния, а именно, прочность и нулевое знание. Соответственно, как показано на фиг.2, в интерактивном протоколе, обмен информацией выполняют n раз между контролером и проверяющим, в то время как исполнение обработки выполняется, как контролером, так и проверяющим.

В случае схемы аутентификации n-ходового открытого ключа, контролер выполняет процесс, используя алгоритм P контролера (этап 1), и информацию T₁ передают проверяющему. Затем процесс выполняет проверяющий, используя алгоритм V проверяющего (этап 2), и информацию Т₂ передают в контролер. Процессы на (этапе 3) - (этапе n) выполняют аналогично и часть информации Т₃, …, T_n передают, и выполняют процесс (этап n+1). Такая схема аутентификации с открытым ключом на основе интерактивного протокола, где часть информации передают/принимают n раз, называется ″n-ходовой″ схемой для аутентификации открытого ключа.

Выше была представлена n-ходовая схема аутентификации открытого ключа.

1-3: Интерактивный протокол схемы аутентификации с открытым ключом SSH10a

Далее, со ссылкой на фиг.3, будет описан интерактивный протокол схемы аутентификации с открытым ключом SSH10a. На фиг.3 показана пояснительная схема для описания интерактивного протокол схемы аутентификации с открытым ключом SSH10a. Кроме того, схема аутентификации с открытым ключом SSH10a представляет собой одну из схем аутентификации с открытым ключом, разработанную авторами настоящего изобретения (Sakumoto, Shirai и Hiwatari), которая основана на задаче одновременного решения уравнения с многочленом от нескольких переменных. Кроме того, такая схема аутентификации с открытым ключом SSH10a представляет собой пример 3-ходовой схемы аутентификации с открытым ключом.

Кроме того, задача одновременного решения уравнения от нескольких переменных с множеством порядков представляет собой задачу для получения вектора (s₁, …, s_n)∈Kⁿ, который удовлетворяет (f₁(s₁, …, s_n), …, f_m(s₁, …, s_n))=y, где заданы m многочленов с множеством порядков n переменными f₁(x₁, …, x_n), …, f_m(х₁, …, x_n) на кольце K и вектор y∈K^m. Задача решения одновременного уравнения с множеством переменных второго порядка или выше называется задачей NP-сложности, и она принадлежит к классу задач, которые чрезвычайно трудно решать.

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

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключа генерирует m многочленов второго порядка с n переменными f₁(x₁, …, x_n), …, f_m(x₁, …, x_n), определенных на кольце K, и вектор s=(s₁, …, s_n)∈Kⁿ. Далее алгоритм Gen генерирования ключа рассчитывает y=(y₁, …, y_m)←(f₁(s), …, f_m(s)). Затем алгоритм Gen генерирования ключа устанавливает (f₁, …, f_m, y) для открытого ключа pk, и устанавливает s для секретного ключа. Кроме того, в дальнейшем вектор n переменных (x₁, …, x_n) будет выражен как x, и m многочленов второго порядка с n переменными (f₁(x), …, f_m(x)) будет выражен как F (х).

Алгоритм Р контролера, алгоритм V проверяющего

Далее, со ссылкой на фиг.3, будут описаны структуры алгоритма P контролера и алгоритма V проверяющего. Интерактивный протокол схемы аутентификации с открытым ключом SSH10a предназначен для подтверждения для проверяющего того, что “контролер знает значение s, которое удовлетворяет y=F(s)”, без утечки информации об s вообще для проверяющего. Кроме того, открытый ключ pk, генерируемый алгоритмом Gen генерирования ключа, как предполагается, совместно используется между контролером и проверяющим. Кроме того, предполагается, что контролер секретно распоряжается секретным ключом sk, генерируемым алгоритмом Gen генерирования ключа.

Здесь будет сделана ссылка на свойство многочлена второго порядка.

Набор из m многочленов второго порядка с n переменными (f₁(х), …, f_m(х)) может быть представлен, как формула (2), представленная ниже. Кроме того, x=(x₁, …, x_n) представляет собой вектор, обозначающий n переменных. Кроме того, A₁, …, A_m представляет собой матрицу n×n. Кроме того, b₁, …, b_m представляет собой вектор n×1. Кроме того, с представляет собой вектор m×1.

Выражение 2

$$F\left(x\right)=\left(\begin{array}{c}{\sout{\int }}_1\left(x\right)\\ ⋮\\ {\sout{\int }}_m\left(x\right)\end{array}\right)=\left(\begin{array}{c}{x}^T{A}_{1}x+b_1^{T}x\\ ⋮\\ x^T{A}_{m}x+b_m^{T}x\end{array}\right)+c\dots \left(2\right)$$

Используя это представление, набор многочленов F может быть представлен, как формулы (3) и (4), показанные ниже. То, что данное представление является справедливым, может быть легко подтверждено из формулы (5), приведенной ниже.

Выражение 3

$$F\left(x_1+x_2\right)=F\left(x_1\right)+F\left(x_2\right)+F\left(x_2\right)+F_b\left(x_1,x_2\right)-c\dots \left(3\right)$$

$$F_b\left(x_1,x_2\right)=\left(\begin{array}{c}{x}_2^T\left(A_1^T+A_1\right)x_1\\ ⋮\\ x_2^T\left(A_m^T+A_m\right)x_1\end{array}\right)\dots \left(4\right)$$

$$\begin{array}{l}{\sout{\int }}_1\left(x_1{x}_2\right)={\left(x_1+x_2\right)}^T{A}_l\left(x_1+x_2\right)+b_l^T\left(x_1+x_2\right)+c_l\\ =x_1^T{A}_l{x}_1+x_1^T{A}_1{x}_2+x_2^T{A}_l{x}_1+x_2^T{A}_l{x}_2+b_l^T{x}_1+b_l^T{x}_2+c_l\\ ={\sout{\int }}_l\left(x_1\right)+{\sout{\int }}_l\left(x_2\right)-c_l+x_1^T{A}_l{x}_2+x_2^T{A}_l{x}_1\\ ={\sout{\int }}_l\left(x_1\right)+{\sout{\int }}_l\left(x_2\right)-c_l+x_1^T{\left(A_l^T\right)}^T{x}_2+x_2^T{A}_l{x}_1\\ ={\sout{\int }}_l\left(x_1\right)+{\sout{\int }}_l\left(x_2\right)-c_l+{\left(A_l^T{x}_1\right)}^T{x}_2+x_2^T{A}_l{x}_1\\ ={\sout{\int }}_l\left(x_1\right)+{\sout{\int }}_l\left(x_2\right)-c_l+x_2^T\left(A_l^T{x}_1\right)+x_2^T{A}_l{x}_1\\ ={\sout{\int }}_l\left(x_1\right)+x_2^T\left(A_l^T+A_l\right)x_1+{\sout{\int }}_l\left(x_2\right)-c_l\dots \left(5\right)\end{array}$$

При делении F(x₁+x₂) на три части, то есть, часть, зависимую от x₁ часть, зависимую от х₂, и часть, зависимую одновременно от x₁ и от x₂, таким образом, часть, F_b(x₁, x₂), зависимая, как от x₁, так и от х₂₎ будет представлять собой билинейную карту в отношении x₁ и x₂. Кроме того, в схеме аутентификации с открытым ключом SSH10a, описанной ниже, используется свойство многочлена второго порядка, как описано выше.

Вернемся к пояснению алгоритма P контролера и алгоритма V проверяющего интерактивного протокола схемы аутентификации с открытым ключом SSH10a (см. фиг.3).

Этап 1:

Вначале, алгоритм P контролера произвольно выбирает число w. Затем алгоритм P контролера применяет, сгенерирован ли вектор r∈Kⁿ и число w', применяя число w к генератору G₁ псевдослучайных чисел. Таким образом, алгоритм P контролера рассчитывает (r, w')←G₁(w). Затем алгоритм P контролера генерирует два вектора t∈Kⁿ и e∈K^m, применяя число w' в генераторе G₂ псевдослучайных чисел. Таким образом, алгоритм P контролера рассчитывает (t, е)←G₂(w'). Затем алгоритм P контролера рассчитывает z←s←r. Такой расчет соответствует операции маскирования секретного ключа вектором r. Кроме того, алгоритм P контролера рассчитывает t'←r+t. Затем алгоритм P контролера рассчитывает е'←F(r)-c+e.

Затем алгоритм Р контролера рассчитывает F_b (z, t) на основе определения функции F_b, представленной формулами (3) и (4), и генерирует хэш-значение c₁ для F_b(z, t)+е и z. Таким образом, алгоритм Р контролера рассчитывает c₁←Н₁(F_b(z, t)+е, z). Кроме того, алгоритм Р контролера генерирует хэш-значение c₂ числа w'. Таким образом, алгоритм Р контролера рассчитывает c₂←Н₂(w'). Кроме того, алгоритм Р контролера генерирует хэш-значение c₃ двух векторов t' и e'. Таким образом, алгоритм Р контролера рассчитывает c₃←H₃(t', e').

Затем алгоритм Р контролера устанавливает St←(F, y, s, r, t, е, z, t', е') и Cmt←(с₁, c₂, с₃). Затем Cmt, сгенерированное на этапе 1, передают проверяющему (алгоритм V проверяющего). Кроме того, Н₁(…), Н₂(…) и H₃(…) представляют собой хеш-функции. Кроме того, операция на этапе 1 будет выражена, как (Cmt; St)←Р_{а, 1}(F, y, s; r, t, е).

Этап 2:

Алгоритм V проверяющего, который принял Cmt, выбирает структуру проверки, которая должна использоваться из трех структур проверки. Затем алгоритм V проверяющего передает контролеру (в алгоритм Р контролера) проблему Ch∈_R {0, 1, 2}, обозначающую выбранную структуру проверки.

Этап 3:

Алгоритм Р контролера, который принял Ch, генерирует ответ Rsp, который должен быть передан обратно в алгоритм V проверяющего, в ответ на проблему Ch, принятую из алгоритма V проверяющего. Если Ch=0, алгоритм Р контролера генерирует ответ Rsp←(r, t, е). Кроме того, если Ch=1, алгоритм Р контролера генерирует ответ Rsp=(z, t, е). Кроме того, если Ch=2, алгоритм Р контролера генерирует ответ Rsp=(z, t', е'). Кроме того, операция на этапе 3 будет выражена, как Rsp←Р_{а, 2} (Ch; St). Кроме того, Rsp, сгенерированное на этапе 3, передают проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял Rsp, выполняет любую из следующих проверок для принятого Rsp.

Если Ch=0, алгоритм V проверяющего выполняет (r”, t”, е”)←Rsp. Затем алгоритм V проверяющего проверяет, справедливо ли c₂=Н₂(t”, е”) и с₃=Н₃(r”+t”, F(r”)-c+e”) или нет.

Если Ch=1, алгоритм V проверяющего выполняет (z”, t”, е”)←Rsp. Затем алгоритм V проверяющего проверяет, справедливо или нет c₁=H₁(F_b(z”, t”)+e”, z”) и c₂=H₂(t”, e”).

Если Ch=2, алгоритм V проверяющего выполняет (z”, t″′, e″′)←Rsp. Затем алгоритм V проверяющего проверяет, справедливо или нет c₁=H₁(F(z”)+F_b(z”, t″′)+e″′-y, z”) и c₃=H₃(t″′, e″′).

Кроме того, операция проверки на этапе 4 будет выражена, как 0/1←Dec_a(F, y; Cmt, Ch, Rsp). В такой операции выход 1 обозначает успешную проверку, и выход 0 обозначает неудачную проверку.

Выше было описано содержание обработки, выполняемой алгоритмом Р контролера и алгоритмом V проверяющего, в схеме аутентификации с открытым ключом SSH10a. Кроме того, в представленной выше схеме с₁, с₂ и c₃ рассчитывают, используя хеш-функции H₁, H₂ и H₃, но функция COM привязки также может использоваться вместо хеш-функций H₁, H₂ и H₃. Кроме того, в данном описании хеш-функция может быть заменена функцией COM привязки.

Функция COM привязки представляет собой функцию, которая принимает, как аргументы, строку S знаков и случайное число ρ. Примеры функции привязки включают в себя схему, представленную Shai Halevi and Silvio Micali на Международной конференции CRYPTO 1996 и т.п. В случае использования этой функции привязки, случайные числа ρ₁, ρ₂ и ρ₃ подготавливают перед расчетом c₁, с₂ и с₃, и c₁, с₂ и c₃ генерируют, применяя функции СОМ (·, ρ₁), СОМ (·, ρ₂), и СОМ (·, ρ₃) привязки, вместо хеш-функций H₁(·), Н₂(·), и Н₃(·). Кроме того, ρ₁ передают, включая его в ответ, из алгоритма P контролера в алгоритм V проверяющего.

1-4: Интерактивный протокол схемы аутентификации с открытым ключом SSH10b

Далее, со ссылкой на фиг.4, будет описан интерактивный протокол схемы аутентификации с открытым ключом SSH10b. На фиг.4 показана пояснительная схема, предназначенная для описания интерактивного протокола схемы аутентификации с открытым ключом SSH10b. Кроме того, схема аутентификации с открытым ключом SSH10b представляет собой одну из схем аутентификации с открытым ключом, разработанных авторами настоящего изобретения (Sakumoto, Shirai и Hiwatari), которая основана на задаче решения одновременного уравнения многочлена от нескольких переменных. Кроме того, такая схема аутентификации с открытым ключом SSH10b представляет собой пример схемы аутентификации с 5-ходовым открытым ключом.

Аналогично интерактивному протоколу схемы аутентификации с открытым ключом SSH10a, интерактивный протокол схемы аутентификации с открытым ключом SSH10b выполнен на основе алгоритма Gen генерирования ключа, алгоритма Р контролера и алгоритма V проверяющего. Ниже будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключа генерирует m многочленов второго порядка для n переменных f₁(x₁, …, x_n), …, f_m(x₁, …, x_n) определенных на кольце K, и вектор c=(s₁, …, s_n)∈Kⁿ. Затем алгоритм Gen генерирования ключа рассчитывает y=(y₁, …, y_m)←(f₁(s), …, f_m(s)). Затем алгоритм Gen генерирования ключа устанавливает (f₁, …, f_m, y) для открытого ключа pk, и затем устанавливает s для секретного ключа. Кроме того, в дальнейшем, вектор n переменных (x₁, …, x_n) будет обозначен как x, и m многочленов второго порядка с n переменными (f₁(x), …, f_m(x)) будут обозначены, как F(x).

Алгоритм P контролера, алгоритм V проверяющего

Далее, со ссылкой на фиг.4, будут описаны структуры алгоритма P контролера и алгоритма V проверяющего. Интерактивный протокол схемы аутентификации с открытым ключом SSH10b предназначен для подтверждения проверяющим, что “контролер знает значение s, которое удовлетворяет y=F(s)”, без утечки информации об s вообще для проверяющего. Кроме того, предполагается, что открытый ключ pk, сгенерированный алгоритмом Gen генерирования ключа, совместно используется между контролером и проверяющим. Кроме того, предполагается, что контролер секретно распоряжается секретным ключом sk, сгенерированным алгоритмом Gen генерирования ключа.

Интерактивный протокол схемы аутентификации с открытым ключом SSH10b выполнен на основе этапов 1-6 обработки, показанных на фиг.4. В дальнейшем будет описана обработка на каждом этапе.

Этап 1:

Вначале алгоритм P контролера произвольно выбирает число w. Затем алгоритм P контролера генерирует векторы r∈Kⁿ, t∈Kⁿ и e∈K^m, применяя число w в генераторе G псевдослучайных чисел. Таким образом, алгоритм P контролера рассчитывает (r, t, e)←G(w). Затем алгоритм P контролера рассчитывает z←s←r. Этот расчет соответствует операции маскирования секретного ключа вектором r.

Далее алгоритм P контролера генерирует хэш-значение c₁ для F_b(z, t)+е и z. Таким образом, алгоритм P контролера рассчитывает c₁←Н₁(F_b(z, t)+е, z). Кроме того, алгоритм P контролера генерирует хэш-значение c₂ векторов r, t и e. Таким образом, алгоритм P контролера рассчитывает c₂←H₂(r, t, е). Кроме того, H₁(…) и Н₂(…) представляет собой хеш-функции.

Далее алгоритм P контролера устанавливает St_A←(F, y, s, r, t, е, z) и Cmt_A←(c₁, с₂). Затем Cmt_A, сгенерированное на этапе 1, передают проверяющему (в алгоритм V проверяющего). Кроме того, H₁(…) и Н₂(…) представляют собой хеш-функции. Кроме того, операция на этапе 1 будет выражена, как (Cmt_A; St_A)←P_{b, 1}(F, y, s; r, t, e).

Этап 2:

Алгоритм V проверяющего, который принял Cmt_A, выбирает одно случайное число α из q типов элементов кольца K. Затем алгоритм V проверяющего передает проблему Ch_A=α контролеру (алгоритм Р контролера).

Этап 3:

Алгоритм Р контролера, который принял Ch_A, рассчитывает t'←α r+t. Кроме того, алгоритм P контролера рассчитывает e'←α(F(r)-c)+e. Затем алгоритм P контролера устанавливает St_B←(St_A, Ch_A, t', e') и Cmt_B←(t', e'). Кроме того, алгоритм P контролера передает Cmt_B проверяющему (алгоритм V проверяющего). Кроме того, операция на этапе 3 будет выражена, как (Cmt_B; St_B)←P_b,2(Ch_A; St_A).

Этап 4:

Алгоритм V проверяющего, который принял Cmt_B, выбирает структуру проверки, предназначенную для использования, из двух структур проверки. Затем алгоритм V проверяющего передает контролеру (алгоритм P контролера) проблему Ch_B∈R{0, 1}, обозначающую выбранную структуру проверки.

Этап 5:

Алгоритм P контролера, который принял Ch_B, генерирует ответ Rsp, который должен быть передан обратно проверяющему (алгоритм V проверяющего) в ответ на проблему Ch_B, принятую из алгоритма V проверяющего следующим образом. Если Ch_B=0, алгоритм Р контролера устанавливают в Rsp←r. Если Ch_B=1, алгоритм P контролера устанавливают в Rsp←z. Затем алгоритм P контролера передает ответ Rsp проверяющему (алгоритм V проверяющего). Кроме того, операция на этапе 5 будет выражена, как Rsp←P_b,3(Ch_B; St_B).

Этап 6:

Алгоритм V проверяющего, который принял ответ Rsp, выполняет следующие процессы проверки, используя ответ Rsp, принятый из контролера (алгоритм Р контролера).

Если Ch_B=0, алгоритм V проверяющего принимает r”←Rsp и проверяет, справедливо или нет с₂=Н₂(r”, t'-α r”, е'-α(F(r”)-c)).

Если Ch_B=1, алгоритм V проверяющего принимает z”←Rsp и проверяет, справедливо или нет c₁=H₁(α(F(z”)-y)+F_b(z”, t')+e', z”).

Кроме того, операция проверки на этапе 6 будет выражена, как 0/1←Dec_b(F, y; Cmt_A, Ch_A, Cmt_B, Ch_B, Rsp). В этой операции выход 1 обозначает успешную проверку, и выход 0 обозначает неудачную проверку.

Выше было описано содержание обработки, выполняемой алгоритмом Р контролера и алгоритмом V проверяющего в схеме аутентификации с открытым ключом SSH10b. Кроме того, в представленной выше схеме c₁ и c₂, рассчитывают, используя функции H₁ и Н₂ хеширования, но функцию СОМ привязки также можно использовать вместо функций H1 и H₂ хеширования.

1-5: Конфигурация повторения интерактивного протокола

Далее, в случае принятия интерактивного протокола схемы аутентификации с открытым ключом SSH10a, описанной выше, вероятность последующей фальсификации может быть подавлена до уровня 2/3 или меньше. Соответственно, если этот интерактивный протокол будет выполнен дважды, вероятность последующей фальсификации может быть подавлена до уровня (2/3)² или меньше. Таким образом, если такой интерактивный протокол будет выполнен N раз, вероятность последующей фальсификации становится (2/3)^N, и если N представляет собой достаточно большое число (например, N = 140), вероятность последующей фальсификации будет уменьшена до пренебрежимо малого уровня.

Аналогично, когда принимают интерактивный протокол описанной выше схемы аутентификации с открытым ключом SSH10b, вероятность последующей фальсификации может быть подавлена до уровня (1/2+1/2q) или меньше. Соответственно, если этот интерактивный протокол будет выполнен дважды, вероятность последующей фальсификации может быть подавлена до уровня (1/2+1/2q)² или меньше. Таким же образом, если такой интерактивный протокол будет выполнен N раз, вероятность последующей фальсификации становится (1/2+1/2q)^N, и если N представляет собой достаточно большое число (например, N = 80), вероятность последующей фальсификации уменьшается до пренебрежимо малого уровня.

Кроме того, не только для схемы аутентификации с открытым ключом SSH10a и схемы аутентификации с открытым ключом SSH10b, но также и для схем аутентификации с открытым ключом, раскрытых в непатентной литературе 1-3, упомянутой выше, когда выполняется интерактивный протокол один раз и вероятность успешной фальсификации не достаточно мала, вероятность успешной фальсификации должна быть уменьшена путем многократного выполнения интерактивного протокола. В качестве способа многократного выполнения интерактивного протокола, используется конфигурация последовательного повторения, показанная на фиг.5, и конфигурация параллельного повторения, показанная на фиг.6.

Конфигурация последовательного повторения представляет собой способ последовательного выполнения интерактивного протокола, такого, как показан на фиг.5, в то время как интерактивный протокол выполняют один раз, и когда первый раунд будет закончен, выполняют второй раунд, и когда будет закончен второй раунд, выполняют третий раунд. С другой стороны, конфигурация параллельного повторения представляет собой способ одновременной передачи сообщений для N раундов при каждом проходе, как показано на фиг.6, где сообщения первого прохода для m_1,1, …, m_N,1 для N раундов передают одновременно, и затем второй проход передачи m_1,2, …, m_N,2 для раундов N передают одновременно, и затем третий проход передачи m_1,3, …, m_N,3 для раундов N передают одновременно.

Теперь, схемы аутентификации с открытым ключом, раскрытые в непатентной литературе 1-3, упомянутой выше, схема аутентификации с открытым ключом SSH10a и схема аутентификации с открытым ключом SSH10b гарантируют уровень безопасности, достаточный для пассивной атаки. Однако ранее не было известно, гарантируется ли в таких схемах аутентификации с открытым ключом абсолютный уровень безопасности, достаточный для активной атаки, или нет, в случае, когда принята конфигурация с параллельным повторением. Такие схемы аутентификации с открытым ключом, представляли собой схемы, в которых контролер доказывал проверяющему, что “контролер знает значение s, которое удовлетворяет y=F(s) для y”, используя одну пару ключей (открытый ключ у, секретный ключ s).

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

В соответствии с этим, авторы настоящего изобретения разработали механизмы гарантирования уровня безопасности, достаточного для активной атаки во время выполнения такой схемы аутентификации с открытым ключом, используя конфигурацию с параллельным повторением. Эти механизмы (настоящий способ №1, настоящий способ №2) будут подробно описаны ниже, используя схему аутентификации с открытым ключом SSH10a и схему аутентификации с открытым ключом SSH10b, в качестве примеров.

1-6: Алгоритм фальсификации против схемы аутентификации с открытым ключом SSH10a

Здесь будет представлено обсуждение со ссылкой на фиг.7 алгоритма фальсификации, который успешно выполняется с вероятностью 2/3 в схеме аутентификации с открытым ключом SSH10a (один интерактивный протокол). На фиг.7 показана пояснительная схема, предназначенная для описания алгоритма фальсификации, который успешно выполняется с вероятностью 2/3 в схеме аутентификации с открытым ключом SSH10a (один интерактивный протокол). Такой алгоритм фальсификации представляет собой алгоритм, где фальсификатор “претендует на то, что он знает значение s, которое удовлетворяет y=F(s)” для проверяющего. Однако даже если этот алгоритм фальсификации будет принят, фальсификация будет неудачной с вероятностью 1/3.

Этап 1:

Вначале, фальсификатор (алгоритм фальсификации) генерирует вектора s, r, t∈Kⁿ и e∈K^m. Затем алгоритм фальсификации произвольно выбирает Ch*∈{0, 1, 2}. Эта Ch* соответствует структуре проверки, где алгоритм фальсификации не может дать ответ. Кроме того, s, используемое здесь, не является легитимным секретным ключом. Однако, при другой структуре проверки, кроме Ch*, контролер (алгоритм Р контролера) может дать правильный ответ без использования легитимного секретного ключа.

Затем алгоритм фальсификации рассчитывает z←s-r и t'←r+t. Кроме того, если Ch*=0, алгоритм фальсификации рассчитывает e'←y-F(s)+F(r)-с+e. С другой стороны, если Ch*=1 или 2, алгоритм фальсификации рассчитывает e'←F(r)-c+e. Затем, если Ch*=0 или 2, алгоритм фальсификации рассчитывает c₁←H₁(F_b(z, t)+e, z). С другой стороны, если Ch*=1, алгоритм фальсификации рассчитывает c₁←H₁(F(z)+F_b(z, t')+e'-y, z).

Затем алгоритм фальсификации рассчитывает c₂←Н₂(t, е) и c₃←H₃(t', e'). Затем алгоритм фальсификации устанавливает St←(Ch*, F, y, c, r, t, e, z, t', e') и Cmt←(c₁ c₂, c₃). Затем, алгоритм фальсификации передает Cmt проверяющему (алгоритм V проверяющего). Дополнительно, операция на этапе 1 будет выражена как (Cmt; Св.)←М_а,1(F, y; Ch*, c, r, t, e).

Этап 2:

Алгоритм V проверяющего, который принял Cmt, выбирает структуру проверки, которая будет использоваться, из трех структур проверки. Затем, алгоритм V проверяющего отправляет фальсификатору (алгоритм фальсификации) проблему Ch∈_R{0, 1, 2}, обозначающую выбранную структуру проверки.

Этап 3:

Алгоритм фальсификации, который принял Ch, генерирует ответ Rsp, который будет отправлен назад в алгоритм V проверяющего в ответ на запрос Ch, принятый из алгоритма V проверяющего. Дополнительно, если Ch=Ch*, алгоритм фальсификации выводит ошибку, и заканчивает интерактивный протокол. Если Ch≠Ch* и Ch=0, алгоритм фальсификации генерирует ответ Rsp←(r, t, e). Кроме того, если Ch=1, алгоритм фальсификации генерирует ответ Rsp=(z, t, е). Кроме того, если Ch=2, алгоритм фальсификации генерирует ответ Rsp=(z, t', e').

Дополнительно, операция на этапе 3 будет выражена как Rsp←М_{а, 2} (Ch; Св.). Кроме того, Rsp, сгенерированный на этапе 3, отправляют проверяющему (алгоритм V проверяющего).

Этап 4:

Если Ch≠Ch*, поскольку ответ Rsp отправляют в алгоритм V проверяющего, процесс проверки 0/1←Dec_a(F, y; Cmt, Ch, Rsp), выполняется алгоритмом V проверяющего.

Выше был описан алгоритм фальсификации против схемы аутентификации с открытым ключом SSH10a. Как было описано, даже если s выбирают произвольно, Rsp, который проходит проверку с вероятностью 2/3 (вероятность Ch≠Ch*), может быть передан обратно проверяющему. Поэтому, фальсификация будет успешно выполняться с вероятностью 2/3 в одном интерактивном протоколе. Таким образом, конфигурация повторения, описанная выше, будет принята.

1-7: Алгоритм фальсификации против схемы аутентификации с открытым ключом SSH10b

Далее, со ссылкой на фиг.8, будет рассмотрен алгоритм фальсификации, который успешно выполняется с вероятностью 1/2 в схеме аутентификации с открытым ключом SSH10b (один интерактивный протокол). На фиг.8 показана пояснительная схема для описания алгоритма фальсификации, который успешно выполняется с вероятностью 1/2 в схеме аутентификации с открытым ключом SSH10b (один интерактивный протокол). Этот алгоритм фальсификации представляет собой алгоритм, в котором фальсификатор “претендует на то, что он знает значение s, которое удовлетворяет y=F(s)” для проверяющего. Однако даже если этот алгоритм фальсификации будет принят, фальсификация будет неудачной с вероятностью 1/2.

Этап 1:

Вначале, фальсификатор (алгоритм фальсификации) генерирует векторы s, r, t∈Kⁿ и e∈K^m. Затем алгоритм фальсификации произвольно выбирает Ch*_B ∈ {0, 1}. Эта Ch*_B соответствует структуре проверки, в которой алгоритм фальсификации не может обеспечить ответ относительно группы i₀. Кроме того, s_i0, используемый здесь, не является легитимным секретным ключом, но алгоритм фальсификации может дать правильный ответ, без использования легитимного секретного ключа в отношении другой структуры проверки, кроме Ch*_B.

Затем алгоритм фальсификации рассчитывает z←s-r. Затем, алгоритм фальсификации вычисляет c₁←H₁(F_b(z, t)+e, z) и c₂←H₂(r, t, e). Затем, алгоритм фальсификации устанавливает St_A←(F, y, Ch*_B, с, r, t, e, z) и Cmt_A←(c₁, с₂). Затем, Cmt_A сгенерированную на этапе 1, отправляют проверяющему (алгоритм V проверяющего). Кроме того, H₁(…) и H₂(…) являются хеш-функциями. Кроме того, операция на этапе 1 будет выражена как (Cmt_A; St_A)←M_{b, 1}(F, y; Ch*_B, c, r, t, e).

Этап 2:

Алгоритм V проверяющего, который принял Cmt_A, выбирает случайное число α среди q типов элементов кольца K. Затем алгоритм V проверяющего передает проблему Ch_A=α фальсификатору (алгоритм фальсификации).

Этап 3:

Алгоритм фальсификации, который принял Ch_A, рассчитывает t'←α r+t. Кроме того, если Ch*_B=1, алгоритм фальсификации вычисляет е'←α(F(r)-c)+е. С другой стороны, если Ch*_B=0, алгоритм фальсификации вычисляет e'←α(y-F(s)+F(r)-с)+е. Затем, алгоритм фальсификации устанавливает St_B←(St_A, Ch_A, t', е') и Cmt_B(f, е'). Кроме того, алгоритм фальсификации отправляет Cmt_B проверяющему (алгоритм V проверяющего). Дополнительно, операция на этапе 3 будет выражена как (Cmt_B; St_B)←M_{b, 2}(Ch_A; St_A).

Этап 4:

Алгоритм V проверяющего, который принял Cmt_B, выбирает структуру проверки, предназначенную для использования, из двух структур проверки. Затем алгоритм V проверяющего передает фальсификатору (алгоритм фальсификации) проблему Ch_B∈_R{0, 1}, обозначающую выбранную структуру проверки.

Этап 5:

Если Ch_B=Ch*_B, алгоритм фальсификации, который принял Ch_B, выводит ошибку и заканчивает интерактивный протокол. Если Ch_B≠Ch*_B, алгоритм фальсификации генерирует ответ Rsp, который должен быть передан обратно проверяющему (алгоритм V проверяющего), в ответ на проблему Ch_B, принятую из алгоритма V проверяющего следующим образом.

Если Ch_B=0, алгоритм фальсификации устанавливает в Rsp←r. Если Ch_B=1, алгоритм фальсификации устанавливает в Rsp←z. Затем алгоритм фальсификации передает ответ Rsp проверяющему (алгоритм V проверяющего). Кроме того, операция на этапе 5 будет выражена, как Rsp←M_{b, 3}(Ch_B; St_B).

Этап 6:

Если Ch_B≠Ch*_B, поскольку ответ Rsp отправляют в алгоритм V проверяющего, процесс проверки 0/1←Dec_b(F, y; Cmt_A, Ch_A, Cmt_B, Ch_B, Rsp), выполняется алгоритмом V проверяющего.

Выше был описан алгоритм фальсификации против схемы аутентификации с открытым ключом SSH10b. Как описано, даже если значение s будет выбрано произвольно, Rsp, который проходит проверку с вероятностью 1/2 (вероятность Ch_B≠Ch*_B), может быть передано обратно проверяющему. Поэтому, фальсификация будет успешной с вероятностью 1/2 в одном интерактивном протоколе. Таким образом, будет принята конфигурация повторения, описанная выше.

Приложение

В представленном выше описании были описаны схема аутентификации с открытым ключом SSH10a, схема аутентификации с открытым ключом SSH10b, их алгоритмы фальсификации и конфигурации повторения интерактивных протоколов. Эти схемы аутентификации с открытым ключом представляют собой схемы, где контролер доказывает проверяющему, что “контролер знает значение s, которое удовлетворяет y=F(s) для y”, используя одну пару ключей (открытый ключ y, секретный ключ s). В соответствии с этим, если выполнялась итерация, которая будет принята при проверке, было невозможно предотвратить знание проверяющим информации о том, что “контролер, который выполнил проверку, использовал значение s”. Кроме того, устойчивость к коллизиям не гарантируется для F, используемого в этих схемах. В результате, не было бы известно, гарантируют ли абсолютно эти схемы аутентификации с открытым ключом уровень безопасности, достаточный для активной атаки в случае принятия конфигурации с параллельным повторением.

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

2: Первый вариант осуществления (настоящий способ №1)

Вначале будет описан первый вариант осуществления (ниже называется настоящим способом №1) в настоящем раскрытии.

2-1: Общий обзор

В настоящем способе №1 применяют для схемы аутентификации с открытым ключом SSH10a и схемы аутентификации с открытым ключом SSH10b механизм, гарантирующий уровень безопасности, достаточный для активной атаки, также в случае принятия конфигурации с параллельным повторением. Как было описано, причина, по которой не было известно, гарантируется ли уровень безопасности, достаточный для активной атаки, или нет, связана с тем, что устойчивость к коллизии не гарантируется для функции F, предназначенной для использования и также, поскольку было бы невозможно предотвратить знание проверяющим информации о том, что “контролер, который выполнил проверку, использовал значение s”. Поэтому, если можно предотвратить знание проверяющим информации о том, что “контролер, который выполнил проверку, использовал значение s” в интерактивном протоколе, можно гарантировать уровень безопасности, достаточный для активной атаки.

В соответствии с этим, авторы настоящей заявки разработали способ, обеспечивающий секретный ключ и открытый ключ y в виде мультиплексированных ключей. В этом способе используется L(L≥2) s₁, …, sL∈Kⁿ, в качестве секретного ключа, и используется y₁, …, yL∈K^m, который удовлетворяет (y₁, …, y_L)=(F(s₁), …, F(s_L)) для m многочленов от нескольких переменных по n переменным F(x)=(f₁(x), …, f_m(x)) в качестве открытого ключа. Кроме того, этот способ представляет собой способ для доказательства “знания значения s_i, которое удовлетворяет y_i=F(s_i) в отношении L-1, для i среди i=1, …, L”, так, что неизвестно, которое s_i использовали в интерактивном протоколе. При применении такого способа, не будет происходить утечка информации, относящейся к тому, ″которое s_i использовалось″ в интерактивном протоколе, и гарантируется уровень безопасности, достаточный для активной атаки.

В соответствии со схемой настоящего способа №1, проверяющий передает контролеру проблему Ch₁, …, Ch_L (структуры проверки) в отношении i=1, …, L, и контролер, который принял эти проблемы Ch₁, …, Ch_L выбирает L-1 проблем Ch_i и отправляет ответ. При использовании такого способа контролер, который знает s₁, …, s_L, может ответить на все L вызовов Ch_i, но фальсификация, предоставленная фальсификатором, который не знает s₁, …, s_L, будет неудачной с определенной вероятностью. Кроме того, поскольку контролер должен реагировать только на L-1 проблем Ch_i, может быть установлена аутентификация без использования s_i для определенной проблемы Ch_i. Таким образом, проверяющему не известно, использовали или нет определенное значение s_i в интерактивном протоколе.

2-2: Применение для схемы аутентификации с открытым ключом SSH10a

Вначале будет описан интерактивный протокол для случая, где схему в соответствии с настоящим способом №1, применяют для схемы аутентификации с открытым ключом SSH10a. На фиг.9 показана пояснительная схема для описания интерактивного протокола для случая, когда схему в соответствии с настоящим способом №1 применяют для схемы аутентификации с открытым ключом SSH10a. Такой интерактивный протокол конфигурируют из алгоритма Gen генерирования ключа, алгоритма Р контролера и алгоритма V проверяющего. В дальнейшем будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключа генерирует m многочленов второго порядка по n переменным f₁(x₁, …, x_n), …, f_m(x₁, …, x_n), определенным на кольце K, и L векторов s₁, …, S_L∈Kⁿ. Кроме того, вектор из n переменных (x₁, …, x_n) будет обозначен как x, и m многочленов второго порядка по n переменным (f₁(x), …, f_m(x)) будут обозначены, как F(x). Далее алгоритм Gen генерирования ключа рассчитывает y₁=F(s₁), …, y_L=F(s_L). Затем алгоритм Gen генерирования ключа устанавливает (F, y₁, …, y_L) для открытого ключа pk, и устанавливает (s₁, …, s_L) для секретного ключа.

Алгоритм Р контролера, алгоритм V проверяющего

Далее, со ссылкой на фиг.9, будут описаны структуры алгоритма Р контролера и алгоритма V проверяющего. Интерактивный протокол настоящей схемы №1 предназначен для доказательства для проверяющего того, что “контролер знает s_i, которое удовлетворяет L-1 частям для y_i=F(s_i)”, так, чтобы вообще не было утечки информации о том, ″которое значение s_i использовалось или не использовалось” для проверяющего. Кроме того, предполагается, что открытый ключ pk, генерируемый алгоритмом Gen генерирования ключа, совместно используется между контролером и проверяющим. Кроме того, предполагается, что контролер секретно распоряжается секретным ключом sk, генерируемым с помощью алгоритма Gen генерирования ключа.

Интерактивный протокол, в соответствии с настоящей схемой №1, конфигурируют из этапов 1-4 обработки, показанных на фиг.9. В дальнейшем будет описана обработка каждого этапа.

Этап 1:

Вначале алгоритм Р контролера генерирует вектор r_i, t_i∈Kⁿ и вектор ei∈K^m поскольку i=1, …, L. Затем, алгоритм Р контролера вычисляет (Cmt_i; St_i)←P_{a, 1}(F, y_i s_i; r;, t_i, e_i). Затем, алгоритм P контролера отправляет Cmt₁, …, Cmt_L проверяющему (алгоритм V проверяющего).

Этап 2:

Алгоритм V проверяющего, который принял Cmt₁, …, Cmt_L, выбирает структуру проверки, которая будет использоваться, из трех структур проверки. Затем, алгоритм V проверяющего передает контролеру (алгоритм Р контролера) проблемы Ch₁, …, Ch_L∈_R{0, 1, 2}, обозначающие выбранную структуру проверки.

Этап 3:

Алгоритм Р контролера, который принял Ch₁, …, Ch_L случайно, выбирает, из i=1, …, L, один индекс i (ниже, i*) проблемы Chi, на которую не будет дан ответ. Затем, алгоритм Р контролера вычисляет Rsp_i←Р_{а, 2}(Chi; St_i) относительно i∈{1,…,L}¥{i*}. Затем, алгоритм Р контролера передает (Rsp₁, …, Rsp_i*-1, Rsp_i*+i, …, Rsp_L, i*) проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял (Rsp₁, …, Rsp_i*-1, Rsp_i*+1, …, Rsp_L, i*) выполняет 0/1←Dec_a(F, y_i; Cmt_i, Ch_i, Rsp_i) относительно i∈{1,…,L}¥{i*}. Затем, в случае приема (выход 1) для всех i∈{1,…,L}¥{i*}, алгоритм V проверяющего предполагает, что проверка установлена.

В представленном выше описании был описан интерактивный протокол для случая, когда схема, в соответствии с настоящим способом №1 применяется в схеме аутентификации с открытым ключом SSH10a. При этом гарантируется, для этого интерактивного протокола, что благодаря безопасности схемы аутентификации с открытым ключом SSH10a, фальсификатор, не имеющий s-_b, может правильно ответить для каждого из i=1, …, L, на проблему Ch_i, переданную проверяющим, с вероятностью только 2/3 или меньше. Кроме того, применяя настоящий способ №1, поскольку становится необходимо правильно ответить на проблему Ch_i, переданную проверяющим в отношении L-1, или больше количества i, вероятность успешной фальсификации составит (2/3)^L+L(1/3(2/3)^L-1=(2+L)2^L-1/3^L.

Кроме того, в интерактивном протоколе, описанном выше, используются все s₁, …, s_L, но если L≤3, возможно, что s_i не будет использоваться для одного из i=1, …, L, что представляет собой точно такое же поведение, как у контролера, который не дал узнать проверяющему, какое значение s, не было использовано. В соответствии с этим, будут описаны интерактивные протоколы (модифицированные примеры 1-3), выполненные с возможностью реализации такой же аутентификации, как и в описанном выше интерактивном протоколе, без использования одного s_i.

2-3: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример 1)

Вначале, со ссылкой на фиг.10, будет описан интерактивный протокол (модифицированный пример 1) для случая, когда схема, в соответствии с настоящим способом №1, применяется для схемы аутентификации с открытым ключом SSH10a. На фиг.10 показана пояснительная схема для описания интерактивного протокола (модифицированный пример 1) для случая, когда схема в соответствии с настоящим способом №1 применяется для схемы аутентификации с открытым ключом SSH10a. Такой интерактивный протокол выполнен на основе алгоритма Gen генерирования ключа, алгоритма Р контролера и алгоритма V проверяющего. В частности, структура алгоритма фальсификации, описанная выше, используется в алгоритме V проверяющего. Кроме того, пояснение будет представлено для случая L=3. Кроме того, индекс s_i, который не используется, будет сделан i₀. В дальнейшем будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключа генерирует m многочленов второго порядка для n переменных f₁(x₁, …, x_n), …, f_m(х₁, …, x_n), определенных по кольцу K, и L векторов s₁, …, s_L∈Kⁿ. В частности, вектор, который выбирают, соответственно, используется, как s_i0. Кроме того, вектор n переменных (x₁, …, x_n) будет обозначен как x, и m многочленов второго порядка по n переменным (f1(x), …, f_m(x)) будут обозначены, как F(x). Затем алгоритм Gen генерирования ключа рассчитывает y₁=F(s₁), …, yL=F(s_L). Кроме того, y_i0=F(s_i0) не обязательно должно быть гарантировано. Затем алгоритм Gen генерирования ключа устанавливает (F, y₁, …, y_L) для открытого ключа pk, и устанавливает (s₁, …, s_L) для секретного ключа.

Алгоритм Р контролера, алгоритм V проверяющего

Далее, со ссылкой на фиг.10, будут описаны структуры алгоритма Р контролера и алгоритма V проверяющего. Кроме того, предполагается, что открытый ключ pk, генерируемый алгоритмом Gen генерирования ключа, совместно используется между контролером и проверяющим. Кроме того, предполагается, что контролер секретно распоряжается секретным ключом sk, генерируемым алгоритмом Gen генерирования ключа.

Интерактивный протокол, в соответствии с настоящей схемой №1, состоит из следующих этапов 1-4, показанных на фиг.10. В дальнейшем будет описана обработка на каждом этапе.

Этап 1:

Вначале алгоритм Р контролера генерирует вектор r_i, t_i∈Kⁿ и вектор e_i∈K^m для i=1, 2, 3. Затем алгоритм Р контролера выбирает одну из Ch*∈{0, 1, 2}. Это значение Ch* соответствует структуре проверки, в которой контролер не может дать ответ в отношении группы i₀. Затем, если i≠i₀, алгоритм Р контролера рассчитывает (Cmt_i; St_i)←Р_{а, 1}(F, y_i, s_i; ri, ti, e_i). С другой стороны, если i=i₀, алгоритм P контролера рассчитывает (Cmt_i; St_i)←M_{a, 1}(F, y_i; Ch*, s_i, r_i, t_i, e_i). Затем алгоритм P контролера передает Cmt₁, Cmt₂ и Cmt₃ проверяющему (алгоритм V проверяющего).

Этап 2:

Алгоритм V проверяющего, который принял Cmt₁, Cmt₂ и Cmt₃, выбирает структуру проверки, предназначенную для использования, из трех структур проверки. Затем алгоритм V проверяющего передает в алгоритм Р контролера (алгоритм Р контролера) проблему Ch₁, Ch₂, Ch₃∈_R{0, 1, 2}, обозначающую выбранную структуру проверки.

Этап 3:

Алгоритм Р контролера, который принял Ch₁, Ch₂ и Ch₃, выбирает индекс i (ниже, i*) одной проблемы Chi, ответ на которую не будет дан, из i=1, …, L следующим образом. Если Ch_i0=Ch*, алгоритм контролера V устанавливает i*←i₀. С другой стороны, если Ch_i0≠Ch*, алгоритм контролера V случайно выбирает i* из i*∈{1,2,3¥{i₀}. Если этот способ установки i* будет использоваться, то независимо от того, какая структура проверки запрашивается проверяющим, i* примет любое из значений 1, 2 и 3 с вероятностью 1/3, соответственно. Таким образом, информация, обозначающая значение, которое приняло i₀, среди 1, 2 и 3, полностью скрывается.

Затем, алгоритм Р контролера вычисляет Rsp_i относительно i∈{1,2,3}¥{i*} следующим образом. Если i≠i₀, алгоритм Р контролера вычисляет Rsp_i←P_{a, 2}(Chi; St_i). Если i=i₀, алгоритм Р контролера вычисляет Rsp_i←M_{a, 2}(Chi; St_i). Затем, алгоритм Р контролера передает (Rsp₁, …, Rsp_i*-1, Rsp_i*+1, …, Rsp_L, i*) проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял (Rsp₁, …, Rsp_i*-1, Rsp_i*+1, …, Rsp_L, i*) выполняет 0/1←Dec_a(F, y_i; Cmt_i, Chi, Rsp_i) относительно i∈{1,2,3}¥{i*}. Затем, в случае приема (выход 1) для всех i∈{1,2,3}¥{i*}, алгоритм V проверяющего предполагает, что проверка установлена.

В представленном выше описании был описан интерактивный протокол (модифицированный пример) для случая, когда схему в соответствии с настоящим способом №1 применяют для схемы аутентификации с открытым ключом SSH10a. Было представлено пояснение для случая L=3, но то же самое можно сказать для случая L=2. Например, одно значение i(i*), которое не будет использоваться, будет установлено из i=1, 2 следующим образом. Если Ch_i0=Ch*, будет установлено i*=i₀. С другой стороны, если Ch_i0≠Ch*, i*=i₀ будет установлено с вероятностью 1/4, и i*≠i₀ будет установлено с вероятностью 3/4. При такой установке, независимо от того какая структура проверки будет запрошена проверяющим, i* будет принимать любое из значений 1 и 2 с вероятностью 1/2, соответственно. В соответствии с этим, информация, обозначающая значение, которое i₀ приняло из значений 1 и 2, полностью скрыта.

2-4: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример 2)

Далее интерактивный протокол (модифицированный пример 2) для случая, когда схему в соответствии с настоящим способом №1 применяют для схемы аутентификации с открытым ключом SSH10a, будет описан со ссылкой на фиг.11. Кроме того, модифицированный пример 2 представляет собой модифицированный пример интерактивного протокола, показанного на фиг.9. На фиг.11 представлена пояснительная схема для описания интерактивного протокола (модифицированный пример 2) для случая, когда схему, в соответствии с настоящим способом №1 применяют для схемы аутентификации с открытым ключом SSH10a. Этот интерактивный протокол выполнен из алгоритма Gen генерирования ключа, алгоритма Р контролера и алгоритма V проверяющего. В дальнейшем будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключа генерирует m многочленов второго порядка для n переменных f₁(x₁, …, x_n), …, f_m(x₁, …, x_n), определенных на кольце K и два вектора s₁, s₂ ∈ Kⁿ. Кроме того, вектор n переменных (x₁, …, x_n) будет обозначен как x, и m многочленов второго порядка для n переменных (f₁(x), …, f_m(x)) будут обозначены, как F(х). Затем алгоритм Gen генерирования ключа рассчитывает y₁=F(s₁) и y₂=F(s₂). Затем алгоритм Gen генерирования ключа устанавливает (F, y₁, y₂), как открытый ключ pk, и устанавливает (s₁, s₂), как секретный ключ.

Алгоритм Р контролера, алгоритм V проверяющего

Далее, со ссылкой на фиг.11, будут описаны структуры алгоритма Р контролера и алгоритма V проверяющего. Интерактивный протокол в соответствии с настоящей схемой №1 предназначен для того, чтобы проверяющий мог доказать, что “контролер знает s_i, которое удовлетворяет одному из y_i=F(s_i)”, без утечки информации о том, ″которое s_i использовали или которое не использовали” вообще для проверяющего. Кроме того, предполагается, что открытый ключ рk генерируемый алгоритмом Gen генерирования ключа, должен совместно использоваться между контролером и проверяющим. Кроме того, предполагается, что контролер секретно распоряжается секретным ключом sk, сгенерированным алгоритмом Gen генерирования ключа.

Интерактивный протокол, в соответствии с настоящей схемой №1 состоит из этапов 1-4 обработки, показанных на фиг.11. В дальнейшем будет описана обработка на каждом этапе.

Этап 1:

Вначале, алгоритм Р контролера генерирует вектор r₁, t₁ ∈ Kⁿ и вектор e_i ∈ Kⁿ. Затем алгоритм Р контролера рассчитывает (Cmt₁; St₁)←Р_{а, 1}(F, y₁, S₁; r₁, t₁, e₁) и (Cmt₂; St₂)←P_{a, 1}(F, y₂, s₂; r₁, t₁, e₁). Кроме того, Cmt₁(c₁₁, c₁₂, c₁₃), и Cmt₂(c₂₁, c₁₂, c₁₃). Затем, алгоритм P контролера передает c₁₁, c₁₂, c₁₃ и c₂₁ проверяющему (алгоритм V проверяющего).

Этап 2:

Алгоритм V проверяющего, который принял c₁₁, c₁₂, c₁₃ и c₂₁, выбирает структуру проверки, которая будет использоваться. Затем, алгоритм V проверяющего отправляет контролеру (алгоритм Р контролера) ряд проблем (Ch₁, Ch₂)∈{0, 1, 2}×{0, 1, 2}, обозначая выбранную структуру проверки.

Этап 3:

Алгоритм Р контролера, который принял Ch₁ и Ch₂ случайно, выбирает индекс i проблемы Chi, на которую должен быть дан ответ. Затем, алгоритм Р контролера вычисляет Rsp_i←Р_{а, 2}(Chi; St_i, r₁, t₁, e₁) для выбранного i. Затем, алгоритм Р контролера передает (Rsp_i, i) проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял Rsp_i, i выполняет 0/1←Dec_a(F, y_i;(c_i1, c₁₂, c₁₃,), Ch_i, Rsp_i). Затем, в случае, когда выход равен 1 (в случае приема), алгоритм V проверяющего предполагает, что проверка установлена.

В представленном выше описании был описан интерактивный протокол (модифицированный пример 2) для случая, когда применяют схему, в соответствии с настоящим способом №1 для схемы аутентификации с открытым ключом SSH10a. Настоящий модифицированный пример имеет характеристику, которая устанавливает набор случайных чисел (r₁, t₁, e₁) и (r₂, t₂, e₂), используемый во время генерирования Cmt₁, St₁, Cmt₂ и St₂ сделаны общими. Благодаря тому, что эти случайные числа являются общими, (c₁₂, c₁₃) и (c₂₂, c₂₃) среди элементов, формирующих Cmt₁=(c₁₁, c₁₂, c₁₃) и Cmt₂=(c₂₁, c₂₂, c₂₃), будут представлять собой общие значения. Таким образом, только четыре значения (c₁₁, c₁₂, c₁₃, c₂₁) понадобится передать во время отправки Cmt₁ и Cmt₂ от контролера проверяющему, и количество передаваемых данных может быть уменьшено. Кроме того, в случае, в соответствии с настоящим модифицированным примером, только информация, относящаяся к одной из групп, будет опубликована при третьем проходе и, таким образом, нулевое знание не будет потеряно, даже если часть случайных чисел будет сделана общей, как описано выше.

2-5: Применение схемы аутентификации с открытым ключом SSH10a (модифицированный пример 3)

Далее, со ссылкой на фиг.12, будет описан интерактивный протокол (модифицированный пример 3) для случая, когда схему настоящего способа №1 применяют для схемы аутентификации с открытым ключом SSH10a. Кроме того, модифицированный пример 3 представляет собой модифицированный пример интерактивного протокола (модифицированный пример 2), показанного на фиг.11. На фиг.12 представлена пояснительная схема для описания интерактивного протокола (модифицированный пример 3) для случая, когда схема в соответствии с настоящим способом №1 применяется для схемы аутентификации с открытым ключом SSH10a. Такой интерактивный протокол выполнен из алгоритма Gen генерирования ключа, алгоритма P контролера и алгоритма V проверяющего. В дальнейшем будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключа генерирует m многочленов второго порядка по n переменным f₁(x₁, …, x_n), …, f_m(x₁, …, x_n), определенным на кольце K и два вектора s₁, s₂ ∈ Kⁿ. Кроме того, вектор по n переменным (x₁, …, x_n) будет обозначен как x, и m многочленов второго порядка по n переменным (f₁(x), …, f_m(x)) будут обозначены, как F(x). Затем алгоритм Gen генерирования ключа рассчитывает y₁=F(s₁) и y₂=F(s₂). Затем алгоритм Gen генерирования ключа устанавливает (F, y₁, y₂) как открытый ключ pk и устанавливает (s₁, s₂), как секретный ключ.

Алгоритм P контролера, алгоритм V проверяющего

Далее, со ссылкой на фиг.12, будут описаны структуры алгоритма Р контролера и алгоритма V проверяющего. Интерактивный протокол, в соответствии с настоящей схемой №1, предназначен для того, чтобы проверяющий мог доказать, что “контролер знает значение s_i, которое удовлетворяет одному из y_i=F(s_i)”, без утечки информации о том, ″которое si использовали или которое не использовали” вообще, для проверяющего. Кроме того, предполагается, что открытый ключ pk, генерируемый алгоритмом Gen генерирования ключа, должен совместно использоваться между контролером и проверяющим. Кроме того, предполагается, что контролер секретно распоряжается секретным ключом sk, сгенерированным алгоритмом Gen генерирования ключа.

Интерактивный протокол, в соответствии с настоящей схемой №1, состоит из этапов 1-4 обработки, показанных на фиг.12. В дальнейшем будет описана обработка на каждом этапе.

Этап 1:

Вначале, алгоритм Р контролера генерирует вектор r₁, t₁ ∈ Kⁿ и вектор e₁ ∈ K^m. Затем, алгоритм P контролера вычисляет (Cmt₁; St₁)←Р_{а, 1}(F, y₁, s₁; r₁, t₁, e₁) и (Cmt₂; St₂)←P_{a, 1}(F, y₂, s₂; r₁, t₁, e₁). В частности, Cmt₁(c₁₁, c₁₂, c₁₃), и Cmt₂(с₂₁ c₁₂, c₁₃). Затем, алгоритм P контролера отправляет c₁₁, c₁₂, c₁₃ и c₂₁ проверяющему (алгоритм V проверяющего).

Этап 2:

Алгоритм V проверяющего, который принял c₁₁, c₁₂, c₁₃ и c₂₁, выбирает структуру проверки, которая будет использоваться. В это время алгоритм V проверяющего выбирает структуру проверки (ряд проблем (Ch₁, Ch₂)) из (Ch₁, Ch₂)∈{(0,0), (1,1), (1,2), (2,1), (2,2)}. Затем, алгоритм V проверяющего отправляет контролеру (алгоритм Р контролера) набор проблем (Ch₁, Ch₂) обозначающий выбранную структуру проверки.

Этап 3:

Алгоритм Р контролера, который принял Ch₁ и Ch₂, случайно выбирает индекс i проблемы Ch_i, на которую должен быть дан ответ. Затем, алгоритм P контролера вычисляет Rsp_i←Р_{а, 2}(Chi; St_i, r₁, t₁, e₁) для выбранного i. Затем, алгоритм P контролера передает (Rsp_i, i) проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял (Rsp_i, i) выполняет 0/1←Dec_a(F, y_i;(c_i1, c₁₂, c₁₃), Chi, Rsp_i). Затем, в случае вывода 1 (в случае приема), алгоритм V проверяющего предполагает, что проверка установлена.

В предшествующем описании был представлен интерактивный протокол (модифицированный пример 3) для случая, когда схема в соответствии с настоящим способом №1 применяется для схемы аутентификации с открытым ключом SSH10a. Настоящий модифицированный пример характеризуется тем, что неиспользуемая структура проверки ограничивается до пяти структур, (Ch₁, Ch₂)∈{(0,0), (1,1), (1,2), (2,1), (2,2)}.

В случае, когда элементы (c₁₂, c₁₃) для Cmt₁ и элементы (с₂₂, с₂₃) для Cmt₂ будут сделаны общими, как описано выше, ответ для Ch₁=0 (ответ для с₁₂ и c₁₃) и ответ для Ch₂=0 (ответ для с₂₂ и с₂₃) будут одинаковыми. В соответствии с этим, то, что “возможно получить ответ на (Ch₁, Ch₂)=(0, 0)”, означает, что “возможно получить ответ, как на Ch₁=0, так и на Ch₂=0”. Поэтому, контролер, который отвечает на (Ch₁, Ch₂)=(0, 0) может ответить на любую из (Ch₁, Ch₂)=(0,1), (0,2), (1,0), (2,0). В соответствии с этим, достаточно, чтобы проверяющий выполнил проверку по пяти структурам, (Ch₁, Ch₂)=(0,0), (1,1), (1,2), (2,1), (2,2).

По описанной причине гарантируется, что если только секретный ключ sk не известен, невозможно ответить на все эти пять структур, описанные выше. Таким образом, тот, кто не знает секретного ключа sk, может ответить только на четыре структуры максимум, и, таким образом, вероятность фальсификации составляет 4/5 максимум. В случае интерактивного протокола, показанного на фиг.9, вероятность фальсификации в случае L=2 составляла 8/9. В соответствии с этим, применение конфигурации модифицированного примера 3 снижает вероятность фальсификации.

2-6: Применение к схеме аутентификации с открытым ключом SSH10b

Далее интерактивный протокол для случая, когда схема, в соответствии с настоящим способом №1, применяется для схемы аутентификации с открытым ключом SSH10b, будет описан со ссылкой на фиг.13. На фиг.13 показана пояснительная схема для описания интерактивного протокола для случая, когда схема, в соответствии с настоящим способом №1 применяется для схемы аутентификации с открытым ключом SSH10b. Такой интерактивный протокол состоит из алгоритма Gen генерирования ключа, алгоритма P контролера и алгоритма V проверяющего. Далее будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритма Gen генерирования ключа генерирует m многочленов второго порядка по n переменным f₁(x₁, …, x_n), …, из (x₁, …, x_n) и векторы L s₁, …, s_L ∈ Kⁿ. Дополнительно, вектор по n переменным (x₁, …, x_n) будет обозначен как х, и m многочленов второго порядка по n переменным (f₁(x), …, из (x)) будут обозначены как F (x). Затем, алгоритм Gen генерирования ключа вычисляет y₁=F(s₁), …, y_L=F(s_L). Затем, алгоритм Gen генерирования ключа устанавливает (F, y₁, …, y_L) для открытого ключа pk, и устанавливает (s₁, …, s_L) для секретного ключа.

Алгоритм Р контролера, Алгоритм V проверяющего

Далее, структуры алгоритма Р контролера и алгоритма V проверяющего будут описаны со ссылкой на фиг.13. Интерактивный протокол существующей схемы №1 предназначен для того, чтобы заставить проверяющего доказать, что “контролер знает s_i, который удовлетворяет части L-1 y_i=F (si)”, не разрешая утечку информации о том, ″какой si использовался или вообще не использовался” проверяющему. Дополнительно, открытый ключ pk генерируемый алгоритмом Gen генерирования ключа, как предполагается, совместно используется между контролером и проверяющим. Кроме того, предполагается, что контролер тайно распоряжается секретным ключом sk, генерируемым алгоритмом Gen генерирования ключа.

Интерактивный протокол, в соответствии с настоящей схемой №1, выполнен из этапов 1-6 обработки, показанных на фиг.13. Далее будет описана обработка на каждом этапе.

Этап 1:

Вначале алгоритм Р контролера генерирует вектор r_i, t_i ∈ Kⁿ и вектор e_i ∈ K^m поскольку i=1, …, L. Затем, алгоритм Р контролера вычисляет (Cmt_{A, i}; St_{A, i})←P_{a, 1}(F, y_i, s_i; r_i, t_i, e_i). Затем, алгоритм P контролера передает (Cmt_{A, 1}, …, Cmt_{A, L}) проверяющему (алгоритм V проверяющего).

Этап 2:

Алгоритм V проверяющего, который принял (Cmt_{A, 1}, …, Cmt_{A, L}) выбирает набор из L случайных чисел (α₁, …, α_L) из q типов элементов кольцевого K. Затем, алгоритм V проверяющего отправляет запрос (Ch_{A, 1}, …, Ch_{A, L})=(α₁, …, α_L) к контролеру (алгоритм Р контролера).

Этап 3:

Алгоритм Р контролера, который принял (Ch_{A, 1}, …, Ch_{A, L}) вычисляет (Cmt_{B, i}; St_{B, i})←P_{b, 2} (Ch_{A, i}; St_{A, i}) относительно i=1, …, L. Затем, алгоритм P контролера передает (Cmt_{B, 1} …, Cmt_{B, L}) проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял (Cmt_{B, 1}, …, Cmt_{B, L}) выбирает структуру проверки, которая будет использоваться, из двух структур проверки для каждого i=1, …, L. Затем, алгоритм V проверяющего передает контролеру (алгоритм Р контролера) проблемы Ch_{B, 1}, …, Ch_{B, L} ∈ _R{0, 1}, обозначающие выбранные структуры проверки.

Этап 5:

Алгоритм Р контролера, который принял Ch_{B, 1}, …, Ch_{B, L} случайно выбирает из i=1, …, L, одно i (ниже, i*), на которую не будет дан ответ. Затем, алгоритм Р контролера вычисляет Rsp_i←P_{b, 3}(Ch_{B, i}; St_{B, i}). Затем, алгоритм Р контролера передает (Rsp₁, …, Rsp_i*-1, Rsp_i*+1, …, Rsp_L, i*) проверяющему (алгоритм V проверяющего).

Этап 6:

Алгоритм V проверяющего, который принял (Rsp₁, …, Rsp_i*-1, Rsp_i*+1, …, Rsp_L, i*) выполняет 0/1←Dec_b(F, y_i; Cmt_{A, i}, Ch_{A, i}, Cmt_{B, i}, Ch_{B, i}, Rsp_i) относительно i ∈ {1, …, L}¥{i*}. Затем, в случае приема (выход 1) для всех i ∈ {1, …, L}¥{i*}, алгоритм V проверяющего предполагает, что проверка установлена.

В представленном выше описании был описан интерактивный протокол для случая, когда схема, в соответствии с настоящим способом №1, применяется для схемы аутентификации с открытым ключом SSH10b. При этом гарантируется, что для данного интерактивного протокола, благодаря защите схемы аутентификации с открытым ключом SSH10b, фальсификатор, не имеющий значение s_i, может правильно ответить для каждого из i=1, …, L, на проблему Ch_i, переданную от проверяющего, с вероятностью только 1/2+1/2q или меньше. Кроме того, путем применения настоящего способа №1, поскольку становится необходимым правильно ответить на проблему Ch_i, переданную от проверяющего в отношении L-1 или большего количества i, вероятность успеха фальсификации будет равна (1/2+1/2q)^L+L(1/2-1/2q)(1/2+1/2q)^L-1.

Кроме того, в интерактивном протоколе, описанном выше, используются все s₁, …,s_L но если L=2, возможно, даже не использовать s_i для одного из i=1, …, L, чтобы себя вести так же, как контролер, и при этом проверяющий не будет знать, какое значение s_i использовалось. В соответствии с этим, будет описан интерактивный протокол (модифицированный пример), выполненный с возможностью реализации такой же аутентификации, как в описанном выше интерактивном протоколе, без использования одного s_i.

2-7: Применение для схемы аутентификации с открытым ключом SSH10b (модифицированный пример)

Далее, со ссылкой на фиг.14, будет описан интерактивный протокол (модифицированный пример) для случая, когда схема, в соответствии с настоящим способом №1 применяется для схемы аутентификации с открытым ключом SSH10b, на фиг.14 показана пояснительная схема для описания интерактивного протокола (модифицированный пример) для случая, когда схема, в соответствии с настоящим способом №1 применяется для схемы аутентификации с открытым ключом SSH10b. Такой интерактивный протокол выполнен из алгоритма Gin генерирования ключей, алгоритма Р контролера и алгоритма V проверяющего. В частности, структура алгоритма фальсификации, описанная выше, используется в алгоритме V проверяющего. Кроме того, пояснение будет представлено для случая L=2. Кроме того, индекс s_i, который не используется, будет сделан равным i₀. В дальнейшем будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключей генерирует m многочленов второго порядка по n переменным f₁(x₁, …, x_n), …, f_m(x₁, …, x_n), определенным на кольце K, и L векторов s₁, …, s_L ∈ Kⁿ. В частности, вектор, который выбран соответствующим, используется, как s_i0. Кроме того, вектор по n переменным (x₁, …, x_n) будет обозначен как x, и m многочленов второго порядка по n переменным (f₁(x), …, f_m(x)) будут обозначены, как F(х). Далее алгоритм Gen генерирования ключа рассчитывает y₁=F(s₁), …, y_L=F(s_L). Кроме того, y_i0=F(s_i0) не обязательно должно быть гарантировано. Затем алгоритм Gen генерирования ключа устанавливает (F, y1, …, y_L) для открытого ключа pk, и устанавливает (s₁, …, s_L) для секретного ключа.

Алгоритм Р контролера, алгоритм V проверяющего

Далее, со ссылкой на фиг.14, будут описаны структуры алгоритма Р контролера и алгоритма V проверяющего. Кроме того, предполагается, что открытый ключ pk, генерируемый алгоритмом Gen генерирования ключа, будет совместно использоваться между контролером и проверяющим. Кроме того, предполагается, что контролер секретно распоряжается секретным ключом sk, генерируемым алгоритмом Gen генерирования ключа.

Интерактивный протокол, в соответствии с настоящей схемой №1, состоит из этапов 1-6 обработки, показанных на фиг.14. В дальнейшем будет описана обработка на каждом этапе.

Этап 1:

Вначале, алгоритм Р контролера генерирует вектор r_i, t_i ∈ Kⁿ и вектор e_i ∈ K^m для i=1, 2. Затем, алгоритм Р контролера выбирает одну Ch_B* ∈ {0, 1}. Эта Ch_B* соответствует структуре проверки, где контролер не в состоянии дать ответ относительно группы i₀. Затем, если i≠i₀, алгоритм Р контролера вычисляет (Cmt_{A, i};, St_{A, i})←P_{b, 1}(F, y_i, si; r_i, t_i, e_i). Кроме того, если i=i₀, алгоритм P контролера вычисляет (Cmt_{A, i}; St_{A, i})←M_{b, 1}(F, y_i; Ch_B*, si, r_i, t_i, e_i). Затем, алгоритм P контролера передает (Cmt_{A, 1} Cmt_{A, 2}) проверяющему (алгоритм V проверяющего).

Этап 2:

Алгоритм V проверяющего, который принял (Cmt_{A, 1}, Cmt_{A, 2}) выбирает ряд двух случайных чисел (α₁, α₂) от q типов элементов кольцевого K. Затем, алгоритм V проверяющего отправляет запрос (Cp_{A, 1}, Ch_{A, 2})=(α₁, α₂) к контролеру (алгоритм Р контролера).

Этап 3:

Алгоритм Р контролера, который принял (Ch_{A, 1}, Ch_{A, 2}) вычисляет Cmt_B, относительно i=1, 2 следующим образом. Если i≠i₀, алгоритм Р контролера вычисляет (Cmt_{B, i}; St_B,i)←P_{b, 2}(Ch_{A, i}; St_{A, i}). Если i=i₀, алгоритм P контролера вычисляет (Cmt_{B, i}; St_{B, i})←M_{b, 2} (Ch_A,i; St_A,i). Затем, алгоритм P контролера передает (Cmt_B,1, Cmt_B,2) проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял (Cmt_{B, 1}, Cmt_{B, 2}) выбирает структуру проверки, которая будет использоваться, из двух структур проверки. Затем, алгоритм V проверяющего отправляет контролеру (алгоритм Р контролера) запрос (Ch_{B, 1}, Ch_{B, 2})∈_R{0, 1} обозначающий выбранную структуру проверки.

Этап 5:

Алгоритм Р контролера, который принял (Ch_{B, 1} Ch_{B, 2}) выбирает один индекс i (ниже, i*), по которому ответ не будет дан, из i=1, 2 следующим образом. Если Ch_i0≠Ch*, алгоритм Р контролера устанавливает Ch_i0≠Ch*. С другой стороны, если i≠i₀, алгоритм Р контролера случайно выполняет установку так, чтобы i*≠i₀. Если этот способ установки i* будет использоваться, то независимо от того, какая структура проверки запрашивается проверяющим, i* примет любое из значений 1 и 2 с вероятностью 1/2, соответственно. Таким образом, информация, обозначающая значение, которое i₀ принимал между 1 и 2, полностью скрывается.

Затем, алгоритм Р контролера вычисляет Rsp_i относительно i∈ {1,2}¥{i*} следующим образом. Если i≠i₀, алгоритм Р контролера вычисляет Rsp_i←P_{b, 3}(Chi; St_i). Если i=i₀, алгоритм Р контролера вычисляет Rsp₁←M_{b, 3}(Chi; St_i). Затем, алгоритм Р контролера передает (Rsp₁, Rsp₂, i*) проверяющему (алгоритм V проверяющего).

Этап 6:

Алгоритм V проверяющего, который принял (Rsp₁, Rsp₂, i*) выполняет 0/1←Dec_b(F, y_i; Cmt_{A, i}, Ch_{A, i}, Cmt_{B, i}, Ch_{B, i}, Rsp_i) относительно i∈{1,2}¥{i*}. Затем, в случае приема (выход 1) для всего i∈{1,2}¥{i*}, алгоритм V проверяющего предполагает, что проверка установлена.

В представленном выше описании был описан интерактивный протокол (модифицированный пример) для случая, когда схема, в соответствии с настоящим способом №1, применяется для схемы аутентификации с открытым ключом SSH10b. Пояснение было представлено здесь для случая L=2, но тот же механизм также может быть реализован для случая L≥3.

В представленном выше описании был описан первый вариант осуществления настоящего раскрытия. Представленное выше пояснение направлено на схему аутентификации с открытым ключом SSH10a и схему аутентификации с открытым ключом SSH10b, в качестве примеров, но объем приложения настоящей схемы №1 не ограничивается ими. Также возможно применение для модифицированных примеров схемы аутентификации с открытым ключом SSH10a и схемы аутентификации с открытым ключом SSH10b, и к другим схемам аутентификации с открытым ключом. Например, в примере, представленном выше, (F, y) установлено для открытого ключа, но поскольку F представляет собой параметр, не зависимый от секретного ключа, это значение F также может быть сделано параметром, общим для всей системы, вместо установки для каждого контролера. В этом случае, открытые ключи, которые должны быть индивидуально опубликованы, будут представлять собой только y, и размер открытого ключа будет уменьшен. Кроме того, в интерактивном протоколе, описанном выше, случайные числа α₁, …, α_L выбирают отдельно для i=1, …, L, но эти случайные числа могут быть сделаны одним общим случайным числом. В этом случае стоимость передачи данных во время пересылки проблемы Ch_{A, i} может быть уменьшена.

3: Второй вариант осуществления (настоящий способ №2)

Далее будет описан второй вариант осуществления (настоящий способ №2) настоящего раскрытия.

3-1: Общий обзор

Настоящий способ №2 применим для механизма гарантирования уровня безопасности, достаточного для активной атаки, схемы аутентификации с открытым ключом SSH10a и схемы аутентификации с открытым ключом SSH10b. Как было описано, причина, по которой неизвестно, был ли гарантирован уровень безопасности, достаточный для активной атаки, или нет, связана с тем, что устойчивость к коллизиям не гарантирована для функции F, предназначенной для использования, и также, поскольку не было возможности предотвратить знание проверяющим информации о том, что “контролер, который выполнил проверку, использовал значение s”. Поэтому, если возможно предотвратить знание проверяющим информации о том, что “контролер, который выполнил проверку, использовал значение s” в интерактивном протоколе, может быть гарантирован уровень безопасности, достаточный для активной атаки.

В соответствии с этим, авторы настоящего изобретения разработали способ, который делает секретный ключ S и открытый ключ у мультиплексированными ключами. В таком способе используется L(L≥2)s₁, …, sL∈Kⁿ, в качестве секретного ключа, и используется y₁, …, yL∈K^m, которое удовлетворяет (y₁, …, y_L)=(F(s₁), …, F(s_L)) для m многочленов множественного порядка от n переменных F(x)=(f₁(x), …, f_m(x)), в качестве открытого ключа. Кроме того, этот способ представляет способ выполнения аутентификации, не разглашая, которое из значений s_i использовали в интерактивном протоколе. При применении такого способа не будет утечки информация, относящейся к тому, ″какое значение s_i использовали” в интерактивном протоколе, и гарантируется уровень безопасности, достаточный для активной атаки.

В соответствии со схемой настоящего способа №2, проверяющий передает контролеру наборы проблем (Ch₁ ⁽⁰⁾, …, Ch_L ⁽⁰⁾) и (Ch₁ ⁽¹⁾, …, Ch_B ⁽ⁱ⁾) в отношении i=1, …, L, и контролер выбирает один из наборов проблем и подает ответ. Обычно, в соответствии с этой схемой, Q наборов (Q≥2) проблем передают контролеру, и контролер выбирает один набор проблем и поддает ответ. При этом будет описан случай, когда Q=2.

Контролер, который знает s₁, …, s_L, имеет возможность подать ответ на оба набора проблем, но фальсификатор, который не знает, s₁, …, s_L, не сможет с определенной вероятностью поддать ответ на любую проблему, в результате чего, фальсификация будет неудачной. Кроме того, контролер может, в отношении одного значения i, дать ответ на один из наборов проблем, без использования s_i, и, таким образом, даже когда будет выполнен интерактивный протокол, где будет принята проверка, какое значение s_i использовали в этом интерактивном протоколе, не будет известно проверяющему.

3-2: Применение для схемы аутентификации с открытым ключом SSH10a

Вначале, со ссылкой на фиг.15, будет описан интерактивный протокол для случая, когда используется схема, в соответствии с настоящим способом №2, для схемы аутентификации с открытым ключом SSH10a. На фиг.15 показана пояснительная схема для описания интерактивного протокола, для случая, когда схема, в соответствии с настоящим способом №2, применяется для схемы аутентификации с открытым ключом SSH10a. Такой интерактивный протокол выполнен из алгоритма Gen генерирования ключа, алгоритма Р контролера и алгоритма V проверяющего. В дальнейшем будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключа генерирует m многочленов второго порядка для n переменных f₁(x₁, …, x_n), …, f_m(x₁, …, x_n), определенных на кольце K и L векторов s₁, …, s_L∈Kⁿ. Кроме того, вектор n переменных (x₁, …, x_n) будет обозначен как x, и m многочленов второго порядка n по переменным (f₁(x), …, f_m(x)) будет обозначен как F(x). Далее алгоритм Gen генерирования ключа рассчитывает y₁=F(s₁), …, yL=F(s_L). Затем алгоритм Gen генерирования ключа устанавливает (F, y₁, …, y_L) для открытого ключа pk, и устанавливает (s₁, …, s_L) для секретного ключа.

Далее, со ссылкой на фиг.15, будут описаны структуры алгоритма Р контролера и алгоритма V проверяющего. Интерактивный протокол, в соответствии с настоящей схемой №1, предназначенный для того, чтобы обеспечить для проверяющего возможность доказательства того, что “контролер знает s_i, которое удовлетворяет L-1 частям y_i=F(s_i)”, без утечки к проверяющему информации о том, ″какое значение s_i использовали или какое не использовали” вообще. Кроме того, открытый ключ pk, генерируемый алгоритмом Gen генерирования ключа, как предполагается, совместно используется между контролером и проверяющим. Кроме того, предполагается, что контролер секретно распоряжается секретным ключом sk, генерируемым алгоритмом для генерирования ключей.

Интерактивный протокол, в соответствии со схемой №2, составлен из обработки этапов 1 - 4 показанных на фиг.15. Ниже, будет описана обработка на каждом этапе.

Этап 1:

Вначале, алгоритм Р контролера генерирует вектор r_i, t_i∈Kⁿ и вектор e_i∈K^m относительно i=1, …, L. Затем, алгоритм Р контролера вычисляет (Cmt_i; St_i)←Р_{а, 1}(F, y_i, s_i; r_i, t_i, e_i). Затем, алгоритм P контролера отправляет Cmt₁, …, Cmt_L проверяющему (алгоритм V проверяющего).

Этап 2:

Алгоритм V проверяющего, который принял Cmt₁, …, Cmt_L, выбирает структуру проверки, которая будет использоваться, из трех структур проверки. В это время алгоритм V проверяющего выбирает комбинацию двух структур проверки. Затем, алгоритм V проверяющего отправляет контролеру (алгоритм Р контролера) наборы проблем (Ch₁ ⁽⁰⁾, …, Ch_L ⁽⁰⁾), (Ch₁ ⁽¹⁾, …, Ch_L ⁽¹⁾)∈_R{0, 1, 2} с указанием выбранных структур проверки.

Этап 3:

Алгоритм Р контролера, который принял (Ch₁ ⁽⁰⁾, …, Ch_L ⁽⁰⁾) и (Ch₁ ⁽¹⁾, …, Ch_L ⁽¹⁾) случайно выбирает ряд проблем, на которые будет дан ответ. Дополнительно, результат выбора будет обозначен как d∈_R{0, 1}. Затем, алгоритм Р контролера вычисляет Rsp_i←Р_{а, 2}(Ch^(d) _i; St_i) относительно i ∈{1, …, L}. Затем, алгоритм Р контролера передает (Rsp₁, …, Rsp_L, d) проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял (Rsp₁, …, Rsp_L, d) выполняет 0/1←Dec_a(F, y_i; Cmt_i, Ch^(d) _i, Rsp_i) относительно i ∈{1, …, L}. Затем, в случае приема (выход 1) для всех i ∈{1, …, L}, алгоритм V проверяющего предполагает, что проверка установлена.

Выше был описан интерактивный протокол для случая, когда схему, в соответствии с настоящим способом №2, применяют для схемы аутентификации с открытым ключом SSH10a. При этом гарантируется для такого интерактивного протокола, что, благодаря безопасности схемы аутентификации с открытым ключом SSH10a, фальсификатор, не знающий значения s_i, может правильно ответить в отношении каждого из i=1, …, L, на проблему Ch_i, переданную от проверяющего, с вероятностью только 2/3 или меньше. Кроме того, благодаря применению настоящего способа №2, поскольку становится необходимым правильно ответить на проблему Ch_i, переданную от проверяющего в отношении L значений i для одного из двух наборов проблем, вероятность успеха фальсификации становится (2/3)^L+(2/3)^L-(1/3)^L=(2^L+1-1)/3^L.

Кроме того, в интерактивном протоколе, описанном выше, используют все значения s₁, …, s_L, но если L≤3, возможно, когда s; не будет использоваться для одного из i=1, …, L, обеспечить точно такое поведение, как у контролера, который не дает возможности проверяющему узнать, какое значение s_i не было использовано. В соответствии с этим, будет описан интерактивный протокол (модифицированный пример), выполненный с возможностью реализации такой же аутентификации, как в описанном выше интерактивном протоколе, без использования одного из s_i.

3-3: Применение для схемы аутентификации с открытым ключом SSH10a (модифицированный пример)

В дальнейшем интерактивный протокол (модифицированный пример) для случая, когда схема, в соответствии с настоящим способом №2, применяется для схемы аутентификации с открытым ключом SSH10a, будет описан со ссылкой на фиг.16. На фиг.16 показана пояснительная схема для описания интерактивного протокола (модифицированного примера) для случая, когда схема, в соответствии с настоящим способом №2, применятся для схемы аутентификации с открытым ключом SSH10a. Такой интерактивный протокол выполнен из алгоритма Gen генерирования ключа, алгоритма Р контролера и алгоритма V проверяющего. В частности, структура алгоритма фальсификации, описанная выше, используется в алгоритме V проверяющего. Кроме того, индекс s_i, который не используется, будет сделан i₀. В дальнейшем будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключа генерирует m многочленов второго порядка для n переменных f₁(x₁, …, x_n), …, f_m(x₁, …, x_n), определенных на кольце K, и L векторов s_i, …, s_L∈Kⁿ. В частности, вектор, который выбран, как соответствующий, используется, как s_i0. Кроме того, вектор n переменных (x₁, …, x_n) будет обозначен как x, и m многочленов второго порядка по n переменным (f₁(x), …, f_m(x)) будут обозначены, как F(х). Далее алгоритм Gen генерирования ключа рассчитывает y₁=F(s₁), …, y_L=F(s_L). Кроме того, y_i0=F(s_i0) не должно обязательно должно быть гарантировано. Затем алгоритм Gen генерирования ключа устанавливают (F, y₁, …, y_L), как открытый ключ pk, и устанавливают (s₁, …, s_L) для секретного ключа.

Алгоритм Р контролера, алгоритм V проверяющего

Далее, со ссылкой на фиг.16, будут описаны структуры алгоритма Р контролера и алгоритма V проверяющего. Кроме того, предполагается, что открытый ключ pk генерируемый алгоритмом Gen генерирования ключа, совместно используется между контролером и проверяющим. Кроме того, предполагается, что контролер тайно распоряжается секретным ключом sk, генерируемым алгоритмом Gen генерирования ключа.

Интерактивный протокол настоящей схемы №2 состоит из этапов 1-4 показанных на фиг.16. Ниже, будет описана обработка каждого этапа.

Этап 1:

Вначале, алгоритм Р контролера генерирует вектор r_i, t_i∈Kⁿ и вектор e_i∈K^m поскольку i=1, …, L. Затем, алгоритм Р контролера выбирает одну Ch*∈{0, 1, 2}. Эта Ch* соответствует структуре проверки, где контролер не в состоянии дать ответ относительно группы i₀. Затем, если i≠i₀, алгоритм Р контролера вычисляет (Cmt_i; St_i)←Р_{а, 1}(F, y_i, si; r_i, t_i, e_i). с другой стороны, если i=i₀, алгоритм Р контролера вычисляет (Cmt_i; St_i)←М_{а, 1}(F, y_i; Ch*, si, r_i, t_i, e_i). Затем, алгоритм P контролера отправляет Cmt₁, …, Cmt_L проверяющему (алгоритм V проверяющего).

Этап 2:

Алгоритм V проверяющего, который принял Cmt₁, …, Cmt_L, выбирает структуру проверки, которая будет использоваться, из трех структур проверки. В этой точке алгоритм V проверяющего выбирает комбинацию двух структур проверки. Затем, алгоритм V проверяющего отправляет контролеру (алгоритм Р контролера) наборы проблем (Ch₁ ⁽⁰⁾, …, Ch_L ⁽⁰⁾), (Ch₁ ⁽¹⁾, …, Ch_L ⁽¹⁾)∈_R{0, 1, 2}, обозначающие выбранные структуры проверки. Кроме того, Chi⁽⁰⁾ не равна Chi⁽¹⁾.

Этап 3:

Алгоритм Р контролера, который принял (Ch₁ ⁽⁰⁾, …, Ch_L ⁽⁰⁾) и (Ch₁ ⁽¹⁾, …, Ch_L ⁽¹⁾) выбирает ряд проблем, на которые будет дан ответ, следующим образом. Кроме того, результат выбора будет обозначен как d∈_R{0, 1}. Если Ch_i0 ⁽⁰⁾=Ch* (состояние 1), алгоритм Р контролера устанавливает в d←1. С другой стороны, если Ch_i0 ⁽¹⁾=Ch* (состояние 2), алгоритм Р контролера устанавливает в d←0. В других случаях, кроме состояний 1 и 2, алгоритм Р контролера случайно устанавливает d ∈ {0, 1}. В соответствии с этим способом установки, независимо от того какая структура проверки запрашивается проверяющим, d принимает любое из значений 0 и 1 с вероятностью 1/2, и таким образом информация, обозначающая значение, которое i₀ принимает среди 1, …, L будет полностью скрыта.

После установки d, алгоритм Р контролера вычисляет Rsp_i относительно i ∈{1, …, L} следующим образом. Если i≠i₀, алгоритм Р контролера вычисляет Rsp_i←Р_{а, 2}(Ch^(d)i; St_i).

С другой стороны, если i=i₀, алгоритм Р контролера вычисляет Rsp_i←M_{a, 2}(Ch^(d) _i; St_i). Затем, алгоритм Р контролера передает (Rsp₁, …, Rsp_L, d) проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял (Rsp₁, …Rsp_L, d) выполняет 0/1←Dec_a(F, y_i; Cmt_i, Ch^(d) _i, Rsp_i) относительно i ∈{1, …, L}. Затем, в случае приема (выход 1) для всех i ∈{1, …, L}, алгоритм V проверяющего предполагает, что проверка установлена.

В представленном выше описании был описан интерактивный протокол (модифицированный пример) для случая, когда схема, в соответствии с настоящим способом №2, применяется для схемы аутентификации с открытым ключом SSH10a. Кроме того, в представленном выше пояснении, два набора проблем были переданы от проверяющего контролеру, но также возможно определить заранее вторую проблему, например, как Ch_i ⁽¹⁾=Ch_i ⁽⁰⁾+1 mod 3. В этом случае, один из наборов проблем не обязательно требуется передавать, и, таким образом, количество передаваемых данных может быть уменьшено.

3-4: Применение для схемы аутентификации с открытым ключом SSH10b

Далее интерактивный протокол для случая, когда схема, в соответствии с настоящим способом №2, применяется для схемы аутентификации с открытым ключом SSH10b, будет описан со ссылкой на фиг.17. На фиг.17 показана пояснительная схема для описания интерактивного протокола для случая, когда схема, в соответствии с настоящим способом №2, применяется для схемы аутентификации с открытым ключом SSH10b. Такой интерактивный протокол выполнен из алгоритма Gen генерирования ключа, алгоритм Р контролера и алгоритма V проверяющего. В дальнейшем будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключа генерирует m многочленов второго порядка по n переменным f₁(х₁, …, x_n), …, из (х₁, …, x_n) определенным на кольце K и векторов L s₁, …, s_L ∈ Kⁿ. Кроме того, вектор по n переменным (х₁, …, x_n) будет обозначен как х, и m многочленов второго порядка n переменных (f₁ (x), …, из (x)) будут обозначены, как F(x). Затем, алгоритм Gen генерирования ключа вычисляет y₁=F(s₁), …, y_L=F(s_L). Затем, алгоритма Gen генерирования ключа устанавливает (F, y₁, …, y_L) для открытого ключа pk, и устанавливает (s₁, …, sL) для секретного ключа.

Алгоритм Р контролера, алгоритм V проверяющего

Далее, со ссылкой на фиг.135, будут описаны структуры алгоритма Р контролера и алгоритма V проверяющего. Интерактивный протокол, в соответствии с настоящей схемой №2, предназначенный для того, чтобы обеспечить для проверяющего возможность доказательства того, что “контролер знает s_i, которое удовлетворяет L-1 частям y_i=F(s_i)”, без утечки к проверяющему информации о том, ″какое значение s_i использовали или какое не использовали” вообще. Кроме того, открытый ключ pk, генерируемый алгоритмом Gen генерирования ключа, как предполагается, совместно используется между контролером и проверяющим. Кроме того, предполагается, что контролер секретно распоряжается секретным ключом sk, генерируемым алгоритмом для генерирования ключей.

Интерактивный протокол, в соответствии с настоящей схемой №2, составлен из обработки этапов 1-6 показанных на фиг.17. Ниже, будет описана обработка на каждом этапе.

Этап 1:

Вначале, алгоритм Р контролера генерирует вектор r_i, t_i∈Kbⁿ и вектор e_i∈K^m относительно i=1, L. Затем, алгоритм Р контролера вычисляет (Cmt_{A, i}; St_{A, i})←P_{a, 1}(F, y_i, s_i; r_i, t_i, e_i). Затем, алгоритм P контролера отправляет (Cmt_{A, 1}, …, Cmt_{A, L}) проверяющему (алгоритм V проверяющего).

Этап 2:

Алгоритм V проверяющего, который принял (Cmt_A, ₁, …, Cmt_{A, L}), выбирает набор из L случайных чисел (α₁, …, α_L) среди q типов элементов кольца K. Затем, алгоритм V проверяющего отправляет запрос (Ch_{A, 1}, …, Ch_{A, L})=(α₁, …, α_L) контролеру (алгоритм Р контролера).

Этап 3:

Алгоритм Р контролера, который принял (Ch_{A, 1}, …, Ch_{A, L}) вычисляет (Cmt_{B, i};St_{B, i})←P_{b, 2}(Ch_{A, i}; St_{A, i}) относительно i=1, …, L. Затем, алгоритм P контролера передает (Cmt_{B, 1}, …, Cmt_{B, L}) проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял (Cmt_{B, 1}, …, Cmt_{B, L}) выбирает структуру проверки, которая будет использоваться, из трех структур проверки. В этой точке алгоритм V проверяющего выбирает комбинацию двух структур проверки. Затем, алгоритм V проверяющего отправляет контролеру (алгоритм Р контролера) наборы проблем (Ch_{B, 1} ⁽⁰⁾, …, Ch_{B, L} ⁽⁰⁾), (Ch_{B, 1} ⁽¹⁾, …, Ch_{B, L} ⁽¹⁾)∈_R{0, 1}^L, обозначающие выбранные структуры проверки. Дополнительно, Ch_{B, i} ⁽⁰⁾ не равен Ch_{B, i} ⁽¹⁾

Алгоритм Р контролера, который принял (Ch_{B, 1} ⁽⁰⁾, …, Ch_{B, L} ⁽⁰⁾) и (Ch_{B, 1} ⁽¹⁾, …, Ch_{B, L} ⁽¹⁾) случайно, выбирает одну установку проблем, на которые будет дан ответ. Дополнительно, результат выбора будет обозначен как d∈_R{0, 1}. Затем, алгоритм Р контролера вычисляет Rsp_i←P_{b, 2} (Ch_{B, i} ^(d); St_{B, i})относительно i ∈{1, …, L}. Затем, алгоритм Р контролера передает (Rsp₁, …, RspL, d) проверяющему (алгоритм V проверяющего).

Этап 6:

Алгоритм V проверяющего, который принял (Rsp₁, …, Rsp_L, d) выполняет 0/1←DeC_b(F, y_i; Cmt_{A, i}, Ch_{A, i}, Cmt_{B, i} Ch_{B, i} ^(d), Rsp_i) относительно i ∈{1, …, L}. Затем, в случае приема (выход 1) для всех i∈{1, …, L}, алгоритм V проверяющего предполагает, что проверка установлена.

Выше был описан интерактивный протокол для случая, когда схему настоящего способа №2 применяли к схеме аутентификации с открытым ключом SSH10b. Для этого интерактивного протокола гарантируется, что вследствие безопасности схемы аутентификации с открытым ключом SSH10b фальсификатор, не имеющий, s_i, в состоянии правильно реагировать на каждое i=1, …, L, проблемы, отправленной проверяющим с вероятностью только 1/2+1/2q или меньше. Кроме того, применяя настоящий способ №2, поскольку становится необходимо правильно ответить на вызов, отправленный от проверяющего относительно L значений i для одного из двух наборов проблем, вероятность успеха фальсификации будет равна (1/2+1/2q)^L+(1/2+1/2q)^L=2(1/2+1/2q)^L.

Кроме того, в интерактивном протоколе, описанном выше, используются все s₁, …, s_L, но даже если s_i не используется для одного из i=1, …, L, возможно получить такое же поведение, как у контролера, не сообщая проверяющему, какое s_i не использовалось. Соответственно, будет описан интерактивный протокол (модифицированный пример) выполненный с возможностью из реализации такой аутентификации как в описанном выше интерактивном протоколе, не используя одно из значений s_i.

3-5: Применение для схемы аутентификации с открытым ключом SSH10b (модифицированный пример)

Вначале интерактивный протокол (модифицированный пример) для случая, когда схема, в соответствии с настоящим способом №2, применяется для схемы аутентификации с открытым ключом SSH10b, будет описан со ссылкой на фиг.18. На фиг.18 показана пояснительная схема для описания интерактивного протокола (модифицированный пример) для случая, когда схема, в соответствии с настоящим способом №2, применяется для схемы аутентификации с открытым ключом SSH10b. Такой интерактивный протокол выполнен из алгоритма Gen генерирования ключа, алгоритма Р контролера и алгоритма V проверяющего. В частности, структура алгоритма фальсификации, описанная выше, используется в алгоритме V проверяющего. Кроме того, индекс s_i, который не используется, будет сделан i₀. Ниже будет описано содержание каждого алгоритма.

Алгоритм Gen генерирования ключа

Вначале будет описана структура алгоритма Gen генерирования ключа. Алгоритм Gen генерирования ключа генерирует m многочленов второго порядка по n переменным f₁(x₁, …, x_n), …, из (x₁, …, x_n) определенным на кольце K и векторов L s₁, …, s_L ∈ Kⁿ. В частности, вектор, который выбирают как соответствующий, используется в качестве S_i0. Дополнительно, вектор по n переменным (x₁, …, x_n) обозначают как x, и m многочленов второго порядка по n переменным (f₁(x), …, из (x)) будут обозначены как F(x). Затем, алгоритм Gen генерирования ключа вычисляет y₁=F(s₁), …, y_L=F(s_L). Дополнительно, y_i0=F(s_i0) не должен быть гарантирован. Затем, алгоритма Gen генерирования ключа устанавливает (F, y₁, …, y_L) для открытого ключа pk и устанавливает (s₁, …, s_L) для секретного ключа.

Алгоритм Р контролера, Алгоритм V проверяющего

Затем, структуры алгоритма Р контролера и алгоритма V проверяющего будут описаны со ссылкой на фиг.18. Кроме того, открытый ключ рк генерируемый алгоритмом Gen генерирования ключа, как предполагается, совместно используется между контролером и проверяющим. Кроме того, предполагается, что контролер тайно распоряжается секретным ключом sk, генерируемым алгоритмом Gen генерирования ключа.

Интерактивный протокол настоящей схемы №2 выполняется с возможностью обработки этапов 1-6 показанный на фиг.18. Ниже будет описан процесс каждого этапа.

Этап 1:

Вначале, алгоритм Р контролера генерирует вектор r_i, t_i∈Kⁿ и вектор e_i∈K^m относительно i=1, …, L. Затем, алгоритм Р контролера выбирает одну Ch_B*∈{0, 1}. Эта Ch* соответствует структуре проверки, где контролер не в состоянии дать ответ относительно группы i₀. Затем, алгоритм Р контролера вычисляет (Cmt_{A, i}; St_{A, i})←P_{b, 1}(F, y_i, s_i; r_i, t_i, e_i) для случая i≠i₀. Кроме того, алгоритм P контролера вычисляет (Cmt_{A, i}; St_{A, i})←M_{b, i}(F, y_i; Ch_B*, si, r_i, t_i, e_i,) для случая i=i₀. Затем, алгоритм P контролера передает (Cmt_{A, 1}, …, Cmt_{A, L}) проверяющему (алгоритм V проверяющего).

Алгоритм V проверяющего, который принял (Cmt_{A, L}, …, Cmt_{A, L}) выбирает набор из L случайных чисел (α₁, …, α_L) из q типов элементов кольца K. Затем, алгоритм V проверяющего отправляет запрос (Ch_{A, 1}, …, Ch_{A, L})=(α₁, …, α_L) к контролеру (алгоритм Р контролера).

Этап 3:

Алгоритм Р контролера, который принял (Ch_{A, 1}, …, Ch_{A, L}) вычисляет Cmt_B,i относительно i=1, …, L следующим образом. Вначале, если i≠i₀, алгоритм Р контролера вычисляет (Cmt_{B, i}; St_{B, i})←P_{b, 2}(Ch_{A, i}; St_{A, i}). С другой стороны, если i=i₀, алгоритм Р контролера вычисляет (Cmt_{B, i}; St_{B, i})←M_{b, 2}(Ch_A,i; St_{A, i}). Затем, алгоритм Р контролера передает (Cmt_{B, 1}, …, Cmt_{B, L}) проверяющему (алгоритм V проверяющего).

Этап 4:

Алгоритм V проверяющего, который принял (Cmt_{B, 1}, …, Cmt_{B, L}) выбирает структуру проверки, которая будет использоваться, из трех структур проверки. В этой точке алгоритм V проверяющего выбирает комбинацию двух структур проверки. Затем, алгоритм V проверяющего отправляет контролеру (алгоритм Р контролера) наборы проблем (Ch_B,1 ⁽⁰⁾, …, Ch_{B, 1} ⁽⁰⁾), (Ch_{B, 1} ⁽¹⁾, …, Ch_{B, L} ⁽¹⁾)∈_R{0, 1}^L, обозначающие выбранные структуры проверки. Дополнительно, Ch_{B, i} ⁽⁰⁾ не равен Ch_B,i⁽¹⁾

Этап 5:

Алгоритм Р контролера, который принял (Ch_{B, 1} ⁽⁰⁾, …, Ch_{B, L} ⁽⁰⁾) и (Ch_{B, 1} ⁽¹⁾, _…, Ch_{B, L} ⁽¹⁾) выбирает ряд проблем, на которые будет дан ответ, следующим образом. Кроме того, результат выбора будет обозначен как d∈R{0, 1}. Если Ch_{B, i0} ⁽⁰⁾= Ch_B*, алгоритм Р контролера устанавливает в d←1. С другой стороны, если Ch_{B, i0} ⁽¹⁾= Ch_B*, алгоритм Р контролера устанавливает в d←0. При использовании этого способа установки, независимо от того какая структура проверки запрашивается проверяющим, d снимет любое из значений 0 и 1 с вероятностью 1/2, соответственно. Таким образом, информация, обозначающая значение, которое d принимал между 0 и 1, полностью скрывается.

Затем, алгоритм Р контролера вычисляет Rsp_i относительно i=1, …, L. Алгоритм Р контролера вычисляет Rsp_i←P_{b, 3}(Ch_{B, i} ^(d); St_{B, i}) для случая i≠i₀. Кроме того, алгоритм Р контролера вычисляет Rsp_i←M_{b, 3}(Ch_{B, i} ^(d); St_{B, i}) для случая i=i₀. Затем, алгоритм Р контролера передает (Rsp₁, …, Rsp_L, d) проверяющему (алгоритм V проверяющего).

Этап 6:

Алгоритм V проверяющего, который принял (Rsp₁, …, Rsp_L, d) выполняет 0/1←Dec_b(F, y_i; Cmt_{A, i}, Ch_{A, i}, Cmt_{B, i}, Ch_{B, i} ^(d), Rsp_i) относительно i=1, …, L. Затем, в случае приема (выход 1) для всех i=1, …, L, алгоритм V проверяющего предполагает, что проверка установлена.

Выше был описан интерактивный протокол (модифицированный пример) для случая, когда схему настоящего способа №2 применяют к схеме аутентификации с открытым ключом SSH10b. Дополнительно, в представленном выше объяснении два набора проблем отправляют от проверяющего контролеру, но также возможно определить заранее второй запрос, например, чтобы Chi⁽¹⁾=Chi⁽⁰⁾+1 mod 2. В этом случае, один из наборов проблем не должен быть отправлен, и таким образом, количество обмениваемых данных может быть уменьшено.

Выше был описан второй вариант осуществления настоящего раскрытия. Представленное выше пояснение было представлено с учетом схемы аутентификации с открытым ключом SSH10a и схемы аутентификации с открытым ключом SSH10b, в качестве примеров, но объем применения настоящей схемы №2 не ограничивается ими. Также возможно приложение к модифицированным примерам схемы аутентификации с открытым ключом SSH10a и схемы аутентификации с открытым ключом SSH10b в других схемах аутентификации с открытым ключом. Например, в представленном выше примере, (F, y) устанавливается для открытого ключа, но поскольку F представляет собой параметр, не зависимый от секретного ключа, это значение F также может быть сделано параметром, общим для всей системы, вместо установки для каждого контролера. В этом случае, открытые ключи, которые требуется индивидуально опубликовать, будут представлять собой только y, и размер открытого ключа будет уменьшен. Кроме того, в интерактивном протоколе, описанном выше, случайные числа α₁, …, α_L, ось выбирают отдельно, где i=1, …, L, но эти случайные числа могут быть сделаны одним общим случайным числом. В таком случае стоимость передачи данных во время передачи проблемы Ch_{A, i,} может быть уменьшена.

4: Приложение

Здесь будет представлено дополнительное пояснение настоящих способов №1 и №2.

4-1: Расширение схемы

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

Применение для задачи декодирования синдрома

Схема аутентификации с открытым ключом на основе задачи декодирования синдрома раскрыта, например, в публикации Jacques Stern, “A New Identification Scheme Based on Syndrome Decoding, CRYPTO 1993, p13-21” and Jacques Stern, “A New Paradigm for Public Key Identification, IEEE Transactions on Information Theory, 1996, p13-21.” В соответствии с этим, такая схема аутентификации с открытым ключом включает в себя 3-ходовую схему и 5-ходовую схему.

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

Применение для задачи ограниченных линейных уравнений

Схема аутентификации с открытым ключом на основе задачи ограниченных линейных уравнений раскрыта, например, в публикации Jacques Stern, “Designing Identification Schemes with Keys of Short Size, CRYPTO 1994, p164-173.” В соответствии с этим, такая схема аутентификации с открытым ключом также включает в себя 3-ходовую схему и 5-ходовую схему.

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

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

Схема аутентификации с открытым ключом на основе задачи ядра с перестановками раскрыта, например, в Adi Shamir, “An Efficient Identification Scheme Based on Permuted Kernels (Extended Abstract),CRYPTO 1989, p606-609.” В соответствии с этим, существуют две структуры проверки для такой схемы аутентификации с открытым ключом, и существует алгоритм фальсификации, который может справиться с одной из двух структур. В соответствии с этим, способ, описанный выше в отношении схемы аутентификации с открытым ключом SSH10b, можно применять для схемы аутентификации с открытым ключом.

Применение для задачи поиска сечения на алгебраической поверхности Схема аутентификации с открытым ключом, на основе задачи поиска сечения на алгебраической поверхности включает в себя 3-ходовую схему и 5-ходовую схему (например, см. JP 2010-125026А). Так же, как и в схеме аутентификации с открытым ключом SSH10a, существуют три структуры проверки для 3-ходовой схемы, и существует алгоритм фальсификации, который может справиться с двумя из этих трех структур. Кроме того, как и в схеме аутентификации с открытым ключом SSH10b, существуют две структуры проверки для 5-ходовой схемы, и существует алгоритм фальсификации, который позволяет справиться с одной из этих двух структур. В соответствии с этим, способ, описанный выше в отношении схемы аутентификации с открытым ключом SSH10a, можно применять для 3-ходовой схемы, и способ, описанный выше в отношении схемы аутентификации с открытым ключом SSH10b, может применяться для 5-ходовой схемы.

Применение для задачи перцептронов с перестановками

Схема аутентификации с открытым ключом на основе задачи перцептронов с перестановками раскрыта, например, в David Pointcheval, “A New Identification Scheme Based on the Perceptrons Problem, EUROCRYPT 1995, p319-328” и David Pointcheval and Guillaume Poupard, “A New NP-Complete Problem and Public-Key Identification, Des. Codes Cryptography, 2003, p5-31.” В соответствии с этим, схема аутентификации с открытым ключом включает в себя 3-ходовую схему и 5-ходовую схему.

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

При применении настоящего способа №1 в схеме с к структурами проверки, обеспечивая при этом секретный ключ в виде мультиплексированного ключа, включающего в себя L=k ключей, одно значение i (ниже называется i*), для которого не будет предоставлен ответ, должно быть выбрано из i=1, …, L следующим образом. В частности, способ выбора i* представляет собой способ выбора i*←i₀ в случае Ch_i0=Ch*, и случайного выбора i* из i*∈{1, …, L}¥{i₀}, в случае Ch_i0≠Ch*.

Кроме того, при применении настоящего способа №1 к схеме с k структурами проверки, обеспечивая мультиплексирование секретного ключа, причем ключ включает в себя L(L<k) ключей, одно значение i (ниже обозначается, как i*), для которого ответ не будет предоставлен, должно быть выбрано из i=1, …, L следующим образом. В частности, способ выбора i* представляет собой способ выбора i*←i₀, в случае Ch_i0=Ch*, и выбора i*←i₀ с вероятностью (1-1/k)^-1(1/L-1/k) и случайного выбора i* из i*∈{1, …, L}¥{i₀} с вероятностью 1-(1-1/k)^-1(1/L-1/k), в случае Ch_i0≠Ch*.

В соответствии с представленным выше способом, независимо от того, какая структура проверки будет запрошена проверяющим, значение i* будет принимать значение среди 1, …, L с вероятностью 1/L, и информация, обозначающая, какое значение приняло i₀ среди 1, …, L будет полностью скрыта.

Как описано выше, настоящие способы №1 и №2 могут применяться не только для схемы аутентификации с открытым ключом SSH10a и схемы аутентификации с открытым ключом SSH10b, но также и к различным схемам аутентификации с открытым ключом.

4-2: Схема аутентификации неинтерактивного открытого ключа Схемы аутентификации с открытым ключом, в соответствии с настоящими способами №1 и №2, описанными выше, представляют собой схемы, в которых проверяющий передает только случайное число, и, таким образом, возможна модификация в 1-ходовую (неинтерактивную) схему аутентификации с открытым ключом. Например, то, что получается в результате применения функции хеширования к содержанию обмена с проверяющим в конфигурации из N параллельных повторений, может использоваться вместо случайного числа для передачи от проверяющего. Случайное число, выбранное контролером, также может быть добавлено к аргументу функции хеширования. Когда сам контролер использует функцию хеширования вместо выбора проверяющим случайного числа, таким образом, будет реализовано такое же поведение, как и в случае, когда проверяющий выбирает случайное число. Кроме того, желательно, чтобы использовалась идеальная функция хеширования. Кроме того, количество N повторений желательно сделать достаточно большим, с тем, чтобы исключить возможность фальсификации. Такое усовершенствование обеспечивает модификации в схеме неинтерактивной аутентификации с открытым ключом.

4-3: Способ уменьшения количества передаваемых данных

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

Как было описано, набор сообщений (c₁, c₂, c₃) передают из контролера проверяющему за первый ход в схему аутентификации с открытым ключом SSH10a. Кроме того, в представленном выше пояснении, использовалось выражение Cmt. В случае конфигурации из N параллельных повторений, этот набор сообщений будет представлять собой (c_1,1, c_1,2, c_1,3, …, c_{N, 1}, c_{N, 2}, c_{N, 3}), как показано на фиг.19, и количество передаваемых данных будет чрезвычайно велико. Таким образом, авторы настоящего изобретения разработали конфигурацию совместной передачи этих сообщения, как одно значение хеширования.

Как показано на фиг.19, при приеме такой конфигурации, сообщение, которое должно быть передано за первый ход, будет представлять собой только одно значение хеширования, и количество передаваемых данных может быть значительно уменьшено. Кроме того, такое значение хеширования и значение хеширования, которое не восстанавливается из ответа на проблему, переданную из контролера, должны быть переданы от контролера вместе с ответом. В соответствии с такой конфигурацией, в случае конфигурации из N параллельных повторений, количество частей информации, предназначенных для передачи, может быть уменьшено на 2N-1. Такая же конфигурация может применяться для схемы аутентификации с открытым ключом SSH10b, как показано на фиг.20. В этом случае количество частей информации, предназначенной для передачи, может быть уменьшено на N-1.

В дальнейшем будет представлено дополнительное пояснение для настоящих способов №1 и №2.

5: Конфигурация аппаратных средств

Каждый алгоритм, описанный выше, может быть выполнен с использованием, например, конфигурации аппаратных средств устройства обработки информации, показанного на фиг.21. Таким образом, обработка каждого алгоритма может быть реализована путем управления аппаратными средствами, показанными на фиг.21, используя компьютерную программу. Кроме того, режим данных аппаратных средств является произвольным, и может представлять собой персональный компьютер, терминал мобильной информации, такой как мобильный телефон, PHS или PDA, игровое устройство, контактную или бесконтактную микросхему IC, контактную или бесконтактную IC-карту или различные типы устройств обработки информации. Кроме того, PHS представляет собой сокращение Системы для персональных мобильных телефонов. Кроме того, PDA представляет собой сокращение для карманного персонального компьютера.

Как показано на фиг.21, такие аппаратные средства, в основном, включают в себя CPU 902, ROM 904, RAM 906, хост-шину 908 и мост 910. Кроме того, данные аппаратные средства включают в себя внешнюю шину 912, интерфейс 914, модуль 916 ввода, модуль 918 вывода, модуль 920 накопителя, привод 922, соединительный порт 924, и модуль 926 передачи данных. Кроме того, CPU представляет собой сокращение для центрального процессорного устройства. Кроме того, ROM представляет собой сокращение для постоянного запоминающего устройства. Кроме того, RAM представляет собой сокращение для оперативного запоминающего устройства.

CPU 902 функционирует, например, как модуль арифметической обработки или модуль управления, и управляет всей работой или частью работы каждого конструктивного элемента на основе различных программ, записанных в ROM 904, RAM 906, модуле 920 накопителя или съемном носителе 928 записи. ROM 904 представляет собой средство для сохранения, например, программы, предназначенной для загрузки в CPU 902, или данных, и т.п., используемых в арифметической операции. RAM 906 временно или постоянно содержит, например, программу, предназначенную для загрузки в CPU 902 или различные параметры и т.п., произвольно изменяющиеся при выполнении программы.

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

Модуль 918 вывода представляет собой, например, устройство дисплея, такое как CRT, LCD, PDP или ELD, устройство вывода звука, такое как громкоговоритель или головные наушники, принтер, мобильный телефон или факсимильное устройство, которое позволяет визуально или на слух уведомлять пользователя о полученной информации. Кроме того, CRT представляет собой сокращение для электронно-лучевой трубки. LCD представляет собой сокращение для жидкокристаллического дисплея. PDP представляет собой сокращение для панели плазменного дисплея. Кроме того, ELD представляет собой сокращение для электролюминесцентного дисплея.

Модуль 920 сохранения представляет собой устройство для сохранения различных данных. Модуль 920 сохранения представляет собой, например, магнитное устройство накопителя, такое как привод жесткого диска (HDD), полупроводниковое устройство сохранения, оптическое устройство сохранения, или магнитооптическое устройство сохранения. HDD представляет собой сокращение для привода жесткого диска.

Привод 922 представляет собой устройство, которое считывает информацию, записанную на съемном носителе 928 записи, таком как магнитный диск, оптический диск, магнитооптический диск или полупроводниковое запоминающее устройство, или записывает информацию на съемный носитель 928 записи. Съемный носитель 928 записи представляет собой, например, носитель записи DVD, носитель записи Blu-ray, носитель записи HD-DVD, различные типы полупроводниковых носителей информации и т.п. Конечно, съемный носитель 928 записи может, например, представлять собой электронное устройство или IC-карту, на которой устанавливается бесконтактная IC - микросхема. IC представляет собой сокращение для интегральной схемы.

Соединительный порт 924 представляет собой порт, такой как порт USB, порт IEEE 1394, SCSI, порт РТС-232С или порт для соединения внешнего подключенного устройства 930, такого как оптический вывод аудиоданных. Внешнее подключенное устройство 930 представляет собой, например, принтер, мобильный музыкальный проигрыватель, цифровую камеру, цифровую видеокамеру или IC блок записи. Кроме того, USB представляет собой сокращение для универсальной последовательной шины. Кроме того, SCSI представляет собой сокращение для системного интерфейса малых компьютеров.

Модуль 926 передачи данных представляет собой устройство передачи данных, предназначенное для подключения к сети 932, и представляет собой, например, карту передачи данных для проводных или беспроводных LAN, Bluetooth (зарегистрированный товарный знак) или WUSB, маршрутизатор оптической передачи данных, маршрутизатор ADSL или устройство для контактной или бесконтактной передачи данных. Сеть 932, соединенная с модулем 926 передачи данных, выполнена из сети, подключенной по проводом или подключенной по беспроводному каналу передачи данных, и представляет собой Интернет, LAN для домашнего использования, инфракрасную передачу данных, передачу данных видимого света, широковещательную передачу данных или спутниковую передачу данных, например. Кроме того, LAN представляет собой сокращение для локальной вычислительной сети. Кроме того, WUSB представляет собой сокращение для беспроводного USB. Кроме того, ADSL представляет собой сокращение для Асимметричной цифровой абонентской линии.

6: Краткая сводка

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

Функциональная конфигурация устройства обработки информации, описанная выше, может быть выражена таким образом, как представлено ниже. Устройство обработки информации включает в себя модуль содержания ключа и модуль выполнения интерактивного протокола как указано ниже. Модуль содержания ключа, предназначенный для содержания L(L≥2) секретных ключей s_i(i=от 1 до L) и L открытых ключей y_i, которые удовлетворяют y_i=F(si) в отношении набора из F многочленов по множеству переменных n-го порядка (n≥2). Кроме того, модуль выполнения интерактивного протокола предназначен для выполнения с проверяющим, интерактивного протокола, для доказательства знания (L-1) секретных ключей s_i, которые удовлетворяют y_i=F(s_i). Кроме того, модуль выполнения интерактивного протокола предотвращает, во время выполнения интерактивного протокола с проверяющим, знание проверяющим, какой секретный ключ s_i использовался.

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

Примечания

Устройство обработки информации, описанное выше, представляет собой пример устройства аутентификации на стороне контролера или стороне проверяющего. Кроме того, ROM 904, RAM 906, модуль 920 сохранения и съемный носитель 928 записи представляют собой примеры модуля для содержания ключа. Кроме того, секретный ключ i и открытый ключ y_i, которые содержат в модуле удержания ключа, генерируют с помощью алгоритма Gen генерирования ключа. Кроме того, алгоритм Р контролера и алгоритм V проверяющего представляют собой примеры модуля выполнения интерактивного протокола. Кроме того, в действительности, функция модуля выполнения интерактивного протокола реализуется путем выполнения алгоритма Р контролера или алгоритма V проверяющего, с помощью функции CPU 902. Кроме того, функции модуля приема проблемы, модуля выбора вызовов, модуля генерирования ответа, модуля передачи ответа и модуля передачи сообщения реализуется с помощью функций, реализованных с помощью алгоритма Р контролера. Кроме того, функция модуля 926 передачи данных используется для обмена информацией.

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

Список номеров ссылочных позиций

Gen Алгоритм генерирования ключей

Р алгоритм контролера

V алгоритм проверяющего.

Изобретение относится к области аутентификации. Технический результат - эффективная защита цифровой подписи. Устройство аутентификации, включающее в себя модуль хранения ключей для хранения L(L≥2) секретных ключей s_i(i = от 1 до L) и L открытых ключей y_i, удовлетворяющих условию y_i=F(s_i) в отношении набора F многочленов нескольких переменных n-го порядка (n≥2), и модуль выполнения интерактивного протокола, предназначенный для выполнения с помощью проверяющего интерактивного протокола для проверки знания (L-1) секретных ключей s_i, удовлетворяющих условию y_i=F(s_i). Модуль выполнения интерактивного протокола включает в себя модуль приема вызовов для приема L вызовов Ch_i от проверяющего, модуль выбора вызовов для произвольного выбора (L-1) вызовов Ch_i из L вызовов Ch_i, принимаемых модулем приема вызовов, модуль генерирования ответов для генерирования, с использованием секретных ключей s_i, (L-1) ответов Rsp_i, соответственно, для (L-1) вызовов Ch_i, выбираемых модулем выбора вызовов, и модуль передачи ответов для передачи проверяющему (L-1) ответов Rsp_i, генерируемых модулем генерирования ответа. 6 н. и 2 з.п. ф-лы, 21 ил.

1. Устройство аутентификации, содержащее:
схему, выполненную с возможностью
установки s∈Kⁿ в качестве секретного ключа и установки многочленов множественного порядка на кольце K, f_i(х₁, …, x_n) (i = от 1 до m) и y_i=f_i(s) в качестве открытого ключа;
передачи сообщения с проверяющему;
приема информации об одной схеме проверки, выбираемой проверяющим из k (k≥3) схем проверки в соответствии с одним элементом сообщения с; и
передачи проверяющему ответной информации, соответствующей принятой информации о схеме проверки, из k вариантов ответной информации,
при этом ответная информация вычислена с использованием информации z∈Kⁿ, где секретный ключ s маскирован посредством векторов r∈Kⁿ, t′∈Kⁿ, где вектор r маскирован посредством вектора t∈Kⁿ, многочлена $$f_i^{"}(x)$$ , где многочлены множественного порядка f_i(х+r) в отношении x маскированы многочленом $$f_i^{\text{'}}(x)$$ .

2. Устройство аутентификации по п. 1,
в котором многочлены множественного порядка f_i(x₁, …, x_n) (i = от 1 до m) представляют собой многочлены второго порядка, а
$$f_i^{\text{'}}(x)$$ представляет собой многочлен первого порядка.

3. Устройство аутентификации по п. 2,
в котором многочлен первого порядка представляет собой многочлен первого порядка f_i(x+t)-f_i(x)-f_i(t)+e_i (e_i∈K) в отношении x.

4. Устройство аутентификации, содержащее
схему, выполненную с возможностью
установки s∈Kⁿ в качестве секретного ключа и установки многочленов второго порядка на кольце K, f_i(x₁, …, x_n) (i = от 1 до m) и y_i=f_i(s) в качестве открытого ключа;
передачи сообщения с проверяющему;
приема информации об одной схеме проверки, выбираемой проверяющим из k (k≥3) схем проверки в соответствии с одним элементом сообщения с; и
передачи проверяющему ответной информации, соответствующей принятой информации о схеме проверки, из k вариантов ответной информации,
при этом ответная информация вычислена с использованием информации z∈Kⁿ, где секретный ключ s маскирован посредством векторов r∈Kⁿ, t′∈Kⁿ, где вектор r маскирован посредством векторов t∈Kⁿ, $$e_i^{\text{'}}\in K$$ , где f_i(r), полученный подстановкой вектора r в многочлены второго порядка f_i, маскирован посредством вектора e_i∈K.

5. Способ аутентификации, содержащий этапы, на которых:
устанавливают, при помощи схемы, s∈Kⁿ в качестве секретного ключа и устанавливают многочлены множественного порядка на кольце K, f_i(x₁, …, x_n) (i = от 1 до m) и y_i=f_i(s) в качестве открытого ключа;
передают, при помощи указанной схемы, сообщение с проверяющему;
принимают, при помощи указанной схемы, информацию об одной схеме проверки, выбранной проверяющим из k (k≥3) схем проверки в соответствии с одним элементом сообщения с; и
передают проверяющему, при помощи указанной схемы, ответную информацию, соответствующую принятой информации о схеме проверки, из k вариантов ответной информации,
при этом вычисляют ответную информацию с использованием информации z∈Kⁿ, где секретный ключ s маскирован посредством векторов r∈Kⁿ, t′∈Kⁿ, где вектор r маскирован посредством вектора t∈Kⁿ, многочлена $$f_i^{"}(x)$$ , в котором многочлены множественного порядка f_i(x+r) в отношении x маскированы многочленом $$f_i^{\text{'}}(x)$$ .

6. Способ аутентификации, содержащий этапы, на которых:
устанавливают, при помощи схемы, s∈Kⁿ в качестве секретного ключа и устанавливают многочлены второго порядка на кольце K, f_i(x₁, …, x_n) (i = от 1 до m) и y_i=f_i(s) в качестве открытого ключа;
передают, при помощи указанной схемы, сообщение с проверяющему;
принимают, при помощи указанной схемы, информацию об одной схеме проверки, выбранной проверяющим из k (k≥3) схем проверки в соответствии с одним элементом сообщения с; и
передают проверяющему, при помощи указанной схемы, ответную информацию, соответствующую принятой информации о схеме проверки, из k вариантов ответной информации,
при этом вычисляют ответную информацию с использованием информации z∈Kⁿ, где секретный ключ с маскирован посредством векторов r∈Kⁿ, t′∈Kⁿ, где вектор r маскирован посредством векторов t∈Kⁿ, $$e_i^{\text{'}}\in K$$ , где f_i(r), полученный подстановкой вектора r в многочлены второго порядка f_i, маскирован посредством вектора e_i∈K.

7. Считываемый компьютером носитель записи, содержащий программу, вызывающую выполнение компьютером этапов, на которых:
устанавливают s∈Kⁿ в качестве секретного ключа и устанавливают многочлены множественного порядка на кольце K, f_i(x₁, …, x_n) (i = от 1 до m) и y_i=f_i(s) в качестве открытого ключа;
передают сообщение с проверяющему;
принимают информацию об одной схеме проверки, выбранной проверяющим из k (k≥3) схем проверки в соответствии с одним элементом сообщения с; и
передают проверяющему ответную информацию, соответствующую принятой информации о схеме проверки, из k вариантов ответной информации,
при этом вычисляют ответную информацию с использованием информации z∈Kⁿ, где секретный ключ s маскирован посредством векторов r∈Kⁿ, t′∈Kⁿ, где вектор r маскирован посредством вектора t∈Kⁿ, многочлена $$f_i^{"}(x)$$ , где многочлены множественного порядка f_i(x+r) в отношении x маскированы многочленом $$f_i^{\text{'}}(x)$$ .

8. Считываемый компьютером носитель записи, содержащий программу, вызывающую выполнение компьютером этапов, на которых:
устанавливают s∈Kⁿ в качестве секретного ключа и устанавливают многочлены множественного порядка на кольце K, f_i(x₁, …, x_n) (i = от 1 до m) и y_i=f_i(s) в качестве открытого ключа;
передают сообщение с проверяющему;
принимают информацию об одной схеме проверки, выбранной проверяющим из k (k≥3) схем проверки в соответствии с одним элементом сообщения с; и
передают проверяющему ответную информацию, соответствующую принятой информации о схеме проверки, из k вариантов ответной информации,
при этом вычисляют ответную информацию с использованием информации z∈Kⁿ, где секретный ключ s маскирован посредством векторов r∈Kⁿ, t′∈Kⁿ, где вектор r маскирован посредством t∈Kⁿ, $$e_i^{\text{'}}\in K$$ , где f_i(r), полученный подстановкой вектора r в многочлены второго порядка f_i, маскирован посредством вектора e_i∈K.