close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Коды, исправляющие ошибки, и
криптография с открытым
ключом
Крук Евгений Аврамович
каф. Безопасности информационных систем
Санкт-Петербургский Государственный Университет
Аэрокосмического Приборостроения
Содержание

Криптография с публичным ключом




Что такое коды, исправляющие ошибки



Декодирование , как «простая задача»
Декодирование, как «трудная задача»
Кодовые криптосистемы



Классическая криптография и криптография с публичным
ключом(КПСК)
Трудные задачи и КСПК
Постквантовая криптография
Система Мак Элиса
Модификации
Проблемы и перспективы развития «легкой криптографии»


Применение
Задачи легкой криптографии
Классическая криптография
Злоумышленник
B
f,f-1
A
f,f-1
y  f ( x)

x f
Примеры



ГОСТ
DES
AES
1
( y)
Простые задачи
Криптография с публичным ключом
Ai
Aj
Функция с закрытыми дверями:
y  f ( x), x  f 1 ( y, K )
x  f 1 ( y,)
Абоненты
Простая задача
Сложная задача
Публичные ключи Секретные ключи
A1
f1(.)
f1-1(.,k1)
AN
fN(.)
fN-1(.,kN)
Система RSA
Открытый
ключ


Секретный
ключ
n

t
s
st  1mod  (n)
pq
E : x  y  xt mod n
D : y  y s  x st  xk ( n)1  x mod n
Стойкость – задача факторизации
Шифрование и дешифрование –
трудоемкие операции
5
КСПК и квантовый компьютер



Shor 1996: Для квантового компьютера
существуют эффективные алгоритмы
разложения чисел на множетели
До практической реализации квантового
компьютера еще далеко,но готовиться к
этому нужно уже сейчас
Нельзя «сидеть» на одной задаче
Решение: КСПК, основанные на NP-полных задачах
Пример : КСПК, основанные на задачах теории кодирования
Что такое трудная задача?
Недетерминированный алгоритм
P
P
NP C
...
...
P1 (n)
...
P2 (n)
Ответ за
P3 (n)
Для создания криптосистемы нужны
трудная массовая задача и
маскирующее преобразование

7
Криптография и трудные задачи

Общеизвестные КСПК основаны на не NP-полных
задачах



RSA
ElGamal
КСПК на ECC
Факторизация Целых Чисел (IFP)
Дискретный логарифм (DLP)
Дискретный логарифм на
эллиптических кривых (EDLP)
Создание эффективного алгоритма
для решения этих задач
ЭКВИВАЛЕНТНО
Взлому криптосистемы
Пример КСПК: Рюкзак - I

Проблема рюкзака




Трудная задача


С = m1*P1+m2*P2+…+mnPn
mi принадлежит {0,1}
P1, P2,…,Pn и С – известно
Определить m1, … mn
P1, P2,…,Pn ― произвольная последовательность
Легкая задача

P1, P2,…,Pn ― сверхвозрастающая последовательность
Пример КСПК: Рюкзак - II

Секретный ключ



Публичный ключ



P1, P2,…,Pn – произвольная последовательность
Pi=Si*b mod N, для i=1..n
Шифрование



S1, S2,…,Sn – cверхвозрастающая
последовательность
b, N
m– сообщение, C–шифротекст
С = m1*P1+m2*P2+…+mnPn
Дешифрование

С’=C*b-1 mod N =(m1*S1+m2*S2+…+mnSn) mod N
Недоказуемость стойкости КСПК
Трудная массовая
П
задача П

 (I )
I
П0
Подмножество простых
индивидуальных задач П0
 ( ( I ))



- Скрывающее преобразование
- Раскрывающее преобразование
Немного о кодах,
исправляющих ошибки
1948, К.Шеннон
Для любого канала связи:
Прямая теорема:
R  C  Pош  0
Обратная теорема:
R  C  Pош  
R
- скорость передачи
C
- пропускная способность канала

кодирование
декодирование 

1
 111

100

0
 000
исправляется
1 ошибка
 000

1
 11111

0
10100
 00000
2 ошибки
 00000

1

 1............1
n/2 ошибок
n

0
 0...........0
n
Pош  0
n 
R
 0
n 
14
кодирование

k n
R
R
k
0
n n 
1
lg N
n
d (ai , a j ) - мера непохожести слов
Декодирование: поиск ближайшего по d к принятому кодовому слову
Расстояние Хэмминга
d (ai , a j ) - число несовпадающих позиций кодового слова
15
Три параметра системы передачи
Три параметра кода
n - длина кода
V - скорость передачи
R - скорость кода
Pош - вероятность ошибки
N - мощность кода
щ - сложность реализации
щ
 Pош
V
n
d
R
Задачи кодирования:
n(d , R)  min
N (n, d )  max
d (n, N )  max
16
Границы для N (n, d )
d  2t  1
- Хэмминга (плотной упаковки)
объем пространства
N
объем шара радиусом t
2n
2n
N

Vn,t  t Cni
i 0
- Варшамова-Гилберта
существует код:
объем пространства
N
объем шара радиусом d  1
N
2n
Vn,d 1

2n

d 1
i
C
n
i 0
17
Сравнение границ
n
R  0
n 
d
 0
n n
Двоичный симметричный канал
В среднем pn ошибок

d  2 pn

d
   2p
n
Хэмминга
?
лучшая известная верхняя граница
ВГ
18
Все ли в порядке?
Пропускная способность ДСК
C  1  H ( p)
Скорость кода, лежащего на границе ВГ
RВГ  1  H ( dn1 )
d  2 pn

RВГ  1  H ( 2np )
Скорость кода, лежащего на границе Хэмминга
RХ  1  H ( p),
но кодов на границе Хэмминга при скоростях R < 1 не существует
?
Расстояние кода, возможно, плохо характеризует вероятность ошибки
19
Декодирование
кодовые слова
Декодирование в сфере
Декодирование по минимуму расстояния  в ближайшее слово ( P0 )
Размер сферы и лемма Евсеева
Для любого (n, N , d ) кода декодирование в сфере радиусом r :
r
i
n
C

2
n
i 0
обеспечивает Pош  2 P0
Основная задача прикладной теории кодирования – задача декодирования
20
Проблемы сложности кодирования
Линейные коды
G - порождающая матрица
H - проверочная матрица
GH T  0
Код {a : a  mG} или {a : aH T  0}
Кодирование:
m  a  mG
Декодирование:
b  ae
S  bH T  eH T
Декодирование по минимуму расстояния eH T  S

W (e)  min
Декодирование в сфере радиусом r
eH T  S

W (e)  r
21
Корректирующая способность
линейных кодов
Стандартная расстановка
a1  0
a2
…
a2 k
e1a1 e1 e1
a2 e1
…
a2k e1
…
…
…
…
a2 e2r
…
a2k e2r
e2r a1 e2r
Лемма Евсеева
P0 1P( Er ), EV
Для ДСК
EV
код
Er - множество лидеров смежных классов
- множество из
2 r наиболее вероятных векторов канала, тогда
P( E \( Er EV ))2 P0
- множество векторов веса до
d ВГ
Комбинаторное декодирование

Декодирование по информационным совокупностям
как задача построения (n, r, t)-покрытия
 1  aˆ1  L 1 (b)
...........................
 a * : d (b, a * )  min d (b, aˆi )
i 1, s
 s  aˆs  L s (b)
................
    {1, ..., n} \ 
  { 1, ...,  s }  { 1, ...,  s }
Задача:
Построение (n, r, t)-покрытия { 1 , ...,  s }такого, что для любого t-множества
ошибок I(t) существует  j , у которого I (t )   j  t
Обобщения декодирования по
информационным совокупностям (и.с.)
I Декодирующие совокупности
DC  {, Q}
  { 1, ...,  s }  множество и.с.
 ~ sl
Q  {q1, ..., ql }  множество покрывающих векторов
 , q  L (b  q)  aˆ ( , q)  декодированный вариант принятого слова
Задача:
Построение (n, r,t , )-покрытия { 1 , ...,  s } такого, что для любого
t-множества ошибок I(t) существует  j, у которого I (t )   j  t  
Обобщения декодирования по
информационным совокупностям (и.с.)
III Декодирование с использованием надкодов
- слово кода
A'1
A'2
A
x
*
r
*
x
A' s
- принятое слово
- слово кода
Список слов
кода A' i , требу 
Результирующий список
ющих проверки
s
S   Si
i 1
A
Сложность декодирования
 (n, k ,t )  max{ s ( A' ), | S |}
A'i
Обобщения декодирования по
информационным совокупностям (и.с.)
II Декодирование с использованием укорочений
G
Задача:
Построение (n, m,t , t1 )-покрытия
Сложность декодирования:
 2 (n, k ,t )  s (n1, k , t1 )
k  (n1, k , d1  2t1  1)  код
Сложность алгоритмов
декодирования
Декодирование по минимуму расстояния
Декодирование на основе покрытий
Декодирование в надкодах
Декодирование на основе укорочений
Параметры комбинаторных
декодеров кодов (24,12) и (48,24)
Алгоритм декодирования
Код (24,12)
Код (48,24)
Память
Число
операций с
векторами
длины 24
Память
Число
операций с
векторами
длины 48
По информационным
совокупностям
1К
400
10К
5000
Комбинированное по
информационным
совокупностям
0,1К
120
2К
4500
На основе укорочений
0,5К
50
8К
3000
Декодирование в надкодах 0,5К
50
2К
2000
Путь развития прикладной теории
кодирования – это путь привлечения для
описания кодов развитого математического
аппарата


Линейные коды
Циклические коды
29
Циклические коды
g ( x),
h( x) :
g ( x)h( x)  x n 1
Код {a( x) : a( x)  m( x) g ( x)}
{a( x) : a( x)h( x)  0 mod x n  1}
Кодирование:
m( x)  a( x)  m( x) g ( x)
Декодирование в сфере радиусом t
 i1 ,,  it - корни g ( x)
Найти e(x) такой, что
b( x)  a( x)  e( x)
j

S

e
(

)
 ij


deg e( x)  t
30
Алгебраическое
декодирование
Дано:
 1  ...  n 1 

2
2 ( n 1) 
 2t-вектор S над GF(q)
1

...


,   GF (q)
Проверочная матрица H  
... ... ...
... 

2t
2 t ( n 1) 
... 
 1 

Найти:
eH T S
e:
 wt (e)t
Алгебраическое
декодирование
eH S  b( )s j , j1,...,2t
j
T

S( s1,......,s2t )
Y1 X 1 Y2 X 2 ...Y2t X 2t s j
j
j
j1,.....,2t
j
Guruswami-Sudan algorithm

Interpolation step: Find a polynomial Q(x,y) having
all points (i,yi) as roots of multiplicity r




Reduces to solving a system of linear equations
Equations are highly structured
Factorization step: Find all polynomials
f(x): deg f(x)≤k, such that Q(x,f(x))=0
Verification step: Check if ( f (1 ),..., f ( n )) matches with
(y1,…, yn) in at least t positions
Декодирование как сложная задача
G(n, k ) :{a : aH T  0}
H - проверочная матрица
GH T  0 G - порождающая матрица
Кодирование
m  a  mG
t  1n log щ
щ  2nt
1/2
0.1
1/2
1
34
Декодирование как простая задача
1
1
1 
H 
 

2t
1 

1 
  n 1 

 

 ( 2t ) n 1 
b  ae
a( j )  0
b( x)  a( x)  e( x)
j  1, 2t
n 1
S j  b( )  e( )   j ( i ) j   i1 ( i1 ) j    i ( i ) j
j
j
i 0
 i  Y1 ,  i  X1 ,,  i  Y ,  i  X
1
1
S j  Y1 X1j   Y Xj
j  1, 2t

 ( x)  (1  xX i )   x    1 x  1
i 1
 S1   1S2    1S   S 1


 S   S     S
 1  1
1 2 1   S 2
  
35
Система Мак-Элиса
Открытый
ключ
G
t
Секретный
ключ

MG0 P
M - невырожденная
P - перестановочная
Шифрование
x  y  xG  e
e - случайный вектор веса  t
Расшифрование
y·P 1  xM G0  eP 1
x'
декодирование в коде
G0
x'
x '·M 1  x


NP-полная задача декодирования
Шифрование и расшифрование - полиномиальные задачи
36
Системы публичных ключей
Открытый ключ Секретный ключ
K

=
MGP
Публичный ключ
Система Мак-Элиса

Шифрование: y=xK+e, K=MGP
сообщение


Дешифрование:
Случайный вектор веса t
(G)
y' yP-1  (xM)G  eP -1 

 z  xM
-1
x  zM
Задача нелегального
пользователя:
(G' )
y' 
 x
Параметры системы McEliece

Система McEliece




Код (1024,524), t=50
длина публичного ключа - 66 КБ
рабочий фактор - 256
длина секретных ключей - 2-4 КБ
t  1n log щ
1/2
0.1
1/2
1
Система McEliece и ее модификациии
Ошибка
eE
кодирование
Cleartext
X



Codewords
a

Ciphertext
y=a+e
McEliece [1978]: E = { e : w( e )  t }
[1993]:
E = { e = e’ M : w( e’ )  t, M – секр }
[1998 …]:
E = { e, e – из специального множества }
КСПК на основе полного
декодирования
Публичные ключи
G' GM , E E  {e | e  e' M , wt (e)  t}
Секретные ключи
M ,G
Способ шифрования
x  y  xG'e, e  E
Способ дшифрования
y'  yM 1  xG  e'
 (G )
y' 
 x
Задача злоумышленника: декодирование в G’ вектора из E
x  y  xG'e, e  E
Задание множества E
M 2  M1M ; M1 : e' ' M1  e' ; wt (e' ' )  t , wt (e' )  t

Параметры кодовых криптосистем
КСПК на основе полного декодирования






Код (256,128), t=8
M, M2 – (256×256) - двоичные матрицы
длина публичных ключей - 2-4 КБ
рабочий фактор - 262
длина секретных ключей - 2-4 КБ
Система McEliece




Код (1024,524), t=50
длина публичного ключа - 66 КБ
рабочий фактор - 261
длина секретных ключей - 2-4 КБ
Сравнение с известными КСПК
Сравнение КСПК на основе полного декодирования
с системами RSA и McEliece
Параметр
RSA
McEliece
Сложность
вскрытия
Совпадает
Совпадает
Скорость
шифрования
Скорость
дешифрования
Длина секретных
ключей
Длина публичных
ключей
Превосходит
Совпадает
Превосходит
Совпадает
совпадает
Совпадает
Длиннее
Короче
Подпись на кодах
Множество сообщений
X

F(X)
Множество
синдромов
A
 - процедура декодирования кода A
Процедура подписывания
x
F
S=F(x)

z
(x,z) – подписанное сообщение

Задача: Построение функции F [1997 ….]
Сравнение
с
известными
подписями
Сравнение подписи Крука-Кабатянского-Смитса
с известными подписями
Параметр
RSA
Эль-Гамаля
Хинмея
АлбадиВиккера
Сложность
подделки
Cовпадает
Совпадает
Превосходит Превосходит
Скорость
шифрования
Превосходит
Совпадает
Совпадает
Совпадает
Скорость
дешифрования
Превосходит
Превосходит
Совпадает
Совпадает
Длина секретных
ключей
Длиннее
Длиннее
Совпадает
Совпадает
Длина публичных Длиннее
ключей
Длиннее
Совпадает
Совпадает
Где еще используются коды?

Решения, основанные на кодах, существуют в








Криптосистемы с публичным ключом
(КСПК)
Цифровая подпись
Аутентификация
Разделение секрета
Дизайн и криптоанализ потоковых
шифров
Управление ключами
Стеганография
Водяные знаки
Часть - II
ПРОБЛЕМЫ И
ПЕРСПЕКТИВЫ
РАЗВИТИЯ ЛЕГКОЙ
КРИПТОГРАФИИ
Необходимость вычислительно
экономных алгоритмов




Сети, использующие маломощные вычислительные
устройства

Сенсорные сети.

Ad-hoc сети (мобильные сети)

Интеллектуальный дом
Проблемы энергоэффективности

Проблема батарейки
Проблемы реального времени

Алгоритмы, выполняемые «на лету»
Упрощенные процедуры обработки

«Легкая» криптография
Легкая криптография


Конфликт между стойкостью и простотой

Требования конфиденциальности
Коды, как основа легкой криптографии

Полиномиальные процедуры шифрования и
расшифрования

Умеренная память
Задачи легкой криптографии
Аутентификация



Аутентификация сообщений – использование
одноразовых подписей. Одним из возможных
вариантов решений этой задачи является
построение систем одноразовых подписей на
основе множеств, свободных от покрытий.
Аутентификация пользователей – наиболее
сложной и востребованной задачей является
задача удаленной аутентификации. Для ее
решения может быть использован
модифицированный алгоритм Мак Эллиса.
Задачи легкой криптографии
Совместное обеспечение защиты информации от
случайных и преднамеренных искажений


Естественным вариантом решения такой задачи
является использование модифицированного
алгоритма Мак Эллиса, позволяющего гибко
распределять имеющуюся корректирующую
способность кода на защиту от преднамеренных и
случайных искажений при передаче или хранении
конфиденциальных данных, а так же на защиту от
несанкционированного доступа. Такой подход
позволяет решить в одном устройстве задачи
помехозащищенности и конфиденциальности.
Задачи легкой криптографии
Системы безопасного хранения и обработки
информации





Разграничение доступа к информации. В этом случае,
обычно рассматривают многоуровневые структуры
доступа и коалиционные структуры. Использование
вложенных кодов.
Разделение секрета. Кодовые структуры общего вида.
Обеспечение анонимности при доступе к информации,
хранящейся в «облачных» сетях на основе
модификации алгоритма Мак-Элиса.
Реализация систем скрытых вычислений, особенно
актуальная при активном использовании «облачных»
хранилищ баз данных .
Защита облачных
вычислений
Распределенное хранение и использование
данных
Задачи:
–
–
–
Создание общего защищенного хранилища
данных
Организация защищенных вычислений
Разработка облачной политики безопасности
52
Проверку временем
никто не отменял
Вопросы
Спасибо.
Вопросы?
Модификации
Открытый
ключ
G
Секретный
ключ

W1
 множество 


ошибок вида 


eW


Шифрование
y  xG  eW1
G0W
W1 
W  
W2 
W - невырожденная
e - случайный вектор
веса  t
Расшифрование
1
W1  W1 
1
yW  xG0  (e, 0)     
W2  W2 
 xG0  (e, 0)
декодирование в
G0
x
55
Коды, исправляющие ошибки
m
k
 a
e
канал
n
Параметры кода
R  1n log N
1
b  ae
n

aˆ
n
n, N , d  2t  1
Граница Хэмминга
ЛП
В.-Г.
1/2
1
 d /n
56
Система публичных ключей на
основе полного декодирования
E  {e | e  e' M , wt (e)  t}
Публичные ключи
G ' , M 2  M 1M
G' GM , E
Секретные ключи
M ,G
M ,G
Способ шифрования
x  y  xG'e, e  E
y  xG'e' ' M 2 , wt (e' ' )  t
Способ дешифрования
y'  yM 1  xG  e'
(G )
y' 
 x
y  xG  e' ' M1
Задача нелегального пользователя: декодирование в G’ вектора из E
x  y  xG'e, e  E
Задание множества E
y  xG'e' ' M 2 , wt (e' ' )  t
M 2  M1M ; M1 : e' ' M1  e' ; wt (e' ' )  t , wt (e' )  t
Подпись на кодах - I
сообщение
подпись
u
z
F1(u)
?
= F2(z)

Публичные ключи:




Секретные ключи

Множество F(u)
сообщений u
H – проверочная матрица (n,k) кода A
t – расстояние кода A
F() – нелинейная необратимая функция
 – процедура декодирования кода A
Множество
допустимых
синдромов S
Параметры подписи:
код (1024,424), t=50
F(u) на основе DES
Сложность подделки -261
Длина публичного ключа – 66кБ
Длина секретного ключа – 2-4кБ
Процедура подписывания

u  F (u)  s 
e
(u,z=e) – подписанное сообщение
Процедура проверки
?
F (u )  s
Часть - II
Управление ключами в
ad-hoc сетях
Ad Hoc Сеть



Радиосвязь
Высокая мобильность узлов
Отсутствие инфраструктуры
Сеть может быть быстро создана и настроена
Сеть обладает повышенной живучестью
Криптосистемы c Публичным Ключом
(КСПК)




Цели: конфиденциальность, целостность,
аутентификация, неотрицание авторства
Цели можно достичь, используя КСПК
Узел владеет Публичным Ключом (ПК) и
Секретным Ключом (СК)
Публичный Ключ (ПК)



Секретный Ключ (СК)



Шифрование и проверка подписи
Должен быть известен остальным узлам
Дешифрование и генерация подписи
Узел хранит этот ключ в секрете
Проблема: атака человек в середине
Инфраструктура Публичных Ключей (ИПК)


ИПК реализует вспомогательные службы
для КСПК
Ассоциация между пользователем и его ПК


Защищенное соединение


Сертификат (CERT)
CERT=<Имя, Tнач, Tкон, ПК, Подпись ЦС>
SSL/TLS/WTLS
Управление сертификатами


Выдача, обновление, отзыв
Выполняется Центром Сертификации (ЦС)
Инфраструктура Публичных Ключей (ИПК)
ИПК в Ad Hoc Сетях

Особенности

Топология часто меняется



Маршруты, состав участников
Отсутствие инфраструктуры
Низкая физическая защищенность узлов
Централизованные решения не эффективны
ЦС должен быть распределенным
Распределенный ЦС

(K,N) Схема Разделения Секрета
(СРС)



СКцс распределен между N узлами
Пороговая (7,17)
- схема
K<N узлов могут совершать
вычисления
с СКцс
Участник коалиции
Меньше чем K не могутИнициатор запроса
Задачи распределенного ЦС

Выдача и обновление сертификата


Выдача проекции СКцс новому узлу


используется при самоинициализации сети
Обновление проекций


сертификат имеет срок жизни (надо обновлять)
противодействие постепенному захвату узлов
Введение списка отозванных узлов
Жизнь сети
Развертывание
сети
самоинициа
лизация
обновление обновление
CERT
CERT
Фаза работы
обновление обновление обновление
CERT
CERT
CERT
Фаза
обновления
Проекций
Фаза работы
Проекции (версия 1)
Проекции (версия 2)
Фаза
обновления
Проекций
Требования к протоколам

СКЦА не должен быть раскрыт в процессе
вычислений


Можно проверить на валидность
промежуточные результаты



Разделение Функции вместо Разделения
Секрета
Проверяемое разделение секрета
Устойчивость к отказу отдельных узлов в
процессе выполнения протокола
Низкая коммуникационная сложность
Основной примитив

Много Схем Разделения Секрета (СРС)




Полиномиальная (Shamir)
На китайском теореме об остатках
На помехоустойчивых кодах
…
?

Много КСПК




RSA
ElGamal
McEliece
…
Разделение Функции
Существующее решение:
RSA + Полиномиальная СРС
Полиномиальная СРС
Полиномиальное (K,N)
2
k 1
разделение
секрета
f ( x)  SKCA  f1 x  f 2 x    f k 1 x


Случайный полином степени K-1
Pvi  f (vi ) mod N
Проекция узла vi:
 SKCA восстановление:
f (x)
интерполяция Лагранжа
f1K узламиf k 1
SKCA
производится
W  g , g ,, g
 Публичные свидетели



Обновление Сертификата - I

Требуется периодически
обновлять CERT
Используется распределенная RSA

d1
Идея

X X
d2
 X
dk
X
d1  d 2    d k  SKCA
( d1  d 2  d k )
Обновление Сертификата - II

Инициатор


Посылает запрос на обновление K узлам
Участник коалиции
 Посылает подписанный частичный
сертификат
CERTv j  (cert )

Pv j
mod N
Инициатор


Проверяет частичные сертификаты, используя
публичных свидетелей W
Вычисляет полный сертификат
K
CERT   (CERTv j )
j 1
lv j ( vi )
mod N , l v j ( v i )
-- коэф.
Лагранжа
Обновление Сертификата - III

Достоинства/Недостатка

Удовлетворяет всем требованиям
Выдача Проекции - I



Может использоваться для самоинициализации
сети
k
Идея
Pvi   Pv j  lv j (vi )
Инициатор

j 1
Посылает запрос выбранной коалиции из K соседних
узлов
Недостаток: неустойчив к потере связи с узлами

Каждая пара узлов коалиции {v j , vr }

Секретно договаривается о смешивающих коэффициентах
Недостаток: высокая коммуникационная сложность
d j ,r
Выдача Проекций - II

Pj  Pv j lv j (vi ) mod N
Участник коалиции




d j ,r
Вычисляет P
j
Защищает смешивающими коэфф.
Послать результат
инициатору
Инициатор

Проверяет полученные части, используя
публичных свидетелей W
k
Недостаток: невалидные части
ведут к рестарту
протокола

P

Вычисляет проекцию
Pv i 
j 1
j
Выдача Проекций - III

Достоинства/Недостатки



Неустойчив к отказу узлов
Высокая коммуникационная сложность
Нельзя точно определить узлы,
пославшие невалидные части
Обновление Проекций - I


Защита от “мобильных захватчиков”
Идея
k 1
f update( x)  b1 x    bk 1 x
f new ( x)  f ( x)  f update( x)
f new (0)  SKCA
Pvi  f new (vi ) mod N
Обновление Проекций - II


Совместное генерирование
коалицией f new (x)
Рассылка зашифрованного
и подписанного

f new (x)
Распределенное вычисление f new (vi )


Переход от мультипликативного разделения
секрета к аддитивному
Защита результата вычислений с помощью
смешивающего коэффициента
Обновление Проекций - III

Достоинства/Недостатки



Неустойчив к отказу узлов
Высокая коммуникационная сложность
Нет проверки на валидность
присылаемых частей
Необходимость вычислительно
экономных алгоритмов




Сети, использующие маломощные вычислительные
устройства

Сенсорные сети.

Ad-hoc сети (мобильные сети)

Интеллектуальный дом
Проблемы энергоэффективности

Проблема батарейки
Проблемы реального времени

Алгоритмы, выполняемые «на лету»
Упрощенные процедуры обработки

«Легкая» криптография
1/--страниц
Пожаловаться на содержимое документа