Общее решение задачи специального распределения частичных секретов с использованием схемы разделения секрета Шамира

В данной работе решается следующая задача: для группы из n участников необходимо раздать каждому из них по два частичных секрета таким образом, чтобы каждой паре участников соответствовала (3, 4)-пороговая структура доступа. Иными словами, каждая пара участников может найти некоторый общий для них секрет, используя любые 3 из 4 имеющихся у них частичных секретов. У данной задачи есть тривиальное решение — разделить между всеми один и тот же секрет, используя (3, 2n)-пороговую схему разделения секрета. Однако теоретический и практический интерес представляет случай, когда каждая пара участников восстановит секрет, отличный от других. В частности, решение данной задачи необходимо для протокола формирования общих ключей, предложенного в [1]. Найдено полное решение рассматриваемой задачи для схемы разделения секрета Шамира, изучены неинтерактивные методы рандомизации протокола формирования общих ключей из работы [1]. Но оказалось, что они не усиливают безопасность этого протокола.