Модулярная схема разделения секрета над кольцом гауссовых целых чисел
Предложена конструкция модулярной схемы разделения секрета над кольцом гауссовых целых чисел, обладающей большей вычислительной стойкостью по сравнению с известной целочисленной модулярной схемой разделения секрета. Запропоновано конструкцію модулярної схеми розподілення секрету над кільцем гауссови...
Saved in:
| Published in: | Реєстрація, зберігання і обробка даних |
|---|---|
| Date: | 2007 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем реєстрації інформації НАН України
2007
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/50878 |
| 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: | Модулярная схема разделения секрета над кольцом гауссовых целых чисел / А.Н. Алексейчук, Ю.Е. Бояринова // Реєстрація, зберігання і оброб. даних. — 2007. — Т. 9, № 1. — С. 87-99. — Бібліогр.: 13 назв. — pос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859626259969998848 |
|---|---|
| author | Алексейчук, А.Н. Бояринова, Ю.Е. |
| author_facet | Алексейчук, А.Н. Бояринова, Ю.Е. |
| citation_txt | Модулярная схема разделения секрета над кольцом гауссовых целых чисел / А.Н. Алексейчук, Ю.Е. Бояринова // Реєстрація, зберігання і оброб. даних. — 2007. — Т. 9, № 1. — С. 87-99. — Бібліогр.: 13 назв. — pос. |
| collection | DSpace DC |
| container_title | Реєстрація, зберігання і обробка даних |
| description | Предложена конструкция модулярной схемы разделения секрета над кольцом гауссовых целых чисел, обладающей большей вычислительной стойкостью по сравнению с известной целочисленной модулярной схемой разделения секрета.
Запропоновано конструкцію модулярної схеми розподілення секрету над кільцем гауссових цілих чисел, що має більшу обчислювальну стійкість у порівнянні з відомою цілочисловою модулярною схемою розподілення секрету.
The design modulo secret sharing scheme over a ring of Gaussian integer, possessing greater computing stability in comparison with known integer modulo secret sharing scheme is offered.
|
| first_indexed | 2025-11-29T11:28:00Z |
| format | Article |
| fulltext |
Методи захисту інформації
в комп’ютерних системах і мережах
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 87
УДК 621.391:519.7
А. Н. Алексейчук1, Ю. Е. Бояринова2
1Институт специальной связи и защиты информации НТУУ «КПИ»
ул. Московская, 45/1, 01011 Киев, Украина
2Институт проблем регистрации информации НАН Украины
ул. Н. Шпака, 2, 03113 Киев, Украина
Модулярная схема разделения секрета
над кольцом гауссовых целых чисел
Предложена конструкция модулярной схемы разделения секрета над
кольцом гауссовых целых чисел, обладающей большей вычислительной
стойкостью по сравнению с известной целочисленной модулярной
схемой разделения секрета.
Ключевые слова: модулярная схема разделения секрета, вычислитель-
ная стойкость, кольцо гауссовых целых чисел.
Введение
Одна из первых модулярных схем разделения секрета (СРС) предложена в
[1]. В этой схеме каждому участнику ni ,1Î ставится в соответствие положитель-
ное целое число (модуль) im¢ , а і-я проекция ключа Z΢0s , выбираемого случайно
и равновероятно из некоторого фиксированного конечного интервала на числовой
прямой, определяется как остаток от деления 0s¢ на im¢ . В [1] показано, что при
определенном способе задания чисел nmm ¢¢ , ... ,1 описанная конструкция позволяет
реализовать ) ,( nk -пороговую структуру доступа на множестве участников
} , ... , 2 ,1{ nP = для любого nk 2 ££ . Впоследствии ряд модификаций и
обобщений описанной СРС исследован в [2–5]. Отметим, что основным преиму-
ществом этих схем разделения секрета по сравнению с идеальными пороговыми
СРС [6] является меньшая временная сложность восстановления секретных клю-
чей разрешенными коалициями участников [4].
Возможность построения модулярных СРС над коммутативными кольцами,
отличными от кольца Z , по аналогии с конструкцией [1], исследовалась в [7–9]. В
частности, в [8] предложены модулярные СРС над кольцом многочленов
])[2( xGF , а в [9] описаны эффективные алгоритмы восстановления ключей раз-
решенными коалициями участников модулярных СРС над кольцами целых гаус-
совых, двойных или дуальных чисел.
А. Н. Алексейчук, Ю. Е. Бояринова
А. Н. Алексейчук, Ю. Е. Бояринова
88
При анализе стойкости схем разделения секрета, построенных над кольцом
гауссовых целых чисел ][iZ , выяснилось, что указанные СРС имеют, по сущест-
ву, такую же вычислительную стойкость, что и их целочисленные аналоги — мо-
дулярные СРС, описанные в [1]. Таким образом, непосредственное «обобщение»
конструкции [1] c кольца целых на кольцо гауссовых целых чисел не приводит к
более эффективным, с точки зрения стойкости или практичности, схемам разде-
ления секрета.
В настоящей статье предложена модулярная СРС над кольцом ][iZ , свобод-
ная от указанных недостатков. Получены аналитические оценки параметров, ха-
рактеризующих стойкость предложенной СРС, и показано, что новая схема разде-
ления секрета является (в ряде случаев — существенно) более стойкой по сравне-
нию с целочисленной модулярной СРС [1].
Основные понятия и вспомогательные результаты
Обозначим }1 ,Z,:{][Z 2
2121 -=Î+= iaaiaai кольцо гауссовых целых чисел.
Известно, что это кольцо является евклидовым относительно нормы 2)( aaN = ,
][ia ZÎ . Более того, справедливо следующее утверждение (см., например [10],
стр. 23).
Лемма 1. Для любых ,0 ],[ , ¹Î biba Z существуют элементы ][, irq ZÎ та-
кие, что
2
1)Im( ,
2
1)Re( , ££+=
b
r
b
rrbqa ; в частности, ).(
2
1)( bNrN £
Используя известные результаты о строении неприводимых элементов кольца
][iZ ([10], стр. 149–151), нетрудно убедиться в справедливости такого утвержде-
ния.
Лемма 2. Пусть ][ , 2121 iibbbiaaa ZÎ+=+= , где == ),(),( 2121 bbaa
= 1))( ),(( =bNaN , 1)( ,1)( >> bNaN (символ ) ,( vu обозначает наибольший об-
щий делитель целых чисел u и v ). Тогда, если iccabc 21 +== , то 1),( 21 =cc .
Обозначим )(Nr число целочисленных решений ) ,( yx неравенства
Nyx £+ 22 , где 0>N . Доказательство следующего утверждения можно найти в
[11], стр. 64.
Лемма 3. Для любого 2³N справедливы неравенства:
22 )2()()2( +<<- NNN prp . (1)
Отметим, что верхняя оценка (1) имеет место для всех 0>N .
Определение модулярной схемы разделения секрета
Пусть n и k — натуральные числа, nk ££2 , nmmm , ... , , 21 — необрати-
мые элементы кольца ][iZ . Обозначим } , ... ,2 ,1{ nP = , Õ
Î
=
Ai
iA mm для любого
PAÍ ,
Модулярная схема разделения секрета над кольцом гауссовых целых чисел
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 89
)(max
1 :
1 AkAPA
mNM
-=Í
= , )(min
:2 AkAPA
mNM
=Í
= . (2)
Предположим, что элементы nmmm , ... , , 21 удовлетворяют следующим услови-
ям:
(а) nimm ii ,1 ,1))Im(),(Re( Î= ;
(б) jinjimNmN ji ¹Î= ,,.1 , ,1))(),(( ;
(в) 21 36
14 MM << .
Для любого RÎx обозначим [ ]x целую часть числа x . Положим:
}1
2
1:{ 2000 -úû
ù
êë
é£Î= MssS Z , (3)
}
4
1)(
4
1:][{ 21 MsNMisS <£Î= Z . (4)
По указанным элементам nmmm , ... , , 21 построим схему разделения секрета
для множества секретных ключей 0S на множестве участников P .
Пусть 0
)0( Ss Î — произвольный секретный ключ. Тогда для нахождения
проекций ][ , ... ,1 icc n ZÎ ключа )0(s дилеру СРС необходимо выполнить следую-
щий алгоритм:
1) выбрать случайно и равновероятно элемент ZÎ)1(s , удовлетворяющий ус-
ловию
2)0(
2
2)1(2)0(
1 4
1
4
1 sMssM -<<-
или, другими словами, условию
Sisss Î+= )1()0(
def
; (5)
2) вычислить ic как остаток от деления s на im в кольце ][iZ .
Отметим, что в силу условия (в) выбор элемента )1(s на первом шаге описан-
ного алгоритма всегда возможен. Обозначим построенную схему разделения сек-
рета ) , ... , ,( 21 nmmmS . Отметим, что число различных секретных ключей в этой
схеме равно:
220 1
2
12 MMS <-úû
ù
êë
é= . (6)
А. Н. Алексейчук, Ю. Е. Бояринова
90
Покажем, что ) , ... , ,( 21 nmmmS является ) ,( nk -пороговой СРС. Предвари-
тельно введем ряд дополнительных обозначений.
Зафиксируем произвольный ключ 0
)0( Ss Î и соответствующий ему набор
проекций ) , ... ,( 1 ncc . Для любого PAÍ обозначим AX множество решений сис-
темы сравнений (СС)
Aimcx ii κ ),(mod (7)
над кольцом ][iZ . Зафиксируем произвольное решение Ax СС (7), удовлетво-
ряющее условию:
.
2
1)Im( ,
2
1)Re( ££
A
A
A
A
m
x
m
x (8)
Отметим, что, согласно лемме 1, такое решение всегда существует, и может быть
получено как остаток от деления любого фиксированного решения СС (7) на эле-
мент Am . Кроме того, на основании условия (б), множество AX имеет следующий
вид:
]}[:{ irrmxX AAA ZÎ+= . (9)
При этом элемент s вида (5) удовлетворяет системе сравнений (7), то есть при-
надлежит множеству (9).
Пусть PAÍ , kA = . Покажем, что участники, входящие в коалицию A , мо-
гут однозначно восстановить элемент s вида (5) по набору проекций ) :( Aici Î и,
следовательно, найти ключ )0(s по формуле )Re()0( ss = . Для этого достаточно
убедиться в том, что любое решение Ax СС (7), удовлетворяющее условию (8),
равно элементу s .
Предположим противное: sxA ¹ . Тогда в силу соотношений AA Xx Î , AXsÎ
элемент Am делит разность Axs - в кольце ][iZ и, следовательно,
1)Re( ³
-
A
A
m
xs или .1)Im( ³
-
A
A
m
xs (10)
С другой стороны, поскольку SsÎ , то на основании равенства (4)
)(
4
1
4
1)( 2 AmNMsN £< , то есть
4
1)( <
Am
sN . Отсюда, используя неравенства (8),
получим:
Модулярная схема разделения секрета над кольцом гауссовых целых чисел
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 91
1
2
1
2
1)Re()Re()Re( =+<+£
-
A
A
AA
A
m
x
m
s
m
xs ,
1
2
1
2
1)Im()Im()Im( =+<+£
-
A
A
AA
A
m
x
m
s
m
xs .
Но эти соотношения противоречат условию (10). Таким образом, исходное пред-
положение sxA ¹ неверно, что и требовалось доказать.
Итак, на основании вышеизложенного можно предположить следующий ал-
горитм восстановления ключа )0(s участниками коалиции A , где kA = :
1) найти хотя бы одно решение ][ix ZÎ системы сравнений (7), используя
известные алгоритмы [9, 12];
2) найти элемент AA Xx Î , удовлетворяющий условию (8), разделив x на
Am с остатком в кольце ][iZ ;
3) положить )Re()0(
Axs = .
Оценки криптографической стойкости предложенной
схемы разделения секрета
Пусть теперь PAÍ — произвольная коалиция участников СРС
) , ... , ,( 21 nmmmS такая, что 1-£ kA . Для указанных выше )0(s и ) , ... ,( 1 ncc обо-
значим AS множество всех элементов 00 Ss Î , каждому из которых соответствует
набор проекций ) :( Aici Î . Более точно: множество AS состоит из всех элемен-
тов 00 Ss Î , для которых существует элемент ZÎ1s такой, что Sisss Î+= 10
def
, и
ic является остатком от деления s на im для всех AiÎ .
Оценим значения параметров AA S=t ,
0
log
S
S
I A
A -= , первый из которых ра-
вен числу опробований, производимых участниками коалиции A для нахождения
секретного ключа )0(s по имеющимся у них проекциям, а второй — «комбина-
торному» количеству информации ([13], стр. 215), содержащейся в наборе проек-
ций ) :( Aici Î о ключе )0(s .
Рассмотрим множество }:][{ SrmxirR AAA Î+Î= Z и определим отображе-
ние AAA SR ®:j , полагая AAAA Rrrmxr Î+= ),Re()(j . Согласно определению
множества AS , отображение Aj сюръективно и, поскольку
)(max)( 0
1
0
1
0
0
sSsR ASsA
Ss
AA
A
A
-
Î
Î
- £= å jj , то
A
A
A
R
S
m
³ , (11)
А. Н. Алексейчук, Ю. Е. Бояринова
92
где
)(max 0
1
def
0
sASSA
A
-
Î
= jm . (12)
Убедимся в справедливости следующих неравенств:
)(
)21(
)(4
)( 1212
AA
A mN
MM
mN
MMR
+
+-
-
³ pp , (13)
1
)(
2 2 +£
A
A mN
M
m . (14)
Для доказательства формулы (13) заметим, что в силу определения множест-
ва AR справедливы следующие соотношения:
Û<+£Û<+£ÛÎ
)(4
)(
)(44
1)(
4
1 21
21
AA
A
A
AAA mN
Mr
m
xN
mN
MMrmxNMRr
AA
A
A m
M
r
m
x
m
M
22
21 <+£Û .
Отсюда, используя неравенства (8), получим, что
}
2
1
22
1
2
:][{ 21 -<£+ÎÊ
AA
A m
M
r
m
M
irR Z }1
2
1
2
:][{ 21 -£<+ÎÊ
AA m
M
r
m
M
ir Z .
Следовательно, справедливо неравенство
))1
2
(())1
2
(( 2122 +--³
AA
A m
M
m
M
R rr , (15)
где функция r определена перед формулировкой леммы 3. Заметим теперь, что на
основании неравенства 1MmA £ , вытекающего из первого соотношения (2), и
условия (в) справедлива оценка 2)1
2
( 22 >-
Am
M
. Таким образом, согласно формуле
(15) и утверждению леммы 3, имеет место неравенство
2122 )21
2
()21
2
( ++---³
AA
A m
M
m
M
R pp , совпадающее с формулой (13). Итак,
неравенство (13) доказано.
Модулярная схема разделения секрета над кольцом гауссовых целых чисел
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 93
Убедимся в справедливости формулы (14). Зафиксируем элементы ASs Î0 и
)( 0
1 sr A
-Îj . Заметим, что для доказательства формулы (14) достаточно установить
справедливость следующего утверждения: для любого )( 0
1 sr A
-΢ j существуют
элементы ZÎa , ][im ZÎ такие, что:
mrr a+=¢ , (16)
)()( AmNmN = , (17)
)(
2
AmN
M
<a . (18)
Действительно, при выполнении указанного утверждения мощность множества
)( 0
1 sA
-j не превосходит количества целых точек a в интервале
)
)(
,
)(
( 22
AA mN
M
mN
M
- , которое, в свою очередь, не превышает 1
)(
2 2 +
AmN
M
.
Итак, пусть )( 0
1 sr A
-΢ j . Обозначим irrr 21 += , irrr 21 ¢+¢=¢ , immmA 21 += ,
issrmxs AA 10 +=+= , (19)
issmrxs AA 10 ¢+=¢+=¢ . (20)
Отметим, что, поскольку Sss ΢ , , то
21 2
1
2
1 MsM <£ , 21 2
1
2
1 MsM <¢£ . (21)
Кроме того, на основании условий (а), (б) и утверждения леммы 2 справедливо
равенство 1),( 21 =mm .
Из формул (19), (20) следует:
22110 )Re()Re( mrmrrmxs AA -=+= , (22)
22110 )Re()Re( mrmrmrxs AA ¢-¢=¢+= . (23)
Вычитая равенство (23) из равенства (22), получим, что 222111 )()(0 mrrmrr ¢--¢-= ,
откуда в силу взаимной простоты чисел 1m и 2m следует, что существует элемент
ZÎa такой, что
А. Н. Алексейчук, Ю. Е. Бояринова
94
211 mrr a+=¢ , 122 mrr a+=¢ . (24)
Положим 12 immm += . Тогда на основании соотношений (24) выполняются
равенства (16), (17). Далее, в силу соотношений (17), (19) и (20)
AA mmmrrss a-=¢-=¢- )( ; следовательно, )(|| || AmNss a=¢- . Наконец, в силу
неравенств (21)
2 |||| || Mssss <¢+£¢- ,
откуда вытекает неравенство (18). Таким образом, сформулированное выше ут-
верждение, а вместе с ним и формула (14), доказаны.
Докажем теперь следующую теорему, устанавливающую оценки криптогра-
фической стойкости описанной выше схемы разделения секрета.
Теорема. Пусть PAÍ — произвольная коалиция участников СРС
) , ... , ,( 21 nmmmS такая, что 1-£ kA . Тогда, каким бы ни был секретный ключ
0
)0( Ss Î , для его восстановления по набору проекций ):( Aici Î участникам коа-
лиции A потребуется выполнить не менее
4
2
21
2 1
)2(4
|| M
MM
MS AA ppt --
+
³= (25)
опробований элементов множества 0S . При этом количество информации относи-
тельно ключа )0(s , содержащейся в наборе ):( Aici Î , удовлетворяет неравенству:
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
è
æ
--
÷
÷
÷
÷
÷
ø
ö
ç
ç
ç
ç
ç
è
æ
+
-£
4
22
1
21
2 1
2
1
1
4
log
MM
M
MM
M
I A
pp
. (26)
Доказательство. На основании формул (11), (13) и (14)
.
2)(
)(
)(
)21(
2)(
)(
)(4
)(
2
12
2
12
MmN
mN
mN
MM
MmN
mN
mN
MMR
S
A
A
A
A
A
AA
A
A
+
×
+
+-
-
+
×
-
³³
p
p
m
(27)
Модулярная схема разделения секрета над кольцом гауссовых целых чисел
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 95
Поскольку 1)( MmN A £ , то первое слагаемое в правой части неравенства (27)
больше либо равно 1
)2(4)2(4
)(
21
2
21
12 -
+
³
+
-
MM
M
MM
MM pp . Следовательно, для дока-
зательства неравенства (25) достаточно показать, что:
4
2
2
12
2)(
)(
)(
)21( M
MmN
mN
mN
MM
A
A
A
£
+
×
+
+ . (28)
Заметим, что выражение в левой части неравенства (28) равно
4
2
12
2
12 22
))(21(
)(
2
)(
1))(21(
M
MM
mN
M
mN
MM
A
A
++
£
+
++ ,
поскольку uvvu 2³+ для любых 0 , >vu . Далее, используя неравенство
21 36
1 MM < , получим
4
2
4
24
2
12
6
7
22
21
22
21 MM
M
MM
<×
+
£÷
÷
ø
ö
ç
ç
è
æ ++ ,
откуда и следует справедливость неравенства (28).
Итак, формула (25) доказана. Справедливость неравенства (26) следует непо-
средственно из оценок (25) и (6). Теорема доказана.
Сравнительный анализ стойкости модулярных схем
разделения секрета над кольцами целых и гауссовых
целых чисел соответственно
Рассмотрим модулярную СРС ) , ... , ,( 21
)0(
nmmm ¢¢¢S над кольцом Z , соответст-
вующую последовательности натуральных чисел nmmm ¢¢¢ , ... , , 21 , удовлетворяющих
условию
A
kA
PAA
kA
PA
mMmM ¢=¢<¢=¢
=
Í
-=
Í :
def
2
1
:
def
1 min max , (29)
где Õ
Î
¢=¢
Ai
iA mm , PAÍ . Указанная СРС является ),( nk -пороговой схемой разде-
ления секрета для множества секретных ключей }:{ 20100 MsMsS ¢<¢<¢Î¢=¢ Z [1].
Справедливо равенство
А. Н. Алексейчук, Ю. Е. Бояринова
96
1120 -¢-¢=¢ MMS . (30)
Пусть PAÍ — коалиция участников СРС ) , ... , ,( 21
)0(
nmmm ¢¢¢S такая, что
1-£ kA . Тогда для параметров At ¢ и AI ¢ , которые определяются аналогично вве-
денным выше параметрам At и AI соответственно, справедливы следующие
оценки:
111 1212
1
12 +
¢
¢-¢
£¢£-
¢
¢-¢
£-
¢
¢-¢
A
A
A m
MM
m
MM
M
MM t , (31)
÷÷
ø
ö
çç
è
æ
¢-¢
-¢-¢
+¢£¢£÷÷
ø
ö
çç
è
æ
¢
-¢-¢
+¢
12
12
1
2
12
2
1
loglog
1
loglog
MM
MMMI
M
MMm AA . (32)
Далее ограничимся рассмотрением коалиций PAÍ , удовлетворяющих усло-
вию 1MmA ¢=¢ . В этом случае при больших значениях 1M ¢ и 2M ¢ справедливы сле-
дующие (приближенные) равенства:
1
12
M
MM
A ¢
¢-¢
=¢t , (33)
1log MI A ¢=¢ . (34)
Сравним значения параметров (33) и (34) с оценками (25) и (26) соответст-
венно. Предположим, что СРС ) , ... , ,( 21 nmmmS и ) , ... , ,( 21
)0(
nmmm ¢¢¢S удовлетво-
ряют следующему условию:
)( ii mNm =¢ , ni ,1Î . (35)
В этом случае )( AA mNm =¢ для любого PAÍ ; в частности, 11 MM ¢= , 22 MM ¢= .
Заметим, что при выполнении условия (35) множества ключей в рассматриваемых
схемах разделения секрета имеют различные мощности:
20 MS = , 120 MMS -=¢ (36)
(равенства (36) являются приближенными, см. формулы (6) и (30)). Поэтому кор-
ректное сравнение стойкости указанных СРС предполагает использование пара-
метров AI , AI ¢ .
Пусть ¥®21 , MM так, что
Модулярная схема разделения секрета над кольцом гауссовых целых чисел
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 97
¥®
1
4
3
2
M
M , 0
1
2 ®
M
M
. (37)
Тогда на основании формул (26) и (34) справедливо следующее неравенство:
)1(
4
log 2 oMII AA +÷
ø
ö
ç
è
æ³-¢
p , (38)
где 0)1( ®o при ¥®21 , MM . Это означает, что количество информации о сек-
ретном ключе, содержащейся в проекциях участников запрещенной коалиции A
СРС ) , ... , ,( 21 nmmmS , примерно на ÷
ø
ö
ç
è
æ
24
log Mp бит меньше, чем количество
информации о ключе, содержащейся в проекциях участников такой же коалиции
СРС ) , ... , ,( 21
)0(
nmmm ¢¢¢S . Аналогичный результат, свидетельствующий о более
высокой стойкости предложенной СРС по сравнению с модулярной схемой раз-
деления секрета [1], получается и в том случае, когда мощности множеств ключей
в обеих СРС (практически) совпадают.
Приведем конкретный пример, иллюстрирующий последнее утверждение.
Пусть }4 ,3 ,2 ,1{=P , 2=k , 125 2
1 +==¢m , 1310 2
2 +==¢m , 22
3 3213 +==¢m ,
1417 2
4 +==¢m и 4321 , , , mmmm — целые гауссовы числа с нормами
4321 , , , mmmm ¢¢¢¢ соответственно (например, можно положить im += 21 , im += 32 ,
im 323 += , im += 44 ). Для любого 4,1Îi зададим последовательности чисел
t
iti mm =, , ( )titi mm ¢=¢, , ... ,2 ,1=t . (39)
Отметим, что для любого натурального t числа tm ,1 , tm ,2 , tm ,3 и tm ,4 удовлетво-
ряют сформулированным выше условиям (а) и (б).
Обозначим:
( )tA
A
PAt mM ¢=
=
Í
1||
:
,1 max , ( )tA
A
PAt mM ¢=
=
Í
2||
:,2 min . (40)
Тогда
t
tM 17,1 = , t
tM 50,2 = , ... ,2 ,1=t . (41)
Отметим также, что ¥®÷÷
ø
ö
çç
è
æ
=
2
,1
4
3
,2
289
5050
t
t
t
M
M
, 0
289
50 2
,1
2
1
,2 ®÷
ø
ö
ç
è
æ=
t
t
t
M
M
, ¥®t (см.
формулы (37)).
А. Н. Алексейчук, Ю. Е. Бояринова
98
Пусть теперь 80=t . Рассмотрим )4,2( -пороговые модулярные схемы разде-
ления секрета, первая из которых (над кольцом Z) определяется последовательно-
стью целых чисел
40
40,1 5=¢m , 40
40,2 10=¢m , 40
40,3 13=¢m , 40
40,4 17=¢m , (42)
вторая (над кольцом ][iZ ) — последовательностью гауссовых целых чисел
( )80
80,2 3 im += , ( )80
80,3 32 im += , ( )80
80,4 4 im += . (43)
Подчеркнем, что числа (43) удовлетворяют сформулированным выше усло-
виям (а), (б) и (в).
Сравним значения параметров, характеризующих стойкость СРС, построен-
ных на основе последовательностей (42) и (43) соответственно.
Согласно равенствам (36), (41), мощности множеств ключей в рассматривае-
мых СРС равны соответственно 4040
40,140,20 1750 -=-=¢ MMS и 40
80,20 50== MS .
Отметим, что 40
0
4040 50 )31(50 <¢<- - S , так, что соотношение 1
00
-×¢ SS прак-
тически равно 1. Далее, на основании равенства (33) число ключей, которые по-
требуется перебрать одному из участников СРС над кольцом Z , равно:
62
40
40,1
40,140,2 219,1 1
17
50
×»-÷
ø
ö
ç
è
æ=
-
=¢
M
MM
At . (44)
При этом согласно неравенству (25), число ключей, которые необходимо пере-
брать любому участнику СРС над кольцом ][iZ , равно:
>×--
÷÷
÷
÷
÷
ø
ö
çç
ç
ç
ç
è
æ
÷
ø
ö
ç
è
æ+
÷
ø
ö
ç
è
æ³ 20
40
80
501
289
5021
1
17
50
4
p
p
t A 12
4
1)21(
17
50
4
1248
80
-×»--÷
ø
ö
ç
è
æ - pp . (45)
Итак, сравнивая выражения (44) и (45), заключаем, что вычислительная стой-
кость СРС, соответствующей системе гауссовых целых чисел (43), примерно в
622 раз выше вычислительной стойкости СРС, соответствующей системе целых
чисел (42), при (практически) одинаковых мощностях множеств секретных клю-
чей в обеих схемах.
В заключение отметим, что предложенную конструкцию СРС
) , ... , ,( 21 nmmmS нетрудно модифицировать таким образом, чтобы получить схе-
мы разделения секрета над кольцом ][iZ , аналогичные целочисленным модуляр-
ным СРС, описанным в [2–4]. Стойкость указанных модифицированных схем раз-
Модулярная схема разделения секрета над кольцом гауссовых целых чисел
ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2007, Т. 9, № 1 99
деления секрета можно оценить, проведя рассуждения, аналогичные изложенным
выше при доказательстве соотношений (25), (26).
1. Mignotte M. How to Share a Secret // Advances in Cryptology — EUROCRYPT’82, Proceed-
ings. — Springer Verlag, 1983. — P. 371–375.
2. Asmuth C., Bloom J. A modular Approach to Key Safeguarding // IEEE Trans. on Inform. Th. —
1983. — IT-29. — P. 208–210.
3. Goldreich O., Ron D., Sudan D. Chinese Remainder with Errors // IEEE Trans. on Inform. Th.
— 2000. — IT-46. — P. 1330–1338.
4. Quisquater M., Preneel B., Vanderwalle J. On the Security of the Threshold Scheme Based on
the Chinese Remainder Theorem // Public Key Cryptography — PKC’02, Proceedings. — Springer Ver-
lag, 2002. — P. 199 – 210.
5. Ifrene S. General Secret Sharing Based on the Chinese Remainder Theorem //
http://eprint.iacr.org/2006/166.
6. Shamir A. How to Share a Secret // Comm. ACM. — 1979. — Vol. 22, N 1. — P. 612–613.
7. Синьков М.В., Бояринова Ю.Е., Калиновский Я.А., Трубников П.В. Развитие задачи разде-
ления секрета // Реєстрація, зберігання і оброб. даних. — 2003. — Т. 5, № 4. — С. 90–96.
8. Галибус Т.Н., Матвеев Г.В. Особенности модулярного разделения секрета //
www.cryptography.ru/db/20.02.2004.
9. Бояринова Ю.Е., Одарич Я.В. Восстановление информации в задаче разделения секрета
для гиперкомплексных числовых систем 2-го порядка с помощью алгоритма Евклида // Реєстрація,
зберігання і оброб. даних. — 2005. — Т. 7, № 1. — С. 103–114.
10. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел / Пер. с англ.
— М.: Мир, 1987. — 416 с.
11. Чандрасекхаран К. Введение в аналитическую теорию чисел / Пер. с англ. — М.: Мир,
1974. — 188 с.
12. Ноден П., Китте К. Алгебраическая алгоритмика / Пер. с франц. — М.: Мир, 1999. —
720 с.
13. Колмогоров А.Н. Теория информации и теория алгоритмов. — М.: Наука, 1987. — 304 с.
Поступила в редакцию 01.03.2007
УДК 621.391:519.7
УДК 621.391:519.7
Предложена конструкция модулярной схемы разделения секрета над кольцом гауссовых целых чисел, обладающей большей вычислительной стойкостью по сравнению с известной целочисленной модулярной схемой разделения секрета.
Ключевые слова: модулярная схема разделения секрета, вычислительная стойкость, кольцо гауссовых целых чисел.
Введение
Для любого обозначим целую часть числа . Положим:
Для любого обозначим целую часть числа . Положим:
Для любого обозначим целую часть числа . Положим:
Из формул (19), (20) следует:
Заметим, что выражение в левой части неравенства (28) равно
Обозначим:
|
| id | nasplib_isofts_kiev_ua-123456789-50878 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1560-9189 |
| language | Russian |
| last_indexed | 2025-11-29T11:28:00Z |
| publishDate | 2007 |
| publisher | Інститут проблем реєстрації інформації НАН України |
| record_format | dspace |
| spelling | Алексейчук, А.Н. Бояринова, Ю.Е. 2013-11-05T23:45:19Z 2013-11-05T23:45:19Z 2007 Модулярная схема разделения секрета над кольцом гауссовых целых чисел / А.Н. Алексейчук, Ю.Е. Бояринова // Реєстрація, зберігання і оброб. даних. — 2007. — Т. 9, № 1. — С. 87-99. — Бібліогр.: 13 назв. — pос. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50878 621.391:519.7 Предложена конструкция модулярной схемы разделения секрета над кольцом гауссовых целых чисел, обладающей большей вычислительной стойкостью по сравнению с известной целочисленной модулярной схемой разделения секрета. Запропоновано конструкцію модулярної схеми розподілення секрету над кільцем гауссових цілих чисел, що має більшу обчислювальну стійкість у порівнянні з відомою цілочисловою модулярною схемою розподілення секрету. The design modulo secret sharing scheme over a ring of Gaussian integer, possessing greater computing stability in comparison with known integer modulo secret sharing scheme is offered. ru Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Методи захисту інформації в комп’ютерних системах і мережах Модулярная схема разделения секрета над кольцом гауссовых целых чисел Модулярна схема розподілення секрету над кільцем гауссових цілих чисел Modulo Secret Sharing Scheme Over a Ring of Gaussian Integers Article published earlier |
| spellingShingle | Модулярная схема разделения секрета над кольцом гауссовых целых чисел Алексейчук, А.Н. Бояринова, Ю.Е. Методи захисту інформації в комп’ютерних системах і мережах |
| title | Модулярная схема разделения секрета над кольцом гауссовых целых чисел |
| title_alt | Модулярна схема розподілення секрету над кільцем гауссових цілих чисел Modulo Secret Sharing Scheme Over a Ring of Gaussian Integers |
| title_full | Модулярная схема разделения секрета над кольцом гауссовых целых чисел |
| title_fullStr | Модулярная схема разделения секрета над кольцом гауссовых целых чисел |
| title_full_unstemmed | Модулярная схема разделения секрета над кольцом гауссовых целых чисел |
| title_short | Модулярная схема разделения секрета над кольцом гауссовых целых чисел |
| title_sort | модулярная схема разделения секрета над кольцом гауссовых целых чисел |
| topic | Методи захисту інформації в комп’ютерних системах і мережах |
| topic_facet | Методи захисту інформації в комп’ютерних системах і мережах |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/50878 |
| work_keys_str_mv | AT alekseičukan modulârnaâshemarazdeleniâsekretanadkolʹcomgaussovyhcelyhčisel AT boârinovaûe modulârnaâshemarazdeleniâsekretanadkolʹcomgaussovyhcelyhčisel AT alekseičukan modulârnashemarozpodílennâsekretunadkílʹcemgaussovihcílihčisel AT boârinovaûe modulârnashemarozpodílennâsekretunadkílʹcemgaussovihcílihčisel AT alekseičukan modulosecretsharingschemeoveraringofgaussianintegers AT boârinovaûe modulosecretsharingschemeoveraringofgaussianintegers |