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

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

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

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

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

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

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

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

Например, в качестве схем цифровой подписи, которые принимают задачу многомерного полинома в качестве основы безопасности, известны схемы, основанные на криптографии Мацумото-Имаи (Matsumoto-Imai (MI)), криптографии, использующие уравнения скрытого поля (HFE), схемы подписи "масло-уксус" (OV) и криптографии, использующие способ ручного преобразования (ТТМ). Например, схема цифровой подписи на основе HFE раскрыта в следующей непатентной литературе 1 и 2.

Перечень цитируемой литературы

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

Непатентная литература 1: Jacques Patarin, «Asymmetric Cryptography with a Hidden Monomial», CRYPTO 1996, pp.45-60

Непатентная литература 2: 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-трудная задача, которую трудно решить даже в том случае, когда используется квантовый компьютер. Обычно схема аутентификации ключа общего доступа, которая имеет задачу многомерного полинома, типичным примером которой служит HFE или тому подобное, использует многостепенную многомерную систему уравнений со специальной функцией-ловушкой. Например, выполнены многостепенная многомерная система уравнений F(x₁, …, x_n)=y, зависящих от х₁, …, x_n, и линейные преобразования А и В, и линейные преобразования А и В управляются секретным образом. В этом случае многостепенная многомерная система уравнений F и линейные преобразования А и В представляют собой функции-ловушки.

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

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

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

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

Согласно варианту осуществления настоящей технологии выполнено устройство обработки информации содержащее блок генерирования сообщения для генерирования сообщения на основании пары многостепенных многомерных полиномов F=(f₁, …, f_m) и вектора s, который является элементом из набора Kⁿ, блок подачи сообщения, который подает сообщение верифицирующей стороне, хранящей пару многостепенных многомерных полиномов F и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), блок генерирования промежуточной информации для генерирования третьей информации на основании первой информации, произвольно выбранной с помощью верифицирующей стороны, и второй информации, полученной во время генерирования сообщения, блок предоставления промежуточной информации для предоставления третьей информации верифицирующей стороне, и блок подачи отклика для предоставления верифицирующей стороне информации отклика, соответствующей образцу верифицирующей стороны, который верифицирующая сторона выбирает из k (где k≥2) образцов верифицирующей стороны. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой ключи общего доступа. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верифицирующей стороны, соответствующего информации отклика на основании ключей общего доступа, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, х₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z, и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнено устройство обработки информации, включающее в себя блок хранения информации для хранения пары многостепенных многомерных полиномов F=(f₁, …, f_m) и векторов y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), блок получения сообщения для получения сообщения, сгенерированного на основании пары многостепенных многомерных полиномов F и вектора s, который представляет собой элемент из набора Kⁿ, блок предоставления информации для предоставления произвольно выбранной первой информации доказывающей стороне, которая выдает сообщение, блок получения промежуточной информации для получения третью информации, сгенерированной доказывающей стороной на основании первой информации и второй информации, полученной во время генерирования сообщения, блок предоставления информации об образце для предоставления доказывающей стороне информации относительно одного образца верификации, произвольно выбранного из k (где k≥3) образцов верификации, блок получения отклика для получения информации отклика, соответствующей выбранному образцу верификации, от доказывающей стороны, и блок верификации для верификации того, сохраняет ли доказывающая сторона вектор s на основании сообщения, первой информации, третьей информации, пары многостепенных многомерных полиномов F и информации отклика. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1l)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнен способ обработки информации, содержащий этапы, на которых генерируют сообщение на основании пары многостепенных многомерных полиномов F=(f₁, …, f_m) и вектора s, который представляет собой элемент из набора Kⁿ, подают сообщение на верифицирующей стороне, хранящей пару многостепенных многомерных полиномов F и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), генерируют третью информации на основании первой информации, произвольно выбранной верифицирующей стороной, и второй информации, полученной во время генерирования сообщения, предоставляют третью информацию верифицирующей стороне и предоставляет верифицирующей стороне информацию отклика, соответствующую образцу верификации, который выбирает верифицирующая сторона из k (где k≥2) образцов верификации. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнен способ обработки информации, включающий в себя этапы, на которых, с помощью устройства обработки информации, которое хранит пару многостепенных многомерных полиномов F=(f₁, …, f_m) и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), получают сообщение, сгенерированное на основании пары многостепенных многомерных полиномов F и вектора s, который представляет собой элемент из набора Kⁿ, предоставляют произвольно выбранную первую информацию доказывающей стороне, которая выдает сообщение, получают третью информацию, сгенерированную доказывающей стороной, на основании первой информации и второй информации, полученной во время генерирования сообщения, предоставляют доказывающей стороне информацию относительно одного образца верификации, произвольно выбранного из k (где k≥3) образцов верификации, и получают информацию отклика, соответствующую выбранному образцу верификации, от доказывающей стороны, верифицируют то, сохраняет ли доказывающая сторона вектор s на основании сообщения, первой информации, третьей информации, пары многостепенных многомерных полиномов F и информации отклика. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнена программа, вызывающая выполнение компьютером функции генерирования сообщения, выполненной с возможностью генерирования сообщения на основании пары многостепенных многомерных полиномов F=(f₁, …, f_m) и вектора s, который представляет собой элемент из набора Kⁿ, функции подачи сообщения, выполненной с возможностью подачи сообщения на верифицирующую сторону, хранящую пару многостепенных многомерных полиномов F и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), функции генерирования промежуточной информации, выполненной с возможностью генерирования третьей информации на основании первой информации, произвольно выбранной верифицирующей стороной, и второй информации, полученной во время генерирования сообщения, функцию предоставления промежуточной информации с возможностью предоставления третьей информации верифицирующей стороне и функцию подачи отклика с возможностью предоставления верифицирующей стороне информации отклика, соответствующей образцу верификации, который выбирает верифицирующая сторона из k (где k≥2) образцов верификации. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнена программа, вызывающая выполнение компьютером функции хранения информации, выполненной с возможностью хранения пары многостепенных многомерных полиномов F=(f1, fm) и векторов y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), функцию получения сообщения, выполненной с возможностью получения сообщения, выработанного на основании пары многостепенных многомерных полиномов F и вектора s, который представляет собой элемент из набора Kⁿ, функции предоставления информации, выполненной с возможностью предоставления произвольно выбранной первой информации доказывающей стороне, которая выдает сообщение, функции получения промежуточной информации, выполненной с возможностью получения третьей информации, сгенерированной доказывающей стороной, на основании первой информации и второй информации, полученной во время генерирования сообщения, функции предоставления информации об образце, выполненной с возможностью предоставления доказывающей стороне информации относительно одного образца верификации, произвольно выбранного из k (где k≥3) образцов верификации, функции получения отклика, выполненной с возможностью получения информации отклика, соответствующей выбранному образцу верификации, от доказывающей стороны, и функции верификации, выполненной с возможностью верификации того, сохраняет ли доказывающая сторона вектор s на основании сообщения, первой информации, третьей информации, пары многостепенных многомерных полиномов F и информации отклика. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+х₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1,2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнен машиночитаемый носитель информации, хранящий программу, причем программа вызывает выполнение компьютером функции генерирования сообщения, выполненной с возможностью генерирования сообщения на основании пары многостепенных многомерных полиномов F=(f₁, …, f_m) и вектора s, который представляет собой элемент из набора Kⁿ, функции подачи сообщения, выполненной с возможностью подачи сообщения на верифицирующей стороне, хранящей пару многостепенных многомерных полиномов F и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), функции генерирования промежуточной информации, выполненной с возможностью генерирования третьей информации на основании первой информации, произвольно выбранной верифицирующей стороной, и второй информации, полученной во время генерирования сообщения, функции предоставления промежуточной информации, выполненной с возможностью предоставления третьей информации верифицирующей стороне и функции подачи отклика с возможностью предоставления верифицирующей стороне информации отклика, соответствующей образцу верификации, который выбирает верифицирующая сторона из k (где k≥2) образцов верификации. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Согласно варианту осуществления настоящей технологии, выполнен машиночитаемый носитель информации, хранящий программу, причем программа вызывает выполнение компьютером функции хранения информации, выполненной с возможностью хранения пары многостепенных многомерных полиномов F=(f₁, …, f_m) и векторов y=(y₁, …, y_m)=(f₁(s), …, f_m(s)), функции получения сообщения, выполненной с возможностью получения сообщения, сгенерированного на основании пары многостепенных многомерных полиномов F и вектора s, который представляет собой элемент из набора Kⁿ, функции предоставления информации, выполненной с возможностью предоставления произвольно выбранной первой информации доказывающей стороне, которая выдает сообщение, функции получения промежуточной информации, выполненной с возможностью получения третьей информации, сгенерированной доказывающей стороной, на основании первой информации и второй информации, полученной во время генерирования сообщения, функцию предоставления информации об образце с возможностью предоставления доказывающей стороне информации относительно одного образца верификации, произвольно выбранного из k (где k≥3) образцов верификации, функции получения отклика, выполненной с возможностью получения информации отклика, соответствующей выбранному образцу верификации, от доказывающей стороны и функции верификации, выполненной с возможностью верификации того, сохраняет ли доказывающая сторона вектор s на основании сообщения, первой информации, третьей информации, пары многостепенных многомерных полиномов F и информации отклика. Вектор s представляет собой секретный ключ. Пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи. Сообщение представляет собой информацию, полученную путем выполнения вычисления, подготовленного заранее, для образца верификации, соответствующего информации отклика, на основании открытых ключей, первой информации, третьей информации и информации отклика. Пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам х₁=(x_1l, …, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z и 1≤z≤k).

Полезные эффекты изобретения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Последовательность описания

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

Далее, со ссылкой на фиг.4-8, будет описан пример структуры алгоритма, который относится к 3-проходной схеме аутентификации открытого ключа. Затем, со ссылкой на фиг.5-17, будет описан пример структуры алгоритма, который относится к 5-проходной схеме аутентификации открытого ключа. Далее, со ссылкой на фиг.18-21, будет описан способ модификации эффективных алгоритмов, который относится к 3-проходной и 5-проходной схемам аутентификации открытого ключа, в алгоритмах схемы цифровой подписи.

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

Содержание

1. Введение

1.1. Алгоритм схемы аутентификации открытого ключа

1.2. Алгоритмы для схемы цифровой подписи

1.3. N-проходная схема аутентификации открытого ключа

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

2.1. Пример конкретной структуры алгоритма

2.2. Эффективный алгоритм, основанный на квадратичном многомерном полиноме

2.2.1. Основная структура

2.2.2. Распараллеленный алгоритм

2.3. Эффективный алгоритм, основанный на многостепенном многомерном полиноме (схема #1)

2.3.1. Основная структура

2.3.2. Распараллеленный алгоритм

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

3.1. Пример конкретной структуры алгоритма

3.2: Эффективный алгоритм, основанный на квадратичном многомерном полиноме

3.2.1. Основная структура

3.2.2. Распараллеленный алгоритм

3.3. Эффективный алгоритм, основанный на многостепенном многомерном полиноме (первый вариант осуществления)

3.3.1. Основная структура

3.3.2. Распараллеленный алгоритм

3.4. Эффективный алгоритм, основанный на многостепенном многомерном полиноме (второй вариант осуществления)

3.4.1. Основная структура

3.4.2. Распараллеленный алгоритм (пример 1 структуры)

3.4.3. Распараллеленный алгоритм (пример 2 структуры: высокая эффективность)

3.4.4. Распараллеленный алгоритм (пример 2 структуры: более высокая эффективность)

4. Модификация схемы цифровой подписи

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

4.1.1. Алгоритм цифровой подписи (пример 1 структуры)

4.1.2. Алгоритм цифровой подписи (пример 2 структуры: высокая эффективность)

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

4.2.1. Алгоритм цифровой подписи (пример 1 структуры)

4.2.2. Алгоритм цифровой подписи (пример 2 структуры: высокая эффективность)

5. Алгоритм гибридного типа

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

5.1.1. Параллельно-последовательный алгоритм

5.1.2. Последовательно-параллельный алгоритм

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

5.2.1. Параллельно-последовательный алгоритм (пример #1 структуры)

5.2.2. Параллельно-последовательный алгоритм (пример #2 структуры)

5.2.3. Последовательно-параллельный алгоритм (пример #1 структуры)

5.2.4. Последовательно-параллельный алгоритм (пример #2 структуры)

6. Приложение

6.1. Способ установки параметра системы

6.2. Способ реагирования на нерегулярный вызов

6.2.1. Способ реагирования доказывающей стороной

6.2.2. Способ реагирования верифицирующей стороной

7. Пример конфигурации аппаратных средств

8. Заключение

1. Введение

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

1.1. Алгоритм схемы аутентификации открытого ключа

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

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

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

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

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

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

Модель

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

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

Дополнительно, выражения "доказывающая сторона" и "верифицирующая сторона" используются в последующем описании, но эти выражения строго означают объекты. Поэтому субъект, который выполняет алгоритм Gen генерирования ключей и алгоритм Р доказывающей стороны, представляет собой устройство обработки информации, соответствующее объекту "доказывающей стороны". Аналогично, субъект, который выполняет алгоритм V верифицирующей стороны, представляет собой устройство обработки информации. Конфигурация аппаратных средств этих устройств обработки информации представляет собой конфигурацию, которая показана, например, на фиг.28. То есть алгоритм Gen генерирования ключей, алгоритм Р доказывающей стороны и алгоритм V верифицирующей стороны выполняются с помощью ЦПУ 902 на основании программы, записанной в ПЗУ 904, ОЗУ 906, запоминающем устройстве 920, съемном носителе 928 записи или т.п.

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

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

[Формула 1]

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

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

Алгоритм V верифицирующей стороны

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

[Формула 2]

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

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

1.2. Алгоритмы для схемы цифровой подписи

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

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

Модель

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

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

Следует отметить, что хотя термины "подписывающая сторона" и "верифицирующая сторона" используются в дальнейшем описании, эти термины, в конечном счете, означают объекты. Следовательно, агент, который выполняет алгоритм Gen генерирования ключа и алгоритм Sig генерирования подписи, представляет собой устройство обработки информации, соответствующее "объекту подписывающей стороны". Аналогичным образом, агент, который выполняет алгоритм Ver верификации подписи, представляет собой устройство обработки информации. Конфигурация аппаратных средств этого устройства обработки информации является такой, как, например, показано на фиг.28. Другими словами, алгоритм Gen генерирования ключей, алгоритм Sig генерирования подписи и алгоритм Ver верификации подписи выполняются с помощью устройства, такого как ЦПУ 902 на основе программы, записанной на устройстве, таком как ПЗУ 904, ОЗУ 906, запоминающее устройство 920 или съемный носитель 928 записи.

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

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

[Формула 3]

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

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

[Формула 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, во время интерактивного протокола. В добавление к этому, интерактивный протокол должен удовлетворять двум условиям, таким как корректность и нулевое знание. По этой причине, во время интерактивного протокола как доказывающая сторона, так и верифицирующая сторона обмениваются информацией n раз при выполнении соответствующих процессов, как показано на фиг.3.

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

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

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

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

2.1. Пример конкретной структуры алгоритма

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

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

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

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

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

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

Операция #1:

Сначала, алгоритм Р доказывающей стороны выбирает любое число seed₀. Затем алгоритм Р доказывающей стороны генерирует вектор r₀, который представляет собой элемент набора Kⁿ, и число seed₁ путем применения числа seed₀ в генераторе PRNG случайных чисел. То есть алгоритм. Р доказывающей стороны вычисляет (r₀, seed₁)<-PRNG(seed₀). Затем алгоритм Р доказывающей стороны генерирует многомерный полином F₁(x)=(f₁₁(x), …, f_1m(x)) путем применения числа seed1 в генераторе PRNG случайных чисел. То есть алгоритм Р доказывающей стороны вычисляет F₁<-PRNG (seed₁).

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

Затем алгоритм Р доказывающей стороны вычисляет r₁<-s-r₀. Это вычисление эквивалентно маскированию секретного ключа s вектором r₀. Дополнительно, алгоритм Р доказывающей стороны вычисляет F₂(x)<-F(x+r₀)+F₁(x). Это вычисление эквивалентно маскированию многомерного полинома F(x+r₀) для х многомерным полиномом F₁(x).

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

Затем алгоритм Р доказывающей стороны генерирует значение хэширования с₀ для r₁ и F₁(r₁). То есть алгоритм Р доказывающей стороны вычисляет с₀<-H(F₁(r₁), r₁). К тому же, алгоритм Р доказывающей стороны генерирует значение хэширования c₁ числа seed₁. То есть алгоритм Р доказывающей стороны вычисляет c₁<-H(seed₁). К тому же, алгоритм Р доказывающей стороны генерирует значение хэширования c₂ многомерного полинома F₂. То есть алгоритм Р доказывающей стороны вычисляет c₂<-H(F₂). Значения хэширования (с₀, c₁, c₂) отправляются в виде сообщения в алгоритм V верифицирующей стороны. В то же время следует отметить, что совершенно отсутствуют утечки информации относительно s, информации относительно r₀ и информации относительно r₁ верифицирующей стороне.

Операция #2:

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

Операция #3:

После получения вызова Ch, алгоритм Р доказывающей стороны генерирует отклик Rsp для отправки в алгоритм V верифицирующей стороны в ответ на принятый вызов Ch. В случае когда Ch=0, алгоритм Р доказывающей стороны генерирует отклик Rsp=seed₀. В случае когда Ch=1, алгоритм Р доказывающей стороны генерирует отклик Rsp=(seed₁, r₁). В случае когда Ch=2, алгоритм Р доказывающей стороны генерирует отклик Rsp=(F₂, r₁). Отклик Rsp, сгенерированный в операции #3, отправляется в алгоритм V верифицирующей стороны. Здесь следует отметить, что совершенно не происходит утечки информации относительно r1 верифицирующей стороне в случае, когда Ch=0, и совершенно не происходит утечки информации относительно r₀ верифицирующей стороне в случае, когда Ch=1 или 2.

Операция #4:

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

В случае когда Ch=0, алгоритм V верифицирующей стороны вычисляет (r₀, seed₁)<-PRNG(Rsp). К тому же, алгоритм V верифицирующей стороны вычисляет F₁<-PRNG(seed₁). Затем алгоритм V верифицирующей стороны верифицирует то, соблюдается или нет равенство c₁=H(seed₁). В добавление к этому, алгоритм V верифицирующей стороны верифицирует то, соблюдается или нет равенство c₂=H(F(x+r₀)+F₁(x)). Алгоритм V верифицирующей стороны выводит значение 1, чтобы показать успешное завершение аутентификации в том случае, когда все эти верификации являются успешными, и выводит значение 0, чтобы показать неуспешное завершение аутентификации в том случае, когда верификация завершилась неудачно.

В случае когда Ch=1, алгоритм V верифицирующей стороны устанавливает (seed₁, r₁)<-Rsp. К тому же, алгоритм V верифицирующей стороны вычисляет F₁<-PRNG(seed₁). Затем алгоритм V верифицирующей стороны верифицирует то, соблюдается или нет равенство с₀=H(F₁(r₁), r₁). В добавление к этому, алгоритм V верифицирующей стороны верифицирует то, соблюдается или нет равенство c₁=H(seed₁). Алгоритм V верифицирующей стороны выводит значение 1, чтобы показать успешное завершение аутентификации в том случае, когда все эти верификации являются успешными, и выводит значение 0, чтобы показать неуспешное завершение аутентификации в том случае, когда верификация завершилась неудачно.

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

(Корректность)

Приведенное здесь описание корректности алгоритмов, которое относится к 3-проходной схеме, будет дополненным. Корректность алгоритмов, которые относятся к 3-проходной схеме, обеспечивается на основании логики того, что F₂, F₁, r₀ и r₁, удовлетворяющие следующим формулам (6) и (7), которые представлены ниже, можно вычислить в случае, когда алгоритм Р доказывающей стороны возвращает соответствующий отклик Rsp для всех вызов Ch=0, 1 и 2, выбранный с помощью алгоритма V верифицирующей стороны".

[Формула 6]

Обеспечив вышеуказанную корректность, тот факт, что успешная подделка с вероятностью более чем 2/3 не возможна, гарантируется до тех пор, пока не будет решена задача решения многостепенной многомерной системы уравнений. То есть чтобы соответствующим образом произвести отклик на все вызовы Ch=0, 1, 2 верифицирующей стороны, фальсификатор должен вычислить F₂, F₁, r₀ и r₁, удовлетворяющие формулам (6) и (7), которые приведены выше. Другими словами, фальсификатор должен вычислить s, удовлетворяющий уравнению F(s)=y. Однако остается вероятность того, что фальсификатор производит соответствующие отклики для двух вызовов более высокого порядка среди вызовов Ch=0, 1, 2 верифицирующей стороны. Поэтому вероятность успеха ложной верификации становится равной 2/3. Кроме того, за счет повторного выполнения вышеуказанного интерактивного протокола достаточно большое число раз, вероятность успешной подделки становится пренебрежимо малой.

(Функция Н хеширования)

Ниже приводится дополнительное описание функции Н хеширования. В вышеприведенных алгоритмах, c₀, c₁, c₂ и тому подобное вычисляют с использованием функции Н хеширования. Однако функцию СОМ фиксации можно использовать вместо функции Н хеширования. Функция СОМ фиксации представляет собой функцию, в которой символьная строка S и случайное число ρ представляют собой множители. Пример функции фиксации включает в себя схему, опубликованную на международной конференции CRYPTO 1996 Шаем Халеви (Shai Halevi) и Сильвио Миколи (Silvio Micali).

Например, будет рассмотрен случай, в котором c₀, c₁ и c₂ вычисляют с использованием функция СОМ фиксации. В этом случае случайные числа ρ₀, ρ₁ и ρ₂ подготавливаются перед вычислением c₀, c₁ и c₂, и c₀, c₁ и c₂ генерируются путем применения функций СОМ(·,ρ₀), COM(·,ρ₁) и COM(·,ρ₂) фиксации вместо применения функции Н(·) хеширования. Кроме того, ρ_i, необходимый для верифицирующей стороны для того, чтобы сгенерировать c_i, устанавливается как включенный в отклик Rsp и отправляется.

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

2.2. Эффективный алгоритм, основанный на квадратичном многомерном полиноме

Далее будет описан способ построения эффективных алгоритмов, которые относятся к 3-проходной схеме. Здесь будет описан случай, в котором пара квадратичных полиномов (f₁(x), …, f_m(x)) используется в качестве многомерных полиномов F. Здесь предполагается, что квадратичный полином f_i(x) будет выражен в виде следующей формулы (8).

[Формула 7]

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

[Формула 8]

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

[Формула 9]

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

Например, вектор t₀, который является элементом набора Kⁿ, и вектор е₀, который является элементом набора K^m, используют для того, чтобы выразить многомерный полином F₁(x), который используется для маскирования многомерного полинома F(x+r), as F₁(x)=G(x, t₀)+е₀. В этом случае сумма многомерного полинома F(x+r₀) и G(x) выражается в виде формулы (13), представленной ниже.

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

[Формула 10]

За счет использования вышеуказанной модификации информация относительно r₀ совсем не вытекает из F₂ (или F₁). Например, даже в случае, когда e₁ и t₁ (или е₀ и t₀) заданы, информация относительно r₀ совсем неизвестна, до тех пор, пока е₀ и t₀ (или e₁ и t₁) неизвестны. Соответственно, обеспечивается нулевое знание. Ниже, со ссылкой на фиг.5 и 6, будет описан эффективный алгоритм, который относится к 3-проходной схеме.

2.2.1. Базовая структура (фиг.5)

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

Операция #1:

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

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

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

Операция #2:

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

Операция #3:

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

Операция #4:

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

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

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

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

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

2.2.2. Распараллеленный алгоритм (фиг.6)

Далее, со ссылкой на фиг.6, будет описан способ распараллеливания алгоритмов, иллюстрированный на фиг.5. Тем не менее, дополнительное описание структуры алгоритма Gen генерирования ключей будет опущено.

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

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

Операция #1:

Алгоритм Р доказывающей стороны сначала выполняет следующие процессы (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₁₁, 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=H(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(r_1i, t_0i)+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 верифицирующей стороны вычисляет c_0i=Н(r_1i, y-F(r_1i)-G(t_1i, r_1i)-e_1i). В добавление к этому, алгоритм V верифицирующей стороны вычисляет c_2i=H(t_1i, e_1i). Затем алгоритм V верифицирующей стороны сохраняет (c_0i, C_1i, c_2i).

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

Пример структур распараллеленных эффективных алгоритмов, которые относятся к 3-х проходной, схеме был описан выше. К тому же, распараллеленные алгоритмы, показанные на фиг.6, включает в себя ухищрение, в котором сообщение преобразуется хэш-значение перед посылкой. Ухищрение повышает эффективность связи. Аналогично, структуру можно модифицировать таким образом, чтобы вызовы Ch₁, …, Ch_N или отклики Rsp₁, …, Rsp_N были преобразованы в хэш-значения перед посылкой. Модификация структуры, выполненная таким образом, позволяет дополнительно повысить ожидаемую эффективность связи.

2.3. Эффективный алгоритм, основанный на многостепенном многомерном полиноме (схема #1)

Вышеизложенные эффективный алгоритмы используют свойство, которые заключаются в том, что полином G, определенный в вышеприведенной формуле (10), становится билинейным в результате выражения многомерного полинома F парой квадратичных полиномов f_i, определенных в приведенной выше формуле (8). Однако когда полином G является аддитивно гомоморфным, эффективный алгоритм можно построить подобным образом даже в случае, когда полином G не является билинейным.

Построение эффективного алгоритма с использованием квадратичного полинома f_i

Когда полином G является аддитивно гомоморфным, зависимость следующих формул (14)-(16) устанавливается с использованием переменных r₀, r₁, t₀ и е₀. К тому же следующая формула (14) представляет собой формулу, полученную путем деления секретного ключа s на s=r₀+r₁ и разложения открытого ключа F(s). Следующие формулы (14)-(16) можно разделить на первую часть (r₁, t₀, е₀), воспроизводимую с помощью (r₀, t₁, e₁), вторую часть (r₁, t₁, e₁), воспроизводимую с помощью (r₁, t₀, е₀), и третью часть, воспроизводимую с помощью (r₁, t₁, e₁).

Например, "r0, t1", входящий в следующую формулу (15), и "F(r₀), e₁", входящий в следующую формулу (16), представляют собой первую часть. Дополнительно, "е₀, G(t₀, r₁)", входящий в следующую формулу (14), "t₀", входящий в следующую формулу (15), и "е₀", входящий в следующую формулу (16), представляют собой вторую часть. Дополнительно, "е₁, F(r₁), G(t₁, r₁)", входящий в следующую формулу (14), представляют собой третью часть. Другими словами, следующая формула (14) включает в себя вторую и третью части, следующая формула (15) включает в себя первую и вторую части, и следующая формула (16) включает в себя первую и вторую части.

Как описано выше, каждая из следующих формул (14)-(16) включает в себя два вида частей. Дополнительно, из определения секретного ключа s и зависимости среди следующих формул (14)-(16), гарантируется, что секретный ключ s не доступен даже тогда, когда используется любой один из (r₀, t₁, e₁), (r₁, t₀, е₀) и (r₁, t₁, e₁). Использование этого свойства позволяет, например, построить эффективный алгоритм, который относится к 3-проходной схеме, показанной на фиг.5.

[Формула 11]

Построение эффективного алгоритма с использованием кубического полинома f₁

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

[Формула 12]

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

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

Например, "r₀, t₀", входящий в следующую формулу (22), "u₀", входящий в следующую формулу (23), и "F(r₀), G_y(r₀, u₀), е₀", входящий в следующую формулу (24), представляют собой первую часть. Дополнительно, "G_y(r₀, u₁), e₁", входящий в следующую формулу (24), представляет собой вторую часть. Дополнительно, "е₀, G_x(r₀, r₁)", входящий в следующую формулу (21), представляет собой третью часть. Дополнительно, "e₁, F(r₁), G_x(t₁, r₁)", входящий в следующую формулу (21), "t₁", входящий в следующую формулу (22), и "u₁", входящий в следующую формулу (23), представляют собой четвертую часть.

Другими словами, следующая формула (21) включает в себя третью и четвертую части, следующие формулы (22) и (23) включают в себя первую и четвертую части, и следующая формула (24) включает в себя первую и вторую части. Таким образом, каждая из следующих формул (21)-(24) включает в себя два вида частей.

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

[Формула 13]

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

[Формула 14]

2.3.1. Базовая структура (фиг.7)

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

Операция #1:

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

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

Затем алгоритм Р доказывающей стороны вычисляет с₀<-Н(r₁, G_x(t₀, r₁)+е₀). Затем алгоритм Р доказывающей стороны вычисляет c₁<-H(r₀-t₀, u₀). Затем алгоритм Р доказывающей стороны вычисляет с₂<-Н(r₀, e₁-G_y(r₀, u₁)). Затем алгоритм Р доказывающей стороны вычисляет с₃<-H(t₀, e₀). Затем алгоритм Р доказывающей стороны вычисляет c₄<-H(u₁, e₁). Сообщения (с₀, 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₁=Н(r₀-t₀, u₀). Затем алгоритм V верифицирующей стороны верифицирует то, соблюдается или нет равенство с2=H(r0, F(r0)+Gy(r0, u0)-е0). Затем алгоритм 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 верифицирующей стороны верифицирует то, соблюдается или нет равенство c₀=H(r₁, е₀-G_x(t₀, r₁)). Затем алгоритм V верифицирующей стороны верифицирует то, соблюдается или нет равенство с₃=H(t₀, е₀). Алгоритм V верифицирующей стороны выводит значение 1, чтобы показать успешное завершение аутентификации в том случае, когда все верификации являются успешными, и выводит значение 0, чтобы показать неуспешное завершение аутентификации в том случае, когда верификация завершилась неудачно.

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

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

2.3.2. Распараллеленный алгоритм (фиг.8)

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

Операция #1:

Как показано на фиг.8, алгоритм Р доказывающей стороны выполняет следующие процессы для i=1-N. Сначала, алгоритм Р доказывающей стороны произвольно генерирует векторы r_0i, t_0i, u_0i, которые представляют собой элементы набора Kⁿ, и вектор e_0i, который является элементом набора K^m. Затем алгоритм Р доказывающей стороны вычисляет r_1i<-s-r_0i. Это вычисление эквивалентно маскированию секретного ключа s вектором r_0i. Затем алгоритм Р доказывающей стороны вычисляет t_1i<-r_0i-t_0i. Затем алгоритм Р доказывающей стороны вычисляет u_1i<-r_1i-u_0i. Затем алгоритм Р доказывающей стороны вычисляет e_1i<-F(r_0i)-e_0i.

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

Затем алгоритм Р доказывающей стороны вычисляет c_0i<-Н(r_1i, G_x(t_0i, r_1i)+e_0i). Затем алгоритм Р доказывающей стороны вычисляет c_1i<-H(r_0i, -t_0i, u_0i). Затем алгоритм Р доказывающей стороны вычисляет c_2i<-H(r_0i, e_1i-G_y(r_0i, u_1i)). Затем алгоритм Р доказывающей стороны вычисляет c_3i<-H(t_0i, e_0i). Затем алгоритм Р доказывающей стороны вычисляет c_4i<-Н(u_1i, e_1i). После генерирования (c_0i, с₁₁, c₂₁, c₃₁, c₄₁, …, c_0N, c_1N, c_2N, c_3N, c_4N) алгоритм P доказывающей стороны вычисляет значение Cmt хэширования <-H(с₀₁, с₁₁, c₂₁, c₃₁, c₄₁, …, c_0N, c_1N, c_2N, c_3N, c_4N).

Значение Cmt хэширования, сгенерированное в операции #1, отправляется в алгоритм V верифицирующей стороны.

Операция #2:

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

Операция #3:

После получения вызова Ch_i (i=1-N) алгоритм Р доказывающей стороны генерирует отклики Rsp_i для каждого i=1-N для отправки в алгоритм V верифицирующей стороны в ответ на каждый принятый вызов Ch_i. В случае когда Ch_i=0, алгоритм Р доказывающей стороны генерирует отклик Rsp_i=(r_0i, t_0i, u_0i, e_0i, c_0i, c_4i). В случае когда Ch_i=1, алгоритм Р доказывающей стороны генерирует отклик Rsp_i=(r_0i, u_1i, e_1i, c_0i, c_1i, c_3i). В случае когда Ch_i=2, алгоритм Р доказывающей стороны генерирует отклик Rsp_i=(r_1i, t_0i, e_0i, c_1i, c_2i, c_4i). В случае когда Ch_i=3, алгоритм Р доказывающей стороны генерирует отклик Rsp_i=(r_1i, t_1i, u_1i, e_1i, c_2i, c_3i). Отклик Rsp_i (i=1-N), сгенерированный в операции #3, отправляется в алгоритм V верифицирующей стороны.

Операция #4:

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

В случае когда Ch_i=0, алгоритм V верифицирующей стороны вычисляет c_1i=H(r_0i-t_0i, u_0i). Затем алгоритм V верифицирующей стороны вычисляет c_2i=H(r_0i, F(r_0i)+G_y(r_0i, u_0i)-e_0i). Затем алгоритм v верифицирующей стороны вычисляет c_3i=H(t_0i, e_0i). Затем алгоритм V верифицирующей стороны сохраняет (c_0i, c_1i, c_2i, c_3i, c_4i).

В случае когда Ch_i=1, алгоритм V верифицирующей стороны вычисляет c_2i=H(r_0i, e_1i-G_y(r_0i, u_1i)). Затем алгоритм V верифицирующей стороны вычисляет c_4i=Н(u_1i, e_1i). Затем алгоритм V верифицирующей стороны вычисляет c_3i=H(t_0i, e_0i). Затем алгоритм V верифицирующей стороны сохраняет (c_0i, c_1i, c_2i, c_3i, c_4i).

В случае когда Ch_i=2, алгоритм V верифицирующей стороны вычисляет c_0i=H(r_1i, G_x(t_0i, r_1i)+e_0i). Затем алгоритм V верифицирующей стороны вычисляет c_3i=H(t_0i, e_0i). Затем алгоритм V верифицирующей стороны вычисляет c_3i=H(t_0i, e_0i). Затем алгоритм V верифицирующей стороны сохраняет (c_0i, c_1i, c_2i, c_3i, c_4i).

В случае когда Ch_i=3, алгоритм V верифицирующей стороны вычисляет c_0i=Н(r_1i, y-F(r_1i)-e_1i-G_x(t_1i, r_1i)). Затем алгоритм V верифицирующей стороны вычисляет c_1i=H(t_1i, r_1i-u_1i). Затем алгоритм V верифицирующей стороны вычисляет c_4i=Н(u_1i, e_1i). Затем алгоритм V верифицирующей стороны сохраняет (c_0i, c_1i, c_2i, c_3i, c_4i).

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

Распараллеливание структуры расширенного алгоритма, который относится к 3-проходной схеме, было описано выше. За счет использования алгоритмов, значительно уменьшается объем данных, необходимый для связи. К тому же, использование кубического полинома позволяет реализовать более высокую безопасность.

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

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

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

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

3.1. Пример конкретной структуры алгоритма (фиг.9)

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

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

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

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

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

Операция #1:

Как показано на фиг.9, алгоритм Р доказывающей стороны произвольно выбирает число seed₀. Затем алгоритм Р доказывающей стороны генерирует вектор r₀, который представляет собой элемент набора Kⁿ, и пары многомерных полиномов F₁(x)=(f₁₁(x), f_1m(x)) путем применения числа seed₀ в генераторе PRNG случайных чисел. То есть алгоритм Р доказывающей стороны вычисляет (r₀, F₁)<-G(seed₀). Затем алгоритм Р доказывающей стороны вычисляет r1<-s-r₀. Это вычисление эквивалентно маскированию секретного ключа s вектором r₀.

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

Затем алгоритм Р доказывающей стороны генерирует F₁(r₁) и значение с₀ хэширования из r₁. То есть алгоритм Р доказывающей стороны вычисляет c₀<-H(F₁(r₁), r₁). К тому же, алгоритм Р доказывающей стороны генерирует значение хэширования c₁ из числа seed₀. То есть алгоритм Р доказывающей стороны вычисляет c₁<-H(seed₀). Сообщения (с₀, c₁), выработанные в операции #1, отправляются в алгоритм V верифицирующей стороны.

Операция #2:

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

Операция #3:

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

Операция #4:

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

Операция #5:

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

Операция #6:

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

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

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

Корректность

Корректность 5-проходной схемы обеспечивается исходя из того факта, что F₁, F₂, , r₀ и r₁ удовлетворяющие следующим формулам (28)-(30), можно вычислить из содержания отклика, когда алгоритм Р доказывающей стороны надлежащим образом производит отклик на вызов Ch_B=0 и 1 по отношению к (с₀, c₁) и двум (Ch_A, ), выбранным с помощью алгоритма V верифицирующей стороны

[Формула 15]

Обеспечив вышеуказанную корректность 5-проходной схемы, тот факт, что подделка с вероятностью выше, чем 1/2+1/q, не возможна, обеспечивается до тех пор, пока не будет решена задача решения многостепенной многомерной системы уравнений. То есть чтобы надлежащим образом произвести отклик на все вызовы Ch_A=0 и 1 верифицирующей стороны, фальсификатор должен вычислить F₁, F₂, , r0 и r₁, удовлетворяющие вышеприведенным формулам (28) и (30). Другими словами, фальсификатор должен вычислить s, удовлетворяющий уравнению F(s)=y. Соответственно, фальсификатору может не удаться подделка с вероятностью выше, чем 1/2+1/q, до тех пор, пока не будет решена задача решения многостепенной многомерной системы уравнений. Кроме того, за счет повторного выполнения вышеизложенного интерактивного протокола достаточно большое число раз, вероятность успешной подделки становится пренебрежимо малой.

Функция Н хеширования

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

Например, будет рассмотрен случай, в котором с₀ и c₁ вычисляют с использованием функция СОМ фиксации. В этом случае случайные числа ρ₀ и ρ₁ подготавливаются перед вычислением с₀ и c₁, и с₀, c₁ генерируются путем применения функций СОМ(·,ρ₀) и СОМ(·,ρ₁) фиксации вместо применения функции Н(·) хеширования. Кроме того, ρ_i, необходимый для верифицирующей стороны для того, чтобы сгенерировать c_i, устанавливается как включенный в отклик Rsp и отправляется.

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

3.2. Эффективный алгоритм, основанный на квадратичном многомерном полиноме

Далее будет описан способ создания эффективных алгоритмов, которые относятся к 5-проходной схеме. Здесь будет описан случай, в котором пара квадратичных полиномов (f₁(x), …, f_m(x)) используется в качестве многомерных полиномов F.

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

[Формула 16]

По этой причине, когда 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, и, таким образом, объем данных, необходимый для связи можно значительно уменьшить. В частности, себестоимость связи можно уменьшить до тысяч и десятков тысяч раз.

За счет использования вышеизложенный модификации информация относительно r₀ совершенно не передается из F₂ (или F₁). Например, даже в том случае, когда e₁ и t₁ (или е₀ и t₀) заданы, информация относительно r₀ совершенно не известна до тех пор, пока не известны е₀ и t₀ (или e₁ и t₁). Соответственно, обеспечивается нулевое знание. Ниже, со ссылкой на фиг.10 и 11, будет описан эффективный алгоритм, который относится к 5-проходной схеме.

3.2.1. Базовая структура (фиг.10)

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

Операция #1:

Как показано на фиг.10, алгоритм Р доказывающей стороны произвольно генерирует вектор r₀, который является элементом набора Kⁿ, вектор t₀, который является элементом набора Kⁿ, и вектор е₀, который является элементом набора K^m. Затем алгоритм Р доказывающей стороны вычисляет r₁<-s-r₀. Это вычисление эквивалентно маскированию секретного ключа s вектором r₀. Затем алгоритм Р доказывающей стороны вычисляет значение хэширования с₀ векторов r₀, t₀, е₀. То есть алгоритм Р доказывающей стороны вычисляет c₀<-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₁ и е₁ алгоритм 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₀<-Rsp. Затем алгоритм V верифицирующей стороны верифицирует то, соблюдается или нет равенство c₀=Н(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.2. Распараллеленный алгоритм (фиг.11)

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

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

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

Операция #1:

Алгоритм Р доказывающей стороны сначала выполняет следующие процессы (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<-H(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. Затем алгоритм Р доказывающей стороны отправляет t₁₁, …, t_1N и е₁₁, …, e_1N в алгоритм V верифицирующей стороны.

Операция #4:

После получения t₁₁, …, t_1N и е₁₁, …, e_1N алгоритм V верифицирующей стороны выбирает, какой образец верификации использовать из двух образцов верификации для i=1-N. Например, алгоритм V верифицирующей стороны может выбрать численное значение из двух численных значений {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_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, c_1i)<-Rsp_i. Затем алгоритм V верифицирующей стороны вычисляет c_0i=H(r_0i-Ch_Ai·r_0i-t_1i, Ch_Ai·F(r_0i)-e_1i). Затем алгоритм V верифицирующей стороны сохраняет (c_0i, c_1i).

Процесс (2): В случае когда Ch_Bi=1, алгоритм V верифицирующей стороны выполняет (r_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).

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

Пример структур распараллеленных эффективных алгоритмов, которые относятся к 5-проходной схеме, был описан выше. К тому же, распараллеленные алгоритмы, показанные на фиг.11, включают в себя ухищрение, в котором сообщение преобразуется в значение хэширования перед отправкой. Ухищрение повышает эффективность связи. Аналогично, структуру можно модифицировать таким образом, чтобы вызовы Ch_A1, Ch_AN, Ch_B1, Ch_BN или отклики Rsp₁, …, Rsp_N преобразовывались в значения хэширования перед отправкой. Предполагается, что модификация структуры, выполненная таким образом, позволит дополнительно повысить эффективность связи.

3.3. Эффективный алгоритм, основанный на многостепенном многомерном полиноме (схема #1)

Вышеизложенные эффективные алгоритмы используют свойство, которое состоит в том, что полином G, определенный в вышеприведенной формуле (10), становится билинейным за счет представления многомерного полинома F с помощью пары квадратичных полиномов f_i, определенных в вышеприведенной формуле (8). Здесь эффективный алгоритм, иллюстрированный на фиг.10, использует тот факт, что открытый ключ F(s) можно разделить на часть, в которой член, который представляет собой Ch_A раз, зависит от Ch_A и другой части. Однако даже в случае 5-проходной схемы, когда полином G является линейным, по меньшей мере, для одного из х и y, эффективный алгоритм можно построить подобным образом даже в том случае, когда полином G не является билинейным.

Построение эффективного алгоритма с использованием кубического полинома f_i

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

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

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

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

Ниже будет описан пример конкретной расширенной структуры алгоритма. Два основных момента, касающихся построения расширенного алгоритма, состоят в том, что сообщение, представленное в виде следующих формул (36) и (37), отправляется верифицирующей стороне, и что часть (первая часть), которая зависит от Ch_A, верифицируется для Ch_A, выбранного верифицирующей стороной. В данном случае поскольку "r₀ и r₁, используемые во время генерирования сообщения, не допускают замены на другие r₀ и r₁ во время верификации", пример структуры, в которой добавлена верификация, касающаяся r₀ и r₁, будет представлен ниже.

[Формула 18]

3.3.1. Базовая структура (фиг.12)

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

Операция #1:

Как показано на фиг.12, алгоритм Р доказывающей стороны произвольно генерирует векторы r₀, t₀, u₀, которые представляют собой элементы набора Kⁿ, и вектор е₀, который является элементом набора K^m. Затем алгоритм Р доказывающей стороны вычисляет r₁<-s-r₀. Это вычисление эквивалентно маскированию секретного ключа s вектором r₀. Затем алгоритм Р доказывающей стороны вычисляет с₀<-Н(r₀, t₀, е₀-G_y(r₀, u₀)). Затем алгоритм Р доказывающей стороны вычисляет c₁<-H(r₁, u₀, G_x(t₀, r₁)+е₀). Сообщения (с0, c1), сгенерированные в операции #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 верифицирующей стороны верифицирует то, соблюдается или нет равенство c₀=Н(r0, 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-проходной схеме, был описан выше. За счет использования алгоритмов, значительно уменьшается объем данных, необходимый для связи. К тому же, использование кубического полинома позволяет реализовать более высокую безопасность.

3.3.2. Распараллеленный алгоритм (фиг.13)

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

Операция #1:

Как показано на фиг.13, алгоритм Р доказывающей стороны выполняет следующие процессы для i=1-N. Сначала, алгоритм Р доказывающей стороны произвольно генерирует векторы r_0i, t_0i, u_0i, которые представляют собой элементы набора Kⁿ, и вектор e_0i, который является элементом набора K^m. Затем алгоритм Р доказывающей стороны вычисляет r_1i<-s-r_0i. Это вычисление эквивалентно маскированию секретного ключа s вектором r_0i Затем алгоритм Р доказывающей стороны вычисляет c_0i<-H(r_0i, t_0i, e_0i,-G_y(r_0i, u_0i). Затем алгоритм P доказывающей стороны вычисляет c_1i<-Н(r_1i, u_0i-G_x(t_0i, r_1i)+e_0i).

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

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

Операция #2:

После получения значения Cmt хэширования алгоритм V верифицирующей стороны произвольно выбирает числа Ch_Ai, …, Ch_AN. Числа Ch_A1, …, Ch_AN отправляются в алгоритм Р доказывающей стороны.

Операция #3:

После получения чисел Ch_Ai, …, Ch_AN алгоритм Р доказывающей стороны выполняет следующий процесс для i=1-N. Сначала, алгоритм Р доказывающей стороны вычисляет t_1i<-Ch_Ai·r_0i-t_0i. Затем алгоритм Р доказывающей стороны вычисляет u_1i<-Ch_Ai·r_1i-u_0i. Затем алгоритм Р доказывающей стороны вычисляет e_1i<-Ch_Ai·F(r_0i)+Ch_Ai·G_y(r_0i, r_1i)-e_0i.

Затем (t₁₁, u₁₁, е₁₁, …, t_1N, u_1N, e_1N), сгенерированные в операции #3, отправляются в алгоритм V верифицирующей стороны.

Операция #4:

После получения (t₁₁, u₁₁, е₁₁, t_1N, u_1N, e_1N) алгоритм V верифицирующей стороны выбирает, какой образец верификации использовать из двух образцов верификации для i=1-N. Например, алгоритм V верифицирующей стороны может выбрать численное значение среди двух численных значений {0, 1}, представляющих собой образцы верификации для i=1-N, и установить выбранное численное значение в вызове Ch_Bi. Вызовы Ch_B1-Ch_BN отправляются в алгоритм Р доказывающей стороны.

Операция #5:

После получения вызовов Ch_B1-Ch_BN, алгоритм Р доказывающей стороны генерирует отклик Rsp_i для отправки в алгоритм V верифицирующей стороны в ответ на принятый вызов Ch_Bi для i=1-N. В случае когда Ch_Bi=0, алгоритм Р доказывающей стороны генерирует отклик Rsp_i=(r_0i, c_1i). В случае когда Gh_Bi=1, алгоритм Р доказывающей стороны генерирует отклик Rsp_i=(r_1i, C_0i). Отклик Rsp_i, сгенерированный в операции #5, отправляется в алгоритм V верифицирующей стороны.

Операция #6:

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

В случае когда Ch_Bi=0, алгоритм V верифицирующей стороны вычисляет c_0i=H(r_0i-Ch_Ai·r_0i-t_1i, Ch_Ai·F(r_0i)+G_y(r_0i, u_1i)-e_1i). Затем алгоритм V верифицирующей стороны сохраняет (c_0i, c_1i).

В случае когда Ch_Bi=1, алгоритм V верифицирующей стороны вычисляет c_1i=H(r_1i, Ch_Ai·r_1i-u_1i, Ch_Ai·(y-F(r_1i))-G_x(t_1i, r_1i)-e_1i). Затем алгоритм V верифицирующей стороны сохраняет (c_0i, c_1i).

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

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

3.4. Эффективный алгоритм, основанный на многостепенном многомерном полиноме (схема #2)

Выше был описан способ построения эффективного алгоритма с использованием кубического полинома f₁ кольца R. Здесь будет рассмотрен способ построения расширенного алгоритма с использованием многостепенного полинома f₁, определенного в кольце R характеристики q и порядка q^k. Многостепенной полином f₁ представлен, например, в виде следующей формулы (38). При использовании многостепенного полинома f₁ компонент g₁ полинома G, определенный как G(x, y)=F(x+y)-F(x)-F(y)=(g₁, …, g_m), выражен в виде следующей формулы (39).

[Формула 19]

Зависимость, показанная в следующей формуле (40), установлена для Ch_A, который является элементом набора R. Дополнительно установлена также зависимость, показанная в следующей формуле (41). Таким образом, используя это свойство (здесь и далее по тексту называется как квазилинейность), открытый ключ F(s) делится на член, который представляет собой Ch_A раз, путем введения новых переменных r₀, r₁, t_0z и е₀. Поскольку G имеет квазилинейность, зависимость среди следующих формул (42)-(44) устанавливается с использованием переменных r₀, r₁, t_0z и е₀. Следующие формулы (42)-(44) можно разделить на первую часть, которая зависит от Ch_A, и вторую часть, которая не зависит от Ch_A. Здесь первую часть можно воспроизвести с помощью (r₁, t_1z, е₁). Вторую часть можно воспроизвести с помощью (r₀, t_1z, e₁).

Например, "е₀, ΣG_z(t_0z, r₁)", входящий в следующую формулу (42), "t_0z", входящий в следующую формулу (43), и "е₀", входящий в следующую формулу (44), представляют собой первые части. С другой стороны, "Ch_A·F(r₀+r₁), е₁, Ch_A·F(r₁), ΣG_z(t_1z, r₁)", входящий в следующую формулу (42), " (где q(z)=q^z и то же самое применяется ниже), входящий в следующую формулу (43), и "Ch_A·F(r₀), e₁", входящий в следующую формулу (44), представляют собой вторые части.

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

[Формула 20]

Ниже будет описан пример конкретной многостепенной расширенной структуры алгоритма. Два основных момента, касающихся построения расширенного алгоритма, состоят в том, что сообщение, представленное в виде следующих формул (45) и (46), отправляется верифицирующей стороне, и что часть (первая часть), которая зависит от Ch_A, верифицируется для Ch_A, выбранного верифицирующей стороной. Здесь, поскольку "r₀ и r₁, используемые во время генерирования сообщения, не допускают замены на другие r₀ и r₁ во время верификации", пример структуры, в которой добавлена верификация, касающаяся r₀ и r₁ будет представлен ниже.

[Формула 21]

3.4.1. Базовая структура (фиг.14)

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

Операция #1:

Как показано на фиг.14, алгоритм Р доказывающей стороны произвольно генерирует векторы r₀, t₀₁, t_0k, которые представляют собой элементы набора Kⁿ, и вектор e₀, который является элементом набора K^m. Затем алгоритм Р доказывающей стороны вычисляет r₁<-s-r₀. Это вычисление эквивалентно маскированию секретного ключа s вектором r₀. Затем алгоритм Р доказывающей стороны вычисляет с₀<-Н(r₀, t₀₁, …, t_0k, е₀). Затем алгоритм Р доказывающей стороны вычисляет c₁<-H(r₁, Σ_zG_z(t_0z, r₁)+е₀) (где Σ_z представляет собой sum для z=1 to k). Сообщения (с0, c1), сгенерированные в операции #1, отправляются в алгоритм V верифицирующей стороны.

Операция #2:

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

Операция #3:

После получения числа Ch_A алгоритм Р доказывающей стороны вычисляет t_1z<-(Ch_A)^q(z-1)·r₀-t_0z для z=1 to k. Затем алгоритм Р доказывающей стороны вычисляет e₁<-Ch_A·F(r₀)-е₀. Затем (t₁₁, …, t_1k, e₁), сгенерированные в операции #3, отправляются в алгоритм V верифицирующей стороны.

Операция #4:

После получения (t₁₁, …, t_1k, 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 верифицирующей стороны верифицирует то, соблюдается или нет равенство c₀=Н(r0, (Ch_A)^q(0)·r₀-t₁₁, …, (Ch_A)^q(k-1)·r₀-t_1k, Ch_A·F(r₀)-e₁). Алгоритм V верифицирующей стороны выводит значение 1, чтобы показать успешное завершение аутентификации в том случае, когда эти верификации являются успешными, и выводит значение 0, чтобы показать неуспешное завершение аутентификации в том случае, когда верификация завершилась неудачно.

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

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

3.4.2. Распараллеленный алгоритм (пример 1 структуры) (фиг.15)

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

Операция #1:

Как показано на фиг.15, алгоритм Р доказывающей стороны выполняет следующие процессы для i=1-N. Сначала алгоритм Р доказывающей стороны произвольно генерирует векторы r_0i, t_01i, …, t_0ki, которые представляют собой элементы набора Kⁿ, и вектор e_0i, который является элементом набора K^m. Затем алгоритм Р доказывающей стороны вычисляет r_1i<-s-r_0i. Это вычисление эквивалентно маскированию секретного ключа s вектором r_0i. Затем алгоритм Р доказывающей стороны вычисляет c_0i<-Н(r_0i, t_01i, t_0ki, e_0i). Затем алгоритм Р доказывающей стороны вычисляет c_1i<-Н(r_1i, Σ_zG_z(t_0zi, r_1i)+e_0i) (где Σ_z представляет собой sum для z=1-k). Сообщения (c_0i, c_1i) (где i=1-N), сгенерированные в операции #1, отправляются в алгоритм V верифицирующей стороны.

Операция #2:

После получения сообщения (c_0i, c_1i) (где i=1-N) алгоритм V верифицирующей стороны произвольно выбирает числа Ch_A1, …, Ch_AN. Числа Ch_A1, …, Ch_AN отправляются в алгоритм Р доказывающей стороны.

Операция #3:

После получения чисел Ch_A1, …, Ch_AN алгоритм Р доказывающей стороны вычисляет t_1zi<-(Ch_Ai)^q(z-1)·r_0i-t_0zi для i=1-N и z=1-k. Затем алгоритм Р доказывающей стороны вычисляет e_1i<-Ch_Ai·F(r_0i)-e_0i. Затем (t_11i, t_1ki, e_1i) (где i=1-N), сгенерированные в операции #3, отправляются в алгоритм V верифицирующей стороны.

Операция #4:

После получения (t_11i, …, t_1ki, e_1i) (где i=1-N) алгоритм V верифицирующей стороны выбирает, какой образец верификации использовать из двух образцов верификации для i=1-N. Например, алгоритм V верифицирующей стороны может выбрать численное значение из двух численных значений {0, 1}, представляющих собой образцы верификации для i=1-N, и установить выбранное численное значение в вызове 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 В случае когда Ch_Bi=1, алгоритм Р доказывающей стороны генерирует отклик Rsp_i=r_1i. Отклик Rsp_i (где i=1-N), сгенерированный в операции #5, отправляется в алгоритм V верифицирующей стороны.

Операция #6:

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

В случае когда Ch_Bi=0, алгоритм V верифицирующей стороны верифицирует то, соблюдается или нет равенство c_0i=H(r_0i, (Ch_Ai)^q(0)·r_0i-t_11i, (Ch_Ai)^q(k-1)·r_0i-t_1ki, Ch_Ai·F(r_0i-e_1i). В случае когда Ch_Bi=1, алгоритм V верифицирующей стороны верифицирует то, соблюдается или нет равенство c_1i=Н(r_1i, Ch_Ai·(y-F(r_1i)-Σ_zG_z(t_1zi, r_1i)).

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

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

3.4.3. Распараллеленный алгоритм (пример 2 структуры: высокая эффективность) (фиг.16)

Однако в распараллеленной структуре многостепенного расширенного алгоритма, иллюстрированного на фиг.15, сообщения (c_0i, c_1i) (где i=1-N) были отправлены на первом проходе без изменения. Однако, принимая во внимание эффективность связи, предпочтительно, чтобы сообщения (c_0i, c_1i) (где i=1-N) отправлялись вместе с одним значением хэширования. Для того чтобы отправлять вместе сообщения (c_0i, c_1i) (где i=1-N) с одним значением хэширования на первом проходе, структуру алгоритма можно модифицировать так, как показано на фиг.16.

В примере структуры фиг.16 алгоритм Р доказывающей стороны вычисляет значение Cmt хэширования <-Н(с₀₁, c₁₁, …, c_0N, c_1N) в операции #1. После генерирования отклика Rsp_i в операции #5, алгоритм Р доказывающей стороны генерирует отклик Rsp_i=(r_0i, c_1i) в случае, когда Ch_Bi=0 и генерирует отклик Rsp_i=(r_1i, c_0i) в случае, когда Ch_Bi=1. С другой стороны, алгоритм V верифицирующей стороны генерирует (c₀₁, с₁₁, …, c_0N, c_1N) из (Ch_Ai, Ch_Bi, Rsp_i) (где i=1-N) в операции #6 и верифицирует то, соблюдается или нет равенство Cmt=Н(с₀₁, c₁₁, …, c_0N, c_1N). Выполняя такую модификацию, можно дополнительное повысить эффективность связи.

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

3.4.4. Распараллеленный алгоритм (пример 2 структуры: более высокая эффективность) (фиг.17)

Однако в распараллеленной структуре многостепенного расширенного алгоритма, иллюстрированного на фиг.15, сообщения (c_0i, c_1i) (где i=1-N) были отправлены на первом проходе без изменения. Дополнительно, (t_11i, …, t_1ki, e_1i) (где i=1-N) были отправлены на третьем проходе без изменения. Однако, принимая во внимание эффективность связи, предпочтительно, чтобы сообщения (c_0i, c_1i) (где i=1-N) отправлялись вместе с одним значением хэширования. Дополнительно, предпочтительно, чтобы (t_11i, …, t_1ki, e_1i) (где i=1-N) отправлялись вместе с одним значением хэширования. Для того чтобы отправлять вместе сообщения (c_0i, c_1i) (где i=1-N) с одним значением хэширования на первом проходе и отправлять вместе (t_11i, …, t_1ki, e_1i) (где i=1-N) с одним значением хэширования на третьем проходе, структуру алгоритма можно модифицировать так, как показано на фиг.17.

В примере структуры фиг.17 алгоритм Р доказывающей стороны вычисляет значение Cmt хэширования <-Н(с₀₁, с₁₁, …, c_0N, c_1N) в операции #1. Алгоритм Р доказывающей стороны вычисляет значение Cmt хэширования_В <-H(t₁₁₁, …, t_1kN, е₁₁, …, e_1N) в операции #3. после генерирования отклика Rsp_i в операции #5, алгоритм Р доказывающей стороны генерирует отклик Rsp_i=(r_0i, t_01i, …, t_0ki, e_0i, c_1i) в случае, когда Ch_Bi=0, и генерирует отклик Rsp_i=(r_1i, t_11i, …, t_1ki, e_1i, c_0i) в случае, когда Ch_Bi=1.

С другой стороны, алгоритм V верифицирующей стороны генерирует (c₀₁, с₁₁, …, c_0N, c_1N) из (Ch_Ai, Ch_Bi, Rsp_i (где i=1-N) и (t₁₁₁, …, t_1kN, е₁₁, e_1N) в операции #6 и верифицирует то, соблюдается или нет равенство Cmt_A=(с₀₁, с₁₁, …, c_0N, c_1N) и Cmt_B=(t₁₁₁, …, t_1kN, е₁₁, e_1N). Выполняя такую модификацию, можно дополнительно повысить эффективность связи.

Дополнительный эффективный распараллеленный алгоритм, основанный на многостепенных расширенных алгоритмах, был описан выше.

Применяя многостепенной расширенный алгоритм, описанный выше, можно реализовать эффективную схему аутентификации открытого ключа, имеющую более высокую безопасность. Например, когда (q, n, m, N)=(24, 45, 30, 88) в расширенном алгоритме, который относится к 5-проходной схеме, длина открытого ключа составляет 120 битов, длина секретного ключа составляет 180 битов, и объем данных связи составляет 27512 битов.

Например, когда условие (q, n, m, N)=(22, 42, 40, 118) удовлетворено в случае многостепенного расширенного алгоритма, который относится к 5-проходной схеме, безопасность обеспечивается на одинаковом уровне. При выполнении этого условия, длина открытого ключа составляет 80 битов, длина секретного ключа составляет 84 битов, и объем данных передачи составляет 27814 битов. То есть путем применения многостепенного расширенного алгоритма, объем данных передачи можно поддерживать на том же самом уровне и можно значительно уменьшить длину открытого ключа и длину секретного ключа.

Условие можно модифицировать в (q, n, m, N)=(23, 28, 27, 97). В этом случае длина открытого ключа составляет 81 битов, длина секретного ключа составляет 84 битов, и объем данных передачи составляет 27145 битов. Кроме того, условие можно модифицировать в (q, n, m, N)=(24, 21, 20, 88). В этом случае длина открытого ключа составляет 80 битов, длина секретного ключа составляет 84 битов, и объем данных передачи составляет 28392 битов. При выполнении любого из этих условий достигается значительная эффективность.

4. Модификация схемы цифровой подписи

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

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

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

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

4.1.1. Алгоритм цифровой подписи (пример 1 структуры) (фиг.18)

Как показано на фиг.18, эффективный алгоритм (например, смотри фиг.6 и 8), который относится к 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₀₁, c₁₁, 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_N. Этот процесс представлен в виде Rsp_i<-Select(Ch_i, a_i). Rsp₁, Rsp_N, сгенерированные в операции #3 с помощью алгоритма Р доказывающей стороны, отправляются в алгоритм V верифицирующей стороны.

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

Алгоритм схемы аутентификации открытого ключа, представленный с помощью вышеизложенных операций #1-#4, модифицируется в алгоритм Sig генерирования подписи и алгоритм Ver верификации подписи, которые иллюстрированы на фиг.18.

Алгоритм 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<-Н(с₀₁, c₁₁, c₂₁, …, c_0N, c_1N, c_2N).

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

Процесс (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.1.2. Алгоритм цифровой подписи (пример 2 структуры: высокая эффективность) (фиг.19)

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

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

Сначала, со ссылкой на фиг.19, будет описана структура усовершенствованного алгоритма Sig генерирования подписи. Алгоритм Sig генерирования подписи включает в себя следующие процессы (1)-(4).

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

Процесс (2): Алгоритм Sig генерирования подписи вычисляет (Ch₁, …, Ch_N)<-H(M, с₀₁, c₁₁, с₂₁, …, c_0N, c_1N, c_2N). Здесь M представляет собой документ, к которому прикрепляется подпись.

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

Процесс (4): Алгоритм Sig генерирования подписи устанавливает (Ch₁, …, Ch_N, Rsp₁, …, Rsp_N) в качестве подписи.

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

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

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

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

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

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

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

4.2.1. Алгоритм цифровой подписи (пример 1 структуры) (фиг.20)

Как показано на фиг.20, эффективный алгоритм (например, смотри фиг.11, 13, и 16), который относится к 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<-Н(с₀₁, 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) для i=1-N. Здесь b₁, …, b_N, сгенерированные в операции #3 с помощью алгоритма Р доказывающей стороны, отправляются в алгоритм V верифицирующей стороны.

Операция #4 включает в себя процесс выбора ChB1, …, Ch_BN. ChB1, …, 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 включает в себя процесс (1) воспроизведения с₀₁, с₁₁, …, c_0N, c_1N, с использованием Ch_A1, …, Ch_AN, Ch_B1, …, Ch_BN, Rsp₁, …, Rsp_N и процесс (2) верификации Cmt=H(с₀₁, с₁₁, …, c_0N, c_1N с использованием воспроизведенных с₀₁, с₁₁, …, c_0N, c_1N.

Алгоритм схемы аутентификации открытого ключа, представленный с помощью вышеизложенных операций #1-#6, модифицируется в алгоритм Sig генерирования подписи и алгоритм Ver верификации подписи, которые иллюстрированы на фиг.20.

Алгоритм 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<-Н(с₀₁, с₁₁, …, c_0N, c_1N).

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

Процесс (4): Алгоритм Sig генерирования подписи генерирует b_i=(t_1i, e_1i) для i=1-N.

Процесс (5): Алгоритм Sig генерирования подписи вычисляет (Ch_B1, …, Ch_BN)<-Н(М, Cmt, Ch_A1, …, Ch_AN, b₁, …, b_N). Дополнительно, можно выполнить модификацию в (Ch_B1, …, Ch_BN)<-H(Ch_A1, …, Ch_AN, b₁, …, b_N).

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

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

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

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

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

Процесс (2): Алгоритм Ver верификации подписи вычисляет (Ch_B1, …, Ch_BN)=Н(М, Cmt, Ch_A1, …, Ch_AN, b₁, b_N). Когда модификация в (Ch_B1, …, Ch_BN)=H(Ch_A1, …, Ch_AN, b₁, …, b_N) выполняется в процессе (5), выполняемом с помощью алгоритма Ver верификации подписи, алгоритм Ver верификации подписи вычисляет (Ch_B1, …, Ch_BN)=H(Ch_A1, …, Ch_AN, b₁, …, b_N).

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

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

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

4.2.2. Алгоритм цифровой подписи (пример 2 структуры: высокая эффективность) (фиг.21)

Как показано на фиг.21, дополнительный эффективный алгоритм (например, смотри фиг.17), который относится к 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_A<-H(с₀₁, с₁₁, …, c_0N, c_1N). Cmt_A, сгенерированный в операции #1 с помощью алгоритма Р доказывающей стороны, отправляется в алгоритм V верифицирующей стороны.

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

Операция #3 включает в себя процесс (1) генерирования bi=(t_1i, e_1i) и процесс (2) вычисления Cmt_B<-Н(b₁, …, b_N) для i=1-N. Cmt_B, сгенерированный в операции #3 с помощью алгоритма Р доказывающей стороны, отправляется в алгоритм V верифицирующей стороны.

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

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

Операция #6 включает в себя процесс (1) воспроизведения c₀₁, с₁₁, …, c_0N, c_1N, b₁ …, b_N с использованием Ch_A1, …, Ch_AN, Ch_B1, …, Ch_BN, Rsp₁, Rsp_N, процесс (2) верификации Cmt_A=Н(с₀₁, с₁₁, …, c_0N, c_1N) с использованием воспроизведенных с₀₁, с₁₁, …, c_0N, c_1N, и процесс (3) верификации Cmt_B=H(b₁ …, b_N) с использованием воспроизведенных b₁ …, b_N.

Алгоритм схемы аутентификации открытого ключа, представленный с помощью вышеприведенных операций #1-#6, модифицируется в алгоритм Sig генерирования подписи и алгоритм Ver верификации подписи, которые иллюстрированы на фиг.21.

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

Сначала будет описана структура алгоритма Sig генерирования подписи. Алгоритм Sig генерирования подписи включает в себя следующие процессы (1)-(8).

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

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

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

Процесс (4): Алгоритм Sig генерирования подписи генерирует b_i=(t_1i, e_1i) для i=1-N.

Процесс (5): Алгоритм Sig генерирования подписи вычисляет Cmt_B<-H(b₁ …, b_N).

Процесс (6): Алгоритм Sig генерирования подписи вычисляет (Ch_B1, …, Ch_BN)<-Н(М, Cmt, Ch_A1, …, Ch_AN, Cmt_B). Дополнительно, можно выполнить модификацию в (Ch_B1, …, Ch_BN)<-H(Ch_A1, …, Ch_AN, Cmt_B).

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

Процесс (8): Алгоритм Sig генерирования подписи устанавливает (Cmt_A, Cmt_B, Rsp₁, …, Rsp_N) в качестве цифровой подписи.

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

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

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

Процесс (2): Алгоритм Ver верификации подписи вычисляет (Ch_B1, …, Ch_BN)=H(М, Cmt_A, Ch_A1, …, Ch_AN, b₁, b_N, Cmt_B). Когда модификация в (Ch_B1, …, Ch_BN)=H(Ch_A1, …, Ch_AN, Cmt_B) выполняется в процессе (6), выполняемом с помощью алгоритма Ver верификации подписи, алгоритм Ver верификации подписи вычисляет (Ch_B1, …, Ch_BN)=H(Ch_A1, …, Ch_AN, Cmt_B).

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

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

Процесс (5): Алгоритм Ver верификации подписи верифицирует Cmt_B=H(b₁, …, b_N) с использованием воспроизведенных b₁, …, b_N.

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

5. Алгоритм гибридного типа

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

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

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

5.1.1. Параллельно-последовательный алгоритм (фиг.22)

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

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

С другой стороны, в случае параллельно-последовательной структуры, сообщения (Cmt₁, …, Cmt_N) N раз отправляются из доказывающей стороны верифицирующей стороне на первом проходе. На втором проходе вызов Ch₁ отправляется один раз из верифицирующей стороны доказывающей стороне. На третьем проходе отклик Rsp₁ отправляется один раз из доказывающей стороны верифицирующей стороне. В дальнейшем, вызовы Ch₂, …, Ch_N и отклики Rsp₂, Rsp_N обмениваются последовательно между доказывающей стороной и верифицирующей стороной.

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

5.1.2. Последовательно-параллельный алгоритм (фиг.23))

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

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

В случае последовательно-параллельной структуры сообщение Cmt₁ отправляется один раз из доказывающей стороны верифицирующей стороне на первом проходе. На втором проходе вызов Ch₁ отправляется один раз из верифицирующей стороны доказывающей стороне. В дальнейшем сообщения Cmt₂, …, Cmt_N и вызовы Ch₂, …, Ch_N обмениваются последовательно между доказывающей стороной и верифицирующей стороной. После того, как вызов Gh_N отправляется из верифицирующей стороны доказывающей стороне, отклики Rsp2, Rsp_N N раз отправляются из доказывающей стороны верифицирующей стороне.

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

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

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

5.2.1. Параллельно-последовательный алгоритм (пример #1 структуры) (фиг.24))

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

В случае базовой структуры сообщение Cmt_A отправляется из доказывающей стороны верифицирующей стороне на первом проходе. На втором проходе число Ch_A отправляется из верифицирующей стороны доказывающей стороне. На третьем проходе вектор Cmt_B отправляется из доказывающей стороны верифицирующей стороне. На четвертом проходе вызов Ch_B отправляется из верифицирующей стороны доказывающей стороне. На пятом проходе отклик Rsp отправляется из доказывающей стороны верифицирующей стороне.

В случае параллельно-последовательной структуры #1 сообщения (Cmt_A1, …, Cmt_AN) N раз отправляются из доказывающей стороны верифицирующей стороне на первом проходе. На втором проходе число Ch_A1 отправляется один раз из верифицирующей стороны доказывающей стороне. На третьем проходе вектор Cmt_B1 отправляется один раз из доказывающей стороны верифицирующей стороне. На четвертом проходе вызов Ch_B1 отправляется один раз из верифицирующей стороны доказывающей стороне. На пятом проходе отклик Rsp₁ отправляется один раз из доказывающей стороны верифицирующей стороне. В дальнейшем Ch_A2, …, Ch_AN, Cmt_B2, …, Cmt_BN, Ch_B2, …, Ch_BN и отклики Rsp₂, …, Rsp_N обмениваются последовательно между доказывающей стороной и верифицирующей стороной.

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

5.2.2. Параллельно-последовательный алгоритм (пример #2 структуры) (фиг.25)

Далее, со ссылкой на фиг.25, будет описан другой пример структуры гибридного типа (здесь и далее по тексту называется как параллельно-последовательная структура #2). На фиг.25 изображена схема, иллюстрирующая алгоритм, имеющий базовую структуру, и алгоритм, имеющий параллельно-последовательную структуру #2.

В случае параллельно-последовательной структуры #2 сообщения (Cmt_A1, …, Cmt_AN) N раз отправляются из доказывающей стороны верифицирующей стороне на первом проходе. На втором проходе числа (Ch_A1, …, Ch_AN) N раз отправляются из верифицирующей стороны доказывающей стороне. На третьем проходе векторы (Cmt_B1, …, Cmt_BN) N раз отправляются из доказывающей стороны верифицирующей стороне. На четвертом проходе вызов Ch_B1 отправляется один раз из верифицирующей стороны доказывающей стороне. На пятом проходе отклик Rsp₁ отправляется один раз из доказывающей стороны верифицирующей стороне. В дальнейшем, Ch_B2, …, Ch_BN, отклики Rsp₂, Rsp_N обмениваются последовательно между доказывающей стороной и верифицирующей стороной.

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

5.2.3. Последовательно-параллельный алгоритм (пример #1 структуры) (фиг.26)

Далее, со ссылкой на фиг.26, будет описан другой пример структуры гибридного типа (здесь и далее по тексту называется как последовательно-параллельная структура #1). На фиг.26 изображена схема, иллюстрирующая алгоритм, имеющий базовую структуру, и алгоритм, имеющий последовательную параллельную структуру #1.

В случае последовательно-параллельной структуры #1 сообщение Cmt_A1 на первом проходе отправляется один раз из доказывающей стороны верифицирующей стороне. На втором проходе число Ch_A1 отправляется один раз из верифицирующей стороны доказывающей стороне. На третьем проходе вектор Cmt_B1 отправляется один раз из доказывающей стороны верифицирующей стороне. На четвертом проходе вызов Ch_B1 отправляется один раз из верифицирующей стороны доказывающей стороне. В дальнейшем, Cmt_A2, …, Cmt_AN, Ch_A2, …, Gh_AN, Cmt_B2, …, Cmt_BN, Ch_B2, …, Ch_BN обмениваются последовательно между доказывающей стороной и верифицирующей стороной. И, наконец, отклики (Rsp₁, …, Rsp_N) N раз отправляются из доказывающей стороны верифицирующей стороне.

В случае последовательно-параллельной структуры #1 обеспечивается безопасность от активного прикрепления. Кроме того, число интерактивностей составляет только 4N+1 раз.

5.2.4. Последовательно-параллельный алгоритм (пример #2 структуры) (фиг.27)

Далее, со ссылкой на фиг.27, будет описан другой пример структуры гибридного типа (здесь и далее по тексту называется как последовательно-параллельная структура #2). На фиг.27 изображена схема, иллюстрирующая алгоритм, имеющий базовую структуру, и алгоритм, имеющий последовательную параллельную структуру #2.

В случае последовательно-параллельной структуры #2 сообщение Cmt_A1 отправляется один раз из доказывающей стороны верифицирующей стороне на первом проходе. На втором проходе число Ch_A1 отправляется один раз из верифицирующей стороны доказывающей стороне. В дальнейшем Cmt_A2, …, Cmt_AN, Ch_A2, …, Ch_AN обмениваются последовательно между доказывающей стороной и верифицирующей стороной. После того как вызов Ch_AN завершен, векторы (Cmt_B1, …, Cmt_BN) N раз отправляются из доказывающей стороны верифицирующей стороне. Затем вызовы (Ch_B1, …, Ch_B1) N раз отправляются из верифицирующей стороны доказывающей стороне. И, наконец, отклики (Rsp₁, …, Rsp_N) N раз отправляются из доказывающей стороны верифицирующей стороне.

В случае последовательно-параллельной структуры #2 обеспечивается безопасность от активного прикрепления. Кроме того, число интерактивностей составляет только 2N+3 раз.

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

6. Приложение

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

6.1. Способ установки параметра системы

Приведенное здесь описание способа установки параметра будет дополнительным.

Коэффициенты многомерных полиномов

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

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

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

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

Число m полинома и число n переменной

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

Вышеизложенный интерактивный протокол представляет собой алгоритм верификации для верифицирующей стороны того, что "доказывающая сторона знает s, удовлетворяющий y=F(s) для y" с использованием пары ключей (открытого ключа y и секретного ключа s). По этой причине, когда интерактивность, принятая при верификации выполняется, вероятность того, что информация, которая показывает то, что "доказывающая сторона использует s во время интерактивности" известно верифицирующей стороне, является бесспорной. Дополнительно, устойчивость к коллизиям не обеспечивается для многомерного полинома F. По этой причине, когда вышеизложенный интерактивный протокол выполняется повторно и параллельно, трудно доказать, что безопасность от активной атаки надежно обеспечена без какого-либо условия.

Соответственно, изобретатели настоящей технологии рассмотрели способ побуждения информации показывать то, что "доказывающая сторона использует s во время интерактивности" будет не известно верифицирующей стороне даже при выполнении интерактивности, принятой при верификации. Дополнительно, изобретатели настоящей технологии разработали способ обеспечения безопасности от активной атаки, которая будет обеспечиваться даже в том случае, когда вышеизложенный интерактивный протокол выполняется повторно и параллельно. Этот способ представляет собой способ установки числа m многомерных полиномов f₁, …, f_m, которые используется в качестве открытых ключей со значением, достаточно меньшим, чем число n переменных. Например, m и n устанавливаются таким образом, чтобы 2^m-n<<1 (например, когда n=160 и m=80, 2^-80<<1).

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

При рассмотрении функции F: Kⁿ->K^m включающей в себя число т многостепенных полиномов с п переменными (где n>m), со ссылкой на фиг.29, число элементов области определения, не имеющей по второго прообраза, составляет не более, чем |K|^m-1. По этой причине, когда |K|^m-n устанавливается достаточно маленьким, вероятность выбора элементов из области определения, не имеющей второго прообраза, можно сделать пренебрежимо малой. То есть когда число m многостепенных полиномов f₁, …, f_m с n переменными устанавливается на значение, достаточно меньшее, чем число n переменных, можно обеспечить то, что два или более секретных ключей s существуют для открытого ключа pk. Следовательно, даже в том случае, когда интерактивность, принятая при верификации, выполняется, информацию, показывающую то, что "доказывающая сторона использует s во время интерактивности", можно предоставить так, чтобы она была не известной для верифицирующей стороны. Таким образом, безопасность от активной атаки обеспечивается даже в том случае, когда интерактивный протокол выполняется повторно и параллельно.

Как описано выше, за счет наложения условия установки, в котором число m многостепенных полиномов f₁, …, f_m с n переменными устанавливается на значение, достаточно меньшее, чем число n переменных (где n>m и предпочтительно 2^m-n<<1), безопасность можно обеспечить тогда, когда интерактивный протокол выполняется повторно и параллельно.

6.2. Способ реагирования на нерегулярный вызов

Ниже будет рассмотрен способ реагирования на нерегулярный вызов.

6.2.1. Способ реагирования доказывающей стороной

Далее будет рассмотрена вероятность того, что верифицирующая сторона выдает ложный вызов в интерактивном протоколе. Например, в случае 3-проходной схемы, доказывающая сторона отправляет сообщения (с₀, c₁, с₂) верифицирующей стороне и верифицирующая сторона отправляет вызов Ch=0 доказывающей стороне. В дальнейшем отклик Rsp, соответствующий вызову Ch=0, отправляется из доказывающей стороны верифицирующей стороне. До сих пор выполнялась нормальная интерактивность.

После этого предполагается, что верифицирующая сторона в дальнейшем будет оспаривать отклик Rsp, соответствующий вызову Ch=1, на доказывающей стороне. Если доказывающая сторона отправляет отклик Rsp, реагирующий на вызов Ch=1, верифицирующей стороне в ответ на вызов, секретный ключ может подвергаться утечке на верифицирующую сторону. На практике может иметь место утечка секретного ключа. Например, верифицирующая сторона может подделать отправку вызова Ch=0, а не вызов Ch=1 на втором проходе и может, кроме того, оспорить отклик Rsp, реагирующий на вызов Ch=1. С другой стороны, доказывающая сторона может неправильно понять, что биты вызова Ch, отправленные на втором проходе, превращаются в разные биты из-за ошибки связи.

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

6.2.2. Способ реагирования верифицирующей стороной

Далее будет рассмотрена вероятность того, что доказывающая сторона выдает себя за другое лицо и оспаривает повторную отправку вызова Ch. Например, предполагается, что доказывающая сторона отправляет сообщения (с₀, c₁, с₂) верифицирующей стороне в 3-проходной схеме, верифицирующая сторона отправляет вызов Ch=0 доказывающей стороне, и затем доказывающая сторона оспаривает повторную отправку вызова Ch. Когда верифицирующая сторона произвольно повторно выбирает вызов Ch в ответ на вызов, существует вероятность того, что выбран вызов Ch=1, который отличается от ранее отправленного вызова Ch=0. В этом случае вызов Ch=1 отправляется из верифицирующей стороны доказывающей стороне. Предполагается, что доказывающая сторона может отправить отклик Rsp, соответствующий вызову Ch=1, верифицирующей стороне.

В этом случае доказывающая сторона может отреагировать на вызов Ch=1, но может и не отреагировать на вызов Ch=0. То есть вероятность того, что доказывающая сторона вводит в заблуждение верифицирующую сторону, не вызывает сомнений. Например, доказывающая сторона может оспорить повторную отправку этого вызова Ch верифицирующей стороне, поскольку доказывающая сторона теряет вызов Ch. С другой стороны, верифицирующая сторона может рассматривать ранее отправленный вызов как потерянный из-за ошибки связи и повторно отправить вызов Ch в ответ на вызов доказывающей стороны. Затем, когда повторно отправленный вызов Ch отличается от ранее оправленного вызова Ch, подделка может быть успешной.

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

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

7. Пример конфигурации аппаратных средств

Каждый алгоритм, описанный выше, можно выполнить с использованием, например, конфигурации аппаратных средств устройства обработки информации, показанной на фиг.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 - это аббревиатура от словосочетания центральное процессорное устройство. К тому же, ROM - это аббревиатура от словосочетания постоянное запоминающее устройство. Более того, RAM - это аббревиатура от словосочетания оперативное запоминающее устройство.

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

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

Блок 918 вывода представляет собой, например, устройство отображения, такое как ЭЛТ, ЖКД, ПДП или ЭЛД, устройство вывода аудио, такое как динамик или наушники, принтер, мобильный телефон или устройство для факсимильной связи, который могут визуально или с помощью звука уведомлять пользователя о полученной информации. Более того, ЭЛТ - это аббревиатура от словосочетания электронно-лучевая трубка. ЖКД - это аббревиатура от словосочетания жидкокристаллический дисплей. ПДП - это аббревиатура от словосочетания плазменная дисплейная панель. К тому же, ЭЛД - это аббревиатура от словосочетания электролюминесцентный дисплей.

Запоминающее устройство 920 представляет собой устройство для хранения различных данных. Запоминающее устройство 920 представляет собой, например, магнитное запоминающее устройство, такое как накопитель на жестком диске (HDD), полупроводниковое запоминающее устройство, оптическое запоминающее устройство или магнитооптическое запоминающее устройство. HDD - это аббревиатура от словосочетания "hard disk drive" (накопитель на жестком диске).

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

Соединительный порт 924 представляет собой порт, такой как порт USB, порт IEEE1394, SCSI, порт RS-232C или порт для подключения устройства 930, подсоединяемого внешним образом, такого как оптический аудиотерминал. Устройство 930, подсоединяемое внешним образом, представляет собой, например, принтер, мобильный музыкальный плеер, цифровой фотоаппарат, цифровую видеокамеру или цифровой диктофон. Более того, USB - это аббревиатура от словосочетания "universal ser₁al bus" (универсальная последовательная шина). К тому же, SCSI - это аббревиатура от словосочетания "small computer system interface" (системный интерфейс малых компьютеров).

Блок 926 связи представляет собой устройство связи, которое будет подсоединяться к сети 932, и представляет собой, например, карту связи для проводной или беспроводной LAN, Bluetooth (зарегистрированный товарный знак) или WUSB, оптический коммуникационный маршрутизатор, маршрутизатор ADSL или устройство для контактной и бесконтактной связи. Сеть 932, подсоединенная к блоку 926 связи, сконфигурирована из сети, подсоединяемой проводным или беспроводным способом, и представляет собой, например, Интернет, LAN для использования в домашних условиях, связь в инфракрасной части спектра, связь в видимой части спектра, широковещание или спутниковую связь. Более того, LAN - это аббревиатура от словосочетания "local area network" (локальная сеть). К тому же, WUSB - это аббревиатура от словосочетания "wireless USB" (беспроводная универсальная последовательная шина). Более того, ADSL - это аббревиатура от словосочетания "asymmetric digital subscriber line" (асимметричная цифровая абонентская линия).

8. Заключение

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

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

(1) Устройство обработки информации, включающее в себя:

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

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

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

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

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

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

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

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

пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и установлены так, что полином G(x₁, х₂), определенный как G(x₁, х₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z, и 1≤z≤k).

(2) Устройство обработки информации по п.(1), в котором

блок генерирования сообщения выполнен с возможностью генерирования сообщения N раз (где N≥2), а

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

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

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

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

(3) Устройство обработки информации по п.(2), в котором

блок генерирования сообщения выполнен с возможностью генерирования сообщения N раз (где N≥2) и генерирования одного значения хэширования из сообщения N раз, при этом

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

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

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

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

(4) Устройство обработки информации, включающее в себя:

блок хранения информации для хранения пары многостепенных многомерных полиномов F=(f₁, …, f_m) и векторов y=(y₁, …, y_m)=(f₁(s), …, f_m(s));

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

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

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

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

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

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

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

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

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

пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается так, что полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z, и 1≤z≤k).

(5) Устройство обработки информации по п.(4), в котором

блок получения сообщения выполнен с возможностью получения сообщения N (где N≥2) раз с интерактивностью один раз, при этом

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

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

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

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

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

(6) Устройство обработки информации по п.(5), в котором

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

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

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

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

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

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

(7) Способ обработки информации, включающий в себя этапы, на которых:

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

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

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

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

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

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

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

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

где пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается так, что полином G(x₁, x₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, x_1n) (где l=1, 2), сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z, и 1≤z≤k).

(8) Способ обработки информации, включающий в себя этапы, на которых: с помощью устройства обработки информации, хранящего пару многостепенных многомерных полиномов F=(f₁, …, f_m) и векторы y=(y₁, …, y_m)=(f₁(s), …, f_m(s)),

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

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

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

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

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

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

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

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

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

пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается так, что полином G(x₁, х₂), определенный как G(x₁, x₂)=F(x₁+x₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z, и 1≤z≤k).

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

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

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

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

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

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

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

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

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

пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается таким образом, чтобы полином G(x₁, х₂), определенный как G(x₁, х₂)=F(x₁+х₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, x_1n) (где l=1, 2), был сконфигурирован как член, пропорциональный (x_n)^q(z) (где 1≤i≤n, q(z)=q^z, и 1≤z≤k).

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

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

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

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

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

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

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

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

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

пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи, причем

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

пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается так, что полином G(x₁, х₂), определенный как G(x₁, х₂)=F(x₁+х₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), сконфигурирован как член, пропорциональный (x_n)^q(z) (где 1≤i≤n, q(z)=q^z, и 1≤z≤k).

(11) Машиночитаемый носитель информации, хранящий программу, вызывающую выполнение компьютером:

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

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

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

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

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

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

пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи, причем

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

пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается так, что полином G(x₁, х₂), определенный как G(x₁, х₂)=F(x₁+х₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z, и 1≤z≤k).

(12) Машиночитаемый носитель информации, хранящий программу, вызывающую выполнение компьютером:

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

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

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

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

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

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

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

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

пара многостепенных многомерных полиномов F и векторы y представляют собой открытые ключи, причем

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

пара многостепенных многомерных полиномов F включает в себя полиномы f₁, …, f_m, определенные в кольце R характеристики q и порядка qk, и устанавливается так, что полином G(x₁, x₂), определенный как G(x₁, х₂)=F(x₁+х₂)-F(x₁)-F(x₂) по отношению к векторам x₁=(x_1l, …, x_1n) (где l=1, 2), сконфигурирован как член, пропорциональный (x_1i)^q(z) (где 1≤i≤n, q(z)=q^z, и 1≤z≤k).

(13) Устройство по любому из пп.(1)-(6), в котором тип, описанные выше, имеют зависимость m<n.

(14) Устройство по п.(13), в котором m и n, описанные выше, имеют зависимость 2^m-n<<1.

Примечание

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

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

Перечень ссылочных позиций

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

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

V - алгоритм верифицирующей стороны

Sig - алгоритм генерирования подписи

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