Регистрация Войти
Рейтинг:1
avatar Crypto

Использование неприводимых кодов Гоппы в схеме МакЭлиса

флаг in
yoyo

Есть ли криптографическая причина для использования непреодолимый полином Гоппы $г$ в схеме Макэлиса? Неприводимость не нужна для определения пригодного для использования кода, поэтому я предполагаю, что существует какая-то структурная атака на приводимые полиномы? [Одно предостережение заключается в том, что презентация, которую я видел для декодирования Паттерсона, использует несводимость, но не нужно использовать этот алгоритм (и он не используется, например, в реализации FPGA). здесь).]

Генерация ключей уже достаточно раздражает без обеспечения неприводимости ИМХО. Единственное, о чем я могу думать, это то, что неприводимость определенно гарантирует, что опора $L$ не пересекается с нулями $г$ при сохранении равномерных распределений по выбору $г$ и $L$

68
0 + 0
Рейтинг:2
Daniel S avatar Crypto
флаг ru
Daniel S

Как вы заметили, $г(Х)$ не может иметь корней в $L$ и поэтому мы должны выполнить хотя бы один полиномиальный НОД, чтобы проверить это.

Для двоичных кодов Гоппы мы также должны проверить, что $г(Х)$ не имеет повторяющихся корней, иначе доказательство минимального расстояния может быть нарушено. Это потребует еще одной проверки GCD.

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

0 + 0
флаг in
yoyo
Я не учел разделяемость (необходимую для "ускорения" на минимальном расстоянии) - я мог купить это как достаточную причину (вместе с оценкой по $L$). Есть ли лучшие тесты на несводимость, чем тот, на который вы ссылаетесь? ($x^{q^n}-x$ довольно большой, или, может быть, я недостаточно эффективно выполняю некоторые полиномиальные арифметические операции.) В статье, на которую я ссылаюсь, берется случайный элемент из соответствующего расширения и вычисляется минимальный полином ( надежда на победителя), а не отказ от выборки случайных полиномов.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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