Степень равномерности систем HFE

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 13:30, 2 декабря 2015.
The Degree of Regularity of HFE Systems
HFE.png
Авторы Vivien Dubois[@: 1],
Nicolas Gama[@: 2]
Опубликован 2010 г.
Перевели Arseniy Kolobaev
Год перевода 2011-2015 г.
Скачать оригинал


Содержание

Аннотация:

HFE это открытый ключ схемы, представленный Патарином в 1996 году. HFE открытый ключ, который представляет собой обширную систему многочленов с множеством переменных над малым конечным полем. Эта система является результатом некой секретной комбинации, на основе которой владелец может решить его в любом произвольном векторе. В то время как безопасность криптосистемы зависела от системы сложности решения открытой системы без люка информации, в 2002 году Фожер экспериментальным путем установил, что базисные вычисления Гренбера работают гораздо лучше в определенных случаях HFE, чем на произвольных системах. В частности Фожер отметил, что регулярное поведение базисных вычислений Гренбера разрушаются в гораздо меньше степени, чем ожидалось для произвольных систем, которые позволяют завершить вычисления намного раньше. Учитывая это отличительное свойство, Фожер и Жу в 2003 году показали отображение HFE систем по отношению к другому многомерному кольцу, представляющему в частности алгебраическую структуру этих систем. Тем не менее, они не предложили фактического вычисления степени равномерности системы HFE над GF (2) с использованием независимых результатов на переопределенной системе уравнений. Однако в случае больших основных полей она остается полностью нерешенной. В данной работе приведены дополнительные свойства систем HFE, которые в большей степени существенны как размер основного возрастающего поля. Используя это свойство в стандартном комбинаторном подсчете можно сказать, что оно дает возможность жесткой численной оценки систем HFE для каких-либо параметров.

Ключевые слова:

  • многомерные многочлены
  • HFE
  • алгебраический криптоанализ

Вступление

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

Криптографическая (криптосистема) система HFE. Одними из самых известных предложений в этой сфере были Скрытые уравнения поля криптографической системы, представленные Патарином в 1996 году. HFE основывается на изящной идее, представленной Мацумото и Имаи в 1988 году путем получения множества уравнений из уравнения с одной переменной над расширенным полем. Когда уравнение с одной переменной может быть эффективно решено, то тоже самое применимо и для многомерной системы, доступ к уравнению с расширенным полем ограничен секретной линейной биекцией на переменной и уравнении. Более формально, пусть Fq - конечное поле, содержащее q элементов, φ - некоторая линейная биекция Fqn, расширение степени n Fq, до . Такая линейная биекция определяется выбором линейной основы . Для любого многочлена функция на , сопоставляется с функцией над . В HFE, многочлены Р имеют небольшую степень для обеспечения эффективного нахождения корня. Кроме того, они имеют специальную форму, которая гарантирует, что является квадратичной. Эта функция состоит из секретной линейной биекции S, T: , и результатом является открытая функция. HFE могут быть использованы в качестве схемы подписи, а также, с некоторыми незначительными механизмами, такими как схема шифрования [1]. Существует много различных вариантов и предложений потенциальных улучшений.

Безопасность систем HFE. Основной вопрос состоит в том, является ли открытая функция односторонней функцией. Поиск прообраза открытой функции такой же как нахождение соответствующей системы квадратных уравнений. Обозначим MQ (Q, N) множеством системы N квадратных уравнений в п переменных над , а HFE (Q, N, D) - подмножеством HFE систем, где D является параметром, который контролирует степень внутреннего многочлена P. Два направления работы до сих пор не в состоянии отличить HFE системы от случайных систем MQ. Одно из направлений в работе, предложенное в [2], целями которого являются так называемые дифференциальные свойства HFE и возможность воспроизведения отличительных признаков с доказательством сложности всех параметров (Q, N, D). Другие направления работы, предложенные в [3][4][5] и непосредственно цели затруднений задач прообраза HFE системы. Поскольку затруднения в проблеме прообраза систем HFE в конечном счете остаются под вопросом, хотелось бы уточнить какое преимущество раскрывают методы, используемые во втором направлении работы и как это свойство зависит от параметров (Q, N, D). Пока что доступна следующая информация.

1. Экспериментальным путем с помощью алгоритмов вычисления базисов Гребнера [6][7] были получены следующие доказательства. Эти алгоритмы проходят через комбинации с полиномиальными коэффициентами из данного набора многочленов и генерируют дополнительные многочлены, которые могут быть использованы для решения системы.
2. Атаки касаются только систем над F2. Эксперименты для различных значений N и D свидетельствуют о том, что степень комбинации, необходимая для вычисления базиса Гребнера (для градуированных упорядочения терминов) системы HFE зависит только от D при достаточно больших n [6]. К сожалению, о расширении этого свойства для больших значений Q не сообщалось. В самом деле, некоторые авторы [8] утверждают, что размер поля должен оказывать сильное негативное влияние на вычисление и наблюдается это на экспериментах с использованием пакета Magma [9].
3. С научной точки зрения, качественное наблюдение было дано в [4] и в нем говорилось о том, как осуществляются комбинации на открытых полиномах, которые соответствуют связанным операциям на внутреннем многочлене. Хотя это явно инициировано путем исследования систем HFE, не было соблюдено вычисление теоретической оценки сложности. Тем не менее, авторы работы [5] показали, что при q = 2, оценка сложности может быть эвристически производена от результатов на переопределенной системе MQ.

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

Наш вклад. Последние исследования о сложности алгоритмов базиса Гребнера концентрируют внимание на понятие степени регулярности системы полиномов [10][11]. Грубо говоря, степень равномерности является наименьшей степенью, при которой происходит нетривиальное падение степени среди алгебраических комбинаций вводимых многочленов. Степень равномерности системы HFE над F2 была экспериментально обнаружена в некотором диапазоне параметра [4] и асимптотически ограничена сверху в [5] с использованием результатов [10][11]. В этой статье мы предлагаем способ вычисления численной границы степени равномерности системы HFE над любым полем и при любых параметрах. В настоящее время это достигается с помощью предыдущих идей и методов [4] [5][10][12] в сочетании с, по-видимому, незамеченным дополнительными свойствами системы HFE, которые становятся все более существенными, когда размер основного поля растет.

Организация статьи. В разделе 2 мы определим степень равномерности системы многочленов и свяжем это понятие с вычислением базиса Гребнера. В разделе 3 мы определим системы HFE более подробно и установим несколько обозначений. В разделе 4 мы отобразим задачу вычисления степени равномерности для некого многомерного кольца, где структура алгебраической системы HFE является очевидной. В разделе 5 мы покажем, как вычислить степень равномерности этих подсистем с использованием классических методов, таких как в [10][12], но с особыми свойствами многочленов, которые будут в нашем распоряжении.

Мы введем численные оценки многих параметров. В разделе 6 мы получим оценки сложности алгебраических атак на HFE.

Алгебраические свойства системы полиномов

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

Решение систем многомерных уравнений.

Предположим, что мы столкнулись с проблемой нахождения общих корней системы полиномов в многомерном кольце R над полем. Будет ли эта система достаточно изменчивой, чтобы ее можно было решить вручную, возможно кто-то попытается объединить заданные полиномы, чтобы получить из них “упрощенные” т.е. сделать их проще, чтобы найти пространство для решений. Например, можно попытаться получить полином из меньшего числа переменных, или с меньшей суммарной степенью. В любом случае, сочетание заданных полином всегда сводится к рассмотрению формы полинома для некоторого многочлена, кратного . Следовательно, эти полиномы являются линейными комбинациями с коэффициентами в R. И цель в том, чтобы найти такую линейную комбинацию в некотором выделенном подпространстве Р.

Чтобы сделать это механически, можно рассмотреть две основные стратегии. Либо выбрать один из априорных поисков места для (например, многочлены со степенью при некоторых границах) и один представляет их коэффициенты в линейной алгебре. (Это основная идея алгоритма XL [5,19].). Или определяет приоритетный список частей, которые должны быть исключены (так называемое упорядочение) и один систематический главный член осуществляет сокращение на многочленах и новые многочлены, которые создаются в результате этого процесса, не могут быть спрогнозированы в том плане, что любая дальнейшая комбинация сводится к нулю. (Это основная идея алгоритмов базиса Гребнера [3,14,10,11].). Эти две стратегии не столь различных, как может показаться. Действительно, для уменьшения главных частей многочленов одну от другой, определяются cсоответствующие наборы множителей , которые необходимы для этого. Тогда остается применить линейную алгебру на результате комбинации и итерировать многочлены с новыми главными частями, которые могут быть найдены в этом процессе. В любом случае, это удобно для организации доступных комбинаций к их полной степени. Для любого целого , пусть будет множеством комбинаций в степени d кратной . Это линейное подпространство всех многочленовстепени не выше d. Эта статья сосредоточена на собственных параметров многочленов,, который мы называем степенью равномерности. Этот параметр был введен в [2,1].

Это обычно рассматривается как основной параметр сложности для следующих интуитивный причин. Пусть А будет алгоритмом, который вычисляет такие комбинации и индексации выполнения шагов t, можно считать подпространством [А(T)] из комбинации степени d кратные, которые вычисляются посредством A до t. Очевидно, что . Теперь, выберите выделенное подпространство . Существует элемент среди комбинаций в степени d, где пересечение с и не равно нулю и такая комбинация была обнаружена в алгоритме A перед действием t если . Когда полиномы не слишком конкретные, то пересечение и , как ожидается, будет отлично от нуля лишь при сумме соответствующих величин, превышающих собственную величину . В этом случае любой алгоритм можно рассматривать согласно комбинации в степени D и найти ненулевой элемент .

Чтобы быть уверенным в нахождении действия t, если . С другой стороны, если пересечение и будет отлично от нуля при значительно меньшей степени, чем ожидалось, то для случайных подпространств можно предположить, что полиномы не являются случайными. Интересным выбором выделенного подпространства являются многочлены низкой степени. Например, можно рассмотреть вопрос о существовании ненулевого многочлена степени, строго меньшего, чем d среди комбинаций в степени d. Такая комбинация называется падением степени и наименьшей степенью, до которой такое падения происходит, является степень равномерности. Точное определение будет представлено в дальнейшем. Алгоритм A находится с помощью степени равномерности, когда на некотором действии t его комбинация подпространства в степени D содержит степень падения. На данный момент, стоит отметить, что при использовании базиса Гребнера лучше использовать упорядоченный алгоритм, конкретной степени. Действительно, в этом случае новые главные части ограничены среди наименьших одночленов степени. Степень равномерности позволяет различать системы многочленов из случайных. Кроме того, любая степень падения может дать новый набор кратный степени d или даже ниже, и который в дальнейшем можно сочетать с существующими комбинациями. Кроме того, для измерения V A (см. 561 страницу) приходится применять больше действий, которые подобны коэффициенту (коэф. возрастания) d и затем одновременно происходит понижение степеней. В свою очередь, падение этих степеней влияют на появление новых степеней в меньшей степени. Каждая из этих степеней падает достаточно низко, чтобы решить систему (например, системы линейных многочленов) или начинает вычисление, пока не получится базиз Гребнера.

Системы с уравнениями поля над конечным полем.

В параметрах криптографических схем, коэффициент конечного поля (с элементами q) и решение находятся с помощью координат в этом конечном поле. Пусть обозначает переменную Р. Затем находятся пути решения систем с дополнительным уравнением .Эквивалентность, с описывается в значении , все мономы в R могут быть уменьшены в соответствии с правилами .Тогда все комбинации многочленов можно рассматривать как приведенное кольцо .

Тогда как в дальнейшем мы вычисляли степень регуляризации неопределенной систем в приведенном кольце, она служит верхнее ограничивающей степенью регуляризации открытой системы HFE с точными многочленами n. В этом случае ожидаемое число N-решений вряд ли будет больше одного и можно показать, что базис Гребнера для любого упорядочения, которое уточняет содержание степени n будет N линейно независимым многочленом в 1 степени (см. полную версию). Таким образом, эти параметры облегчают нахождение решений из базиса Гренбера. Так как в дальнейшем нам встретится система квадратичных полиномов, то для удобства мы уточним следующие определения для данного случая. Пусть будет системой квадратичных многочленов в . Для любого целого рассмотрим подпространство комбинации где имеют степень не более d − 2 в . По определению это изображение в пространстве на плоскости.

Важным наблюдением является то, что ядро всегда содержит предсказуемый ненулевой набор, называемый тривиальной сизигией. Примерами тривиальной сизигии является комбинация над k-наборов с для некторого i, j и в другом случае 0. Формальное определение тривиальной сизигии состоит в следующем. Для неизвестных множеством k-наборов над таких как Для любых многочленов над мы называем тривиальной сизигией из , где определения k-наборов в точке . При поиске степени падания нас интересует только подпространство , образованное старшей степенью однородного части образа . Это пространство, образованное однородной частью комбинации степени d , где является однородным многочленом степени d−2. Мы определяем падение степени d из как k-набор из степени d − 2 однородной полиномы, т.к. часть однородной степени d равна 0.Тривиальные сизигии однородных частей степени d − 2 из в степени d − 2 обычно падает и мы называем это тривиальным падением степени. Мы называем степень регулярности из наименьшим d, которое не является тривиальным падением из , существующим в степени d.

Определение системы HFE

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

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

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

ψ.

Так же напомним, что возведение в степень q линейно и различные n, возведенные в q на называются изображения (значение) Фробениуса. Если говорить более детально, то для любой возрастающей функции , мы называем q степенью из Xa суммы , где является разложением a на основе q. В частности, константы имеют степени q в 0 степени и изображения Фробениуса имеют степень q в1 степени. Так как любая функция является линейной комбинацией степенных функций, то определим степень q как максимальную степень значения переменной. Следующие предположения обеспечивают нас следующим: изображения в q степени в и в степень .


Предположение 1. Пусть S произвольная линейная биекция из в . для любого целого числа , определяет биекцию из полиномов в с q в степени d в набор чисел из n над со степенью d.

Пожалуйста, обратитесь к полной версии доказательства. Теперь мы готовы определить системы HFE. Напомним, что введение открытого ключа HFE это данные n координат многочленов состава , где является линейной биекцией, из в , T линейная биекция из в и P является функцией над , которая как и многочлен имеет вид где D является параметром схемы. Для любой линейной биекции S, мы называем системы HFE систем , которые являются изображениями многочленов над формой. Из предыдущего предположения мы видим, что системы HFE квадратичные и единственная особенность этого класса в том, чтобы соответствовать многочлену в степени выше ограниченного . Так как T является линейной биекцией на открытом ключе HFE, то имеет все алгебраические свойства системы HFE.

Комбинация HFE полиномов

В этом разделе мы обозначили комбинации системы HFE, чтобы связать с ними операции на определение общего полинома в . Это соответствие было изложено в [4] и раскрыто здесь. На самом деле это зависит от конкретной формы HFE, определяющей многочлены и следовательно будет справедливой для структуры любой аналогичной криптографической системы. Для упрощения обозначений мы обозначим . Этот раздел представляет собой цепочку технических моментов, которые необходимы для полного изложения. Для быстрого чтения можно сразу перейти к пункту 4.4.


Из комбинации в в комбинацию Из комбинации в   R q {\displaystyle \ R {q}} в комбинацию   R q n {\displaystyle \ R {q^{n}}}

Пусть P будет любым полиномом в и . Мы определили комбинацию как линейную комбинацию с коэффициентами в . Таким образом, набором из n-чисел линейной комбинации над является произведение n x n матрицы над . Из предположения 1 следует, что <math<\ \phi_{s^{-1}} </math> линейная биекция и линейного отображения (изображения) на к линейной комбинации изображений Фробениуса над . Мы уточнили этот результат, когда в и оказалось вместо и .


Предположение 2. Пусть будет произвольной линейной биекцией из в . Существует линейная биекция из , где матрица n x n над будет такой же для любого и в .


Доказательство. Мы построили (начертили) от руки, рассматривая множество постоянных функций P=a с a в больше (выше) единицы. Поскольку линейна, нам нужно рассмотреть только P=a для a над основой . Для любого i=1, пусть обозначает значение S на каноническом i-том векторе из . Для любого , является i-ым столбцом из и должен быть установлен в . и быть линейным для линейности . Рассмотрим , чье значение равно нулю. Затем будет линейной биекцией для любого i=1,…,n и мы имеем .. Единственным решением это обратимой системы является , которое доказывает, что инъективно. Сурьективность следует из , отображающей подпространство одинаковой размеренности над . Уравнение (1) над константой также показывает, что степень q из равна степени из . В частности для любого P в степени 2q и для , мы определим и с другой стороны для Предположение 1. Для любого , является биекцией .

Доказательство. преобразовывается из набора из n чисел в степени q в матрицу n × n степени . Обе линейные оболочки имеют одинаковую размерность над , согласно 1 предположению и, следовательно, являются взаимной биекцией. Наконец, свойство имеет сходство с и оценивается в частности как P. Так как размерность является n раз размерностью и , то они являются размерностью над и над , то свойство подразумевает следующее: .

Из степени падения в в степень падения q в Из степени падения в   R q {\displaystyle \ R {q}} в степень падения q в   R q n {\displaystyle \ R {q^{n}}}

При рассмотрении степени падения, единственное, что действительно интересно так это порожденное ограниченное пространство части старшей однородной степени. Для любого квадратного полинома в и любого числа , пусть V h d обозначает подпространство, генерируемое однородной частью степени d многочленов . Аналогичным образом, для любого многочлена P q-степени 2 в и любое целое число , пусть обозначает подпространство q в степени d однородного многочлена . Довольно вероятно, что мы получим:

Предположение 2. Пусть в и . Тогда для любого , существует линейная биекция из

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

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

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

Тривиальные Сизигии и Тривиальная Степень Падений

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

Пусть обозначает множество набора из чисел над такое как . Для любых многочленов в мы вычисляем значение тривиальных сизигиев в наборе чисел из в в точке .Как условное обозначение, пусть обозначает множество тривиальных сизигий . Элементы <math.\ \bar{R}_q </math> являются многочленами в обоих и . Для любого монома в , , пусть , обозначает их степени в ,math>\ x_1,...,x_n </math> и соответственно. Поскольку переменные будут специализированны на квадратичных многочленах в , то мы обозначим (определим) (1, 2) степенью мономов в как и (1, 2) степень многочлена в как максимальную (1, 2) степень его мономов. Следовательно, любой элемент со степенью (1,2) дает элемент <math\ T_q \left (p_1,...,p_n \right ) </math> со степенью . Мы называем тривиальными сизигиями с предполагаемой степенью элементов , которые соответствуют элементу , имеющему степень (1,2) . Тривиальные сизигии с предполагаемой степенью обозначены . С другой стороны, можно аналогично рассмотреть вопрос о расширении с дополнительной переменной , и определить как набор из чисел над таких как . Для любого в , пусть обозначает вычисление значения набора из чисел в точке . Наконец, для любого -степени 2 и любых чисел , пусть обозначает элементы, соответствующие элементам , имеющим (1,2) степень . Из серии простых обобщений предыдущих результатов, мы можем показать (см. полную версию). Свойство 4. Пусть в в степени 2 и . Для любого ,

Отображение степени равномерности от к Отображение степени равномерности от   R q {\displaystyle \ R {q}} к   R q n {\displaystyle \ R {q^{n}}}

Напомним, что степень равномерности системы квадратичных полиномов является таким наименьшим целым , что нетривиальная степень падения существует в степени . В предыдущей системе обозначений является наименьшим, таким как ядро строго больше чем . Теперь пусть будет произвольной линейной биекцией из к и в такое же как . Затем имеет в степени 2 и по Равенству 2 и по Свойству 3.

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

Многомерное представление в . Нашим первым шагом является простое альтернативное обозначение для элементов . Эта запись была предложена в пункте [9]. Как уже было замечено, мы можем разделить любую степень в соответствии с разложением в показателя . Теперь просто введем различные обозначения для Фробениуса : для пусть обозначает . Заметим, что для любого , , где индексы берутся по модулю . Использование этих отношений для любой степени соответствует уникальному многомерному моному в . Он тривиально расширяется для всех многочленов в . Сложение и умножение совместимо с этой записью. Таким образом, отождествляется как кольцо с . Наряду с этой идентификацией, степень становится степенью в многомерной кольце. Кроме того, для любого многочлена в , пусть обозначает последовательность Фробениуса. Для любого , где индексы равны модулю . Когда имеет в степени 2, то его Фробениус является многомерным квадратичным многочленом. Так как -множество действительно выражено через Фробениуса, то для удобства они переименованы дальнейшего обозначения. Следовательно, переименовывается на

Кольцо переименовывается в . Множество переименовывается в -чисел над таких как . Следовательно, идентифицируется с . И элементы <math\> T_{q^n} \left (P_0,...,P_{n-1} \right )_{d-2}^h являются степенью однородных частей элементов . Наконец, наша характеристика (свойство 5) переписывается, когда .

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

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

Свойство 7. Степень равномерности квадратичных многочленов в равна степени равномерности степени двоих однородных частей.

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

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

Доказательство. – комбинация в , для любого в . Любое слагаемое может быть разделено хотя бы одним из , т.к. нулевой степени. Любое слагаемое может иметь степень только в единственной неопределенности, и не более во всех остальных , т.к. имеет степень не более для любого . Поэтому, любое слагаемое точно имеет степень в одной неопределенности, и не более в остальных. Следовательно, предполагаем однозначно определенное распределение . Используя однозначно определенные многочлены из мы создаем элемент из , определяя для каждого , что (индексы по модулю ). Заметим, что слагаемые состоят из слагаемых , разделенных одной неопределенностью до степени . Как результат, каждый из них имеет абсолютную степень в меньшую (на ) чем у порождающей. В частности, когда имеет (1,2)-степень не более чем , то соответственно имеет такие же слагаемые (1,2)-степени , как и у , т.к. они отличаются в слагаемых, меньших (1,2) – степени. Следовательно, мы заканчиваем с указанной характеризацией, которую мы использовали в этой части. Свойство 9. Пусть - квадратичный однородный многочлен в . Степень равномерности в может быть вычислена, как наименьшее , такое, что степень является однородным набором из элементов , удовлетворяет условию: и не состоит из элементов .

Предел степени равномерности HFE систем

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

Верхний предел степени равномерности

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

Которые взаимосвязаны следующим образом:

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

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

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

Случай HFE систем

В [15] было замечено, что когда получается из фробеунисова HFE многочлена они выражаются через множества малых сдвигов путем последовательных переменных: выражается через до , - через до - через до (индексы по модулю ). Затем авторы отметили, что следствие этого свойства состоит в том, что небольшие подсистемы многочленов охватывают лишь небольшое подмножества возможных переменных. Последовательные подсистемы заданного размера являются эквивалентными относительно циклового сдвига, мы рассмотрим подсистем , где . Подсистема выражается через первые переменных, где для всех и после. Степень равномерности ограничена сверху соответствующей степенью равномерности подсистемы для всех . Действительно, падение степени соответствует падению степени с нуля на последних координатах. С другой стороны, в разделе [5.3] (свойство 11) мы покажем, что всегда, когда падение степени не является тривиальным для его выполнение с нулем на последних координатах также не является тривиальным для . Поэтому, авторы [15] вычислили приблизительную степень равномерности для любой подсистемы , используя асимптотическую формулу [2]. Для этого необходимо, чтобы и, полагается, что квадратичный полином удовлетворяет условию, для которого формула является верной. Вместо этого мы используем предыдущую границу насыщения: мы ограничим степень равномерности сверху, применив границу к . Следовательно, она ограничена сверху наименьшим , таким что: (3) Где показывает зависимость от первых переменных. Т.к. данный верхний предел использует свойство, показанное в [15], то мы будем называть его GJS границей.

Рассмотрим дополнительное свойство HFE систем. Т.к. многочлены получаются из одночленов , где , то комбинации этих многочленов необходимо получать из одночленов, которые делятся на для некоторых и . Пусть – подпространство, порожденное такими одночленами. Для любой подсистемы мы улучшаем GJS границу, используя наименьший , такой что: (4) Где – подпространство, порожденное степенью одночлена для первых переменных. Различия между и значительно увеличиваются вместе с ростом . На самом деле, при фиксированных и , средний вес Хэмминга мультистепеней степени уменьшается с ростом . Относительное число одночленов содержащих 2 переменных, расстояние между которыми не превышает (индексы по модулю ), растет медленнее. Мы назваем HFE границу верхним пределом степени равномерности , полученную их недавнего улучшения. Теперь для любых и мы вычислим вышеуказанные размерности (показатели), используя формулы индукции и получим соответственное численное значение верхнего предела.

Формулы индукции для вычисления нашего верхнего предела

Мы покажем, как вычислить размерность (показатель) для , и , при любых . Размерность (показатель) кольца - количество однородных одночленов степени для переменных, где все экспоненты находятся в пределах и . Очевидно, что для , или , ; для всех и когда , , то удовлетворяет индукции . Другими словами, -тая часть ряда части . В частности, при .

Количество одночленов, возникающих в комбинациях HFE. Пусть – размерность (показатель) дополнения к , для любых и . Это количество одночленов степени в последующих переменных, с экспонентами по модулю , таких что все переменные с ненулевыми экспонентами (индексы по модулю ) находятся на расстоянии хотя бы позиций. Сначала проигнорируйте то, что расстояние между индексами взято по модулю , а также то, что мы разрешаем (частный случай) и иметь ненулевые степени. Тогда имеет вид простой «треугольник Паскаля» формулы , для любой , где: и тогда, когда или . Когда меньше, чем , то искомая размерность (показатель) совпадает с , т.к. последние переменные имеют нулевые экспоненты. В другом случае, когда расстояние должно быть взято по модулю , таким образом, мы получаем все значения путем рассмотрения сегментов, определяемых одночленами, содержащими , содержащими содержащими и одночленами, которые не содержат их вовсе. Следовательно, . И,наконец, .

Размерность (показатель) тривиальных сизигиев в степени . Определим используя . Нашим первым шагом станет нахождение генераторов модуля .

Свойство 10. -мерный набор является элементом тогда и только тогда, когда он образует комбинацию с коэффициентами многочлена -мерного набора. Доказательство. Разобьем на для каждого -мерного набора . -мерный набор <mayh>\ \left M_0,...,M_k \right ) </math> является элементом тогда и только тогда, когда равен по модулю . Это равнозначно тому, что (без модуля). Мы докажем, что последнее равенство предполагает, что является комбинацией . Сделаем это методом индукции для . Если , тогда, если или равны нулю, то они оба равны нулю, в другом случае , а и . Допустим, что свойство выполняется для . Тогда, если равно нулю, мы наталкиваемся на свойство для , в другом случае все , должны содержать и должны являться фактормножеством , отсюда следует, что , откуда мы получаем . Возвращаясь к основному доказательству мы получаем, что , где последний -мерный набор можно разложить в . Т.к. и являются однородными для переменных , то части (1,2)-степени элементов раскладываются этими генераторами. Заменим переменные на , тогда тривиальные сизигии примут вид

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

Свойство 11. Для с точностью до степени равномерности , ( Следовательно, степень равномерности ограничена сверху степенью равномерности ,math>\ \hat{P}_0,..., \hat{P}_{k-1} </math> из-за взаимоуничтожения , который не является тривиальным в смысле того, что не является тривиальным в смысле .) Доказательство. Для начала напомним, что имеет степень 2, а имеет степень . Поэтому, не имеет элементов степени 0 или 1. Для любых и определим множество Заметим, что для это множество в точности совпадает с . Мы покажем, что для с точностью до степени равномерности и для , . (6)

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

Второе уравнение предполагает, что лежит в , что показано в (6). Теперь, используя (6), от до ,