Рейтинг:0

Сколько комбинаций всех $n$ игроков требуется для восстановления секрета в $(k,n)$-пороговой схеме разделения секретов?

флаг ua

В $t+1$ снаружи $n$ схема обмена секретами, где есть сеть $n$ игроков, чтобы восстановить секрет $t+1<n$ игроки нужны, чтобы поделиться своими частями $(x_i,f(x_i))$ так как полиномиальная функция степени $t$ можно вычислить. Однако все $n$ хотят иметь доступ к этому секрету, но по крайней мере $t+1$ снаружи $n$ нужны для расчета. Сколько комбинаций необходимо среди $n$ игроков, чтобы все они могли восстановить секрет. Конечно, некоторые из них станут частью $t+1$ группа, которая восстанавливает полиномиальную функцию более одного раза.

Morrolan avatar
флаг ng
Обратите внимание, что в вашем заголовке говорится о схеме $(k, n)$, а ваше тело работает по схеме $(t+1, n)$. Может захотеть исправить то или иное.
kelalaka avatar
флаг in
$C(n,t-1) = \frac{n!}{(t-1)!(n-(t-1))!}$
Hunger Learn avatar
флаг ua
@kelalaka да, ты прав... возьми $C(n,k)=\frac{n!}{k!(n-k)!}$, где $k=t-1$... так просто
Morrolan avatar
флаг ng
Это даст вам количество всех возможных подмножеств с элементами $t-1$, взятых из набора с элементами $n$. Боюсь, вы меня здесь потеряли. :D Как это нижняя или верхняя граница количества (различных) групп участников, необходимых для совместной работы, чтобы каждый из них узнал секрет? Или я неправильно понял ваш вопрос?
Hunger Learn avatar
флаг ua
@ Морролан, я тоже не понимаю твоего вопроса. Не могли бы вы повторить это еще раз?
Morrolan avatar
флаг ng
@HungerLearn Я не понимаю связи между комментарием $C(n, t-1)$ и тем, как я понял ваш вопрос. Я отредактировал свой ответ ниже, указав, как я понял ваш вопрос - правильно ли это понимание?
Рейтинг:1
флаг ng

Уточнение

Я так понял ваш вопрос:

  • Участники будут сотрудничать в наборах $(P_1, P_2, \ldots)$ из $t+1$ участников каждый, и восстановить секрет.
  • Они будут продолжать это делать, пока каждый участник не узнает секрет (хотя бы один раз)
  • Тогда вопрос состоит в том, чтобы найти границы для числа требуемых различных множеств. $P_i$. Проще говоря: «Сколько различных групп участников требуется (не более/не менее), чтобы каждый участник узнал секрет»

Нижняя граница

Всего будет не менее $\lceil\frac{n}{t+1}\rceil$ наборы $t+1$ участников каждый, реконструируя тайну. По крайней мере два из этих множеств будут иметь непустое пересечение, если только $t+1$ делит $n$, в этом случае возможно попарно непересекающееся расщепление.

Верхняя граница

С другой стороны, верхняя граница числа различных наборов $t+1$ участников каждый, такой, чтобы каждый участник узнал секрет хотя бы один раз, будет задано $n - (t + 1) + 1$.

В стороне

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

Hunger Learn avatar
флаг ua
Нет, твой ответ правильный. Это то, что я хотел знать. «Они будут продолжать это делать, пока каждый участник не узнает секрет (хотя бы один раз»… и да, вы правильно поняли, но я был сбит с толку, когда увидел ваш вопрос…. Все в порядке! ответьте еще раз! Большое спасибо!

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

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