Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m
Введено понятие схемы разделения d ≥ 2 секретов с многоадресным сообщением (d-СРСМС). Предложена конструкция совершенной d-СРСМС, основанная на линейных преобразованиях над кольцом вычетов целых чисел. Установлены необходимые и достаточные условия существования и предложен алгоритм построения указан...
Saved in:
| Date: | 2006 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем реєстрації інформації НАН України
2006
|
| Series: | Реєстрація, зберігання і обробка даних |
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/50832 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m / А.Н. Алексейчук, А.Л. Волошин // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 1. — С. 92-102. — Бібліогр.: 5 назв. — pос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-50832 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-508322025-02-09T20:11:36Z Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m Схема розділення декількох секретів із багатоадресним повідомленням на основі лінійних перетворень над кільцем лишків за модулем m Multi-Secret Sharing Scheme with Broadcast Message Based on Linear Transformations Over a Residue Ring Modulo m Алексейчук, А.Н. Волошин, А.Л. Методи захисту інформації в комп’ютерних системах і мережах Введено понятие схемы разделения d ≥ 2 секретов с многоадресным сообщением (d-СРСМС). Предложена конструкция совершенной d-СРСМС, основанная на линейных преобразованиях над кольцом вычетов целых чисел. Установлены необходимые и достаточные условия существования и предложен алгоритм построения указанной d-СРСМС для произвольной заранее определенной иерархии доступа. Введено поняття схеми розділення d ≥ 2 секретів із багатоадресним повідомленням (d-СРСБП). Запропоновано конструкцію досконалої d-СРСБП, що заснована на лінійних перетвореннях над кільцем лишків цілих чисел. Установлено необхідні та достатні умови існування та запропоновано алгоритм побудови зазначеної d-СРСБП для довільної, заздалегідь визначеної ієрархії доступу. The conception of a secret sharing scheme with broadcast message for the sharing of d ≥ 2 secrets (d-SSSBM) is introduced. A construction of a perfect d-SSSBM based on linear transformations over a residue ring of integers is proposed. Necessary and sufficient conditions for existence of such a scheme and an algorithm of it’s construction for any predefined access hierarchy are established. 2006 Article Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m / А.Н. Алексейчук, А.Л. Волошин // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 1. — С. 92-102. — Бібліогр.: 5 назв. — pос. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50832 621.391:519.7:510.5 ru Реєстрація, зберігання і обробка даних application/pdf Інститут проблем реєстрації інформації НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Методи захисту інформації в комп’ютерних системах і мережах Методи захисту інформації в комп’ютерних системах і мережах |
| spellingShingle |
Методи захисту інформації в комп’ютерних системах і мережах Методи захисту інформації в комп’ютерних системах і мережах Алексейчук, А.Н. Волошин, А.Л. Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m Реєстрація, зберігання і обробка даних |
| description |
Введено понятие схемы разделения d ≥ 2 секретов с многоадресным сообщением (d-СРСМС). Предложена конструкция совершенной d-СРСМС, основанная на линейных преобразованиях над кольцом вычетов целых чисел. Установлены необходимые и достаточные условия существования и предложен алгоритм построения указанной d-СРСМС для произвольной заранее определенной иерархии доступа. |
| format |
Article |
| author |
Алексейчук, А.Н. Волошин, А.Л. |
| author_facet |
Алексейчук, А.Н. Волошин, А.Л. |
| author_sort |
Алексейчук, А.Н. |
| title |
Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m |
| title_short |
Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m |
| title_full |
Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m |
| title_fullStr |
Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m |
| title_full_unstemmed |
Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m |
| title_sort |
схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| publishDate |
2006 |
| topic_facet |
Методи захисту інформації в комп’ютерних системах і мережах |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/50832 |
| citation_txt |
Схема разделения нескольких секретов с многоадресным сообщением на основе линейных преобразований над кольцом вычетов по модулю m / А.Н. Алексейчук, А.Л. Волошин // Реєстрація, зберігання і оброб. даних. — 2006. — Т. 8, № 1. — С. 92-102. — Бібліогр.: 5 назв. — pос. |
| series |
Реєстрація, зберігання і обробка даних |
| work_keys_str_mv |
AT alekseičukan shemarazdeleniâneskolʹkihsekretovsmnogoadresnymsoobŝeniemnaosnovelineinyhpreobrazovaniinadkolʹcomvyčetovpomodulûm AT vološinal shemarazdeleniâneskolʹkihsekretovsmnogoadresnymsoobŝeniemnaosnovelineinyhpreobrazovaniinadkolʹcomvyčetovpomodulûm AT alekseičukan shemarozdílennâdekílʹkohsekretívízbagatoadresnimpovídomlennâmnaosnovílíníinihperetvorenʹnadkílʹcemliškívzamodulemm AT vološinal shemarozdílennâdekílʹkohsekretívízbagatoadresnimpovídomlennâmnaosnovílíníinihperetvorenʹnadkílʹcemliškívzamodulemm AT alekseičukan multisecretsharingschemewithbroadcastmessagebasedonlineartransformationsoveraresidueringmodulom AT vološinal multisecretsharingschemewithbroadcastmessagebasedonlineartransformationsoveraresidueringmodulom |
| first_indexed |
2025-11-30T09:54:56Z |
| last_indexed |
2025-11-30T09:54:56Z |
| _version_ |
1850208678302449664 |
| fulltext |
Методи захисту інформації
в комп’ютерних системах і мережах
92
УДК 621.391:519.7:510.5
А. Н. Алексейчук1, А. Л. Волошин2
1Специальный факультет СБ Украины в составе Военного института
телекоммуникаций и информатизации НТУУ «КПИ»
2ДСТСЗИ СБ Украины
Схема разделения нескольких секретов
с многоадресным сообщением на основе линейных
преобразований над кольцом вычетов по модулю m
Введено понятие схемы разделения d ³ 2 секретов с многоадресным
сообщением (d-СРСМС). Предложена конструкция совершенной d-
СРСМС, основанная на линейных преобразованиях над кольцом выче-
тов целых чисел. Установлены необходимые и достаточные условия
существования и предложен алгоритм построения указанной d-
СРСМС для произвольной заранее определенной иерархии доступа.
Ключевые слова: криптографическая защита информации, схема раз-
деления секрета, иерархия доступа, кольцо вычетов.
Введение
Среди разнообразных конструкций схем разделения секрета (СРС) представ-
ляют практический интерес так называемые схемы разделения секрета с многоад-
ресным сообщением (СРСМС — secret sharing schemes with broadcast message) [1–
4]. В этих схемах необходимым условием восстановления секретного ключа каж-
дой разрешенной коалицией участников является предварительное получение
всеми участниками некоторого открытого сообщения, передаваемого дилером по
широковещательному каналу связи.
Впервые СРСМС выделены в отдельный класс схем разделения секрета в их
общей классификации, приведенной в работе [1]. В [2] описан алгоритм построе-
ния пороговой СРСМС (структура доступа которой состоит из всех коалиций
мощности не меньшей заданного числа участников). В [3] предложена СРСМС,
реализующая структуру доступа общего вида с изменяющимся в дискретные мо-
менты времени составом разрешенных коалиций участников. Наконец, в [4] по-
строена общая теоретико-информационная модель СРСМС, и получены нижние
границы количества информации, хранящейся у участников произвольной схемы
разделения секрета с многоадресным сообщением.
© А. Н. Алексейчук, А. Л. Волошин
Схема разделения нескольких секретов с многоадресным
сообщением на основе линейных преобразований над кольцом вычетов по модулю m
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 93
Естественным обобщением СРСМС являются криптографические протоколы,
позволяющие «разделять» одновременно d ³ 2 секретных ключей таким образом,
чтобы участники каждой коалиции после получения некоторого открытого сооб-
щения, передаваемого дилером по широковещательному каналу связи, могли од-
нозначно восстановить определенные («назначенные» им, согласно протоколу)
секретные ключи. Более формальное определение указанных СРС, названных в
настоящей статье схемами разделения d секретов с многоадресным сообщением
(d-СРСМС), приведено ниже.
Следует отметить, что в силу разнообразия иерархий доступа, реализуемых d-
СРСМС (см. ниже п. 2), спектр возможных применений этих криптографических
протоколов может быть весьма широким, начиная от систем разделенной элек-
тронной цифровой подписи и, заканчивая протоколами управления доступом к
ресурсам информационных и телекоммуникационных систем. Таким образом, за-
дача разработки методов построения d-СРСМС является актуальной и практиче-
ски важной.
В настоящей статье предлагается конструкция совершенных d-СРСМС, осно-
ванная на линейных преобразованиях над кольцом вычетов по модулю m. Охарак-
теризованы иерархии доступа предложенных d-СРСМС. На основе результатов,
полученных ранее в [5], установлены необходимые и достаточные условия суще-
ствования и предложен алгоритм построения d-СРСМС, реализующей заранее оп-
ределенную иерархию доступа. Наконец, представлены две модификации исход-
ной схемы разделения d секретов с многоадресным сообщением, каждая из кото-
рых позволяет активизировать любую (заранее определенную) иерархию доступа
из некоторого семейства таких иерархий на множестве участников d-СРСМС.
1. Математическая модель схемы разделения нескольких секретов
с многоадресным сообщением
Следуя основной идее определения схемы разделения (одного) секрета с мно-
гоадресным сообщением [4], определим d-СРСМС как криптографический прото-
кол, состоящий из следующих двух этапов.
На первом этапе (предварительного распределения секретной информации)
дилер передает по защищенному каналу связи индивидуальную секретную ин-
формацию каждому участнику d-СРСМС.
На втором этапе (разделения и восстановления секретных ключей) дилер
выбирает набор, состоящий из d секретных ключей, принадлежащих некоторому
множеству S. Затем он вычисляет по этому набору некоторое сообщение В, кото-
рое передает всем участникам d-СРСМС по широковещательному каналу связи.
Предполагается, что после получения сообщения В каждая коалиция участников
может однозначно восстановить «назначенное» ей, согласно протоколу, (возмож-
но пустое) множество секретных ключей из исходного набора.
Назовем схему разделения нескольких секретов с многоадресным сообщени-
ем совершенной, если:
1) до получения сообщения В каждая коалиция участников не имеет никакой
информации о значениях секретных ключей;
А. Н. Алексейчук, А. Л. Волошин
94
2) после получения сообщения В каждая коалиция участников может восста-
новить «назначенные» ей, согласно протоколу, секретные ключи, в то время как
об остальных ключах она не имеет никакой апостериорной информации.
Отметим, что в частном случае 1=d понятие совершенной d-СРСМС совпа-
дает с известным понятием совершенной схемы разделения (одного) секрета с
многоадресным сообщением, реализующей единственную структуру доступа [4].
Опишем предлагаемую конструкцию d-СРСМС, основанную на линейных
преобразованиях над кольцом вычетов по модулю m.
Пусть даны различные простые числа p1, …, pw и натуральные числа d1, …, dw
такие, что å
=
=
w
j
jdd
1
. Положим wd
w
d ppm ×××= 1
1 , R = Z/(m), Rj = Z/ )( jd
jp , wj ,1Î ,
S = {(sij): sij Î GF(pj), 1,0 -Î jdi , wj ,1Î }.
Обозначим R* и D(R) = R\R* соответственно множество обратимых элементов и
множество делителей нуля кольца R.
Зафиксируем (k + 1)´(n + 2)-матрицу G над кольцом R с элементами gij,
( ki ,0Î , 1,0 +Î nj , k, n ³ 2) следующего вида:
÷÷
÷
÷
÷
ø
ö
çç
ç
ç
ç
è
æ
¢
= ¯
+
+
0
0
001
1
1,0
n
n
gG
g
G
M
L
, (1)
где g0,n+1 Î R*, ¯
+1ng Ï D(R)(k). Занумеруем столбцы этой матрицы слева направо
числами от 0 до n + 1, а строки — сверху вниз числами от 0 до k.
Матрице G вида (1) поставим в соответствие d-СРСМС r(G), реализующую
распределение наборов секретных ключей (sij) Î S, 1,0 -Î jdi , wj ,1Î , между
участниками, принадлежащими множеству P = {1, 2, …, n}. Отметим, что в пред-
лагаемой ниже конструкции d-СРСМС матрица G известна всем участникам схе-
мы разделения секрета.
На этапе предварительного распределения секретной информации дилер не-
зависимо, случайно и равновероятно выбирает элементы a1, …, ak Î R и вычисля-
ет вектор
( )( ) ( )( )¯
+¢= 1111 ,,,,,,,, nkkn gGaaaab KKK pp , (2)
первые n координат которого составляют секретную информацию участников.
При этом элемент pi Î R доставляется i-му участнику d-СРСМС r(G) по защи-
щенному каналу связи, ni ,1Î , а элемент b(a1, …, ak) хранится в секрете у дилера.
Схема разделения нескольких секретов с многоадресным
сообщением на основе линейных преобразований над кольцом вычетов по модулю m
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 95
На этапе разделения и восстановления секретных ключей (sij) Î S, 1,0 -Î jdi ,
wj ,1Î , дилер применяет следующий алгоритм.
1. Вычисляет элементы:
sj = å
-
=
1
0
jd
i
ij
i
j sp , wj ,1Î . (3)
2. Находит единственный элемент s Î R такой, что s º sj (mod jd
jp ), wj ,1Î .
3. Вычисляет многоадресное сообщение
RaabsgВ kn Î+= + ),...,( 11,0 (4)
и направляет его по широковещательному каналу связи всем участникам d-
СРСМС r(G).
Назовем описанную d-СРСМС линейной над кольцом R схемой разделения d
секретов с многоадресным сообщением.
Для любого делителя wl
w
l ppt ×××= 1
1 числа m ( jj dl ££0 , wj ,1Î ) обозначим
tY~ совокупность всех множеств А участников d-СРСМС r(G), которые при объе-
динении своих секретных значений и получении многоадресного сообщения В
могут восстановить ровно dj – lj младших pj-х разрядов числа sj вида (3), wj ,1Î .
Следуя терминологии, принятой в [5], назовем семейство множеств
)|:~(~ mttY=Y иерархией доступа d-СРСМС r(G).
Ниже приведено полное описание иерархии доступа d-СРСМС r(G) и пока-
зано, что r(G) является совершенной схемой разделения нескольких секретов с
многоадресным сообщением.
2. Характеризация иерархии доступа d-СРСМС r(G)
Введем ряд вспомогательных обозначений.
Для любой матрицы H над кольцом R, имеющей n столбцов, и произвольного
множества A Í P обозначим HA подматрицу матрицы H, содержащуюся в ее
столбцах с номерами из A.
Для любой матрицы H над кольцом R обозначим M(Н) и
R
H R-модули, по-
рожденные строками и столбцами матрицы H соответственно. Для любого
}1,0{ +ÈÍ nPU обозначим ||M(GU)|| число различных векторов, содержащихся в
столбцах с номерами из множества U таблицы размера |M(G)|´(n + 2), составлен-
ной из элементов модуля M(G).
Следующая теорема устанавливает свойство совершенности d-СРСМС r(G) и
описывает строение ее иерархии доступа.
А. Н. Алексейчук, А. Л. Волошин
96
Теорема 1. Для любого делителя t числа m справедливо равенство:
tY~ = {A Í P: tR = IG(A)}, (5)
где
IG(A) = {r Î R:
RnAGrG }1{0 +ÈÎ }, A Í P.
При этом до получения многоадресного сообщения B участники d-СРСМС
r(G) не имеют никакой информации о секретных ключах sij, 1,0 -Î jdi , wj ,1Î :
||GРÈ0|| = ||GР||m. (6)
Кроме того, если tY~ ¹ Æ, mppt wl
w
l |1
1 ×××= , то после получения сообщения В
участники, входящие в произвольную коалицию tA YÎ ~ , не имеют никакой ин-
формации о ключах sij с номерами 1, --Î jjj dldi , wj ,1Î :
||GAÈ 0 È{n+1}|| = ||GAÈ{n+1}|| t.
Таким образом, r(G) является совершенной d-СРСМС.
Доказательство. Равенство (6) следует непосредственно из формулы (1). Ос-
тальные утверждения теоремы доказываются аналогично теореме 1 в статье [5].
Заметим, что соотношения (1)–(5) позволяют построить алгоритм восстанов-
ления участниками произвольной коалиции tA YÎ ~ «назначенных» ей, согласно
протоколу, секретных ключей sij, 1,0 --Î jj ldi , wj ,1Î .
Пусть mppt wl
w
l |1
1 ×××= , tA YÎ ~ , | | ARίc — произвольное решение системы
линейных уравнений )( 10 +
¯ -= nA GGtxG над кольцом R (см. формулы (1), (5)).
Обозначим ):( AiiA Î= pp вектор-строку, составленную из секретных значений,
полученных участниками коалиции A на первом этапе d-СРСМС r(G). Для любо-
го wj ,1Î обозначим )(tja элемент кольца Rj = Z/ )( jd
jp , обратный к произведе-
нию )(mod jd
j
j
l ppÕ
¹n
n
n .
Заметим, что на основании формул (2)–(4) справедливы следующие равенст-
ва:
j
l
j sp j º ))(mod())(( 1
1,0
jd
jAnj ptBgt +¯-
+ cpa , wj ,1Î . (7)
Таким образом, вычислив значения (7), участники коалиции A однозначно
восстановят секретные ключи sij с номерами 1,0 --Î jj ldi , wj ,1Î .
Схема разделения нескольких секретов с многоадресным
сообщением на основе линейных преобразований над кольцом вычетов по модулю m
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 97
3. Критерий существования и алгоритм построения d-СРСМС r(G)
для заданной иерархии доступа
Пусть задано семейство )|:( mttY=Y попарно непересекающихся подмно-
жеств tY множества 2Р (случай tY = Æ не исключается) таких, что P
mt
t 2
|
=YU .
Требуется установить необходимые и достаточные условия, при которых се-
мейство Y является иерархией доступа некоторой линейной над кольцом R d-
СРСМС и (в случае существования) построить в явном виде матрицу G вида (1),
задающую такую d-СРСМС.
Для решения поставленной задачи воспользуемся результатами, полученны-
ми ранее в [5]. Докажем следующую теорему.
Теорема 2. Пусть существует k´(n + 1)-матрица
( )HhH ¢= ¯ , (8)
над кольцом R такая, что
¯h Ï D(R)(k), (9)
и для любых mt | , tA YÎ выполняется равенство:
||M(НAÈ{0})|| = ||M(НA)||t. (10)
Тогда существует d-СРСМС r(G), реализующая семейство Y , в качестве ие-
рархии доступа, где матрица G имеет вид:
÷÷
ø
ö
çç
è
æ
¢
= ¯¯ hH
G
0
1001 L
. (11)
Справедливо также обратное утверждение.
Доказательство. Согласно теореме 1 из [5], при выполнении соотношений
(9), (10) для любого mt | имеет место равенство:
tY = {A Í P: tR = IH(A)}, (12)
где
IH(A) = {r Î R:
RAHrh ί }, A Í P.
Обозначим }|:~{~ mttY=Y иерархию доступа d-СРСМС r(G), где матрица G
определяется по формуле (11). На основании соотношений (5), (12) для доказа-
А. Н. Алексейчук, А. Л. Волошин
98
тельства равенства Y=Y
~ достаточно убедиться в справедливости следующего
утверждения: для любых mt | , tA YÎ , r Î R
RAHrh ί Û
RnAGrG }1{0 +ÈÎ . (13)
Но формула (13) следует непосредственно из равенств (8), (11). Таким обра-
зом, существование матрицы H, удовлетворяющей условиям (9), (10), влечет су-
ществование d-СРСМС r(G) с иерархией доступа Y , где матрица G определяется
по формуле (11).
Обратное утверждение теоремы доказывается аналогично с использованием
теоремы 1 из [5].
Отметим, что необходимые и достаточные условия существования матрицы
H вида (8), удовлетворяющей соотношениям (9), (10), получены в той же статье
[5] (теорема 2). Как показано в [5], эти условия могут быть положены в основу
алгоритма построения искомой матрицы Н, а, следовательно, и матрицы G вида
(11), задающей d-СРСМС r(G) с иерархией доступа Y . Описание этого алгорит-
ма и оценка его временной сложности приведены в [5].
4. Обобщение конструкции d-СРСМС r(G) на схемы разделения
нескольких секретов с многоадресным сообщением
для семейств иерархий доступа
В [4] введено понятие совершенной СРСМС, реализующей произвольное ко-
нечное семейство структур доступа. В такой схеме на этапе разделения и восста-
новления секретного ключа дилер формирует многоадресное сообщение B таким
образом, чтобы активизировать лишь одну (заранее определенную) структуру
доступа из заданного семейства структур. При этом каждая коалиция участников,
принадлежащая выбранной структуре доступа, может однозначно восстановить
секрет по принятому сообщению B и секретной информации, полученной от ди-
лера на первом этапе; все остальные коалиции участников не имеют никакой апо-
стериорной информации о секретном ключе. Таким образом, различные способы
формирования сообщения B позволяют задавать различные (простые) схемы раз-
деления секрета на множестве участников при неизменной секретной информа-
ции, полученной ими на первом этапе СРСМС.
Ниже представлены две модификации d-СРСМС r(G), описанной в п. 2, каж-
дая из которых обобщает конструкцию r(G) и является схемой разделения d сек-
ретов с многоадресным сообщением, реализующей некоторое семейство иерархий
доступа. Обе модификации отличаются от исходной d-СРСМС r(G) исключи-
тельно способом формирования сообщения B (см. формулу (4)).
В первой модификации на шаге 3 алгоритма, описанного в п. 2, дилер фикси-
рует число t такое, что m|t , генерирует случайный равновероятный и не зави-
сящий от s элемент Rr Î и вычисляет сообщение B по формуле:
rmaabsgВ kn t
++= + ),...,( 11,0 . (14)
Схема разделения нескольких секретов с многоадресным
сообщением на основе линейных преобразований над кольцом вычетов по модулю m
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 99
Во второй модификации d-СРСМС r(G) для выбранного m|t дилер вычис-
ляет сообщение B, полагая:
),...,( 11,0 kn aabsgВ t+= + . (15)
Ясно, что при 1=t каждое из соотношений (14), (15) совпадает с равенством
(4).
С целью описания семейств иерархий доступа, реализуемых предложенными
d-СРСМС, введем следующие обозначения.
Для любых Rvu Î, обозначим ),( vu и ],[ vu соответственно наибольший об-
щий делитель и наименьшее общее кратное чисел u и v.
Для любых натуральных делителей t,t числа m обозначим символом )()1( ttY
(символом )()2( tt¢Y ) совокупность всех коалиций А P2Î таких, что t является
наименьшим натуральным числом, для которого участники, входящие в A, могут
однозначно восстановить элемент ts по секретным значениям All Î ,p и много-
адресному сообщению В вида (14) (вида (15)).
Отметим, что на основании соотношений s º sj (mod jd
jp ), wj ,1Î , и формулы
(3) для любых mppt wl
w
l |1
1 ×××= , m|t , q = 1, 2 участники произвольной коалиции
)()( tq
tA YÎ могут однозначно восстановить секретные ключи sij с номерами
1,0 --Î jj ldi , wj ,1Î и только их.
Положим )()( tqY = )|:)(( )( mtq
t tY , )(qY = )|:)(( )( mq ttY , q = 1, 2. Как пока-
зывает следующая теорема, семейство )(qY состоит из всех различных иерархий
доступа, реализуемых q-й модификацией d-СРСМС r(G). При этом множества
)()( tq
tY , mmt | ,| t , q = 1, 2, могут быть явно выражены через множества вида (5),
образующие иерархию доступа исходной d-СРСМС r(G).
Теорема 3. Для любого m|t и q = 1, 2 семейство )()( tqY является разбиени-
ем множества P2 . При этом для любого mt | :
U }],[,|:~{)()1( tfmfft =tY=tY , (16)
U }
),(
,|:~{)()2( t
f
fmfft =
t
Y=tY . (17)
Доказательство. Первое утверждение теоремы следует непосредственно из
определения множеств )()( tq
tY , mt | .
Для доказательства равенства (16) достаточно показать, что для любых mf | ,
fA YÎ
~ число ],[ tft = является наименьшим натуральным делителем числа m,
для которого участники коалиции A могут однозначно восстановить элемент ts
А. Н. Алексейчук, А. Л. Волошин
100
по секретным значениям All Î ,p и сообщению В вида (14). Убедимся в справед-
ливости этого утверждения.
Заметим, что в силу условия fA YÎ
~ и формул (1), (2), (5) f является наи-
меньшим делителем числа m, для которого участники коалиции A могут одно-
значно восстановить элемент fb(a1, …, ak) по известным им значениям All Î ,p .
Умножая равенство (14) на ],[ tft = , получим ++= + ),...,(],[
11,0 kn aafb
f
ftsgtВ t
)(],[ mrf
t
t
+ , откуда следует, что
)),...,(],[()( 1
1
1,0 kn aafb
f
ftBgts t
-= -
+ . (18)
Итак, зная fb(a1, …, ak) и В, участники коалиции A восстановят ts по формуле (18).
Пусть теперь t1 — произвольный делитель числа m, для которого элемент t1s
однозначно определяется значениями All Î ,p и сообщением (14). Покажем, что
1| tt .
Прежде всего, заметим, что 1| tt , поскольку в противном случае на основании
равенства )1(),...,())(( 1
1
1,01,0 -+++= -
++ rmaabmgsgВ knn tt
, вытекающего из фор-
мулы (14), существует, по крайней мере, два различных элемента, t1s и
))(( 1
1,01 t
mgst n
-
++ , соответствующих заданным All Î ,p , и В. Далее, умножая ра-
венство (14) на 1t , получим соотношение ),...,( 1111,01 kn aabtstgВt += + , из которого,
согласно условию fA YÎ
~ , следует, что 1| tf . Итак, 1|],[ tft t= , что и требова-
лось доказать.
Аналогичным образом доказывается равенство (17).
В заключение рассмотрим пример, позволяющий более наглядно проиллюст-
рировать изложенные выше результаты.
Пусть m = dp , где p — простое число, d ³ 2, r(G) — линейная над кольцом
)/( dpR Z= схема разделения d секретных ключей с многоадресным сообщением,
соответствующая матрице G вида (1).
Согласно теореме 1, иерархия доступа d-СРСМС r(G) состоит из d + 1 попар-
но непересекающихся классов (уровней) ip
Y~ , di ,0Î , находящихся во взаимно
однозначном соответствии с делителями числа dp . При этом, если ƹY ip
~ , то
участники каждой коалиции ip
A YÎ ~ , расположенной на i-м уровне иерархии дос-
тупа, могут однозначно восстановить по значениям All Î ,p , и сообщению B ви-
да (4) ровно id - секретных ключей s0, s1, …, sd–i–1 Î GF(p) из набора s = (si:
1,0 -Î di ), распределяемого дилером. В частности, произвольная коалиция уча-
Схема разделения нескольких секретов с многоадресным
сообщением на основе линейных преобразований над кольцом вычетов по модулю m
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2006, Т. 8, № 1 101
стников, находящаяся на i-м уровне, 1,0 -Î di , имеет доступ ко всей секретной
информации, зашифрованной на ключах, однозначно восстанавливаемых коали-
циями, расположенными на более «низких» уровнях (с номерами j > i).
Предположим, что после завершения первого этапа d-СРСМС r(G) требуется
ограничить «права доступа» коалиций, расположенных на уровнях с номерами 0,
1, …, n – 1, переведя все указанные коалиции на n-й уровень иерархии доступа d-
СРСМС r(G), и при этом сохранить «права доступа» каждой коалиции, находя-
щейся на уровне с номером dj ,nÎ . Для решения этой задачи дилер фиксирует
nt p= и передает участникам сообщение B вида (14) по широковещательному
каналу связи. Тем самым на множестве участников формируется новая иерархия
доступа )()1( tY , состоящая из непустых множеств вида (16). Нетрудно видеть,
что эта иерархия доступа состоит из 1+n-d уровней вида
U
n
=
n Y=Y n
0
)1( ~)(
i
pp ip , 11
~)()1(
+n+n Y=Y n
pp
p , …, dd pp
p Y=Y n ~)()1(
и, следовательно, удовлетворяет сформулированным выше ограничениям на «пра-
ва доступа» коалиций участников.
Пусть теперь ставится задача переместить каждую коалицию участников на n
уровней «вверх» (с i-го на (i – min{i, n})-й уровень иерархии доступа Y~ , di ,0Î )
после выполнения первого этапа d-СРСМС r(G). В этом случае дилер фиксирует
nt p= и передает участникам d-СРСМС сообщение B вида (15). На основании
равенства (17) сформированная таким образом новая иерархия доступа )()2( tY
состоит из 1+n-d уровней следующего вида:
U
n
=
n Y=Y
0
)2( ~)(0
i
pp ip , 11
~)()2(
+nY=Y n
pp
p , …, dd pp
p Y=Y n
n-
~)()2( .
Коалиции, находящиеся на уровне )()2(
0
nY p
p
новой иерархии доступа, могут
однозначно восстановить все секретные ключи si, 1,0 -Î di ; коалиции, располо-
женные на следующем уровне )()2(
1
nY p
p
, могут восстановить ключи с номерами
2,0 -Î di и т.д. Наконец, участники произвольной коалиции )()2( n
n-YÎ pA dp
, не
имеющие никакой апостериорной информации о ключах si ( 1,0 -Î di ) в исход-
ной d-СРСМС r(G), получат возможность восстановить ключи с номерами
1,0 -n-Î di .
Подчеркнем, что все представленные выше схемы разделения нескольких
секретов с многоадресным сообщением являются, безусловно, стойкими, то есть
А. Н. Алексейчук, А. Л. Волошин
102
обеспечивают (в рамках принятой модели) невозможность получения каких-либо
сведений о соответствующих секретных ключах независимо от ограничений на
производительность вычислительных средств участников d-СРСМС или внешне-
го (пассивного) противника.
1. Simmons G.J. How to (Really) Share a Secret // Advances in Cryptology — CRYPTO’88. —
Lecture Notes in Comput. Science, 1990. — P. 390–448.
2. Harn L., Hwang T., Laih C., Lee J. Dynamic Threshold Scheme Based on the Definition of
Сross-Рroduct in a N-dimensional Linear Space // Advances in Cryptology — EUROCRYPT’89. —
Lecture Notes in Comput. Science. — Vol. 435. — P. 286–298.
3. Martin K. Discrete Structures in the Theory of Secret Sharing. — PhD Th. — University of
London. — 1991.
4. Blundo C., Cresti A., De Santis A., Vaccaro U. Fully Dynamic Secret Sharing Schemes //
Advances in Cryptology — CRYPTO’93. — Lecture Notes in Comput. Science, 1994. — P. 110–125.
5. Алексейчук А.Н., Волошин А.Л. Совершенная схема множественного разделения секрета
над кольцом вычетов по модулю m // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 4.
— С. 44–53.
Поступила в редакцию 30.01.2006
УДК 621.391:519.7:510.5
УДК 621.391:519.7:510.5
УДК 621.391:519.7:510.5
А. Н. Алексейчук1, А. Л. Волошин2
Введение
© А. Н. Алексейчук, А. Л. Волошин
1. Математическая модель схемы разделения нескольких секретов
с многоадресным сообщением
2. Характеризация иерархии доступа d-СРСМС ((G)
3. Критерий существования и алгоритм построения d-СРСМС ((G)
для заданной иерархии доступа
|