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

Shamir Secret Sharing и восстановление полиномиальной функции из акций

флаг co
Macko

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

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

113
0 + 0
kelalaka avatar
флаг in
kelalaka
Добро пожаловать в Cryptgraphy.SE SSS должен работать в ограниченных полях. Вы хотите, чтобы описать нам, чтобы восстановить секрет, учитывая долю? Это хорошо написано в [Википедии] (https://en.wikipedia.org/wiki/Shamir's_Secret_Sharing#Computationally_efficient_approach). Если что-то непонятно, вы можете спросить об этом.
3
Ответить
Macko avatar
флаг co
Macko
Я хочу знать, особенно в классическом подходе, как найти коэффициенты полинома, который использовался в момент создания первых акций. Я знаю, что есть один, но у него есть некоторые недостатки в реализации - я имею в виду гауссовский.
0
Ответить
poncho avatar
флаг my
poncho
Зачем тебе коэффициенты? Разве не единственная вещь, которую вы заинтересованы в восстановлении, это секрет?
0
Ответить
Macko avatar
флаг co
Macko
Конечно, это больше: например, простота реализации, быстрое выполнение и неуязвимость для атак (время). Следующим шагом является то, как смягчить проблемы в классическом подходе Шамира — например, злонамеренный поставщик общего доступа для восстановления (как закодировать общий ресурс, чтобы он был неуязвим для несанкционированного доступа).
0
Ответить
kelalaka avatar
флаг in
kelalaka
Зачем нужна атака по времени? Построить секрет на локальном автономном компьютере? Есть академические работы о SSS без дилера [обмен секретами Шамира без дилера] (https://crypto.stackexchange.com/q/84143/18298) и [Duckduckgo] (https://duckduckgo.com/?q=shamir). +секрет+обмен+без+дилера&t=canonical&ia=web)
0
Ответить
Macko avatar
флаг co
Macko
Поэтому я забыл упомянуть основную идею: знание коэффициентов имеет решающее значение, потому что я хочу генерировать больше акций за счет выхода.
0
Ответить
kelalaka avatar
флаг in
kelalaka
Снова разделить каждую долю с помощью SSS?
0
Ответить
Macko avatar
флаг co
Macko
если я снова разделю каждую долю с помощью SSS и использую некоторые доли из первого сгенерированного пула и некоторые разделенные доли, что означает, что я могу восстановить свой секрет?
0
Ответить
poncho avatar
флаг my
poncho
Если у вас есть акции в размере $t$ (где $t$ — это пороговое значение), можно легко генерировать больше акций, не утруждая себя вычислением внутренних коэффициентов.
0
Ответить
Macko avatar
флаг co
Macko
вау, пожалуйста, опишите это как можно проще, потому что единственный способ, который я знаю, - это решение линейных уравнений
0
Ответить
poncho avatar
флаг my
poncho
Ну, вы знаете, что стандартная логика восстановления секрета принимает ряд долей $(x_1, y_1), (x_2, y_2), ..., (x_t, y_t)$ и возвращает общий секрет, который представляет собой полином, оцениваемый при 0. Итак, для построения доли по координате x $x'$ берем искусственные доли $(x_1 - x', y_1), (x_2 - x', y_2), ..., (x_t - x', y_t)$, и передайте это секретной логике реконструкции - это даст вам исходный многочлен, оцененный в $x'$, то есть соответствующую координату $y'$ - новая доля равна $(x', y')$ . Промойте и повторите для всех дополнительных акций, которые вам нужны.
1
Ответить
Macko avatar
флаг co
Macko
Таким образом, в целом эта формула интерполяции работает, но интересно то, что если я генерирую долю, xi которой находится в диапазоне [1..10], то для всех комбинаций кортежей доли я могу найти секретное значение. Это также верно, когда я генерирую больше долей [15...20], но интересная часть заключается в том, что когда я смешиваю пары из этих двух серий, удаленные xi дают неверный ответ в интерполяции. Итак, у меня есть ошибка в моем коде (о чем я так не думаю), или Лагранж очень ограничен в интерполяции.
0
Ответить
Macko avatar
флаг co
Macko
Итак, есть идеи по замене интерполяции Лагранжа?
0
Ответить
Macko avatar
флаг co
Macko
Реконструкция @poncho не работает должным образом: я подготовил пороговое количество точек (долей), которые они генерировали в начале, затем я создал новые точки (xn-x', yn), затем поместил их в свою функцию интерполяции и вычислил в x '. Новые доли имеют правильный новый xi, но результат интерполяции дает всем им одинаковое значение. Можете, пожалуйста, привести пример?
0
Ответить
poncho avatar
флаг my
poncho
@Macko: «Я помещаю их в свою функцию интерполяции и вычисляю в x '»; нет, вычислить интерполяцию в 0 (то есть выполнить в точности стандартную логику восстановления секрета)
1
Ответить
Macko avatar
флаг co
Macko
@пончо Отлично! Ага! Это работает как шарм :) и не используются двойники, не решаются уравнения, это то, что я хотел :) Большое спасибо ...
0
Ответить
Рейтинг:1
Pegasus avatar Crypto
флаг sd
Pegasus

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

На основании этого получаем случайные точки (, ()) ÷ 0. Каждая точка сообщается одному из . Участники. Для любого подмножества точек полином можно восстановить с помощью интерполяции Лагранжа. Имея полином (), для значения = 0 мы получаем значение (0) = 0, которое является секретом.

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

0 + 0
Macko avatar
флаг co
Macko
Является ли интерполяция Лагранжа лучше, чем исключение Гаусса при нахождении полиномиальных коэффициентов? Можете описать, как выполнить выборочную интерполяцию с использованием Лагранжа для поиска коэффициентов?
0
Ответить
Pegasus avatar
флаг sd
Pegasus
Пусть — полином степени t: f (x) = a0 + a1x + ··· +atxt Может быть восстановлен по t + 1 точкам (xi, f (xi)) с различными сечениями (единственным образом) , Через t таких точек проходят полиномы бесконечной степени от t.
0
Ответить
Macko avatar
флаг co
Macko
Можете ли вы указать все ограничения при создании новых акций для данного секрета: например, порог не менее 2? и т.д
0
Ответить
Pegasus avatar
флаг sd
Pegasus
Новые акции могут быть легко добавлены без изменения старых: Расчет новых баллов. Обратите внимание, что может быть более 1 доли, также полином можно редактировать без необходимости изменения секрета.
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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