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

Shamir Secret Sharing и замена интерполяции Лагранжа

флаг co
Macko

Shamir Secter Sharing в стандартной версии (бумажной версии) довольно хорошо работает с интерполяцией Лагранжа для создания большего количества долей. Проблемы возникают, когда вы генерируете больше пар (xi, yi) и пытаетесь восстановить секрет из долей, которые как бы далеки друг от друга. Алгоритм работает, но значение секрета, которое вы получаете, несколько отличается, что неприемлемо для использования в продакшене. Я думаю, что это связано с феноменом Рунге.

Итак, какие есть варианты? Можно ли использовать какие-либо лучшие интерполяции? Может быть, есть какой-то способ генерации (xi,yi) из секрета, который мог бы давать стабильные результаты по Лагранжу?

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

85
0 + 0
Morrolan avatar
флаг ng
Morrolan
Это не кажется правильным. Вы работаете в конечном поле с целыми значениями? В парах коэффициент/значение не должно быть потери точности, поэтому интерполяция (с достаточным количеством точек) должна давать точный результат. См. также это: https://crypto.stackexchange.com/questions/14608/does-runge-phenomenon-affect-shamirs-secret-sharing-scheme?rq=1
3
Ответить
Macko avatar
флаг co
Macko
Я не работаю в конечном поле. Я генерирую 5 акций при запуске с порогом, установленным на 2. Затем я генерирую еще 5, передавая в качестве входных данных как минимум 2 акции из начального поколения.
0
Ответить
poncho avatar
флаг my
poncho
Если вы не работаете в ограниченной области, почему вы считаете, что то, что вы делаете, безопасно?
0
Ответить
Macko avatar
флаг co
Macko
Итак, вы утверждаете, что если я сделаю интерполяцию в конечном поле, Лагранж будет работать правильно? Остановимся на вопросе...
0
Ответить
Morrolan avatar
флаг ng
Morrolan
Да. В конечном поле вы не пострадаете от какой-либо потери точности, поэтому интерполяция гарантированно даст исходный многочлен, с которого мы начали. См. Ответ, связанный выше, для более подробной информации. Но важно понимать, что работа в ограниченной области **абсолютно необходима** для обеспечения безопасности.То, что Шамир делится секретами с реалами, дает очень мало с точки зрения безопасности.
0
Ответить
Daniel avatar
флаг ru
Daniel
@Morrolan Я публиковал это несколько раз на этой неделе, но важно развеять заблуждение, что вам абсолютно *нужно* конечное поле. **Любое** конечное кольцо работает до тех пор, пока точки, которые вы выбираете для оценки, удовлетворяют определенному свойству (ненулевые различия обратимы) https://crypto.stackexchange.com/a/96507/13843. Конечно, действительные числа, будучи бесконечными, не подпадают под эту категорию.
2
Ответить
Mark avatar
флаг ng
Mark
Также стоит отметить, что SSS не требует лагранжевой интерполяции, и ее расширения могут быть полезны. В частности, SSS можно преобразовать в терминах кодов Рида-Соломона. Используя стандартное декодирование Рида-Соломона (скажем, Berklamp-Massay), можно получить версию SSS, устойчивую к повреждению некоторого количества общих ресурсов (основной код Рида-Соломона «исправляет» эти «ошибки»). Однако это требует изменения алгоритма реконструкции/декодирования.
1
Ответить
Macko avatar
флаг co
Macko
@Daniel, так что, если мне не нужно конечное поле, как выбрать точки? Если я выбираю точки по какому-то правилу (нужно пояснение), то для них должна работать интерполяция?
0
Ответить
Macko avatar
флаг co
Macko
@ Марк Рид-Соломон использует конечное поле под капотом? Является ли Рид-Соломон обобщенной версией SSS?
0
Ответить
Macko avatar
флаг co
Macko
Поэтому я выбираю вариант изменения интерполяции: как насчет Чебышева?
0
Ответить
Mark avatar
флаг ng
Mark
@Macko, вникающий в эти детали, скорее всего, только запутает вас в этот момент. Ваш вывод должен заключаться в том, что SSS требует «конечной арифметики» (для начала вы можете упростить до конечных полей) для проверки безопасности. В этой настройке конечного поля интерполяция Лагранжа работает нормально. Существуют и другие варианты (например, Berkleamp Massay), если у вас есть более специализированные требования, но вы еще не заявили об этом. В конечной арифметической настройке феномена Рунге нет, поэтому ваша проблема должна быть решена (и ваша конструкция на самом деле будет безопасной - в настоящее время это не так)
1
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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