Результат интеллектуальной деятельности: УСТРОЙСТВО ОБРАБОТКИ ИНФОРМАЦИИ, СПОСОБ ОБРАБОТКИ ИНФОРМАЦИИ И ПРОГРАММА

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

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

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

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

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

Указанный RSA-алгоритм подписи принимает за основу обеспечения безопасности принцип «трудности разложения большого составного числа на простые множители» (в последующем, проблема разложения на простые множители). Кроме того, DSA-алгоритм подписи принимает за основу обеспечения безопасности принцип «трудности решения проблемы дискретного логарифмирования». Эти принципы базируются на том факте, что не существуют алгоритмы, позволяющие эффективно решать проблему разложения на простые множители и проблему дискретного логарифмирования с использованием классического компьютера. Иными словами, упомянутые выше трудности предполагают вычислительные сложности для классического компьютера. Однако считается, что решения проблемы разложения на простые множители и проблемы дискретного логарифмирования могут быть эффективно вычислены с использованием квантового компьютера.

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

Например, в качестве алгоритмов цифровой подписи, использующих проблему многочленов от нескольких переменных в качестве основы безопасности, известны такие алгоритмы, как алгоритмы на основе криптографии Мацумото-Имаи (Matsumoto-Imai (MI)), криптографии с использованием уравнений скрытого поля (Hidden Field Equation (HFE)), алгоритмы подписи типа Oil-Vinegar (OV) signature и криптографии с использованием ручного преобразования (Tamed Transformation Method (TTM)). Например, алгоритм цифровой подписи на основе HFE-криптографии рассмотрен в следующей непатентной литературе 1 и 2.

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

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

Непатентная литература 1: Жак Патарен, "Асимметричная криптография со скрытым одночленом" (Jacques Patarin, Asymmetric Cryptography with a Hidden Monomial, CRYPTO 1996, pp. 45-60).

Непатентная литература 2: Патарен Ж., Куртуа Н. и Губин Л., "КВАРЦ, Цифровые подписи длиной 128 бит", (Patarin, J., Courtois, N., and Goubin, L., QUARTZ, 128-Bit Long Digital Signatures, In Naccache, D., Ed.). Topics in Cryptology - CT-RSA 2001 (San Francisco, CA, USA, April 2001), vol. 2020 of Lecture Notes in Computer Science, Springer-Verlag., pp. 282-297.

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

Техническая проблема

Как указано выше, задача многочленов от нескольких переменных представляет собой пример так называемой НП-трудной (NP-hard) проблемы, которую трудно решить даже при использовании квантового компьютера. Обычно алгоритм аутентификации с открытым ключом, использующий проблему многочлена от нескольких переменных, описываемую уравнениями HFE или аналогичным способом, использует уравнение множества порядков с несколькими переменными с потайным входом. Например, используют уравнение F(x₁,…,x_n)=y множества порядков с несколькими переменными x₁, …, x_n и линейные преобразования А и В, управляемые секретным образом. В таком случае, уравнение F множества порядков с несколькими переменными и линейные преобразования А и В являются потайными входами.

Объект, знающий потайные входы F, А и В, может решить уравнение B(F(A(x₁,…,x_n)))=y′ относительно переменных x₁, …, x_n. С другой стороны, уравнение B(F(A(x₁,…,x_n)))=y′ относительно переменных xi,..., Хп не может быть решено субъектом, который не знает потайных входов F, А и В. Используя этот механизм, можно реализовать алгоритм аутентификации с открытым ключом и алгоритм цифровой подписи, использующие трудности решения уравнения множества порядков с несколькими переменными в качестве основы для обеспечения безопасности.

Как описано выше, для реализации алгоритма аутентификации с открытым ключом или алгоритма цифровой подписи необходимо подготовить специальную систему уравнений множества порядков с несколькими переменными, удовлетворяющую условию B(F(A(x₁,…,x_n)))=y. Далее, в момент генерации подписи необходимо решить систему уравнений F множества порядков с несколькими переменными. По этой причине совокупность доступных систем уравнений F множества порядков с несколькими переменными до сих пор ограничивалась относительно легко решаемыми системами уравнений. Таким образом, ранее в известных схемах использовались только системы B(F(A(x₁,…,x_n)))=y уравнений множества порядков с несколькими переменными на основе сочетания трех функций (потайных входов) В, F и А, которые можно относительно решить, вследствие чего трудно обеспечить достаточную степень безопасности.

Соответственно, в свете изложенных выше обстоятельств, авторы настоящего изобретения разработали эффективные и в высокой степени защищенные алгоритм аутентификации с открытым ключом и алгоритм цифровой подписи с использованием систем уравнений множества порядков с несколькими переменными, для которых отсутствуют или присутствуют в недостаточном количестве средства для эффективного решения (потайные входы) (Коити Сакумото, Тайдзо Сираи и Харунага Хиватари, «Алгоритмы идентификации с открытым ключом на основе квадратичных полиномов от нескольких переменных» (Koichi Sakumoto, Taizo Shirai and Harunaga Hiwatari, "Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials", CRYPTO 2011, LNCS 6841, pp. 706 to 723,2011.)).

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

Решение проблемы

Согласно одному из вариантов настоящего изобретения предложено устройство обработки информации, содержащее модуль генерации чисел, выполненный с возможностью генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и модуль назначения, выполненный с возможностью назначения чисел, генерируемых посредством модуля генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными. Модуль назначения группирует коэффициенты членов, имеющих идентичное сочетание переменных, из совокупности коэффициентов многочленов множества порядков с несколькими переменными, составляющими элементами которых является пара многочленов F множества порядков с несколькими переменными, и выполняет процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложено устройство обработки информации, содержащее модуль генерации чисел, выполненный с возможностью генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и модуль назначения, выполненный с возможностью назначения чисел, генерируемых посредством модуля генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными. Модуль назначения группирует матрицу коэффициентов в каждой строке или столбце, когда многочлены множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, выражены в квадратичной форме, при этом модуль назначения выполняет процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложено устройство обработки информации, содержащее модуль генерации чисел, выполненный с возможностью генерации чисел, количество которых идентично количеству коэффициентов членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и модуль назначения, выполненный с возможностью назначения чисел, генерируемых посредством модуля генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, в последовательности, заранее определенной между доказывающей стороной и проверяющей стороной.

Согласно другому варианту настоящего изобретения предложен способ обработки информации, содержащий этап генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и этап назначения генерируемых чисел коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными. На этапе назначения чисел группируют коэффициенты членов, имеющих идентичное сочетание переменных, из совокупности коэффициентов многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, и выполняют процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложен способ обработки информации, содержащий этап генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и этап назначения генерируемых чисел коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными входит в составляющие элементы. На этапе назначения чисел группируют матрицу коэффициентов в каждой строке или столбце, когда многочлены множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, выражены в квадратичной форме, и выполняют процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложен способ обработки информации, содержащий этап генерации чисел, количество которых идентично количеству коэффициентов членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и этап назначения чисел, генерируемых посредством модуля генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, в последовательности, заранее определенной между доказывающей стороной и проверяющей стороной.

Согласно другому варианту настоящего изобретения предложена программа, вызывающая выполнение компьютером функции генерации чисел для генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и функции назначения для назначения чисел, генерируемых посредством функции генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными. Функция назначения группирует коэффициенты членов, имеющих идентичное сочетание переменных, из совокупности коэффициентов многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, и выполняет процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложена программа, вызывающая выполнение компьютером функции генерации чисел для генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и функции назначения для назначения чисел, генерируемых посредством функции генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными. Функция назначения группирует матрицу коэффициентов в каждой строке или столбце, когда многочлены множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, выражены в квадратичной форме, при этом функция назначения выполняет процедуру назначения в блоках групп.

Согласно другому варианту настоящего изобретения предложена программа, вызывающая выполнение компьютером функции генерации чисел для генерации количества чисел, идентичного количеству коэффициентов членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными, и функции назначения чисел, генерируемых посредством модуля генерации чисел, коэффициентам многочленов множества порядков с несколькими переменными, составляющими элементами которых является указанная пара многочленов F множества порядков с несколькими переменными, в последовательности, заранее определенной между доказывающей стороной и проверяющей стороной.

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

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

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

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

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

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

Фиг. 3 представляет пояснительную схему для описания структуры алгоритма,

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

Фиг. 4 представляет пояснительную схему для описания эффективного 3-проходного алгоритма аутентификации с открытым ключом.

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

Фиг. 6 представляет пояснительную схему для описания эффективного 3-проходного алгоритма аутентификации с открытым ключом.

Фиг. 7 представляет пояснительную схему для описания примера структуры эффективного 5-проходного алгоритма аутентификации с открытым ключом.

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

Фиг. 9 представляет пояснительную схему для описания параллелизации эффективного 5-проходного алгоритма аутентификации с открытым ключом.

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

Фиг. 11 представляет пояснительную схему для описания способа модификации эффективного 5-проходного алгоритма аутентификации с открытым ключом для преобразования его в алгоритм цифровой подписи.

Фиг. 12 представляет пояснительную схему для описания примера структуры хэш-функции.

Фиг. 13 представляет пояснительную схему для описания способа верификации подписи (нормальный способ установки), относящегося к алгоритму цифровой подписи на основе 3-проходной схеме.

Фиг. 14 представляет пояснительную схему для описания способа верификации подписи (способ уменьшения объема памяти), относящегося к алгоритму цифровой подписи на основе 3-проходной схемы.

Фиг. 15 представляет пояснительную схему для описания способа верификации подписи (нормальный способ установки), относящегося к алгоритму цифровой подписи на основе 5-проходной схеме.

Фиг. 16 представляет пояснительную схему для описания способа верификации подписи (способ уменьшения объема памяти), относящегося к алгоритму цифровой подписи на основе 5-проходной схемы.

Фиг. 17 представляет пояснительную схему для описания способа (способ #1 выделения) выделения троичных случайных чисел из двоичных случайных чисел.

Фиг. 18 представляет пояснительную схему для описания способа (способ #2 выделения) выделения троичных случайных чисел из двоичных случайных чисел.

Фиг. 19 представляет пояснительную схему для описания способа (способ #3 выделения) выделения троичных случайных чисел из двоичных случайных чисел.

Фиг. 20 представляет пояснительную схему для описания способа (способ #3 выделения) выделения троичных случайных чисел из двоичных случайных чисел.

Фиг. 21 представляет пояснительную схему для описания способа (способ #3 выделения) выделения троичных случайных чисел из двоичных случайных чисел.

Фиг. 22 представляет пояснительную схему для описания способа структурирования данных (способ #1 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

Фиг. 23 представляет пояснительную схему для описания способа структурирования данных (способ #1 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

Фиг. 24 представляет пояснительную схему для описания способа структурирования данных (способ #1 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

Фиг. 25 представляет пояснительную схему для описания способа структурирования данных (способ #1 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

Фиг. 26 представляет пояснительную схему для описания способа структурирования данных (способ #1 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

Фиг. 27 представляет пояснительную схему для описания способа структурирования данных (способ #2 структурирования) для эффективной подстановки коэффициентов многочленов от нескольких переменных.

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

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

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

Порядок описания

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

Далее, 3-проходный алгоритм аутентификации с открытым ключом будет рассмотрен со ссылками на Фиг. 4-6. Затем, 5-проходный алгоритм аутентификации с открытым ключом будет рассмотрен со ссылками на Фиг. 7-9. Далее, способ модификации эффективных 3-проходных и 5-проходных алгоритмов аутентификации с открытым ключом для преобразования этих алгоритмов в алгоритмы цифровой подписи будет рассмотрен со ссылками на Фиг. 10-11.

Затем, способы уменьшения объемов памяти, необходимых для верификации подписи во время выполнения алгоритмов цифровой подписи, относящихся к описанным здесь вариантам, будут рассмотрены со ссылками на Фиг. 12-16. Далее, способы эффективного выделения троичных случайных чисел из двоичных случайных чисел будут рассмотрены со ссылками Фиг. 17-21. Затем, способы эффективной подстановки коэффициентов многочленов от нескольких переменных будут рассмотрены со ссылками Фиг. 22-27. Далее, пример конфигурации аппаратуры в устройстве для обработки информации, способном реализовать каждый алгоритм согласно вариантам настоящего изобретения будет рассмотрен со ссылками Фиг. 28. Наконец, будет кратко изложено резюме технических принципов вариантов настоящего изобретения и преимуществ, обеспечиваемых этими техническими принципами.

Содержание

1. Введение

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

1-2: Алгоритмы цифровой подписи

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

2. Структуры 3-проходных алгоритмов аутентификации с открытым ключом

2-1: Пример конкретной структуры алгоритма

2-2: Пример структуры параллелизованного алгоритма

2-3: Пример структуры алгоритма на основе кубического многочлена от нескольких переменных

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

3-1: Пример конкретной структуры алгоритма

3-2: Пример структуры параллелизованного алгоритма

3-3: Пример структуры алгоритма на основе кубического многочлена от нескольких переменных

4: Модификация алгоритма цифровой подписи

4-1: Модификация 3-проходного алгоритма аутентификации с открытым ключом и преобразование его в алгоритм цифровой подписи

4-2: Модификация 5-проходного алгоритма аутентификации с открытым ключом и преобразование его в алгоритм цифровой подписи

5: Способ уменьшения объема памяти, необходимого для верификации подписи

5-1: Структура хэш-функции

5-2: Пример применения 3-проходного алгоритма цифровой подписи

5-3: Пример применения 5-проходного алгоритма цифровой подписи

6: Способ выделения последовательности троичных случайных чисел из последовательности двоичных случайных чисел

6-1: Способ #1 выделения (2-битовое группирование)

6-2: Способ #2 выделения (нет группирования)

6-3: Способ #3 выделения (k-битовое группирование)

6-3-1: Базовая структура

6-3-2: Дополнительный способ выделения

7: Способ эффективной подстановки коэффициентов в многочлены от нескольких переменных

7-1: Базовое определение

7-2: Структурирование данных

7-2-1: Способ #1 структурирования

7-2-2: Способ #2 структурирования

7-2-3: Способ #3 структурирования

8: Пример конфигурации аппаратуры

9: Резюме

1. Введение

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

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

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

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

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

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

Первое условие формулируется так: «уменьшить насколько это возможно вероятность фальсификации со стороны фальсификатора, не имеющего секретного ключа sk, во время выполнения интерактивного протокола». Состояние, когда это первое условие выполняется, называется «корректность» (soundness). Другими словами, корректность означает, что «фальсификатор, с большой вероятностью не обладающий секретным ключом sk, ничего не фальсифицировал во время выполнения интерактивного протокола». Второе условие формулируется так: «даже при выполнении интерактивного протокола совсем не происходит утечки информации о секретном ключе sk_A доказывающей стороны А к проверяющей стороне В». Состояние, когда это второе условие выполняется, называется «нулевое разглашение» (zero knowledge).

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

Модель

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

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

Кроме того, термины «доказывающая сторона» ("prover") и «проверяющая сторона» ("verifier") используются в последующем описании, но они везде обозначают строго «субъекты». Таким образом, субъект, выполняющий алгоритм Gen генерации ключей и алгоритм Р доказывающей стороны, представляет собой устройство для обработки информации, соответствующее субъекту «доказывающая сторона». Аналогично, субъект, выполняющий алгоритм V проверяющей стороны, представляет собой устройство для обработки информации. Пример аппаратной конфигурации устройства для обработки информации показан на Фиг. 28, например. Иными словами, алгоритм Gen генерации ключей, алгоритм Р доказывающей стороны и алгоритм V проверяющей стороны реализуются центральным процессором CPU 902 на основе программы, записанной в постоянном запоминающем устройстве (ПЗУ ROM) 904, в запоминающем устройстве с произвольной выборкой (ЗУПВ RAM) 906, в модуле 920 памяти, на сменном носителе 928 записи или на аналогичном носителе.

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

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

Алгоритм Р доказывающей стороны

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

Алгоритм V проверяющей стороны

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

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

Изложенное выше, таким образом, суммирует принципы алгоритма аутентификации с открытым ключом

1-2: Алгоритмы цифровой подписи

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

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

Модель

Как показано на Фиг. 2, в модели алгоритма цифровой подписи присутствуют два субъекта - подписывающая сторона и проверяющая сторона. Кроме того, модель алгоритма цифровой подписи построена из трех алгоритмов: алгоритма Gen генерации ключей, алгоритма Sig генерации подписи и алгоритма Ver верификации подписи.

Подписывающая сторона использует алгоритм Gen генерации ключей для формирования пары из ключа sk подписи и проверочного ключа pk, уникальной для этой подписывающей стороны. Подписывающая сторона использует также алгоритм Sig генерации подписи с целью генерации цифровой подписи q для присоединения к сообщению М. Другими словами, подписывающая сторона является субъектом, прикрепляющим цифровую подпись к сообщению М. В то же время, проверяющая сторона использует алгоритм Ver верификации подписи для проверки цифровой подписи, прикрепленной к сообщению М. Другими словами, проверяющая сторона - это субъект, проверяющий цифровую подпись q с целью подтвердить, является ли создатель сообщения М подписывающей стороной.

Отметим, что где бы термины «подписывающая сторона» ("signer") и «проверяющая сторона» ("verifier") ни использовались в последующем описании, они в конечном счете обозначают субъектов. Следовательно, агент, выполняющий алгоритм Gen генерации ключей и алгоритм Sig генерации подписи, представляет собой устройство для обработки информации, соответствующее субъекту «подписывающая сторона». Аналогично, агент, выполняющий алгоритм Ver верификации подписи, представляет собой устройство для обработки информации. Вариант аппаратной конфигурации устройства для обработки информации показан на Фиг. 28, например. Иными словами, алгоритм Gen генерации ключей, алгоритм Sig генерации подписи и алгоритм Ver верификации подписи реализуются устройством, таким как центральный процессор CPU 902, на основе программы, записанной в постоянном запоминающем устройстве (ПЗУ ROM) 904, в запоминающем устройстве с произвольной выборкой (ЗУПВ RAM) 906, в модуле 920 памяти или на сменном носителе 928 записи.

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

Указанный алгоритм Gen генерации ключей, используется подписывающей стороной. Этот алгоритм Gen генерации ключей представляет собой алгоритм, генерирующий пару из ключа sk подписи и проверочного ключа pk, уникальную для соответствующей подписывающей стороны. Проверочный ключ pk, сформированный алгоритмом Gen генерации ключей, делается общедоступным (публикуется). В то же время, подписывающая сторона сохраняет секретность ключа sk подписи, сформированного алгоритмом Gen генерации ключей. Этот ключ sk подписи затем используется для генерации цифровой подписи q с целью прикрепления ее к сообщению М. Например, алгоритм Gen генерации ключей получает на вход параметр 1^p защищенности (где p - целое число, равное или больше 0), и передает на выход ключ sk подписи и проверочный ключ pk. В таком случае алгоритм Gen генерации ключей может быть формализован и выражен следующей формулой (3).

Алгоритм Sig генерации подписи

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

Алгоритм Ver верификации подписи

Указанный алгоритм Ver верификации подписи используется проверяющей стороной. Алгоритм Ver верификации подписи представляет собой алгоритм для проверки, является ли цифровая подпись q действительной и цифровой подписью для сообщения М. Этот алгоритм Ver верификации подписи представляет собой алгоритм, получающий проверочный ключ pk подписывающей стороны, сообщение М и цифровую подпись q в качестве входных данных и передающий на выход 0 или 1 (1 бит). Формализованно указанный алгоритм Ver верификации подписи представлен следующей формулой (5). В этот момент, проверяющая сторона принимает решение, что цифровая подпись q является недостоверной, если алгоритм Ver верификации подписи генерирует на выходе 0 (если проверочный ключ pk отклоняет сообщение М и цифровую подпись q), и признает достоверность цифровой подписи q, если алгоритм Ver верификации подписи генерирует на выходе 1 (если проверочный ключ pk принимает сообщение М и цифровую подпись q).

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

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

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

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

В случае n-проходного алгоритма аутентификации с открытым ключом доказывающая сторона выполняет процедуру с использованием алгоритма Р доказывающей стороны (операция #1) и передает информацию T₁ проверяющей стороне. После этого проверяющая сторона выполняет процедуру с использованием алгоритма V проверяющей стороны (операция #2) и передает информацию Т₂ доказывающей стороне. Такое выполнение процедур и передачу информации T_k осуществляют последовательно для k=3-n, и, наконец, осуществляет процедуру (операция #n+1). Передача и прием информации таким способом п раз называется, таким образом, «п-проходной» схемой аутентификации с открытым ключом.

Изложенное выше, таким образом, описывает n-проходный алгоритм аутентификации с открытым ключом

2. Структуры 3-проходных алгоритмов аутентификации с открытым ключом

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

2-1: Пример конкретной структуры алгоритма (Фиг. 4)

Сначала, пример конкретной структуры алгоритма, относящейся к 3-проходной схеме, будет рассмотрен со ссылками на Фиг. 4. Фиг. 4 представляет пояснительную схему для описания конкретной структуры алгоритма, относящейся к 3-проходной схеме. Здесь будет описан случай использования пары квадратичных многочленов (f₁(x), …, f_m(x)) в качестве части открытого ключа pk. Здесь предполагается, что квадратичный многочлен f_i(x) представлен следующей формулой (6). Кроме того, вектор (x₁, …, x_n) обозначен x, а пара квадратичных многочленов (f₁(x), …, f_m(x)) от нескольких переменных обозначены как многочлены F(x) от нескольких переменных.

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

При использовании этих формул многочлен F может быть выражен следующими формулой (8) и формулой (9). На основе следующей формулы (10) можно легко подтвердить, что это выражение удовлетворяется.

Если F(x+y) разбить на первую часть, зависящую только от х, вторую часть, зависящую только от y, и третью часть, зависящую и от х, и от y, тогда член G(x, y), соответствующий третьей части, становится билинейным относительно х и y. В последующем этот член G(x, y) будет также называться билинейным членом. Использование этого свойства позволяет построить эффективный алгоритм.

Например, используйте вектор t₀, являющийся элементом множества Kⁿ, и вектор ео, являющийся элементом множества K^m, для представления многочлена F₁(x) от нескольких переменных, служащего для маскирования многочленов F(x+r) от нескольких переменных, в виде F₁(x)=G(x, t₀)+e₀. В этом случае сумма многочленов F(x+r₀) и G(x) от нескольких переменных, представлена формулой (11) ниже. Здесь, если t₁=r₀+t₀, e₁=F(r₀)+e₀, многочлен F₂(x)=F(x+r₀)+F₁(x) от нескольких переменных может быть представлен вектором t₁, являющимся элементом множества Kⁿ, и вектором e₁, являющимся элементом множества K^m. По этой причине, когда задан многочлен F₁(x)=G(x, t₀)+e₀, многочлены F₁ и F₂ могут быть выражены с использованием вектора из множества Kⁿ и вектора из множества K^m, и, следовательно, можно реализовать эффективный алгоритм, которому для связи и обмена информацией необходим лишь небольшой объем данных.

Кроме того, из многочлена F₂ (или F₁) совсем нет утечки информации относительно r₀. Например, даже если даны e₁ и t₁ (или e₀ и t₀), информация относительно го остается совсем неизвестной до тех пор, пока неизвестны e₀ и t₀ (или e₁ и t₁). Соответственно, обеспечивается нулевое разглашение. Далее будут описаны алгоритмы, относящиеся к классу 3-проходных алгоритмов и построенные на основе изложенной выше логики. Алгоритм по 3-проходной схеме, который будет описан здесь ниже, построен из алгоритма Gen генерации ключей, алгоритма Р доказывающей стороны и алгоритма V проверяющей стороны.

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

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

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

В дальнейшем, процедура, выполняемая алгоритмом Р доказывающей стороны, и процедура, выполняемая алгоритмом V проверяющей стороны, в ходе работы по протоколу взаимодействия будут описаны со ссылками на Фиг. 4. Во время исполнения протокола взаимодействия доказывающая сторона совсем не допускает утечки информации о секретном ключе s и сообщает проверяющей стороне, что «она сама знает величину s, удовлетворяющую уравнению y=F(s)». С другой стороны, проверяющая сторона осуществляет проверку, действительно ли доказывающая сторона знает величину s, удовлетворяющую уравнению y=F(s). Предполагается, что открытый ключ pk, сформированный алгоритмом Gen генерации ключей, публикуется. Кроме того, предполагается, что доказывающая сторона сохраняет секретность своего секретного ключа s. В дальнейшем описание будет дано со ссылками на логическую схему, изображенную на Фиг. 4.

Операция #1:

Как показано на Фиг. 4, алгоритм Р доказывающей стороны сначала случайным образом генерирует вектор r₀, t₀, являющийся элементом множества Kⁿ, и вектор е₀, являющийся элементом множества K^m. После этого алгоритм Р доказывающей стороны вычисляет r₁<-s-r₀. Эти расчеты эквивалентны маскированию секретного ключа s с использованием вектора r₀. Кроме того алгоритм Р доказывающей стороны вычисляет t₁<-r₀-t₀. После этого алгоритм Р доказывающей стороны вычисляет e₁<-F(r₀) -e₀.

Операция #1 (продолжение):

После этого алгоритм Р доказывающей стороны вычисляет с₀<-H(r₁, G(t₀, r₁)+e₀). После этого алгоритм Р доказывающей стороны вычисляет c₁<-H(t₀, e₀). После этого алгоритм Р доказывающей стороны вычисляет c2<-H(t₁, e₁). Сообщение (с₀, c₁, с₂), генерируемое в ходе операции #1 посылают алгоритму V проверяющей стороны.

Операция #2:

После приема сообщения (с₀, c₁, c₂) алгоритм V проверяющей стороны выбирает, какую схему использовать, из совокупности трех схем верификации. Например, алгоритм V проверяющей стороны может выбрать числовую величину из совокупности трех числовых величин {0, 1, 2}, представляющих схемы верификации, и задает выбранную числовую величину в качестве параметра Запрос (challenge) Ch. Этот запрос Ch передают алгоритму Р доказывающей стороны.

Операция #3:

По получении запроса Ch алгоритм Р доказывающей стороны генерирует ответ Rsp для передачи алгоритму V проверяющей стороны в ответ на принятый запрос Ch. Если Ch=0, алгоритм Р доказывающей стороны генерирует ответ Rsp=(r₀, t₁, e₁). Если Ch=1, алгоритм Р доказывающей стороны генерирует ответ Rsp=(r₁, t₀, e₀). Если Ch=2, алгоритм Р доказывающей стороны генерирует ответ Rsp=(r₁, t₁, e₁). Ответ Rsp, генерируемый в ходе операции #3, посылают алгоритму V проверяющей стороны.

Операция #4:

После приема ответа Rsp алгоритм V проверяющей стороны выполняет следующую процедуру верификации с использованием принятого ответа Rsp.

Если Ch=0, алгоритм V проверяющей стороны проверяет, выполняется ли равенство c₁=Н(r₀-t₁, F(r₀)-e₁). Кроме того, алгоритм V проверяющей стороны проверяет, выполняется ли равенство c₂=H(t₁, e₁). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

Если Ch=1, алгоритм V проверяющей стороны проверяет, выполняется ли равенство с₀=H(r₁, G(t₀, r₁)+e₀). Кроме того, алгоритм V проверяющей стороны проверяет, выполняется ли равенство c₁=H(t₀, e₀). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

Если Ch=2, алгоритм V проверяющей стороны проверяет, выполняется ли равенство с₀=H(r₁, y-F(r₁)-G(t₁, r₁)-e₁). Кроме того, алгоритм V проверяющей стороны проверяет, выполняется ли равенство с₂=H(t₁, e₁). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

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

2-2: Пример структуры параллелизованного алгоритма (Фиг. 5)

Далее, способ параллелизации алгоритма, относящегося к 3-проходной схеме, показанной на Фиг. 4, будет описан со ссылками на Фиг. 5. Однако дальнейшее описание структуры алгоритма Gen генерации ключей будет опущено.

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

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

Операция #1:

Как показано на Фиг. 5, алгоритм Р доказывающей стороны сначала выполняет следующие процессы с (1) по (6) для i=1-N.

Процесс (1): Алгоритм Р доказывающей стороны генерирует векторы r_0i, t_0i, являющиеся элементами множества Kⁿ, и вектор e_0i, являющийся элементом множества K^m.

Процесс (2): Алгоритм Р доказывающей стороны вычисляет r_1i<-s-r_0i. Эти расчеты эквивалентны маскированию секретного ключа s с использованием вектора r_0i. Кроме того алгоритм Р доказывающей стороны вычисляет t_1i<-r_0i+t_0i.

Процесс (3): Алгоритм Р доказывающей стороны вычисляет e_1i<-F(r_0i)-e_0i.

Процесс (4): Алгоритм Р доказывающей стороны вычисляет c_0i<-Н(r_1i, G(r_1i, t_0i)+e_0i).

Процесс (5): Алгоритм Р доказывающей стороны вычисляет c_1i<-H(t_0i, e_0i).

Процесс (6): Алгоритм Р доказывающей стороны вычисляет c_2i<-H(t_1i, e_1i).

Операция #1 (продолжение):

После выполнения описанных выше процессов с (1) по (6) для i=1-N, алгоритм Р доказывающей стороны вычисляет Cmt<-H(c₀₁, с₁₁, с₂₁, …, c_0N, c_1N, c_2N). Хэш-величину Cmt, генерируемую в ходе операции #1, передают алгоритму V проверяющей стороны. Таким путем сообщение (c₀₁, с₁₁, с₂₁, …, c_0N, c_1N, c_2N) преобразуют в хэш-величину, передаваемую алгоритму V проверяющей стороны, тем самым позволяя уменьшить объем обмена информацией в процессе связи.

Операция #2:

После приема хэш-величины Cmt алгоритм V проверяющей стороны выбирает схему верификации для использования из совокупности трех схем верификации для каждого из i=1-N. Например, алгоритм V проверяющей стороны может, для каждого из i=1-N, выбрать числовую величину из совокупности трех цифровых величин {0, 1, 2}, представляющих схемы верификации, и задать выбранную числовую величину в качестве параметра запроса Ch_i. Параметры запросов Ch₁, …, Ch_N передают алгоритму Р доказывающей стороны.

Операция #3:

По получении запросов Ch₁, …, Ch_N алгоритм Р доказывающей стороны генерирует ответы Rsp₁, …, Rsp_N для передачи алгоритму V проверяющей стороны в ответ на каждый из принятых запросов Ch₁, …, Ch_N. Если Ch_i=0, алгоритм Р доказывающей стороны генерирует ответ Rsp_i=(r_0i, t_1i, e_1i, c_0i). Если Ch_i=1, алгоритм Р доказывающей стороны генерирует ответ Rsp_i=(r_1i, t_0i, e_0i, c_2i). Если Ch_i=2, алгоритм Р доказывающей стороны генерирует ответ Rsp_i=(r_1i, t_1i, e_1i, c_1i).

Ответы Rsp₁, …, Rsp_N, генерируемые в ходе операции #3, посылают алгоритму V проверяющей стороны.

Операция #4:

После приема ответов Rsp₁, …, Rsp_N алгоритм V проверяющей стороны выполняет следующие процессы с (1) по (3) для i=1-N с использованием принятых ответов Rsp₁, …, Rsp_N. Здесь алгоритм V проверяющей стороны выполняет процесс (1) для случая Ch_i=0, процесс (2) для случая Ch_i=1 и процесс (3) для случая Ch_i=2.

Процесс (1): Если Ch_i=0, алгоритм V проверяющей стороны выделяет (r_0i, t_1i, e_1i, c_0i) на основе Rsp_i. После этого, алгоритм V проверяющей стороны вычисляет c_1i=Н(r_0i-t_1i, F(r_0i)-e_1i). Кроме того, алгоритм V проверяющей стороны вычисляет c_2i=H(t_1i, e_1i). Затем алгоритм V проверяющей стороны сохраняет (c_0i, c_1i, c_2i).

Процесс (2): Если Ch_i=1, алгоритм V проверяющей стороны выделяет (r_1i, t_0i, e_0i, c_2i) на основе Rsp_i. После этого, алгоритм V проверяющей стороны вычисляет c_0i=Н(r_1i, G(t_0i, r_1i)+e_0i). Кроме того, алгоритм V проверяющей стороны вычисляет c_1i=H(t_0i, e_0i). Затем алгоритм V проверяющей стороны сохраняет (c_0i, c_1i, c_2i).

Процесс (3): Если Ch_i=2, алгоритм V проверяющей стороны выделяет (r_1i, t_1i, e_1i, c_1i) на основе Rsp_i. После этого, алгоритм V проверяющей стороны вычисляет Н(r_1i, y-F(r_1i)-G(t_1i, r_1i)-e_1i). Кроме того, алгоритм V проверяющей стороны вычисляет c_2i=Н(t_1i, e_1i). Затем алгоритм V проверяющей стороны сохраняет (c_0i, c_1i, c_2i).

После выполнения описанных выше процессов с (1) по (3) для i=1-N, алгоритм V проверяющей стороны проверяет, выполняется ли равенство Cmt=H(c₀₁, с₁₁, c₂₁, …, c_0N, c_1N, C_2N). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если процедура верификации закончилась неудачей.

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

2-3: Пример структуры алгоритма на основе кубического многочлена от нескольких переменных

Здесь будет рассмотрен способ построения эффективного алгоритма с использованием кубического многочлена f₁ для кольца R, выраженного следующей формулой (12). Многочлен F=(f₁, …, f_m) от нескольких переменных, выраженный с применением пары кубических многочленов f₁ удовлетворяет следующей формуле (13). Здесь, G_x(x, y) представляет линейный член от х. Кроме того, G_y(x, y) представляет линейный член от y. Когда выражены G_x=(gx₁,…, g_xm) и G_y=(g_y1, …, g_ym), можно вывести параметры g_x1 и g_y1 согласно следующим формуле (14) и формуле (15), соответственно. Здесь, поскольку второй член справа в составе g_x1 также является линейным по одной из переменных x и y, этот второй член справа может содержать g_y1.

Как понятно из приведенных выше формулы (14) и формулы (15), многочлены G_x(x, y) и G_y(x, y) становятся аддитивно гомоморфными по x и y. Таким образом, с использованием этого свойства открытый ключ F(s) разделен путем введения новых переменных r₀, r₁, t₀, u₀ и е₀, как в способе построения эффективного алгоритма с использованием квадратичного многочлена f_i.

Поскольку многочлены G_x и G_y являются аддитивно гомоморфными, взаимосвязи между формулами с (16) по (19) установлены с использованием переменных r₀, r₁, t₀, u₀ и е₀. Следующие формулы с (16) по (19) могут быть разделены на первую часть, воспроизводимую с использованием (r₀, t₀, u₀, е₀), вторую часть, воспроизводимую с использованием (r₀, u₁, e₁), третью часть, воспроизводимую с использованием (r₁, t₀, е₀), и четвертую часть, воспроизводимую с использованием (r₁, t₁, u₁, e₁).

Например, "r₀, t₀", включенные в следующую формулу (17), "u₀", включенный в следующую формулу (18), и "F(r₀), G_y(r₀, u₀), е₀", включенные в следующую формулу (19) являются первой частью. Кроме того, "G_y(r₀, u₁), e1", включенные в следующую формулу (19), являются второй частью. Кроме того, "е₀, G_x(r₀, r₁)", включенные в следующую формулу (16), являются третьей частью. Кроме того, "e₁, F(r₁), G_x(t₁, r₁)", включенные в следующую формулу (16), "t₁", включенный в следующую формулу (17), и "u₁", включенный в следующую формулу (18), составляют четвертую часть.

Другими словами, следующая формула (16) включает третью и четвертую части, следующая формула (17) и следующая формула (18) включают первую и четвертую части и следующая формула (19) включает первую и вторую части. Таким образом, каждая из следующих формул с (16) по (19) включает два вида частей.

Само определение секретного ключа s и взаимосвязь между следующими формулами (16)-(19) обеспечивают, что секретный ключ s невозможно получить, даже если используется какая-либо из групп (r₀, t₀, u₀, е₀), (r₀, u₁, e₁), (r₁, t₀, е₀) и (r₁, t₁, u₁, e₁). Использование этого свойства позволяет, например, построить эффективный алгоритм (далее именуемый - расширенный алгоритм) с использованием кубического многочлена f₁ на кольце R.

Далее будет описан пример структуры конкретного расширенного алгоритма. К работе расширенного алгоритма относятся два базовых момента, а именно - проверяющей стороне направляют сообщение, выраженное одной из следующих формул (20)-(22), и проверяют одну из указанных частей с первой по четвертую. Однако только такая проверка может и не позволить проверить, что параметр "r₁", входящий в состав третьей части, идентичен параметру "r₁", входящему в состав четвертой части. Аналогично, может оказаться невозможно проверить, что параметр "r₀", входящий в состав первой части, идентичен параметру "r₀", входящему в состав второй части, или что параметры "t₀, e₀", входящие в состав первой части, идентичны параметрам "t₀, e₀", входящим в состав третьей части. Кроме того, может оказаться невозможно проверить, что параметры "u₁, e₁", входящие в состав второй части, идентичны параметрам "u₁, e₁", входящим в состав четвертой части. Соответственно, ниже будет приведен пример структуры, позволяющей осуществить такую проверку.

2-3-1: Базовая структура (Фиг. 7)

Далее, пример конфигурации расширенного алгоритма, относящегося к 3-проходной схеме, будет рассмотрен со ссылками на Фиг. 6. Однако дополнительное описание структуры алгоритма Gen генерации ключей будет опущено.

Операция #1:

Как показано на Фиг. 6, алгоритм Р доказывающей стороны случайным образом генерирует векторы r₀, t₀, u₀, являющиеся элементами множества Kⁿ, и вектор е₀, являющийся элементом множества K^m. После этого алгоритм Р доказывающей стороны вычисляет r₁<-s-r₀. Эти расчеты эквивалентны маскированию секретного ключа s с использованием вектора го. После этого алгоритм Р доказывающей стороны вычисляет t₁<-r₀+t₀. После этого алгоритм Р доказывающей стороны вычисляет u₁<-r₁+u₀. После этого алгоритм Р доказывающей стороны вычисляет e₁<-F(r₀)-е₀.

Операция #1 (продолжение):

После этого алгоритм Р доказывающей стороны вычисляет c₀<-H(r₁, G_x(t₀, r₁)+е₀). После этого алгоритм Р доказывающей стороны вычисляет c₁<-Н(r₀-t₀, u₀). После этого алгоритм Р доказывающей стороны вычисляет с₂<-Н(r₀, e₁-G_y(r₀, u₁)). После этого алгоритм Р доказывающей стороны вычисляет c₃<-H(t₀, е₀). После этого алгоритм Р доказывающей стороны вычисляет c₄<-H(u₁, e₁). Сообщения (с₀, c₁, c₂, c₃, c₄), генерируемые в ходе операции #1 посылают алгоритму V проверяющей стороны.

Операция #2:

После приема сообщений (с₀, c₁, c₂, с₃, c₄) алгоритм V проверяющей стороны выбирает, какую схему использовать, из совокупности четырех схем верификации. Например, алгоритм V проверяющей стороны может выбрать числовую величину из совокупности четырех числовых величин {0, 1, 2, 3}, представляющих схемы верификации, и задает выбранную числовую величину в качестве параметра Запрос Ch. Этот запрос Ch передают алгоритму Р доказывающей стороны.

Операция #3:

По получении запроса Ch алгоритм Р доказывающей стороны генерирует ответ Rsp для передачи алгоритму V проверяющей стороны в ответ на принятый запрос Ch. Если Ch=0, алгоритм Р доказывающей стороны генерирует ответ Rsp=(r₀, t₀, u₀, е₀). Если Ch=1, алгоритм Р доказывающей стороны генерирует ответ Rsp=(r₀, u₁, e₁). Если Ch=2, алгоритм Р доказывающей стороны генерирует ответ Rsp=(r₁, t₀, е₀). Если Ch=3, алгоритм Р доказывающей стороны генерирует ответ Rsp=(r₁, t₁, u₁, e₁). Ответ Rsp, генерируемый в ходе операции #3, посылают алгоритму V проверяющей стороны.

Операция #4:

После приема ответа Rsp алгоритм V проверяющей стороны выполняет следующую процедуру верификации с использованием принятого ответа Rsp.

Если Ch=0, алгоритм V проверяющей стороны проверяет, выполняется ли равенство c₁=H(r₀-t₀, u₀). После этого, алгоритм V проверяющей стороны проверяет, выполняется ли равенство c₂=H(r₀, F(r₀)+G_y(r₀, u₀)-е₀). После этого, алгоритм V проверяющей стороны проверяет, выполняется ли равенство с₃=H(t₀, е₀). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

Если Ch=1, алгоритм V проверяющей стороны проверяет, выполняется ли равенство с₂=H(r₀, e₁-G_y(r₀, u₁)). После этого, алгоритм V проверяющей стороны проверяет, выполняется ли равенство c₄=H(u₁, e₁). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

Если Ch=2, алгоритм V проверяющей стороны проверяет, выполняется ли равенство с₀=H(r₁, e₀-G_x(t₀, r₁)). После этого, алгоритм V проверяющей стороны проверяет, выполняется ли равенство с₃=H(t₀, e₀). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

Если Ch=3, алгоритм V проверяющей стороны проверяет, выполняется ли равенство с₀=H(r₁, y-F(r₁)-e₁-G_x(t₁, r₁)). После этого, алгоритм V проверяющей стороны проверяет, выполняется ли равенство c₁=H(t₁, r₁, u₁). После этого, алгоритм V проверяющей стороны проверяет, выполняется ли равенство c₄=H(u₁, e₁). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

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

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

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

В случае 3-проходной схемы вероятность ложной верификации составляет 2/3 на каждый цикл выполнения протокола взаимодействия. Однако в случае 5-проходной схемы вероятность ложной верификации составляет 1/2+1/q на каждый цикл выполнения протокола взаимодействия. Здесь q обозначает порядок кольца, которое нужно использовать. Соответственно, когда порядок кольца достаточно велик, вероятность ложной верификации на один цикл 5-проходной схемы можно уменьшить, и, таким образом, вероятность ложной верификации может быть значительно уменьшена при выполнении протокола взаимодействия небольшое число раз.

Например, если нужно, чтобы вероятность ложной верификации была не больше 1/2ⁿ, протокол взаимодействия в 3-проходной схеме нужно выполнить не меньше n/(log3-1)=1.701n раз. С другой стороны, если нужно, чтобы вероятность ложной верификации была не больше 1/2ⁿ, протокол взаимодействия в 5-проходной схеме нужно выполнить не меньше n/(1-log(1+1/q)) раз. Соответственно, когда q=24, объем информации связи, необходимый для обеспечения одного и того же уровня защищенности, в 5-проходной схеме меньше, чем в 3-проходной схеме.

3-1: Пример конкретной структуры алгоритма (Фиг. 7)

Сначала, пример конкретной структуры алгоритма, относящейся к 5-проходной схеме, будет рассмотрен со ссылками на Фиг. 7. Фиг. 7 представляет пояснительную схему для описания конкретной структуры алгоритма, относящейся к 5-проходной схеме. Здесь будет описан случай использования пары квадратичных многочленов (f₁(x), …, f_m(x)), как части открытого ключа pk. Здесь предполагается, что квадратичный многочлен f_i(x) представлен приведенной выше формулой (6). Кроме того, вектор (x₁, …, x_n) обозначен x, а пара квадратичных многочленов (f₁(x), …, f_m(x)) от нескольких переменных обозначены как многочлены F(x) от нескольких переменных.

Как в эффективных алгоритмах, относящихся к 3-проходной схеме, два вектора, а именно вектор t₀, являющийся элементом множества Kⁿ, и вектор е₀, являющийся элементом множества K^m, используют для представления многочлена F₁(x) от нескольких переменных, служащего для маскирования многочленов F(x+r₀) от нескольких переменных, в виде F₁(x)=G(x, t₀)+е₀. При использовании этих формул можно для многочлена F(x+r₀) от нескольких переменных получить соотношение, выраженное следующей формулой (23).

По этой причине, когда t₁=Ch_A·r₀+t₀, e₁=Ch_A·F(r₀)+е₀, многочлен F₂(x)=Ch_A·F(x+r₀)+F₁(x) от нескольких переменных после маскирования также может быть выражен двумя векторами, а именно вектором t₁, который является элементом множества Kⁿ, и вектором e₁, который является элементом множества K^m. По этой причине, когда задан многочлен F₁(x)=G(x, t₀)+е₀, многочлены F₁ и F₂ могут быть выражены с использованием вектора из множества Kⁿ и вектора из множества K^m, и, следовательно, можно реализовать эффективный алгоритм, которому для связи необходим лишь небольшой объем данных.

Кроме того, из многочлена F₂ (или F₁) совсем нет утечки информации относительно r₀. Например, даже если даны e₁ и t₁ (или е₀ и t₀), информация относительно r₀ остается совсем неизвестной до тех пор, пока неизвестны е₀ и t₀ (или e₁ и t₁). Соответственно, обеспечивается нулевое разглашение. Далее будут описаны алгоритмы, относящиеся к классу 5-проходных алгоритмов и построенные на основе изложенной выше логики. Алгоритм по 5-проходной схеме, который будет описан здесь, построен из алгоритма Gen генерации ключей, алгоритма Р доказывающей стороны и алгоритма V проверяющей стороны.

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

Алгоритм Gen генерации ключей формирует многочлены f₁(x₁, …, x_n), …, f_m(x₁, …, x_n) от нескольких переменных, определенные в кольце k и вектор s=(s₁, …, s_n), являющийся элементом множества Kⁿ. Далее алгоритм Gen генерации ключей вычисляет y=(y1, …, y_m)<-(f₁(s), …, f_m(s)). Кроме того, алгоритм Gen генерации ключей задает (f₁ …, f_m, y) в открытом ключе pk и задает s в качестве секретного ключа. В последующем, вектор (x₁, …, x_n) обозначен x, а пара многочленов (f₁(x), …, f_m(x)) от нескольких переменных обозначена как F(x).

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

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

Операция #1:

Как показано на Фиг. 7, алгоритм Р доказывающей стороны случайным образом генерирует вектор r₀, являющийся элементом множества Kⁿ, вектор t₀, являющийся элементом множества Kⁿ, и вектор е₀, являющийся элементом множества K^m. После этого алгоритм Р доказывающей стороны вычисляет r₁<-s-r₀. Эти расчеты эквивалентны маскированию секретного ключа s с использованием вектора r₀. После этого алгоритм Р доказывающей стороны вычисляет хэш-величину со для векторов r₀, t₀, е₀. Иными словами, алгоритм Р доказывающей стороны вычисляет с₀<-H(r₀, t₀, е₀). После этого алгоритм Р доказывающей стороны вычисляет G(t₀, r₁)+е₀ и хэш-величину c₁ от r₁. Иными словами, алгоритм Р доказывающей стороны вычисляет с₀<-H(r₁, G(t₀, r₁)+е₀). Сообщения (с₀, c₁), генерируемые в ходе операции #1, посылают алгоритму V проверяющей стороны.

Операция #2:

После приема сообщений (с₀, c₁), алгоритм V проверяющей стороны случайным образом выбирает одно число Ch_A из совокупности q колец K и передает выбранное число Ch_A алгоритму Р доказывающей стороны.

Операция #3:

После приема числа Ch_A, алгоритм Р доказывающей стороны вычисляет t₁<-Ch_A·r₀-t₀. Кроме того, алгоритм Р доказывающей стороны вычисляет e₁<-Ch_A·F(r₀)-е₀. Алгоритм Р доказывающей стороны передает t₁ и e₁ алгоритму V проверяющей стороны.

Операция #4:

После приема t₁ и e₁ алгоритм V проверяющей стороны выбирает, какую схему верификации использовать, из совокупности двух схем верификации. Например, алгоритм V проверяющей стороны может выбрать числовую величину из совокупности двух числовых величин {0, 1}, представляющих схемы верификации, и задает выбранную числовую величину в качестве параметра запроса Ch. Этот запрос Ch_B передают алгоритму Р доказывающей стороны.

Операция #5:

По получении запроса Ch_B алгоритм Р доказывающей стороны генерирует ответы Rsp для передачи алгоритму V проверяющей стороны в ответ на принятый запрос Ch_B. Если Ch_B=0, алгоритм Р доказывающей стороны генерирует ответ Rsp=r₀. Если Ch_B=1, алгоритм Р доказывающей стороны генерирует ответ Rsp=r₁. Ответ Rsp, генерируемый в ходе операции #5, посылают алгоритму V проверяющей стороны.

Операция #6:

После приема ответа Rsp алгоритм V проверяющей стороны выполняет следующую процедуру верификации с использованием принятого ответа Rsp.

Если Ch_B=0, алгоритм V проверяющей стороны выполняет r₀<-Rsp. Затем, алгоритм V проверяющей стороны проверяет, выполняется ли равенство с₀=Н(r₀, Ch_A·r₀-t₁, Ch_A·F(r₀)-e₁). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

Если Ch_B=1, алгоритм V проверяющей стороны выполняет r₁<-Rsp. Затем алгоритм V проверяющей стороны проверяет, выполняется ли равенство c₁=H₁(r₁, Ch_A·(y-F(r₁)-G(t₁, r₁)-e₁)). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

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

3-2: Пример структуры параллелизованного алгоритма (Фиг. 8)

Далее, способ параллелизации алгоритма, относящегося к 5-проходной схеме, показанной на Фиг. 7, будет описан со ссылками на Фиг. 8. Однако дальнейшее описание структуры алгоритма Gen генерации ключей будет опущено.

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

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

Операция #1:

Как показано на Фиг. 8, алгоритм Р доказывающей стороны сначала выполняет следующие процессы с (1) по (4) для i=1-N.

Процесс (1): Алгоритм Р доказывающей стороны генерирует векторы r_0i, t_0i, являющиеся элементами множества Kⁿ, и вектор e_0i, являющийся элементом множества K^m.

Процесс (2): Алгоритм Р доказывающей стороны вычисляет r_1i<-s-r_0i. Эти расчеты эквивалентны маскированию секретного ключа s с использованием вектора r_0i.

Процесс (3): Алгоритм Р доказывающей стороны вычисляет c_0i<-Н(r_0i, t_0i, e_0i).

Процесс (4): Алгоритм Р доказывающей стороны вычисляет c_1i<-Н(r_1i, G(t_0i, r_1i)+e_0i).

После выполнения описанных выше процессов с (1) по (4) для i=1-N, алгоритм Р доказывающей стороны вычисляет хэш-величину Cmt<-Н(с₀₁, с₁₁, …, c_0N, c_1N). Хэш-величину Cmt, генерируемую в ходе операции #1, посылают алгоритму V проверяющей стороны.

Операция #2:

После приема хэш-величины Cmt, алгоритм V проверяющей стороны случайным образом выбирает одно число Ch_Ai из совокупности q колец K для i=1-N и передает выбранное число Ch_Ai (i=1-N) алгоритму Р доказывающей стороны.

Операция #3:

После приема числа Ch_Ai(i=1-N), алгоритм Р доказывающей стороны вычисляет t_1i<-Ch_Ai·r_0i-t_0i для i=1-N. Кроме того, алгоритм Р доказывающей стороны вычисляет e_1i<-Ch_Ai·F(r_0i)-e_0i для i=1-N. Далее, алгоритм Р доказывающей стороны вычисляет хэш-величины d<-H(t₀₁₁, е₁₁, …, t_1N, e_1N). Затем, алгоритм Р доказывающей стороны передает полученную хэш-величину алгоритму V проверяющей величины.

Операция #4:

После приема хэш-величины алгоритм V проверяющей стороны выбирает схему верификации для использования из совокупности двух схем верификации для каждого из i=1-N. Например, алгоритм V проверяющей стороны может, для каждого из i=1-N, выбрать числовую величину из совокупности двух цифровых величин {0, 1}, представляющих схемы верификации, и задать выбранную числовую величину в качестве параметра запроса Ch_Bi. Этот запрос Ch_Bi(i=1-N) передают алгоритму Р доказывающей стороны.

Операция #5:

По получении запроса Ch_Bi (i=1-N) алгоритм Р доказывающей стороны генерирует ответ Rsp_i для передачи алгоритму V проверяющей стороны в ответ на принятый запрос Ch_Bi для i=1-N. Если Ch_Bi=0, алгоритм Р доказывающей стороны генерирует ответ Rsp_i=(r_0i, c_1i). Если Ch_Bi=1, алгоритм Р доказывающей стороны генерирует ответ Rsp_i=(r_0i, t_0i, e_0i, c₁t_1i, e_1i, c_0i). Ответ Rsp_i (i=1-N), генерируемый в ходе операции #5, посылают алгоритму V проверяющей стороны.

Операция #6:

После приема ответов Rsp_i (i=1-N) алгоритм V проверяющей стороны выполняет следующие процессы (1) и (2) с использованием принятого ответа Rsp_i (i=1-N).

Процесс (1): Если Ch_Bi=0, алгоритм V проверяющей стороны выполняет (r_0i, t_0i, e_0i, c_1i)<-Rsp_i. Алгоритм V проверяющей стороны вычисляет c_0i=H(r_0i, t_0i, e_0i). Далее, алгоритм V проверяющей стороны вычисляет t_1i<-Ch_Ai·r_0i+t_0i, и e_1i<-Ch_Ai·F(r_0i)-e_0i. Затем алгоритм V проверяющей стороны сохраняет (c_0i, c_1i, t_1i, e_1i).

Процесс (2): Если Ch_Bi=1, алгоритм V проверяющей стороны выполняет (r_1i, t_1i, e_1i, c_0i)<-Rsp_i. После этого, алгоритм V проверяющей стороны вычисляет c_1i=Н(r_1i-Ch_Ai·(y-F(r_1i))-G(t_1i, r_1i)-e_1i). Затем алгоритм V проверяющей стороны сохраняет (c_0i, c_1i, t_1i, e_1i).

После вьшолнения процессов с (1) по (2) для i=1-N, алгоритм V проверяющей стороны проверяет, выполняется ли равенство Cmt=H(c_0i, с₁₁, …, c_0N, c_1N). После этого, алгоритм V проверяющей стороны проверяет, выполняется ли равенство d=H(t₁₁, е₁₁, …, t_1N, e_1N). Затем, алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

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

3-3: Пример структуры алгоритма на основе кубического многочлена от нескольких переменных

Здесь будет рассмотрен способ построения эффективного алгоритма с использованием кубического многочлена f₁ для кольца R, как в случае 3-проходной схемы. Когда кубический многочлен f₁ выражен, как в приведенной выше формуле (12), из формулы (14) и формулы (15) можно понять тот факт, что G_x(x, y) и G_y(x, y) становятся линейными по x и y.

Таким образом, используя описанное выше свойство, открытый ключ F(s) разделен на член, кратный Ch_A, путем введения новых переменных r₀, r₁, t₀, u₀ и е₀. Поскольку многочлены G_x и G_y являются линейными по x и y, взаимосвязи между формулами с (24) по (27) установлены с использованием переменных r₀, r₁, t₀, u₀ и е₀. Следующие формулы с (24) по (27) могут быть разбиты на первую часть, зависящую от Ch_A, и вторую часть, не зависящую от Ch_A. Здесь первую часть можно воспроизвести с использованием (r₁, t₁, u₁, e₁). Вторую часть можно воспроизвести с использованием (r₀, t₁, u₁, e₁).

Например, "е₀, G_x(t₀, r₁)", включенные в следующую формулу (32), "t₀", включенный в следующую формулу (33), "u₀" включенный в следующую формулу (26), и "е₀, G_y(r₀, u₀)", включенные в следующую формулу (27) являются первыми частями. С другой стороны, "Ch_Ai·F(r₀+r₁), e₁, Ch_A·F(r₁), G_x(t₁, r₁)", включенные в следующую формулу (24), "Ch_A·r₀, t₁", включенные в следующую формулу (25), "Ch_A·r₁, u₁", включенные в следующую формулу (34), и "Ch_A·F(r₀), G_y(r₀, u₁), e₁", включенные в следующую формулу (27), являются вторыми частями.

Само определение секретного ключа s и взаимосвязь между следующими формулами (24)-(27) обеспечивают, что секретный ключ s невозможно получить, даже если используется какая-либо из групп (r₁, t₁, u₁, e₁) или (r₀, t₁, u₁, e₁). Использование этого свойства позволяет, например, построить эффективный алгоритм (далее именуемый - расширенный алгоритм) с использованием кубического многочлена f₁ на кольце R.

Далее будет описан пример структуры конкретного расширенного алгоритма. К работе расширенного алгоритма относятся два базовых момента, а именно - проверяющей стороне направляют сообщение, выраженное одной из следующих формул (28)-(29), и проверяют часть, зависящую от параметра от Ch_A, для величины этого параметра Ch_A, выбранной проверяющей стороной. Здесь, поскольку «векторы r₀ и r₁, используемые в момент генерации сообщения, нельзя в момент верификации заменить другими векторами r₀ и r₁», ниже будет приведен пример структуры, в которую добавлена верификация по r₀ и r₁.

Далее, базовая конфигурация расширенного алгоритма, относящегося к 5-проходной схеме, будет рассмотрена со ссылками на Фиг. 9. Однако дальнейшее описание структуры алгоритма Gen генерации ключей будет опущено.

Операция #1:

Как показано на Фиг. 9, алгоритм Р доказывающей стороны случайным образом генерирует векторы r₀, t₀, u₀, являющиеся элементами множества Kⁿ, и вектор е₀, являющийся элементом множества K^m. После этого алгоритм Р доказывающей стороны вычисляет r₁<-s-r₀. Эти расчеты эквивалентны маскированию секретного ключа s с использованием вектора r₀. После этого алгоритм Р доказывающей стороны вычисляет c₀<-H(r₀, t₀, е₀-G_y(r₀, u₀)). После этого алгоритм Р доказывающей стороны вычисляет c₁<-H(r₁, u₀, G_x(t₀, r₁)+е₀). Сообщения (с₀, c₁), генерируемые в ходе операции #1, посылают алгоритму V проверяющей стороны.

Операция #2:

После приема сообщений (с₀, c₁) алгоритм V проверяющей стороны случайным образом выбирает число Ch_A. Это число Ch_A передают алгоритму Р доказывающей стороны.

Операция #3:

После приема числа Ch_A, алгоритм Р доказывающей стороны вычисляет t₁<-Ch_A·r₀-t₀. После этого, алгоритм Р доказывающей стороны вычисляет u₁<-Ch_A·r₁-u₀. После этого, алгоритм Р доказывающей стороны вычисляет e₁<-Ch_A·F(r₀)+Ch_A·G_y(r₀, r1)-е₀. Затем, (t₁, u₁, e₁), генерируемые в ходе операции #3, посылают алгоритму V проверяющей стороны.

Операция #4:

После приема (t₁, u₁, e₁) алгоритм V проверяющей стороны выбирает, какую схему верификации использовать, из совокупности двух схем верификации. Например, алгоритм V проверяющей стороны может выбрать числовую величину из совокупности двух числовых величин {0, 1}, представляющих схемы верификации, и задает выбранную числовую величину в качестве параметра запроса Ch_B. Этот запрос Ch_B передают алгоритму Р доказывающей стороны.

Операция #5:

По получении запроса Ch_B алгоритм Р доказывающей стороны генерирует ответ Rsp для передачи алгоритму V проверяющей стороны в ответ на принятый запрос Ch_B. Если Ch_B=0, алгоритм Р доказывающей стороны генерирует ответ Rsp=r₀. Если Ch_B=1, алгоритм Р доказывающей стороны генерирует ответ Rsp=r₁. Ответ Rsp, генерируемый в ходе операции #5, посылают алгоритму V проверяющей стороны.

Операция #6:

После приема ответа Rsp алгоритм V проверяющей стороны выполняет следующую процедуру верификации с использованием принятого ответа Rsp.

Если Ch_B=0, алгоритм V проверяющей стороны проверяет, выполняется ли равенство с₀=Н(r₀, Ch_A·r₀-t₁, Ch_A·F(r₀)+G_y(r₀, u₁)-e₁). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

Если Ch_B=1, алгоритм V проверяющей стороны проверяет, выполняется ли равенство c₁=H(r₁, Ch_A·r₁-u₁, Ch_A·(y-F(r₁))-G_x(t₁, r₁)-e₁). Алгоритм V проверяющей стороны передает на выход величину 1, чтобы указать на успех аутентификации, если все эти процедуры верификации завершились успешно, и передает на выход величину 0, чтобы указать на неудачу аутентификации, если какая-либо процедура верификации закончилась неудачей.

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

4: Модификация алгоритма цифровой подписи

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

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

4-1: Модификация 3-проходного алгоритма аутентификации с открытым ключом и преобразование его в алгоритм цифровой подписи (Фиг. 10)

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

На Фиг. 10 показан эффективный алгоритм (например, см. Фиг. 5), относящийся к 3-проходной схеме с интерактивностью три раза и четырьмя операциями, т.е. с операции #1 по операцию #4.

Операция #1 содержит процесс (1) генерации a_i=(r_0i, t_0i, e_0i, r_1i, t_1i, e_1i, c_0i, c_1i, c_2i) и процесс (2) вычисления Cmt<-H(c_0i, с₁₁, c₂₁, …, c_0N, c_1N, c_2N). Параметр Cmt, генерируемые алгоритмом Р доказывающей стороны в ходе операции #1, посылают алгоритму V проверяющей стороны.

Операция #2 содержит процедуру выбора параметра Ch₁, …, Ch_N. Параметр Ch₁, …, Ch_N, выбранный в ходе операции #2 посредством алгоритма V проверяющей стороны, посылают алгоритму Р доказывающей стороны.

Операция #3 содержит процедуру генерации ответов Rsp₁, …, Rsp_N с использованием Ch₁, …, Ch_N и a₁ …, a_N. Этот процесс выражен в виде Rsp_i<-Select (Ch_i, a_i). Ответы Rsp₁, …, Rsp_N, генерируемые алгоритмом Р доказывающей стороны в ходе операции #3, посылают алгоритму V проверяющей стороны.

Операция #4 содержит процесс (1) воспроизведения c₀₁, с₁₁, с₂₁, …, c_0N, c_1N, c_2N с использованием Ch₁, …, Ch_N и Rsp₁, …, Rsp_N и процесс (2) верификации Cmt=H(c₀₁, с₁₁, c₂₁, …, c_0N, c_1N, c_2N) с использованием воспроизведенных c₀₁, c₁₁, c₂₁, …, c_0N, c_1N, c_2N.

Алгоритм аутентификации с открытым ключом, представленный в виде операций с операции #1 по операцию #4 модифицирован для преобразования в алгоритм Sig генерации подписи и алгоритм Ver верификации подписи, изображенные на Фиг. 10.

(Алгоритм Sig генерации подписи)

Сначала будет описана алгоритма Sig генерации подписи. Алгоритм Sig генерации подписи содержит процессы с (1) по (5),

Процесс (1): Алгоритм Sig генерации подписи генерирует a_i=(r_0i, t_0i, e_0i, r_1i, t_1i, e_1i, c_0i, c_1i, c_2i).

Процесс (2): Алгоритм Sig генерации подписи вычисляет Cmt<-H(c₀₁, с₁₁, c₂₁, …, c_0N, c_1N, c_2N).

Процесс (3): Алгоритм Sig генерации подписи вычисляет (Ch₁, …, Ch_N)<-Н(М, Cmt). Здесь М обозначает документ, к которому прикрепляют подпись.

Процесс (4): Алгоритм Sig генерации подписи вычисляет Rsp_i<-Select (Ch_i, a_i).

Процесс (5): Алгоритм Sig генерации подписи задает (Cmt, Rsp₁, …, Rsp_N) в качестве подписи.

Алгоритм Ver верификации подписи

Далее будет описана структура алгоритма Ver верификации подписи. Алгоритм Ver верификации подписи содержит следующие процессы с (1) по (3),

Процесс (1): Алгоритм Ver верификации подписи вычисляет (Ch₁, …, ch_N)<-Н(М, Cmt).

Процесс (2): Алгоритм Ver верификации подписи генерирует с₀₁, с₁₁, с₂₁, …, c_0N, c_1N, c_2N с использованием Ch₁, …, Ch_N и Rsp₁, …, Rsp_N.

Процесс (3): Алгоритм Ver верификации подписи проверяет Cmt=Н(с₀₁, с₁₁, c₂₁, …, c_0N, c_1N, c_2N) с использованием воспроизведенных c₀₁, с₁₁, с₂₁, …, c_0N, c_1N, c_2N.

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

4-2: Модификация 5-проходного алгоритма аутентификации с открытым ключом и преобразование его в алгоритм цифровой подписи (Фиг. 11)

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

На Фиг. 11 показан эффективный алгоритм (например, см. Фиг. 8), относящийся к 5-проходной схеме с интерактивностью пять раз и шестью операциями, т.е. с операции #1 по операцию #6.

Операция #1 содержит процесс (1) генерации a_i=(r_0i, t_0i, e_0i, r_1i, t_1i, e_1i, c_0i, c_1i) для i=1-N и процесс (2) вычисления Cmt<-H(c₀₁, с₁₁, …, c_0N, c_1N). Параметр Cmt, генерируемый алгоритмом Р доказывающей стороны в ходе операции #1, посылают алгоритму V проверяющей стороны.

Операция #2 содержит процедуру выбора параметра Ch_A1, …, Ch_AN. Параметр Ch_A1, …, Ch_AN, выбранный в ходе операции #2 посредством алгоритма V проверяющей стороны, посылают алгоритму Р доказывающей стороны.

Операция #3 содержит процедуру генерации b_i=(t_1i, e_1i) и процедуру генерации d=Н (t₁₁, е₁₁, …, t_1N, e_1N) для i=1-N. Здесь параметры d, генерируемые алгоритмом Р доказывающей стороны в ходе операции #3, посылают алгоритму V проверяющей стороны.

Операция #4 содержит процедуру выбора параметра Ch_B1, …, Ch_BN. Параметры Ch_B1, …, Ch_BN, выбранные в ходе операции #4 посредством алгоритма V проверяющей стороны, посылают алгоритму Р доказывающей стороны.

Операция #5 содержит процедуру генерации ответов Rsp₁, …, Rsp_N с использованием Ch_B1, …, Ch_BN, a₁, …, a_N, b₁, …, b_N. Этот процесс выражен в виде Rsp_i<-Select (Ch_Bi, a_i, b_i). Ответы Rsp₁, …, Rsp_N, генерируемые алгоритмом Р доказывающей стороны в ходе операции #5, посылают алгоритму V проверяющей стороны.

Операция #6 содержит процесс воспроизведения с₀₁, с₁₁, …, c_0N, c_1N, t₁₁, е₁₁, …, t_1N, e_1N с использованием Ch_A1, …, Ch_AN, Ch_B1, …, Ch_BN, Rsp₁, …, Rsp_N, процесс верификации Cmt=H(c₀₁, с₁₁, …, c_0N, c_1N) с использованием воспроизведенных c₀₁, c₁₁, …, c_0N, c_1N и процесс верификации d=H(t₁₁, е₁₁, …, t_1N, e_1N).

Алгоритм аутентификации с открытым ключом, представленный в виде операций с операции #1 по операцию #6 модифицирован для преобразования в алгоритм Sig генерации подписи и алгоритм Ver верификации подписи, изображенные на Фиг. 11.

(Алгоритм Sig генерации подписи)

Сначала будет описана структура алгоритма Sig генерации подписи. Алгоритм Sig генерации подписи содержит процессы с (1) по (7).

Процесс (1): Алгоритм Sig генерации подписи генерирует a_i=(r_0i, t_0i, e_0i, r_1i, t_1i, e_1i, c_0i, c_1i).

Процесс (2): Алгоритм Sig генерации подписи вычисляет Cmt<-H(c₀₁, с₁₁, …, c_0N, c_1N).

Процесс (3): Алгоритм Sig генерации подписи вычисляет (Ch_A1, …, Ch_AN)<-Н(М, Cmt). Здесь М обозначает документ, к которому прикрепляют подпись.

Процесс (4): Алгоритм Sig генерации подписи осуществляет генерацию b_i=(t_1i, e_1i) для i=1-N. Далее, алгоритм Sig генерации подписи вычисляет d=Н (t₁₁, е₁₁, …, t_1N, e_1N).

Процесс (5): Алгоритм Sig генерации подписи вычисляет (Ch_B1, …, Ch_BN)<-H(M, Cmt, Ch_A1, …, Ch_AN, d). Кроме того можно осуществить модификацию для преобразования в (Ch_B1, …, Ch_BN)<-H(Ch_A1, …, Ch_AN, d).

Процесс (6): Алгоритм Sig генерации подписи вычисляет Rsp_i<-Select (Ch_Bi, a_i, b_i).

Процесс (7): Алгоритм Sig генерации подписи задает (Cmt, d, Rsp₁, …, Rsp_N) в качестве цифровой подписи.

Алгоритм Ver верификации подписи

Далее будет описана структура алгоритма Ver верификации подписи. Алгоритм Ver верификации подписи содержит следующие процессы с (1) по (4).

Процесс (1): Алгоритм Ver верификации подписи вычисляет (Ch_A1, …, Ch_AN)=Н(М, Cmt).

Процесс (2): Алгоритм Ver верификации подписи вычисляет (Ch_B1, …, Ch_BN)=H(M, Cmt, Ch_A1, …, Ch_AN, d). Когда осуществляется модификация для преобразования в (Ch_B1, …, Ch_BN)=H(Ch_A1, …, Ch_AN, d) в ходе выполнения процесса (5), осуществляемого алгоритмом Ver верификации подписи, этот алгоритм Ver верификации подписи вычисляет (Ch_B1, …, Ch_BN)=H(Ch_A1, …, Ch_AN, d).

Процесс (3): Алгоритм Ver верификации подписи генерирует t₁₁, е₁₁, …, t_1N, e_1N, c₀₁, с₁₁, …, c_0N, c_1N с использованием Ch_A1, …, Ch_AN, Ch_B1, …, Ch_BN, Rsp₁, …, Rsp_N.

Процесс (4): Алгоритм Ver верификации подписи проверяет Cmt=H(c₀₁, с₁₁, …, c_0N, c_1N) с использованием воспроизведенных c₀₁, с₁₁, …, c_0N, c_1N, и d=Н (t₁₁, е₁₁, …, t_1N, e_1N).

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

5: Способ уменьшения объема памяти, необходимого для верификации подписи

В частности, согласно описанному выше алгоритму цифровой подписи процедура верификации подписи выполнялась после того, как алгоритм Ver верификации подписи получит все цифровые подписи. Однако в случае описанного выше алгоритма цифровой подписи объем данных цифровой подписи относительно велик. По этой причине при выполнении аутентификации с использованием такого устройства, как радио идентификационное устройство (Radio Frequency IDentification (RFID)), имеющее память небольшого объема, необходимо всегда обращать внимание на свободный объем памяти, коэффициент использования памяти в процессе аутентификации или другой подобный показатель. Кроме того, при использовании устройства, обладающего недостаточно большой памятью, предполагается, что в некоторых случаях аутентификация не производится. Соответственно, авторы настоящего изобретения разработали способ уменьшения объема памяти, необходимого для верификации подписи.

5-1: Структура хэш-функции (Фиг. 12)

Сначала авторы настоящего изобретения сосредоточились на структуре хэш-функции. Во многих случаях, хэш-функция имеет структуру, группирующую входные данные в блоки и обрабатывающую эти данные в единицах блоков. Например, в случае SHA-1, хэш-функция имеет структуру, показанную на Фиг. 12. Хэш-функция, показанная на Фиг. 12, генерирует хэш-величину путем группирования заполненных входных данных М в Z блоков m₁, …, m_Z и работает с блоками m_j с применением заданной функции CF вместе с начальной величиной IV или промежуточной величиной CV_j, последовательно увеличивая индекс j. Таким образом, когда получена промежуточная величина CV_j, ранее использованные блоки становятся ненужными. Соответственно, на основе этих характеристик была разработана структура (далее именуемая способ уменьшения требований к памяти) для уменьшения объема памяти, требуемого для реализации алгоритма. Далее будет рассмотрен способ применения этой структуры к описанному выше алгоритму цифровой подписи.

5-2: Пример применения 3-проходного алгоритма цифровой подписи (Фиг. 14)

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

Нормальный способ установки: Фиг. 13

Обычно, как показано на Фиг. 13, алгоритм Ver верификации подписи, относящийся к описанному выше алгоритму цифровой подписи, принимает (Cmt, Rsp₁, …, Rsp_N), входящие в состав цифровой подписи, за один раз (S101). После этого, алгоритм Ver верификации подписи выполняет (Ch₁, …, Ch_N)<-Н(М, cmt) (S102). После этого, алгоритм Ver верификации подписи выполняет (с₀₁, с₁₁, с₂₁, …, c_0N, c_1N, c_2N)<- Reproduce (Ch₁, …, Ch_N; Rsp₁, …, Rsp_N) (S103). После этого, алгоритм Ver верификации подписи проверяет Cmt=H(c₀₁, с₁₁, с₂₁, …, c_0N, c_1N, c_2N) (S104) и завершает последовательность операций, относящихся к верификации подписи.

Способ уменьшения объема памяти: Фиг. 14

В случае нормального способа установки, когда цифровые подписи принимают за один раз, как на этапе S101, изображенном на Фиг. 13, необходимо использовать память для сохранения (Rsp₁, …, Rsp_N) до завершения процедуры этапа S103. Однако, как понятно из структуры алгоритма, показанной на Фиг. 5, для воспроизведения (c_0i, c_1i, c_2i), осуществляемого на этапе S103, не используется никакая информация, кроме (Ch_i; Rsp_i). Кроме того, если рассматривать структуру хэш-функции, показанную на Фиг. 12, понятно, что при вычислении хэш-функции на этапе S104 осуществляют группирование и обработку в единицах блоков. Соответственно, структура, относящаяся к верификации подписи оказывается усовершенствована и преобразована в структуру, показанную на Фиг. 14.

В случае структуры, показанной на Фиг. 14, алгоритм Ver верификации подписи сначала принимает только параметр Cmt, входящий в состав цифровой подписи (S111). После этого, алгоритм Ver верификации подписи выполняет (Ch₁, …, Ch_N)<-H(M, cmt) (S112). После этого, алгоритм Ver верификации подписи последовательно выполняет процедуры этапов c S113 по S115, увеличивая i от i=1 до N.

На этапе S113 алгоритм Ver верификации подписи принимает Rsp_i (S113). После этого, алгоритм Ver верификации подписи выполняет (c_0i, c_1i, c_2i)<- Reproduce (Ch_i; Rsp_i) с использованием принятого Rsp_i (S114). После выполнения процедуры этапа S114 параметры Ch_i и Rsp_i становятся ненужными. Соответственно, алгоритм Ver верификации подписи стирает эти параметры Ch_i и Rsp_i из памяти после выполнения процедуры этапа S114.

После этого, алгоритм Ver верификации подписи выполняет tmp_i<-H_i (tmp_i-1; c_0i, c_1i, c_2i) (этап S115). Кроме того, хэш-функдия H_i представляет собой функцию, передающую на выход промежуточную величину, генерируемую при вычислении до c_0i, c_1i, c_2i посредством хэш-функции H. На практике, поскольку размер входных данных функции Hj отличается в зависимости от выбранной функции, выполняют при необходимости подходящую коррекцию длины входных данных, такую как добавление битов. При использовании функции Hi, хэш-функция Н выражена в виде алгоритма, содержащего процессы с (1) по (3), которые будут описаны ниже. Тогда величина tmp_N является конечной выходной величиной (хэш-величиной) хэш-функции Н. На практике, на конечной стадии выполняют дополнительную операцию заполнения в соответствии со спецификацией хэш-функции.

Процесс (1): tmp₀<- нулевая строка символов

Процесс (2):

для i=1-N

tmp_i<-H_i (tmp_i-1; c_0i, c_1i, c_2i)

end for

Процесс (3): передача tmp_N на выход

После выполнения процедур этапов с S113 по S115 для i=1-N, алгоритм V проверяющей стороны проверяет (S116), выполняется ли равенство Cmt=tmp_N и завершает последовательность процедур, относящихся к верификации плоскости. Как описано выше, алгоритм Ver верификации подписи стирает информацию, которая становится ненужной во время многократного выполнения процедур этапов с S113 по S115. из памяти. По этой причине объем памяти, необходимый для верификации подписи, оказывается уменьшен до минимально возможного уровня. Вследствие этого, описанная выше процедура верификации подписи может быть выполнена даже в устройстве, имеющем память лишь небольшого объема.

5-3: Пример применения 5-проходного алгоритма цифровой подписи (Фиг. 16)

Далее, будет описан способ применения указанного выше подхода для уменьшения необходимого объема памяти к алгоритму цифровой подписи по 5-проходной схеме, изображенному на Фиг. 11.

Нормальный способ установки: Фиг. 15

Обычно, как показано на Фиг. 15, алгоритм Ver верификации подписи, относящийся к описанному выше алгоритму цифровой подписи, принимает (Cmt, d, Rsp₁, …, Rsp_N), входящие в состав цифровой подписи, за один раз (S121). После этого, алгоритм Ver верификации подписи выполняет (Ch_A1, …, Ch_AN)<- Н(М, cmt) (S122). После этого, алгоритм Ver верификации подписи выполняет (Ch_B1, …, Ch_BN)<- Н(М, Cmt, Ch_A1, …, Ch_AN, d) (S123). После этого, алгоритм Ver верификации подписи выполняет (c₀₁, с₁₁, …, c_0N, c_1N, d₁₁, е₁₁, …, d_1N, e_1N)<- Reproduce (Ch_A1, …, Ch_AN, Ch_B1, …, Ch_BN; Rsp₁, …, Rsp_N) (S124). После этого, алгоритм Ver верификации подписи проверяет Cmt=H(c₀₁, с₁₁, …, c_0N, c_1N) и d=H(d₁₁, е₁₁, …, d_1N, e_1N) (S125) и завершает последовательность операций, относящихся к верификации подписи.

Способ уменьшения объема памяти: Фиг. 16

Когда цифровые подписи принимают за один раз, как на этапе S121, изображенном на Фиг. 15, необходимо использовать память для сохранения (Rsp₁, …, Rsp_N) до завершения процедуры этапа S124. Однако, как понятно из структуры алгоритма, показанной на Фиг. 8, для воспроизведения (c_0i, c_1i, d_1i, e_1i), осуществляемого на этапе S124, не используется никакая информация, кроме (Ch_Ai, Ch_Bi; Rsp_i). Кроме того, если рассматривать структуру хэш-функции, показанную на Фиг. 12, понятно, что при вычислении хэш-функции на этапе S125 осуществляют группирование и обработку в единицах блоков. Соответственно, структура, относящаяся к верификации подписи. оказывается усовершенствована и преобразована в структуру, показанную на Фиг. 16.

В случае структуры, показанной на Фиг. 16, алгоритм Ver верификации подписи сначала принимает только параметр Cmt, входящий в состав цифровой подписи (S131). После этого, алгоритм Ver верификации подписи выполняет (Ch_A1, …, Ch_AN)<- Н(М, cmt) (S132).

После этого, алгоритм Ver верификации подписи принимает параметр d (S133). После этого, алгоритм Ver верификации подписи выполняет (Ch_B1, …, Ch_BN)<- Н(М, Cmt, Ch_A1, …, Ch_AN, d) с использованием принятого параметра d (S134). После выполнения процедуры этапа S134 параметр d становится ненужным. Соответственно, алгоритм Ver верификации подписи стирает параметр d из памяти после выполнения процедуры этапа S134. После этого, алгоритм Ver верификации подписи последовательно выполняет процедуры этапов с S135 по S137, увеличивая i от i=1 до N.

На этапе S135 алгоритм Ver верификации подписи принимает Rsp_i (S135). После этого, алгоритм Ver верификации подписи выполняет (c_0i, c_1i, t_1i, e_1i)<- Reproduce (Ch_Ai, Ch_Bi; Rsp_i) с использованием принятого Rsp_i (S136). После выполнения процедуры этапа S133 параметры Ch_Ai, Ch_Bi, и Rsp_i становятся ненужными. Соответственно, алгоритм Ver верификации подписи стирает эти параметры Ch_Ai, Ch_Bi и Rspi из памяти после выполнения процедуры этапа S136.

После этого, алгоритм Ver верификации подписи выполняет tmp_i<- H_i (tmp_i-1; c_0i, c_1i) и tmp_i′<- Hi (tmp_i-1′; t_1i, e_1i) (этап S137). После выполнения процедур этапов с S135 по S137 для i=1-N, алгоритм V проверяющей стороны проверяет (S138), выполняются ли равенства Cmt=tmp_N и d=tmp_N′ и завершает последовательность процедур, относящихся к верификации плоскости. Как описано выше, алгоритм Ver верификации подписи стирает информацию, которая становится ненужной во время многократного выполнения процедур этапов с S135 по S137, из памяти. По этой причине объем памяти, необходимый для верификации подписи, оказывается уменьшен до минимально возможного уровня. Вследствие этого, описанная выше процедура верификации подписи может быть выполнена даже в устройстве, имеющем память лишь небольшого объема.

Выше были описаны способы уменьшения объема памяти, необходимого для верификации подписи.

6: Способ выделения последовательности троичных случайных чисел из последовательности двоичных случайных чисел

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

6-1: Способ #1 выделения (2-битовое группирование) (Фиг. 17)

Сначала, способ (далее именуемый способ #1 выделения) группирования двоичных чисел из М бит по два бита каждое и выделения троичных чисел будет рассмотрен со ссылками на Фиг. 17. Как показано Фиг. 17, когда строку случайных чисел в двоичном представлении группируют по два бита каждое, можно получить М/2 2-битовых двоичных чисел. Например, если "00" соответствует троичному числу "0", "01" соответствует троичному числу "1" и "10" соответствует троичному числу "2", из случайного числа, представленного в двоичном виде в единицах по 2 бит, можно получить строку троичных случайных чисел. Однако 2-битовая величина "11" исключена. Иными словами, способ #1 выделения представляет способ выделения 3¹ элементов, выраженных 1 троичным символом, и 2² элементов, выраженных 2 двоичными символами. Таким образом, вероятность P₁ того, что N или более троичных чисел выделить невозможно представлена следующей формулой (30).

Математическое выражение 16

6-2: Способ #2 выделения (нет группирования) (Фиг. 18)

Затем, способ (далее именуемый способ #2 выделения) выделения случайных чисел из L троичных символов с использованием случайных чисел из М двоичных символов без группирования будет рассмотрен со ссылками на Фиг. 18. Здесь, L максимальное целое число, удовлетворяющее соотношению 3^L≤2^M. Имеется 2^M чисел, которые могут быть выражены посредством М двоичных символов. С другой стороны, имеется только 3^L чисел, которые могут быть выражены посредством L троичных символов. По этой причине, из 2^M чисел, которые могут быть выражены посредством М двоичных символов, 2^M-3^L чисел не используются в качестве случайных чисел в троичном представлении. Таким образом, вероятность P₂ того, что N или более троичных чисел выделить невозможно, представлена следующей формулой (31).

6-3: Способ #3 выделения (k-битовое группирование) (Фиг. 19) Описанный выше способ #1 выделения представляет собой способ группирования строки случайных чисел в двоичном представлении для получения совокупности групп минимального размера. С другой стороны, описанный выше способ #2 выделения представляет собой способ группирования строки случайных чисел в двоичном представлении для получения совокупности групп максимального размера (поскольку рассматривается М-битовое группирование). Как понятно из приведенных выше формул (30) и (31), вероятность того, что N или более троичных чисел будет невозможно выделить, различна в зависимости от длины группирования. Кроме того, когда строку случайных чисел из М двоичных символов группируют в единичные блоки по k бит, как показано на Фиг. 19, вероятность Р₃ того, что N или более троичных чисел выделить невозможно, представлена следующей формулой (32).

Таким образом, вероятность Р₃ того, что N или более троичных чисел выделить невозможно, можно минимизировать, и можно более эффективно выделить строку случайных чисел в троичном представлении. Например, если М=512 и N=140, вероятность Р₃ оказывается минимальной при k=8.

6-3-1: Базовая структура (Фиг. 20)

Здесь порядок процедуры выделения строки случайных чисел, содержащей L троичных символов, из строки случайных чисел, содержащей М двоичных символов, будет рассмотрен со ссылками на Фиг. 20. Как показано на Фиг. 20, сначала генерируют строку случайных чисел из М двоичных символов (S201). После этого, строку случайных чисел из М двоичных символов группируют в единичные блоки по k бит (S202). После этого, выделяют битовую строку, удовлетворяющую условию X_2k≤3^L, из битовых строк X_2k, сгруппированных в единичные блоки по k бит (S203). После этого, выделенную битовую строку передают на выход в троичном представлении (S204) и выполнение последовательности процедур завершается.

6-3-2: Дополнительный способ выделения (Фиг. 21)

Вычисляя длину k группирования, при которой вероятность Р₃, выраженная приведенной выше формулой (15), является минимальной, и, выполняя алгоритм, показанный на Фиг. 20, можно эффективно выделить строку случайных чисел в троичном представлении из строки случайных чисел в двоичном представлении. Однако авторы настоящего изобретения разработали способ выделения строки случайных чисел в троичном представлении более эффективно, сосредоточившись на том факте, что битовая строка, удовлетворяющая соотношению X_2k>3^L, не используется на этапе S204, показанном на Фиг. 20. Этот способ будет описан ниже со ссылками на Фиг. 21.

Этот способ представляет собой способ выделения строки символов в троичном представлении с использованием битовых строк, не выделенных на этапе S204, показанном на Фиг. 20. Как показано на Фиг. 21, сначала выделяют множество битовых строк, не выделенных на этапе S204, показанном на Фиг. 20, и удовлетворяющих соотношению X;k>З¹' (например, когда множество битовых строк выражено как y₁y₂ … y_N, и каждая индивидуальная битовая строка y_i удовлетворяет соотношению 3^L≤y_i<2^k) (S211). После этого, вычитают 3^L из каждой выделенной битовой строки у; и вычисляют множество новых битовых строк (например, когда множество новых битовых строк выражено как z₁z₂…z_N′, и каждая индивидуальная битовая строка z_i=y_i-3^L удовлетворяет соотношению 0≤z_i<2^k-3^L) (S212).

После этого, выделяют битовую строку X, удовлетворяющую условию Х<3^L, из множества новых битовых строк (S213). Здесь, L′ максимальное целое число, удовлетворяющее соотношению 3^L′≤2^k-3^L. После этого, битовую строку, выделенную на этапе S213, передают на выход в троичном представлении (S214) и выполнение последовательности процедур завершается. Применяя этот алгоритм, можно выделить L′ новых троичных чисел с вероятностью 3^L′/(2^k-3^L). Кроме того, рекурсивно используя этот способ, можно выделить больше троичных чисел. Иными словами, на этапе S213 можно аналогичным образом выделить троичные числа из битовых строк, удовлетворяющих соотношению Х≥3^L′.

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

7: Способ эффективной подстановки коэффициентов в многочлены от нескольких переменных

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

7-1: Базовое определение

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

7-2: Структурирование данных

Однако число коэффициентов в многочленах от нескольких переменных является значительным. Когда один коэффициент выражен в единицах по 1 бит, данные в объеме по меньшей мере несколько десятков тысяч бит необходимы для представления многочлена от нескольких переменных. По этой причине нагрузка при подстановке чисел для коэффициентов многочлена от нескольких переменных очень велика. Соответственно, авторы настоящего изобретения разработали способы (способы #1 и #2 структурирования) для реализации эффективности процесса подстановки чисел для коэффициентов путем структурирования коэффициентов многочлена от нескольких переменных в виде совокупности заданных единиц (единичных блоков). Кроме того, авторы настоящего изобретения разработали способ (способ #3 структурирования) для повышения эффективности обработки данных, когда процедура подстановки осуществляется несколько раз применительно к коэффициентам одного и того же многочлена от нескольких переменных. Ниже эти способы будут описаны подробно.

7-2-1: Способ #1 структурирования (Фиг. 22-26)

Сначала будет описан способ #1 структурирования. Как показано на Фиг. 22 и 23, способ #1 структурирования представляет собой способ сбора коэффициентов членов одного рода, входящих в состав многочлена от нескольких переменных, в качестве одной структуры данных. В-примере, показанном на Фиг. 22, коэффициенты с a_1IJ по a_MIJ многочлена F от нескольких переменных собирают в качестве структуры А данных, а коэффициенты с b_1I по b_MI собирают в качестве структуры В данных. Кроме того, как показано на Фиг. 23, этот же способ применим к многочлену G от нескольких переменных. В этом случае, коэффициенты с (a_1IJ+a_1JI) по (a_MIJ+a_MJI) собирают в качестве структур данных.

Когда способ #1 структурирования не применяется, вычисление многочлена F от нескольких переменных, содержащего М многочленов от N переменных каждый осуществляется посредством алгоритма, показанного в (примере 1). В случае (примера 1), необходимо выполнять 1-битовую операцию "И" (AND) (&) 2×N×(N+1)×M/2 раз. Кроме того, необходимо выполнить 1-битовую операцию "исключающее-ИЛИ" (XOR) (^∧) 1×N×(N+1)×M/2 раз. Здесь предполагается, что входные данные x содержат N бит.

(пример 1)

С другой стороны, как показано на Фиг. 22, когда коэффициенты структурированы, а генерируемые случайные числа применяют последовательно по несколько за раз в качестве коэффициентов многочлена F от нескольких переменных, алгоритм подстановки коэффициентов выражен как в (примере 2). В случае (примера 2), выполняют М-битовую операцию "И" (AND) (&) только 2×N×(N+1)/2 раз и выполняют М-битовую операцию "исключающее ИЛИ" (XOR) (^∧) только N×(N+1)/2 раз. Кроме того, в каждом цикле генерируют а_(1-M)IJ. Коэффициенты могут быть использованы в обратном порядке. Например, когда цикл выполняется N(N-1)/2 раз, можно не генерировать коэффициенты [a_(1-M)IJ] каждый раз, а формировать их только однажды на каждые М раз. Кроме того, в цикле из М раз можно использовать коэффициенты [a_(1-M)IJ], поворачивая их бит за битом.

(пример 2)

Как показано Фиг. 22, когда коэффициенты структурированы, промежуточные результаты, получаемые в результате применения этих коэффициентов к многочлену F от нескольких переменных, могут быть сохранены в таблице. В этом случае применяется следующий алгоритм, представленный как в (примере 3). Кроме того, a_IJ[x₁, …, x_k] [z₁, …, z_k]=(a_{(k(I-1)+1)(k(J-1)+1)}&x₁&z₁) ^∧…^∧ (a_{(k(I-1)+1)(k(J-1)+k)}&x₁&z_k) ^∧...^∧ (a_{(k(I-1)+k)(k(J-1)+1)}&x_k&z₁) ^∧...^∧ (a_{(k(I-1)+k)(k(J-1)+k)}&x_k&z_k) сохраняют в массивах с a_IJ [0] [0] по a_IJ [2^k-1], соответственно. В случае (примера 3), выполняют М-битовую операцию "исключающее ИЛИ" (XOR) (^∧) только (N/k)(N/k+1)/2 раз. Однако необходимый объем памяти равен произведению 2^2k/k² на объем памяти, требуемый для алгоритма из (примера 2).

Например, когда k=1, М-битовую операцию "исключающее-ИЛИ" (XOR) вьшолняют 120*119/2=7140 раз, необходимый объем памяти в 2²=4 раз больше объема памяти для (примера 2), а число циклов не изменяется. Кроме того, когда k=2, М-битовую операцию "исключающее-ИЛИ" (XOR) вьшолняют 60*59/2=1770 раз, необходимый объем памяти в 2⁴=4 раз больше, а число циклов составляет 1/4. Когда k=4, М-битовую операцию "исключающее-ИЛИ" (XOR) вьшолняют 30*29/2=435 раз, необходимый объем памяти в 2⁸/4²=16 раз больше, а число циклов составляет 1/16,4. Когда k=6, М-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 20*19/2=190 раз, необходимый объем памяти в 2¹²/6²=114 раз больше, а число циклов составляет 1/37,6. Когда k=8, М-битовую операцию "исключающее-ИЛИ" (XOR) вьшолняют 15*14/2=135 раз, необходимый объем памяти в 2¹⁶/8²=1024 раз больше, а число циклов составляет 1/52,9. (пример 3)

Способ, описанный в (примере 3) может содержать вычисление заранее величин F_IJ(…) согласно следующей формуле (33) и сохранение результатов в виде массива.

Здесь, F_IJ(x_k(I-1)+1, …, x_k(I-1)+k, x_k(J-1)+1, …, x_k(J-1)+k) обозначает часть, определяемую посредством [x_k(I-1)+1, …, x_k(I-1)+k] и [x_k(J-1)+1, …, x_k(J-1)+k] в F(x₁, …, x_n).

Приведенные здесь конкретные алгоритмы представляют собой примеры случаев применения способа #1 структурирования к многочлену F от нескольких переменных. В такой структуре можно ожидать, что процесс выполнения этого алгоритма будет проходить с высокой скоростью.

(Применение к G)

Выше алгоритм для вычисления многочлена F от нескольких переменных с применением способа #1 структурирования был описан со ссылками на Фиг. 22. С другой стороны, каждый элемент многочлена G от нескольких переменных выражен в квадратичной форме. Поэтому, как показано на Фиг. 23, описанный выше способ #1 структурирования аналогичным образом применим к вычислению многочлена G от нескольких переменных без изменений.

Например, когда описанный выше способ #1 структурирования не применяется, алгоритм для вычисления многочлена G выражен в следующем (примере 1′). Здесь предполагается, что входные данные x и y содержат каждые по N бит.

(пример 1′)

Когда описанный выше способ #1 структурирования применяется в описанном выше (примере 1′), алгоритм для вычисления многочлена G выражен в следующем (примере 2′).

(пример 2′)

В случае способа сохранения промежуточного результата, полученного путем применения коэффициентов многочлена G от нескольких переменных, в таблице, алгоритм для вычисления многочлена G от нескольких переменных выражен в следующем (пример 3′) в соответствии с указанным выше (пример 3). Кроме того, a_IJ[x₁, …, x_k] [y₁, …, y_k]=(a_{(k(I-1)+1)(k(J-1)+1)}&x₁&y₁) ^∧…^∧ (a_{(k(I-1)+1)(k(J-1)+k)}&x₁&y_k) ^∧...^∧ (a_{(k(I-1)+k)(k(J-1)+1)}&x_k&y₁) ^∧...^∧ (a_{(k(I-1)+k)(k(J-1)+k)}&x_k&y_k) сохраняют в массивах с a_IJ [0] [0] по a_IJ [2^k-1] [2^k-1], соответственно.

В случае (примера 3′), выполняют М-битовую операцию "исключающее ИЛИ" (XOR) (^∧) только (N/k)² раз. Однако необходимый объем памяти равен произведению 2^2k/k² на объем памяти, требуемый для алгоритма из (примера 2′).

Например, когда k=1, М-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 120²=14400 раз, необходимый объем памяти в 2²=4 раз больше объема памяти для (примерп 2′), а число циклов не изменяется. Кроме того, когда k=2, М-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 60²=3600 раз, необходимый объем памяти в 2⁴=4 раз больше, а число циклов составляет 1/4. Когда k=4, М-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 30²=900 раз, необходимый объем памяти в 2⁸/4²=16 раз больше, а число циклов составляет 1/16. Когда k=6, М-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 20²=400 раз, необходимый объем памяти в 2¹²/6²=114 раз больше, а число циклов составляет 1/36. Когда k=8, М-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 15²=225 раз, необходимый объем памяти в 2¹⁶/8²=1024 раз больше, а число циклов составляет 1/64.

(пример 3′)

Способ, описанный в (примере 3′) может, в частности, представлять собой способ вычисления заранее величин G_IJ(…) согласно следующей формуле (34) и сохранение результатов в виде массива.

Здесь, G_IJ(x_k(I-1)+1, …, x_k(I-1)+k, x_k(J-1)+1, …, x_k(J-1)+k) обозначает часть, определяемую посредством [x_k(I-1)+1, …, x_k(I-1)+k] и [x_k(J-1)+1, …, x_k(J-1)+k] в G(x₁, …, x_n, y₁, …, y_N).

Конкретные структуры алгоритма, относящегося к способу #1 структурирования, были описаны на примере случая вычисления многочлена G от нескольких переменных. В такой структуре можно ожидать, что процесс выполнения этого алгоритма будет проходить с высокой скоростью.

Применение к кубическому многочлену F от нескольких переменных Способы структурирования коэффициентов квадратичного многочлена от нескольких переменных были рассмотрены выше в качестве конкретных примеров способа #1 структурирования. Аналогично можно структурировать также коэффициенты кубического многочлена от нескольких переменных. В примере, показанном на Фиг. 24, коэффициенты с a_1IJL по a_MIJL собирают в качестве структуры А данных, а коэффициенты с b_1IJ по b_MIJ собирают в качестве структуры В данных и коэффициенты с c_1I по c_MI собирают в качестве структуры С данных. Благодаря структурированию коэффициентов таким способом можно эффективно вычислять многочлен от нескольких переменных.

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

(пример 4)

С другой стороны, когда коэффициенты структурированы, алгоритм выражен в следующем (примере 5). В случае (примера 5), М-битовую операцию "И" (AND) (&) выполняют только 2×N×(N+1)×(N+2)/6 раз и М-битовую операцию "исключающее ИЛИ" (XOR) (^∧) выполняют только 1×N×(N+1)×(N+2)/6 раз. Кроме того, в каждом цикле генерируют a_(1-M)IJL. Коэффициенты могут быть использованы в обратном порядке. Например, когда цикл выполняется, можно не генерировать коэффициенты [a_(1-M)IJL] каждый раз, а формировать их только однажды на каждые М раз. Кроме того, в цикле из М раз можно использовать коэффициенты [a_(1-M)IJ], поворачивая их бит за битом.

(пример 5)

Когда коэффициенты структурированы, промежуточные результаты, получаемые в результате применения этих коэффициентов к многочлену F от нескольких переменных, могут быть сохранены в таблице. В этом случае применяется следующий алгоритм, представленный как в (примере 6). Кроме того, a_IJL[x₁, …, x_k][z₁, …, z_k][w₁, …, w_k]=∑_1≤α,_β,γ≤k (a_{(k(I-1)+α)(k(J-1)+β)(k(L-1)+γ)} &x_α &z_β &w_γ) сохраняют в массивах с a_IJL [0] [0] [0] по a_IJL [2^k-1] [2^k-1] [2^k-1], соответственно. В случае (примера 6), выполняют М-битовую операцию "исключающее ИЛИ" (XOR) (^∧) только (N/k)(N/k+1)(N/k+2)/6 раз. Однако необходимый объем памяти равен произведению 2^2k/k³ на объем памяти, требуемый для алгоритма из (примера 4).

Например, когда k=1, М-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 120*121*122/6=295240 раз, необходимый объем памяти в 2³=8 раз больше объема памяти для (примера 4), а число циклов не изменяется. Кроме того, когда k=2, М-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 60*61*62/6=37820 раз, необходимый объем памяти в 2⁶/8=8 раз больше, а число циклов составляет 1/7.8. Когда k=4, М-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 30*31*32/6=4960 раз, необходимый объем памяти в 2¹²/4³=64 раз больше, а число циклов составляет 1/59,5. Когда k=6, М-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 20*21*22/6=1540 раз, необходимый объем памяти в 2¹⁸/6³=1214 раз больше, а число циклов составляет 1/192.

(пример 6)

Способ, описанный в (примере 6) может, в частности, представлять собой способ вычисления заранее величин F_IJ(…) согласно следующей формуле (35) и сохранения величин в виде массива.

Здесь, F_IJ(x_k(I-1)+1, …, x_k(I-1)+k, x_k(J-1)+1, …, x_k(J-1)+k, x_k(L-1)+1, …, x_k(L-1)+k) обозначает часть, определяемую посредством [x_k(I-1)+1, …, x_k(I-1)+k], [x_k(J-1)+1, …, x_k(J-1)+k], и [x_k(L-1)+1, …, x_k(L-1)+k] в F(x₁, …, x_n).

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

(Применение к кубическим многочленам G_x и G_y от нескольких переменных) Как и в предыдущих (примере 5) и (примере 6) способ #1 структурирования также применим к многочленам G_x и G_y, как показано на Фиг. 25 и 26. Когда способ #1 структурирования не применяется, вычисления, относящиеся к структуре А данных кубического многочлена G_x от нескольких переменных, осуществляются, например, посредством следующего алгоритма (пример 4′Х).

(пример 4′Х)

Когда описанный выше способ #1 структурирования применяется в описанном выше (примере 4′Х), алгоритм для вычисления многочлена G_x от нескольких переменных выражен в следующем (примере 5′Х). Кроме того, в описанном выше (примере 6) промежуточные результаты, получаемые в результате применения этих коэффициентов к многочлену G_x от нескольких переменных, могут быть сохранены в таблице.

(пример 5′Х)

Когда способ #1 структурирования не применяется, вычисления кубического многочлена G_y от нескольких переменных, осуществляются, например, посредством следующего алгоритма из (примера 4′Y).

(пример 4′Y)

Когда описанный выше способ #1 структурирования применяется в описанном выше (примере 4′Y), алгоритм для вычисления многочлена G_y от нескольких переменных выражен в следующем (примере 5′Y). Кроме того, в описанном выше (примере 6) промежуточные результаты, получаемые в результате применения этих коэффициентов к многочлену G_y от нескольких переменных, могут быть сохранены в таблице.

(пример 5′Y)

Выше были описаны случаи применения способа #1 структурирования к кубическим многочленам G_x и G_y от нескольких переменных. В такой структуре можно ожидать, что процесс выполнения этого алгоритма будет проходить с высокой скоростью. 7-2-2: Способ #2 структурирования (Фиг. 27)

Далее будет описан способ #2 структурирования. Как показано на Фиг. 27, способ #2 структурирования представляет собой способ представления многочлена от нескольких переменных в квадратичной форме и сбора строк и столбцов этой квадратичной формы в качестве одной структуры данных. В примере, показанном на Фиг. 27, структура данных собрана в направлении строк.

Как показано на Фиг. 27, когда коэффициенты структурированы, а генерируемые случайные числа применяют последовательно по несколько за раз в качестве коэффициентов многочлена от нескольких переменных, алгоритм подстановки коэффициентов выражен как в (примере 4). В случае примера 4, выполняют N-битовую операцию "И" (AND) (&) только (N+1)×М раз, выполняют N-битовую операцию "исключающее ИЛИ" (XOR) (^∧) только N×М раз и выполняют операцию функции Q только М раз.

(пример 4)

Как показано на Фиг. 27, когда коэффициенты структурированы, промежуточные

результаты, получаемые в результате применения этих коэффициентов к многочлену от нескольких переменных, могут быть сохранены в таблице. В этом случае применяется алгоритм подстановки коэффициентов, представленный как в (примере 5). Кроме того, A_I [x₁, …, x_k]=(A_(k(I-1)+1)&x₁) ^∧…^∧ (A_(k(I-1)+k)&x_k) сохраняют в массивах с A_I [0] по A_I [2^k-1], соответственно. В случае примера 5, выполняют N-битовую операцию "исключающее ИЛИ" (XOR) (^∧) только (N/k)×M раз и выполняют N-битовую операцию функции Q только М раз. Однако необходимый объем памяти равен произведению 2^k/k на объем памяти, требуемый для алгоритма из (примера 4).

Например, когда k=1, N-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 120 раз, необходимый объем памяти в два раза больше объема памяти для (примера 4), а число циклов не изменяется. Кроме того, когда k=4, N-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 30 раз, необходимый объем памяти в 2⁴/4=4 раз больше, а число циклов составляет 1/4. Когда k=8, N-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 15 раз, необходимый объем памяти в 2⁸/8=32 раз больше, а число циклов составляет 1/8. Когда k=16, N-битовую операцию "исключающее-ИЛИ" (XOR) выполняют 8 раз, необходимый объем памяти в 2¹⁶/16=4096 раз больше, а число циклов составляет 1/15.

(пример 5)

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

7-2-3: Способ #3 структурирования

Далее будет описан способ #3 структурирования. Способ #3 структурирования представляет собой способ последовательного выполнения процедуры N раз (где N≥2) параллельно путем выполнения сегмента «для генерации нескольких коэффициентов и выполнения процедуры подстановки нескольких коэффициентов N раз» в единичных блоках вместо того, чтобы генерировать многочлен из случайных чисел N раз и выполнять процедуру подстановки в одном и том же многочлене от нескольких переменных N раз. При использовании этого способа повышается производительность всех процессов, выполняемых N раз, в случае, когда стоимость генерации случайных чисел не является пренебрежимо малой.

Например, в алгоритме, представленном на Фиг. 5, вычисление многочленов F и G от нескольких переменных осуществляется многократно N раз, и при этом происходит обновление факторов операции #1. Соответственно, в таком вычислительном сегменте процедура вычислений конфигурирована для многократного выполнения с использованием одних и тех же коэффициентов. Когда многочлен F(r_0i) (где i=1-N) от нескольких переменных вычисляют с использованием описанного выше алгоритма из (примера 2), все из N векторов r_0i конфигурированы для применения к однажды сформированному массиву [a_IJL], а затем выполняется процедура относительно следующего массива [a_IJL]. В такой конфигурации один и тот же массив [a_IJL] коэффициентов, в конечном итоге, не генерируют N раз.

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

8: Пример конфигурации аппаратуры (Фиг. 28)

Каждый алгоритм, описанный выше, может быть выполнен с использованием, например, конфигурации аппаратуры устройства для обработки информации, представленного на Фиг. 28. Иными словами, выполнение каждого алгоритма может быть реализовано посредством управления аппаратурой, показанной на Фиг. 28 с использованием компьютерной программы. Кроме того, характер аппаратуры может быть произвольным - это может быть персональный компьютер, мобильный информационный терминал, такой как мобильный телефон, PHS или PDA, игровой автомат, контактный или бесконтактный кристалл интегральной схемы, контактная или бесконтактная электронная карточка с встроенной интегральной схемой или разнообразная информационная аппаратура. Здесь PHS представляет собой сокращение от Personal Handy-phone System, т.е. персональный миниатюрный радиотелефон. Кроме того, PDA представляет собой сокращение от Personal Digital Assistant, т.е. персональный цифровой помощник.

Как показано на Фиг. 28, эта аппаратура содержит главным образом процессор CPU 902, ПЗУ ROM 904, ЗУПВ RAM 906, главную шину 908 и мост 910. Кроме того, эта аппаратура содержит внешнюю шину 912, интерфейс 914, модуль 916 ввода, модуль 918 вывода, модуль 920 памяти, привод 922 носителя записи, соединительный порт 924 и модуль 926 связи. Здесь CPU представляет собой сокращение от Central Processing Unit, т.е. центральный процессор. Кроме того, ROM представляет собой сокращение от Read Only Memory, т.е. постоянное запоминающее устройство (ПЗУ). Далее, RAM представляет собой сокращение от Random Access Memory, т.е. запоминающее устройство с произвольной выборкой (ЗУПВ).

Центральный процессор 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 представляет собой сокращение от Cathode Ray Tube, т.е. электронно-лучевая трубка. Кроме того, LCD представляет собой сокращение от Liquid Crystal Display, т.е. жидкокристаллический дисплей. Кроме того, PDP представляет собой сокращение от Plasma Display Panel, т.е. панель плазменного дисплея. Кроме того, ELD представляет собой сокращение от Electro-Luminescence Display, т.е. электролюминесцентный дисплей.

Модуль 920 памяти представляет собой устройство для хранения разнообразных данных. Указанный модуль 920 памяти представляет собой, например, магнитное запоминающее устройство, такое как накопитель HDD, полупроводниковое запоминающее устройство, оптическое запоминающее устройство или магнитооптическое запоминающее устройство. Здесь, HDD представляет собой сокращение от Hard Disk Drive, т.е. накопитель на жестком диске.

Привод 922 носителя записи представляет собой устройство, считывающее информацию, записанную на сменном носителе 928 записи, таком как магнитный диск, оптический диск, магнитооптический диск или полупроводниковое запоминающее устройство, или записывает информацию на сменном носителе 928 записи. Этот сменный носитель 928 записи может представлять собой, например, диск DVD, диск Блю-рей, диск HD-DVD, разнообразные полупроводниковые запоминающие устройства или аналогичные компоненты. Безусловно, сменный носитель 928 записи может представлять собой, например, электронное устройство или электронную карточку, на которой смонтирован бесконтактный кристалл интегральной схемы. Здесь 1C представляет собой сокращение от Integrated Circuit, т.е. интегральная схема.

Соединительный порт 924 представляет собой порт, такой как USB-порт, порт IEEE 1394, порт SCSI, порт RS-232C или порт для присоединения внешнего устройства 930, такого как оптический аудио терминал. Указанное внешнее устройство 930 представляет собой принтер, мобильный музыкальный плеер, цифровой фотоаппарат, цифровая видеокамера или записывающее устройство на основе интегральной схемы. Более того, USB представляет собой сокращение от Universal Serial Bus, т.е. универсальная последовательная шина. Кроме того, SCSI представляет собой сокращение от Small Computer System Interface, т.е. интерфейс малых вычислительных систем.

Модуль 926 связи представляет собой устройство связи для соединения с сетью 932 связи и может быть, например, картой связи для взаимодействия с кабельной ли радио сетью LAN, карту стандарта Bluetooth (зарегистрированная торговая марка) или WUSB, оптическим маршрутизатором связи, маршрутизатором ADSL или устройством для контактной или бесконтактной связи. Сеть 932 связи, соединяемая с модулем 926 связи, конфигурирована по принципу кабельной или беспроводной ста связи и может быть, например, сетью Интернет, домашней сетью LAN, сетью инфракрасной связи, сетью оптической связи в видимом диапазоне, сетью вещания или сетью спутниковой связи. Здесь, LAN представляет собой сокращение от Local Area Network, т.е. локальная сеть связи. Кроме того, WUSB представляет собой сокращение от Wireless USB, т.е. радио USB. Далее, ADSL представляет собой сокращение от Asymmetric Digital Subscriber Line, т.е. асимметричная цифровая абонентская линия.

9: Резюме

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

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

(1) Устройство обработки информации, содержащее:

модуль генерации чисел, выполненный с возможностью генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными; и

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

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

(2) Устройство обработки информации, содержащее:

модуль генерирования чисел, выполненный с возможностью генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными; и

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

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

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

(4) Устройство обработки информации согласно (3), в котором модуль генерации чисел выполнен с возможностью генерации одного числа при генерации чисел по количеству коэффициентов, принадлежащих одной группе, и генерации необходимого количества чисел путем поворота генерируемых чисел на каждый бит.

(5) Устройство обработки информации согласно (1) или (2), дополнительно содержащее:

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

(6) Устройство обработки информации, содержащее:

модуль генерации чисел, выполненный с возможностью генерации чисел в количестве, идентичном количеству коэффициентов членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными; и

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

(7) Устройство обработки информации согласно любому из (1)-(7),

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

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

(8) Устройство обработки информации согласно любому из (1)-(7), содержащее:

модуль генерации сообщений, выполненный с возможностью генерации сообщения на основе указанной пары многочленов F=(f₁, …, f_m) множества порядков от нескольких переменных, определенных в кольце K, и вектора s, являющегося элементом множества Kⁿ;

модуль передачи сообщений, выполненный с возможностью передачи указанного сообщения проверяющей стороне, хранящей указанную пару многочленов F множества порядков от нескольких переменных и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)); и

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

при этом вектор s представляет собой секретный ключ,

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

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

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

(9) Устройство обработки информации согласно любому из (1)-(7), содержащее:

модуль хранения информации, выполненный с возможностью хранения указанной пары многочленов F=(f₁, …, f_m) множества порядков от нескольких переменных, определенных в кольце K, и векторов y=(y₁, …, y_m)=(f₁(s), …, f_m(s));

модуль получения сообщений, выполненный с возможностью получения сообщения, генерируемого на основе указанной пары многочленов F множества порядков от нескольких переменных и вектора s, являющегося элементом множества Kⁿ;

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

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

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

при этом вектор s представляет собой секретный ключ,

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

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

(10) Устройство обработки информации согласно любому из (1)-(7), содержащее:

модуль генерации сообщений, выполненный с возможностью генерации сообщения на основе указанной пары многочленов F=(f₁, …, f_m) множества порядков от нескольких переменных, определенных в кольце К, и вектора s, являющегося элементом множества Kⁿ;

модуль передачи сообщений, выполненный с возможностью передачи указанного сообщения проверяющей стороне, хранящей указанную пару многочленов F множества порядков от нескольких переменных и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s));

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

модуль передачи промежуточной информации, выполненный с возможностью передачи третьей информации проверяющей стороне; и

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

при этом вектор s представляет собой секретный ключ,

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

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

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

(11) Устройство обработки информации согласно любому из (1)-(7), содержащее:

модуль хранения информации, выполненный с возможностью хранения пары многочленов F=(f₁, …, f_m) множества порядков от нескольких переменных, определенных в кольце K, и векторов y=(y₁, …, y_m)=(f₁(s), …, f_m(s));

модуль получения сообщений, выполненный с возможностью получения сообщения, генерируемого на основе указанной пары многочленов F множества порядков от нескольких переменных и вектора s, являющегося элементом множества Kⁿ;

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

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

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

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

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

при этом вектор s представляет собой секретный ключ,

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

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

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

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

(13) Устройство обработки информации согласно любому из (1)-(7), содержащее:

модуль генерации подписи, выполненный с возможностью генерации цифровой подписи для документа М с использованием указанной пары многочленов F=(f₁, …, f_m) множества порядков от нескольких переменных, определенных в кольце K, и ключа подписи, являющегося элементом множества Kⁿ; и

модуль передачи подписи, выполненный с возможностью передачи цифровой подписи проверяющей стороне, хранящей пару многочленов F множества порядков от нескольких переменных и векторы y=(f1(s), …, fm(s));

(14) Способ обработки информации, содержащий:

этап генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными; и

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

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

(15) Способ обработки информации, содержащий:

этап генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными; и

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

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

(16) Способ обработки информации, содержащий:

этап генерации чисел в количестве, идентичном количеству коэффициентов членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными; и

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

(17) Программа, вызывающая выполнение компьютером:

функции генерации чисел для генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными; и

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

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

(18) Программа, вызывающая выполнение компьютером:

функции генерации чисел для генерации чисел, используемых в коэффициентах членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков с несколькими переменными, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий указанную пару многочленов F множества порядков с несколькими переменными; и

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

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

(19) Программа, вызывающая выполнение компьютером:

функции генератора чисел, осуществляющую генерацию чисел в количестве, идентичном количеству коэффициентов членов, входящих в пару многочленов F=(f₁, …, f_m) множества порядков от нескольких переменных, с использованием заданной функции на основе информации, совместно используемой объектами, исполняющими алгоритм аутентификации с открытым ключом или алгоритм цифровой подписи, применяющий открытый ключ, содержащий пару многочленов F множества порядков от нескольких переменных; и

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

(20) Компьютерный носитель записи, на котором записана программа согласно (19).

Замечание

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

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

В приведенном выше описании были предложены алгоритмы, использующие хэш-функцию Н, однако здесь может быть также применена функция фиксации (commitment function СОМ) вместо хэш-функции Н. Функция фиксации СОМ представляет собой функцию, входными данными которой являются строка S символов и случайное число ρ. Одним из примеров функции фиксации является алгоритм, предложенный Шаи Галеви и Сильвио Микали (Shai Halevi and Silvio Micali) на международной конференции CRYPTO 1996.

Список позиционных обозначений

Gen алгоритм генерации ключей

Р алгоритм доказывающей стороны

V алгоритм проверяющей стороны

Sig алгоритм генерации подписи

Ver алгоритм верификации подписи