Совершенные схемы разделения секрета и конечные универсальные алгебры
Предложен метод построения совершенных схем разделения секрета по конгруэнциям конечных универсальных алгебр, обобщающий известные способы синтеза линейных схем разделения секрета над конечными полями или коммутативными кольцами. Запропоновано метод побудови досконалих схем розділення секрету за кон...
Збережено в:
| Опубліковано в: : | Реєстрація, зберігання і обробка даних |
|---|---|
| Дата: | 2005 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем реєстрації інформації НАН України
2005
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/50768 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Совершенные схемы разделения секрета и конечные универсальные алгебры / А.Н. Алексейчук // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 2. — С. 55-65. — Бібліогр.: 23 назв. — pос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860119870173085696 |
|---|---|
| author | Алексейчук, А.Н. |
| author_facet | Алексейчук, А.Н. |
| citation_txt | Совершенные схемы разделения секрета и конечные универсальные алгебры / А.Н. Алексейчук // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 2. — С. 55-65. — Бібліогр.: 23 назв. — pос. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Предложен метод построения совершенных схем разделения секрета по конгруэнциям конечных универсальных алгебр, обобщающий известные способы синтеза линейных схем разделения секрета над конечными полями или коммутативными кольцами.
Запропоновано метод побудови досконалих схем розділення секрету за конгруенціями скінчених універсальних алгебр, який узагальнює відомі способи синтезу лінійних схем розділення секрету над скінченими полями або комутативними кільцями.
A method of constructing perfect secret sharing schemes which are obtained from congruences of finite universal algebras is provided. This method extends well-known constructions of linear secret sharing schemes over finite fields or commutative rings.
|
| first_indexed | 2025-12-07T17:38:49Z |
| format | Article |
| fulltext |
Методи захисту інформації в комп’ютерних
системах і мережах
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 2 55
УДК 621.391:519.7:510.5
А. Н. Алексейчук
Специальный факультет СБ Украины в составе Военного института
телекоммуникаций и информатизации НТУУ «КПИ»
Совершенные схемы разделения секрета
и конечные универсальные алгебры
Предложен метод построения совершенных схем разделения секрета
по конгруэнциям конечных универсальных алгебр, обобщающий из-
вестные способы синтеза линейных схем разделения секрета над ко-
нечными полями или коммутативными кольцами.
Ключевые слова: криптографическая защита информации, схема раз-
деления секрета, структура доступа, универсальная алгебра.
Введение
Схема разделения секрета (СРС) [1–4] представляет собой пару криптографи-
ческих протоколов, позволяющих «распределять» секрет s0 (рассматриваемый
как элемент некоторого абстрактного конечного множества S0) среди участников
1, 2, …, n таким образом, чтобы только некоторые, заранее определенные (разре-
шенные) группы участников могли восстановить значение секрета при объедине-
нии своих компонент (проекций секрета). Схема разделения секрета называется
совершенной, если любая запрещенная группа участников не может получить ни-
какой дополнительной, к имеющейся априорной, информации о возможном зна-
чении секретного ключа, и несовершенной — в противном случае.
Важнейшим показателем практичности схемы разделения секрета является ее
информационная скорость (information rate), определяемая как отношение длины
секрета s0 к максимальной длине соответствующих ему проекций [3, 4]. При ре-
шении прикладных задач с использованием СРС, как правило, стремятся спроек-
тировать схему разделения секрета таким образом, чтобы (при прочих равных ус-
ловиях) повысить ее информационную скорость, то есть минимизировать макси-
мальную длину проекций, хранящихся у ее участников. Наиболее «экономичны-
ми» в этом смысле среди совершенных СРС являются идеальные схемы разделе-
ния секрета, для которых длины проекций секретных ключей в точности равны
длине секрета (логарифму мощности множества S0).
Известно [5, 6], что идеальные СРС существуют не для каждой структуры
доступа (совокупности разрешенных групп) на множестве участников схемы. С
© А. Н. Алексейчук
А. Н. Алексейчук
56
другой стороны, общие методы построения совершенных СРС для произвольных
монотонных структур доступа [7, 8] приводят к малопрактичным конструкциям
СРС с экспоненциально малыми (от числа участников) информационными скоро-
стями. Задачи полного описания идеальных структур доступа и разработки мето-
дов построения совершенных СРС, имеющих наибольшую (для данной структуры
доступа) информационную скорость, являются в настоящее время важнейшими
открытыми проблемами в области теоретического исследования схем разделения
секрета [9, 10].
Большинство известных совершенных СРС (см., например, [3, 4, 11–13])
представляют собой линейные схемы, в которых секретные ключи и их проекции
являются элементами конечномерных векторных пространств над конечным по-
лем, а вычисление проекций осуществляется с помощью линейных преобразова-
ний, применяемых к секретным ключам и вспомогательным случайным данным.
Простота построения, изучения свойств и разнообразие приложений линейных
СРС над конечными полями обусловливают повышенное внимание, уделяемое
этим схемам в современных теоретических и прикладных исследованиях [4, 9,
14].
Известен ряд обобщений линейных СРС над полями. Так, в [15–17] изучают-
ся схемы разделения секрета (с определенными дополнительными свойствами),
определяемые в терминах гомоморфизмов конечных абелевых групп или свобод-
ных модулей над коммутативным кольцом с единицей. Практически эффективные
конструкции нелинейных СРС для определенных структур доступа предложены в
[10]. Вместе с тем, задача построения новых классов совершенных схем разделе-
ния секрета, реализующих различные структуры доступа и имеющих приемле-
мые, с практической точки зрения, информационные скорости, является по-
прежнему актуальной.
В настоящей статье предложен общий метод построения совершенных СРС
на основе систем отношений эквивалентности на конечном множестве, в частно-
сти, систем конгруэнций конечных универсальных алгебр. Показано, что каждая
совершенная схема разделения секрета может быть (по существу однозначно) за-
дана системой отношений эквивалентности, удовлетворяющих определенным ус-
ловиям. В частности, если указанные отношения эквивалентности являются кон-
груэнциями конечной абелевой группы с операторами, представляющей собой
модуль над кольцом с единицей или векторное пространство над полем, то пред-
ложенная конструкция СРС приводит к обычным линейным схемам разделения
секрета [3, 11–13]. Разнообразие и особенности строения конкретных классов
универсальных алгебр могут служить основанием для возможного повышения
эффективности известных совершенных СРС на основе предложенного метода.
Дальнейшее изложение построено следующим образом. В п. 1 приводятся
необходимые сведения об отношениях эквивалентности, универсальных алгебрах
и совершенных схемах разделения секрета. Более подробную информацию по
этим вопросам можно найти соответственно в [18–20] и [3–6]. В п. 2 изложены
основные результаты статьи, а в п. 3 сформулированы краткие выводы и задачи
дальнейших исследований.
Совершенные схемы разделения секрета и конечные универсальные алгебры
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 2 57
1. Вспомогательные понятия и результаты
Пусть X — конечное множество. Напомним, что (бинарным) отношением на
множестве X называется произвольное непустое подмножество декартова произ-
ведения 2Х = X ´ X. Рефлексивное, симметричное и транзитивное отношение на
множестве X называется отношением эквивалентности (ОЭ) [18].
Обозначим J(X) совокупность всех ОЭ на множестве X. Известно [18], что
J(X) является полной решеткой относительно операций Ù и Ú (пересечения и объ-
единения отношений эквивалентности соответственно). Для любых r, e Î J(X)
пересечение r Ù e совпадает с точной нижней гранью ОЭ r и e в решетке J(X), то
есть наибольшим отношением эквивалентности, содержащимся в каждом из от-
ношений r, e. Объединение (точная верхняя грань) r Ú e отношений эквивалент-
ности r и e совпадает с пересечением всех ОЭ на множестве X, содержащих одно-
временно r и e.
Композиция r · e отношений эквивалентности r и e определяется равенством:
r · e = {(x, y) Î 2Х | $ z Î X: (x, z) Î r, (z, y) Î e}.
Для любых r, e Î J(X) справедливы включения r, e Í r · e Í r Ú e. При этом рав-
носильны следующие утверждения [18, 20]:
(а) r · e — отношение эквивалентности на множестве X;
(б) ОЭ r и e перестановочны, то есть r · e = e · r;
(в) r · e = r Ú e.
Далее будем отождествлять произвольное отношение эквивалентости r Î
Î J(X) с фактормножеством X/r, то есть разбиением множества X, состоящим из
различных классов эквивалентности по отношению r. Соответственно будем
отождествлять решетку J(X) с решеткой всех разбиений множества X и обозна-
чать последнюю тем же символом. Отметим, что J(X) является полумодулярной
решеткой с ранговой функцией
r(r) = |X| – n(r), r Î J(X),
где n(r) = |X/r| — число блоков разбиения r [18, 19]. Условие полумодулярности
решетки J(X) фактически означает, что для любых r, e Î J(X) выполняется нера-
венство:
n(r Ú e) + n(r Ù e) ³ n(r) + n(e). (1)
Ниже используется следующая интерпретация слагаемых в формуле (1) (см.
[19], стр. 33). Пусть 1A , …, vA vA и 1B , …, mB — все различные блоки разбиений
r и e соответственно. Рассмотрим двудольный граф Г(r, e) на множестве вершин
{ 1A , …, vA , 1B , …, mB }, в котором пара вершин { iA , jB } образует (неориентиро-
ванное) ребро в том и только в том случае, когда iA Ç jB ¹ Æ, n,1Îi , m,1Îj .
Тогда числа n(r) + n(e), n(r Ù e) и n(r Ú e) равны соответственно числу вершин,
А. Н. Алексейчук
58
числу ребер и числу связных компонент графа Г(r, e). В частности, для любых r,
e Î J(X) равносильны утверждения:
(а¢) Г(r, e) является полным двудольным графом;
(б¢) n(r Ù e) = n(r)n(e);
(в¢) r · e = e · r = 1X, где 21 XX = — наибольший элемент решетки J(X).
Пусть Â — универсальная алгебра с носителем X [18]. Отношение эквива-
лентности r на множестве X называется конгруэнцией алгебры Â, если для любой
операции w: nX ® X данной алгебры и произвольных наборов (x1, …, xn), (y1, …,
yn) Î nX выполняется условие
((xi, yi) Î r, ni ,1Î ) Þ (w(x1, …, xn), w(y1, …, yn)) Î r.
Множество JÂ(X) всех конгруэнций алгебры Â является подрешеткой решет-
ки J(X). Другими словами, объединение r Ú e и пересечение r Ù e произвольных
конгруэнций r и e алгебры Â также является ее конгруэнцией [18, 20].
Алгебра Â называется конгруэнц-перестановочной, если для любых двух
конгруэнций r, e Î JÂ(X) выполняется равенство r · e = e · r. Отметим, что ре-
шетка JÂ(X) конгруэнц-перестановочной алгебры Â является модулярной, то есть
неравенство (1) обращается в равенство [18, 20]. Хорошо известны многочислен-
ные примеры конгруэнц-перестановочных алгебр. Это — группы с операторами
(в частности, ассоциативные кольца, модули над кольцом с единицей, векторные
пространства над полем), конечные лупы, решетки с относительными дополне-
ниями и др. [20].
Приведем необходимые сведения о совершенных (комбинаторных) схемах
разделения секрета. При этом будем придерживаться терминологии и обозначе-
ний, введенных в [6].
Пусть Si — непустые конечные множества, ni ,0Î . Положим nSSSS ´´´= ...10 ,
P = {1, 2, …, n}, P = P È {0}, 2P = {A: A Í P}.
Для любых V Í S, A = {i(1), i(2), …, i(k)} Í P , где 0 £ i(1) < i(2) < … < i(k) £ n,
обозначим символом AV мультимножество, состоящее из всех k-наборов
( )()2()1( ,...,, kiii sss ), полученных в результате удаления из каждого набора
( nsss ,...,, 10 ) Î V компонент is с номерами i Ï A. Символом AV обозначим число
различных элементов мультимножества AV .
Пусть Г Í 2P — некоторый монотонный класс подмножеств множества P (то
есть такой, что из условий A Î Г, A Í B Í P следует включение B Î Г). Согласно
определению [5, 6], множество (код) V Í S задает совершенную схему разделения
секрета с множеством секретных ключей 0S , реализующую на множестве участ-
ников P структуру доступа Г, если выполняются следующие утверждения:
0ÈAV = AV для любого A Î Г, (2)
Совершенные схемы разделения секрета и конечные универсальные алгебры
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 2 59
0ÈAV = AV 0V для любого A Î 2P/Г. (3)
Практически «распределение» секретного ключа 0s Î 0S между участника-
ми СРС V осуществляется следующим образом. Имеется доверенный центр рас-
пределения ключей (дилер), который по заданному значению 0s случайно и рав-
новероятно выбирает элемент s = ( nsss ,...,, 10 ) Î V такой, что 00 s=s . Затем i-му
участнику СРС по защищенному каналу связи доставляется проекция is ключа
0s , ni ,1Î . На основании условия (2) участники, принадлежащие произвольной
разрешенной группе A Î Г, совместно смогут однозначно восстановить ключ 0s
по имеющимся у них проекциям. При этом, в силу условия (3), никакая запре-
щенная группа участников A¢ Î 2P/Г не сможет получить, исходя из набора про-
екций ( is : i Î A¢), дополнительной (к имеющейся априорной) информации о клю-
че 0s [6].
Число
rV = },1:
||log
||logmin{ 0 ni
S
S
i
Î (4)
называется информационной скоростью СРС V Í S и является основным парамет-
ром, характеризующим практическую эффективность данной схемы разделения
секрета. Известно (см., например, [3, 4, 6]), что информационная скорость произ-
вольной совершенной СРС V не превосходит 1. В случае Vr = 1 схема разделения
секрета V называется идеальной. Известным примером идеальной СРС является
произвольная «векторная» схема разделения секрета, определяемая посредством
линейного кода V над конечным полем ( iS = GF(q), ni ,0Î , V — подпространство
векторного пространства S = GF(q)n+1 над полем GF(q)) [11].
2. Метод построения совершенных СРС по конгруэнциям
конечных универсальных алгебр
Докажем утверждение, характеризующее совершенные схемы разделения
секрета в терминах определенных систем отношений эквивалентности на конеч-
ном множестве.
Утверждение 1. Пусть Г — произвольная (монотонная) структура доступа на
множестве P, r — вещественное число, 0 < r £ 1. Тогда совершенная СРС, имею-
щая информационную скорость r и реализующая структуру доступа Г, существует
в том и только в том случае, когда существуют конечное множество X и система
отношений эквивалентности 0p , 1p ,…, np Î J(X), удовлетворяющие условиям:
Аp
def
= iAi
p
Î
Ù Í 0p для любого A Î Г, (5)
А. Н. Алексейчук
60
Аp · 0p = Х1 для любого A Î 2P/Г, (6)
r = },1:
)(log
)(log
min{ 0 ni
n
n
i
Î
p
p
. (7)
Доказательство. Пусть V Í S — код совершенной СРС, реализующей струк-
туру доступа Г на множестве P, и Vr = r.
Положим l = V , X = {1, 2, …, l}. Запишем слова, принадлежащие коду V, в
виде прямоугольной таблицы размера l ´ (n + 1). Заметим, что i-й столбец данной
таблицы представляет собой вектор значений некоторого отображения ij : X ®
® iS , ni ,0Î . Положим ip = Ker ij , где Ker ij = {(x, y) Î 2Х : ij (x) = ij (y)} —
ядро отображения ij ( ni ,0Î ), и покажем, что ОЭ 0p , 1p , …, np на множестве X
удовлетворяют условиям (5)–(7).
Для любого множества A Í P зададим отображение Аj : X ® АS , полагая
Аj (x) = Aii x Î))((j , x Î X.
Заметим, что
Ker Аj (x) = iAi
jKer
Î
Ù = iAi
p
Î
Ù = Аp , (8)
n( Аp ) = AV (9)
для любого A Í P . На основании равенств (8), (9) соотношения (2), (3) равно-
сильны соответственно следующим соотношениям:
n( Аp Ù 0p ) = n( Аp ) для любого A Î Г, (10)
n( Аp Ù 0p ) = n( Аp )n( 0p ) для любого A Î 2P/Г. (11)
Далее, в силу включения Аp Ù 0p Í Аp условие (10) равносильно утверждению:
Аp Ù 0p = Аp для любого A Î Г, которое, в свою очередь, равносильно условию
(5). В силу равносильности утверждений (а¢)–(в¢), приведенных в п. 1, условие
(11) равносильно условию (6). Наконец, справедливость равенства (7) вытекает
непосредственно из формул (4), (9) и равенства | iS | = iV , ni ,0Î .
Итак, существование совершенной СРС V такой, что Vr = r, реализующей
структуру доступа Г, влечет существование конечного множества X и ОЭ 0p , 1p ,
…, np Î J(X), удовлетворяющих условиям (5)–(7).
Совершенные схемы разделения секрета и конечные универсальные алгебры
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 2 61
Докажем обратное утверждение. Пусть 0p , 1p , …, np — отношения эквива-
лентности на конечном множестве X, для которых выполняются условия (5)–(7).
Положим Si = X/ ip и обозначим ij каноническую проекцию множества X на
множество iS , ni ,0Î . Из векторов значений отображений 0j , 1j , …, nj соста-
вим таблицу V, полагая Vi равным вектору значений отображения ij , ni ,0Î . За-
метим, что на основании рассуждений, изложенных в первой части доказательст-
ва, построенный код V задает совершенную СРС, обладающую требуемыми свой-
ствами. Утверждение доказано.
Полученный результат позволяет предложить общий метод построения со-
вершенных схем разделения секрета на основе конгруэнций конечных универ-
сальных алгебр. Суть метода раскрывается в формулировках следующих утвер-
ждений.
Утверждение 2. Пусть Â — конечная алгебра с носителем X, 0p , 1p , …, np
— конгруэнции алгебры Â такие, что
(і) 0p · ( iAi
p
Î
Ù ) = ( iAi
p
Î
Ù ) · 0p для любого A Í P = {1, 2, …, n},
(іі) 0p — максимальная конгруэнция алгебры Â.
Тогда система конгруэнций 0p , 1p ,…, np задает на множестве P совершен-
ную СРС, реализующую структуру доступа:
Г = {A Í P: iAi
p
Î
Ù Í 0p }. (12)
Информационная скорость указанной СРС определяется по формуле (7).
Доказательство. Заметим, что в силу максимальности конгруэнции 0p и
равносильности условий (а)–(в), приведенных в п. 1, для любого множества A Î
2P / Г выполняется равенство ( iAi
p
Î
Ù ) · 0p = 1X. Следовательно, система конгруэн-
ций 0p , 1p ,…, np удовлетворяет условиям (5), (6), и на основании утверждения 1
существует совершенная СРС, имеющая информационную скорость (7) и реали-
зующая структуру доступа (12).
Утверждение доказано.
Следствие. Пусть 0p — максимальная, а 1p ,…, np — произвольные конгру-
энции конечной конгруэнц-перестановочной алгебры Â. Тогда система конгруэн-
ций 0p , 1p ,…, np задает совершенную СРС на множестве n участников, структу-
ра доступа которой определяется по формуле (12), а информационная скорость —
по формуле (7). Код V указанной СРС имеет вид:
V = {( 0j (x), 1j (x), …, nj (x)): x Î X},
А. Н. Алексейчук
62
где ij — каноническая проекция алгебры Â на факторалгебру по конгруэнции
ip , ni ,0Î .
Отметим, что в частном случае, когда алгебра Â является абелевой группой с
операторами, представляющей собой векторное пространство над конечным по-
лем, схема разделения секрета, описанная в формулировке следствия, совпадает с
«векторной» СРС Э. Брикела [11].
Утверждения 1, 2 можно непосредственно использовать для построения раз-
нообразных «конкретных» схем разделения секрета, выбирая подходящим обра-
зом универсальную алгебру Â и систему отношений эквивалентности на носителе
этой алгебры. Пусть, например, Â является модулем конечной длины над конеч-
ным коммутативным кольцом с единицей (здесь и далее модуль Â рассматривает-
ся как абелева группа с операторами) [20]. Положим ip равным фактормодулю
Â/Âi, где Âi — некоторый подмодуль модуля Â, ni ,0Î . Пусть ij : Â ® Âi — ка-
нонический гомоморфизм модулей. Тогда, отождествляя фактормодуль ip = Â/Âi
с ядром гомоморфизма ij ( ni ,0Î ) и применяя к системе конгруэнций 0p , 1p ,…,
np модуля Â утверждение 1, получим, что набор гомоморфизмов ij : Â ® Âi,
ni ,0Î в том и только в том случае задает совершенную схему разделения секрета
со структурой доступа Г Í 2P, когда выполняются следующие условия:
I
Ai
i
Î
jKer Í Ker 0j для любого A Î Г, (13)
I
Ai
i
Î
jKer + Ker 0j = Â для любого A Î 2P/Г. (14)
Отметим, что соотношения (13), (14) характеризуют так называемые линей-
ные совершенные СРС над конечным полем [12, 13]. По сути, аналогичные соот-
ношения используются в [16, 17] для задания совершенных СРС над некоторыми
коммутативными кольцами и группами.
В качестве еще одного возможного применения утверждения 1, укажем спо-
соб построения совершенных схем разделения секрета по определенной системе
подгрупп произвольной конечной группы.
Утверждение 3. Пусть Х — конечная группа, 0G — максимальная, а iG —
произвольная подгруппа группы Х, ni ,1Î . Пусть, далее, ip обозначает множест-
во различных левых смежных классов группы Х по подгруппе iG , ni ,0Î . Тогда
при выполнении хотя бы одного из условий
(i¢) iG — нормальный делитель группы Х, ni ,1Î ,
(ii¢) 0G — нормальный делитель группы Х
Совершенные схемы разделения секрета и конечные универсальные алгебры
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 2 63
система разбиений 0p , 1p ,…, np задает совершенную СРС V, реализующую
структуру доступа (12). Информационная скорость СРС V равна:
Vr = },1:
):log(
):log(min{ 0 ni
GX
GX
i
Î ,
где (X: H) обозначает индекс подгруппы H в группе X.
Доказательство. Для любого A Í P положим AG = I
Ai
iG
Î
. Заметим, что AG
является подгруппой группы X, и разбиение Аp = iAi
p
Î
Ù совпадает с разложением
группы X в левые смежные классы по этой подгруппе.
Пусть теперь для некоторого A Í P группа AG не содержится в группе G0.
Тогда при выполнении любого из условий (і¢), (іі¢) произведение AG 0G = 0G AG
является подгруппой группы X, которая совпадает с X в силу максимальности 0G .
Таким образом, на основании утверждения 1 для завершения доказательства оста-
ется убедиться в справедливости следующего утверждения.
Пусть G и H — подгруппы группы Х такие, что Х = GH, и H — нормальный
делитель X. Тогда любые два левых смежных класса группы X по подгруппам G и
H соответственно имеют непустое пересечение.
Докажем это. Пусть xG и yH — левые смежные классы группы X соответст-
венно по подгруппам G и H. Из равенств GH = HG = Х следует, что y = 11hg , x =
= 22 gh для некоторых 1g , 2g Î G, 21 , hh Î H. Следовательно, xG = 2h G и (так как
H — нормальный делитель группы X) yH = 1g H = H 1g . Остается заметить, что
12 gh Î H 1g Ç 2h G = yH Ç xG, что и требовалось доказать.
Заключение
Описанные выше конструкции совершенных схем разделения секрета свиде-
тельствуют о большом разнообразии конкретных СРС, которые могут быть полу-
чены путем задания некоторой конечной универсальной алгебры и соответст-
вующей системы ОЭ на ее носителе. Вместе с тем, более важным (и более труд-
ным) является вопрос о том, насколько в действительности различны структуры
доступа указанных СРС. Известно [13], что для любой монотонной структуры
доступа существует реализующая ее линейная СРС над конечным полем (опреде-
ляемая соотношениями (13), (14)). Однако метод построения таких СРС, изло-
женный в [13], в общем случае, приводит к малопрактичным конструкциям ли-
нейных схем разделения секрета, имеющих крайне малые значения информаци-
онной скорости. Вопрос о том, насколько более эффективно можно реализовать те
или иные структуры доступа с помощью СРС, построенных по системам конгру-
энций универсальных алгебр, отличных от конечных векторных пространств, яв-
ляется в настоящее время открытым.
Задача оптимизации информационной скорости совершенных схем разделе-
ния секрета, реализующих заданную структуру доступа Г, естественным образом
А. Н. Алексейчук
64
приводит к вопросу о том, каково наибольшее число блоков разбиения 0p Î J(X),
удовлетворяющего (для заданных отношений эквивалентности 1p ,…, np Î J(X) и
монотонного класса Г Í 2P) условиям (5), (6). Обозначим Г0 совокупность мини-
мальных элементов класса Г. Тогда на основании соотношения (5) справедливо
включение
0p Ê Гp
def
= )(
0
i
AiA
p
ÎGÎ
ÙÚ ,
из которого следует, что n( 0p ) £ n( Гp ). Нахождение необходимых и достаточных
условий, при которых полученное неравенство обращается в равенство (то есть
ОЭ Гp = 0p удовлетворяет условию (6)), представляет собой практически важ-
ную, интересную задачу.
Отметим, что полученное выше алгебраическое описание совершенных СРС
(см. утверждение 1) можно распространить на другие, «родственные» схемам раз-
деления секрета, криптографические протоколы: схемы предварительного рас-
пределения ключей и схемы широковещательного шифрования [21]. Решающий
шаг в этом направлении сделан в статьях [22, 23], где представлены конструкции
линейных схем распределения ключей, включающие в себя, в качестве частных
случаев, практически все известные ранее способы построения таких схем (см.
[23]). Для того чтобы получить алгебраические варианты определений схемы
предварительного распределения ключей и схемы широковещательного шифро-
вания (по сути равносильные общепринятым теоретико-информационным опре-
делениям этих понятий [21]), достаточно отказаться от условия линейности ото-
бражений в конструкциях схем распределения ключей, предложенных в [22, 23].
1. Blakley G.R. Safeguarding Cryptographic Keys // Proc. AFIPS 1979 National Computer
Conference. — N-Y. — 1979. — Vol. 48. — P. 313–317.
2. Shamir A. How to share a secret // Comm. ACM. — 1979. — Vol. 22, N 1. — P. 612–613.
3. Stinson D.R. An Explication of Secret Sharing Schemes // Designs, Codes and Cryptography. –
1992. — Vol. 2. — P. 357–390.
4. Seberry J., Charnes Ch., Pieprzyk J., Safavi-Naini R. 41 Crypto Topics and Application. CRC
Handbook of Algorithms and Theory of Computation. — CRC Press.: Baca Raton, 1999. — P. 1–51.
5. Brickell E.F., Davenport D.M. On the Classification of Ideal Secret Sharing Schemes // J.
Cryptology — 1991. — Vol. 4. — P. 123–134.
6. Блейкли Р.Г., Кабатянский Г.А. Обобщенные идеальные схемы, разделяющие секрет, и
матроиды // Проблемы передачи информации. — 1997. — Т. 33. — Вып. 3. — С. 102–110.
7. Ito M., Saito A., Nishizeki T. Secret Sharing Scheme Realizing General Access Structure // Proc.
IEEE Globecom’ 87. — Tokyo. — 1987. — P. 99–102.
8. Benaloh J., Leichter J. Generalized Secret Sharing and Monotone Functions // Advances in
Cryptology. — CRYPTO’88. — Lecture Notes in Comput. Sci. — 1990. — Vol. 403. — P. 27–35.
Совершенные схемы разделения секрета и конечные универсальные алгебры
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 2 65
9. Marti-Farre J., Padro C. Secret Sharing Schemes on Access Structures with Intersection
Number to One // Proc. Third Conf. on Security and Communication Networks’02. — Amalfi. — 2002.
— Vol. 2576. — P. 354–363.
10. Beimel A., Ishai Y. On the Power of Nonlinear Secret Sharing // Proc. 16th Conf. on
Computational Complexity. — 2001. — P. 188–202.
11. Brickell E.F. Some Ideal Secret Sharing Schemes // J. Combin. Math. and Combin. Comput. —
1989. — N 9. — P. 105–113.
12. Blakley G.R., Kabatianski G.A. Linear Algebra Approach to Secret Sharing Schemes // Error
Control, Cryptology and Speech Compression. — Lecture Notes in Comput. Sci.— 1994. — Vol. 829. —
P. 33–40.
13. Simmons G.J., Jackson W., Martin K. The Geometry of Secret Sharing Schemes // Bull. of the
ICA. — 1991. — N 1. — P. 71–88.
14. Cramer R., Damgard I., Maurer U. General Secure Multi-Party Computation from any Linear
Secret Sharing Schemes // Advances in Cryptology — EUROCRYPT’00. — Lecture Notes in Comput.
Sci. — 2000. — Vol. 1807. — P. 316–334.
15. Frankel Y., Desmedt Y. Classification of Ideal Homomorphic Threshold Schemes over Finite
Abelian Groups // Advances in Cryptology — EUROCRYPT’92. — Lecture Notes in Comput. Sci. —
1993. — Vol. 658. — P. 25–34.
16. Cramer R., Fear S. Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups //
Advances in Cryptology — EUROCRYPT’02. — Lecture Notes in Comput. Sci. — 2002. — Vol. 2442.
— P. 272–287.
17. Cramer R., Fear S., Ishai Y., Kushilevitz E. Efficient Multi-Party Computation over Rings //
Cryptology ePrint Archive, Report 2003/030. — 2003.
18. Кон П. Универсальная алгебра: Пер. с англ. — М.: Мир, 1968. — 351 с.
19. Айгнер М. Комбинаторная теория: Пер. с англ. — М.: Мир, 1982. — 558 с.
20. Биркгоф Г. Теория решеток: Пер. с англ. — М.: Наука, 1984. — 568 с.
21. Stinson D.R. On Some Methods for Unconditionally Secure Key Distribution and Broadcast
Encryption // Designs, Codes and Cryptography. — 1997. — Vol. 12. — P. 215–243.
22. Padro C., Gracio I., Martin S., Morillo P. Linear Key Predistribution Schemes // Designs,
Codes and Cryptography. — 2002. — Vol. 25. — P. 281–298.
23. Padro C., Gracio I., Martin S., Morillo P. Linear Broadcast Encryption Schemes // Discrete
Appl. Math. — 2003. — Vol. 128. — P. 223–238.
Поступила в редакцию 07.02.2005
|
| id | nasplib_isofts_kiev_ua-123456789-50768 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Russian |
| last_indexed | 2025-12-07T17:38:49Z |
| publishDate | 2005 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Алексейчук, А.Н. 2013-11-02T00:22:31Z 2013-11-02T00:22:31Z 2005 Совершенные схемы разделения секрета и конечные универсальные алгебры / А.Н. Алексейчук // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 2. — С. 55-65. — Бібліогр.: 23 назв. — pос. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50768 621.391:519.7:510.5 Предложен метод построения совершенных схем разделения секрета по конгруэнциям конечных универсальных алгебр, обобщающий известные способы синтеза линейных схем разделения секрета над конечными полями или коммутативными кольцами. Запропоновано метод побудови досконалих схем розділення секрету за конгруенціями скінчених універсальних алгебр, який узагальнює відомі способи синтезу лінійних схем розділення секрету над скінченими полями або комутативними кільцями. A method of constructing perfect secret sharing schemes which are obtained from congruences of finite universal algebras is provided. This method extends well-known constructions of linear secret sharing schemes over finite fields or commutative rings. ru Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Методи захисту інформації в комп’ютерних системах і мережах Совершенные схемы разделения секрета и конечные универсальные алгебры Досконалі схеми розділення секрету та скінченні універсальні алгебри Perfect Secret Sharing Schemes and Finite Universal Algebras Article published earlier |
| spellingShingle | Совершенные схемы разделения секрета и конечные универсальные алгебры Алексейчук, А.Н. Методи захисту інформації в комп’ютерних системах і мережах |
| title | Совершенные схемы разделения секрета и конечные универсальные алгебры |
| title_alt | Досконалі схеми розділення секрету та скінченні універсальні алгебри Perfect Secret Sharing Schemes and Finite Universal Algebras |
| title_full | Совершенные схемы разделения секрета и конечные универсальные алгебры |
| title_fullStr | Совершенные схемы разделения секрета и конечные универсальные алгебры |
| title_full_unstemmed | Совершенные схемы разделения секрета и конечные универсальные алгебры |
| title_short | Совершенные схемы разделения секрета и конечные универсальные алгебры |
| title_sort | совершенные схемы разделения секрета и конечные универсальные алгебры |
| topic | Методи захисту інформації в комп’ютерних системах і мережах |
| topic_facet | Методи захисту інформації в комп’ютерних системах і мережах |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50768 |
| work_keys_str_mv | AT alekseičukan soveršennyeshemyrazdeleniâsekretaikonečnyeuniversalʹnyealgebry AT alekseičukan doskonalíshemirozdílennâsekretutaskínčenníuníversalʹníalgebri AT alekseičukan perfectsecretsharingschemesandfiniteuniversalalgebras |