Модулярная схема разделения секрета над кольцом гауссовых целых чисел

Предложена конструкция модулярной схемы разделения секрета над кольцом гауссовых целых чисел, обладающей большей вычислительной стойкостью по сравнению с известной целочисленной модулярной схемой разделения секрета. Запропоновано конструкцію модулярної схеми розподілення секрету над кільцем гауссови...

Full description

Saved in:
Bibliographic Details
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