В работах Д. Шаума (см., например: [14, 15]) впервые была предложена схема подписи с верификацией по запросу, в которой участник V (проверяющий подпись)


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Дорджиев,
вложения,
ñíîâíûå ïîíÿòèÿ, îïðåäåëåíèÿ è îáîçíà÷åíèÿ áóäóò äàâàòüñÿ â ñîîòâåòñòâèè ñ ðàáîòîé [10].
Çäåñü îòìåòèì ëèøü ñëåäóþùåå.
êà÷åñòâå îäíîãî èç îñíîâíûõ ìàòåìàòè÷åñêèõ îáúåêòîâ â äàííîé
ðàáîòå èñïîëüçóþòñÿ îäíîñòîðîííèå ôóíêöèè, òî åñòü ôóíêöèè, äëÿ êîòîðûõ íå ñóùåñòâóåò ýôôåêòèâíûõ
àëãîðèòìîâ èíâåðòèðîâàíèÿ.
ïåðâûå òàêîãî ðîäà ôóíêöèþ äëÿ êîíêðåòíîãî êðèïòîãðàôè÷åñêîãî
ïðèëîæåíèÿ (îòêðûòîãî ðàñïðåäåëåíèÿ êëþ÷åé) ïðåäëîæèëè Ó.
Äèôôè è
Õåëëìàí â
ðàáîòå
[11].
Äëÿ ôóíêöèè Äèôôè–Õåëëìàíà âû÷èñëåíèå ñòåïåíåé â ìóëüòèïëèêàòèâíîé ãðóïïå âû÷åòîâ íàä
êîíå÷íûì ïîëåì ÿâëÿåòñÿ ïðîñòîé çàäà÷åé ñ òî÷êè çðåíèÿ ñîñòàâà íåîáõîäèìûõ âû÷èñëåíèé, â òî âðåìÿ
êàê èçâëå÷åíèå äèñêðåòíûõ ëîãàðèôìîâ â ýòîì ïîëå – ïðåäïîëîæèòåëüíî ñëîæíàÿ âû÷èñëèòåëüíàÿ
çàäà÷à.
åîáõîäèìî îòìåòèòü, ÷òî âñå ïðåäëàãàåìûå ñåãîäíÿ îäíîñòîðîííèå ôóíêöèè òîëüêî
óñòü
log
îáîçíà÷àåò, ÷òî
ÿâëÿåòñÿ äèñêðåòíûì ëîãàðèôìîì
ïî îñíîâàíèþ
ãäå
âû÷åòîâ ïî ìîäóëþ
Ë
þáîé ïîëèíîìèàëüíûé àëãîðèòì ìîæåò ïî çàäàííûì
è
âû÷èñëèòü
ëèøü ñ ïðåíåáðåæèìî ìàëîé âåðîÿòíîñòüþ
2.ДДД Èñïîëüçóåìûå ñõåìû è ïðîòîêîëû
Ñõåìà ïðèâÿçêè ê áèòó
ïîçâîëÿåò ó÷àñòíèêó
«ïðèâÿçàòüñÿ» ê çíà÷åíèþ íåêîòîðîãî
áèòà òàêèì îáðàçîì, ÷òîáû íå äàòü âîçìîæíîñòè ó÷àñòíèêó
ïîëó÷èòü êàêóþ-ëèáî èíôîðìàöèþ
î çíà÷åíèè ýòîãî áèòà áåç ñâîåé ïîìîùè, è â òî æå âðåìÿ òàêàÿ ñõåìà äîëæíà ãàðàíòèðîâàòü, ÷òî
õåìà ïðèâÿçêè ê áèòó
) ñîñòîèò èç äâóõ ïðîòîêîëîâ (àëãîðèòìîâ) – ïðîòîêîëà
ñîáñòâåííî ïðèâÿçêè ê áèòó è ïðîòîêîëà îòêðûòèÿ áèòà.
óñòü äàëåå
, òî åñòü ñòðîêà
âûáðàíà ñëó÷àéíî, ñ ðàâíîìåðíûì ðàñïðåäåëåíèåì âåðîÿòíîñòåé ñðåäè âñåõ ñòðîê äëèíû
Äëÿ ïðèâÿçêè ê áèòó
ó÷àñòíèê
èíèöèèðóåò ñõåìó ïðèâÿçêè ê áèòó è ïîëó÷àåò ïî îêîí÷àíèè
åå ðàáîòû ïàðó ïàðàìåòðîâ
è
âûäàåòñÿ ó÷àñòíèêó
, â òî âðåìÿ êàê
èëè
(â çàâèñèìîñòè îò çíà÷åíèÿ áèòà ïðèâÿçêè) õðàíèòñÿ ó÷àñòíèêîì
â ñåêðåòå.
ðè âûïîëíåíèè
ïðîòîêîëà îòêðûòèÿ áèòà ïàðàìåòð
ñòàíîâèòñÿ èçâåñòíûì
, êîòîðûé ìîæåò åäèíñòâåííûì
Ñ
õåìà ïðèâÿçêè ê áèòó
) ïðåäñòàâëÿåò ñîáîé ïàðó äâóõñòîðîííèõ
ïðîòîêîëîâ (
Îòêð
) – ïðîòîêîëà ïðèâÿçêè ê áèòó
Ïðèâ
è
ïðîòîêîëà îòêðûòèÿ áèòà
Îòêð
ïðè ðåàëèçàöèè êîòîðûõ âûïîëíÿþòñÿ ñëåäóþùèå óñëîâèÿ áåçîïàñíîñòè:
Óñëîâèå ïîëíîòû.
Äëÿ ëþáîãî
{0,1}, ëþáîé êîíñòàíòû
� 0 è äëÿ äîñòàòî÷íî áîëüøèõ
âåðîÿòíîñòü
Óñëîâèå îäíîçíà÷íîñòè.
Äëÿ âñåõ âîçìîæíûõ ýôôåêòèâíûõ àëãîðèòìîâ
(âîçìîæíûõ
âåðîÿòíîñòü
(C0,D,r)Îòêð = 0ДДД &ДДД (C1,D,r)Îòêð = 1]ДДД ↵ДДД (r*)Ïðîò = (C0, C1,D)) n-c,ãäå
Óñëîâèå íåðàçëè÷èìîñòè.
) = {(
= (
)} ñåìåéñòâà ñëó÷àéíûõ
ïåðåìåííûõ {
âîéñòâî ïîëíîòû îçíà÷àåò, ÷òî åñëè îáà ó÷àñòíèêà ñëåäóþò ïðîòîêîëó, òî îí êîððåêòíî
çàâåðøèòñÿ ñ âåðîÿòíîñòüþ, áëèçêîé ê 1.
âîéñòâî îäíîçíà÷íîñòè îçíà÷àåò, ÷òî ó÷àñòíèê
ïðè îäíîì è òîì æå çíà÷åíèè
íå ìîæåò îäíîâðåìåííî ïðèâÿçàòüñÿ èëè ê 0, èëè ê
íåðàçëè÷èìîñòè ãîâîðèò î òîì, ÷òî äëÿ âñåõ äîñòàòî÷íî áîëüøèõ
íå ñóùåñòâóåò ñïîñîáà îòëè÷èòü
Дорджиев,
ïðèâÿçêó ê 0 îò ïðèâÿçêè ê 1, êîòîðûé áûë áû ëó÷øå, ÷åì ïðîñòîå óãàäûâàíèå.
ïîñëåäíåå ñâîéñòâî îçíà÷àåò, ÷òî ìû ìîæåì ðàçðåøèòü ó÷àñòíèêó
âûáîð
ïî ñâîåìó óñìîòðåíèþ.
î äàæå â ýòîì ñëó÷àå âåðîÿòíîñòü îáìàíà ó÷àñòíèêà
çâåñòíî, ÷òî ñõåìû ïðèâÿçêè ê áèòó ñóùåñòâóþò, åñëè ñóùåñòâóþò îäíîñòîðîííèå
ïåðåñòàíîâêè.
ðèâåäåì ñõåìó, èñïîëüçóåìóþ â äàííîé ðàáîòå.
óñòü
– ïðîñòîå ÷èñëî è
– áîëüøîé ïðîñòîé äåëèòåëü
– 1.
óñòü òàêæå
1(mod
1. Ýòî óñëîâèå ïðè ïîñòðîåíèè â äàëüíåéøåì ñõåìû ïðèâÿçêè ê áèòó ÿâëÿåòñÿ
îáÿçàòåëüíûì ïî ñëåäóþùåé ïðè÷èíå.
òåðìèíàõ òåîðèè ãðóïï êàæäûé ýëåìåíò
ïîäãðóïïû
(ïðîñòîãî ïîðÿäêà) ãðóïïû âû÷åòîâ ïî ìîäóëþ
ñ îáðàçóþùèì
è ýëåìåíòîì
(1
), òî
åñòü ýëåìåíò
), ìîæåò ñàì ñëóæèòü îáðàçóþùèì ïîäãðóïïû, òî åñòü
1(mod
) ñëåäóåò ñ÷èòàòü îäíîñòîðîííåé ïåðåñòàíîâêîé.
1. Ó÷àñòíèê
2. Ó÷àñòíèê
âûáèðàåò ñëó÷àéíûé ïàðàìåòð
R *
è âû÷èñëÿåò
), ãäå
{0,1} åñòü âûáðàííûé äëÿ ïðèâÿçêè áèò.
3. Ó÷àñòíèê
1. Äëÿ òîãî ÷òîáû ó÷àñòíèê
óáåäèëñÿ, ÷òî çíà÷åíèå
äåéñòâèòåëüíî áûëî ïðèâÿçàíî ê
, îí âûäàåò çàïðîñ ó÷àñòíèêó
î ïåðåäà÷å åìó çíà÷åíèÿ
, êîòîðîå, ïî ñóùåñòâó, ÿâëÿåòñÿ
2. Ó÷àñòíèê
3. Ó÷àñòíèê
ïðîâåðÿåò, âûïîëíÿåòñÿ ëè ñðàâíåíèå
òîáû äîêàçàòü áåçîïàñíîñòü ñõåìû ïðèâÿçêè ê áèòó, íåîáõîäèìî äîêàçàòü, ÷òî ëåæàùèé â
îáëàäàåòñëåäóþùèìèñâîéñòâàìè1. ПППÏðè ïðèâÿçêå ó÷àñòíèêàДДД À ê áëîáó îí ôàêòè÷åñêè ïðèâÿçûâàåòñÿ êДДД áèòóДДД b.2. НННÍåò òàêîãî áëîáà, ïîñðåäñòâîì êîòîðîãî ó÷àñòíèê
ìîã áû îäíîâðåìåííî îòêðûòü
ëèáî 0, ëèáî
1 (èëè, ïî êðàéíåé ìåðå, äëÿ êðèïòîãðàôè÷åñêèõ ïðîòîêîëîâ áëîá ñ ïðèâÿçêîé ê
âû÷èñëèòåëüíî òðóäíî îòëè÷èòü îò áëîáà ñ
3. Ó÷àñòíèê
íå ïîëó÷àåò íèêàêîé èíôîðìàöèè î òîì, êàê
ìîæåò îòêðûòü ëþáîé
ëîá íå äîëæåí íåñòè â ñåáå íèêàêîé èíôîðìàöèè î ëþáîì äðóãîì ñåêðåòå, êîòîðûé
åçîïàñíîñòü ñõåìû ïðèâÿçêè ê áèòó, à ñëåäîâàòåëüíî, è âûïîëíåíèå ñâîéñòâ áëîáà
Òåîðåìà
ñîîòâåòñòâèè ñ ãèïîòåçîé
1.1 è â óñëîâèÿõ îïðåäåëåíèÿ
2.1 ñõåìà
ÿâëÿåòñÿ
Äîêàçàòåëüñòâî òåîðåìû 2.1.
Äëÿ äîêàçàòåëüñòâà òåîðåìû íåîáõîäèìî äîêàçàòü
âûïîëíåíèå óñëîâèé ïîëíîòû, îäíîçíà÷íîñòè è íåðàçëè÷èìîñòè.
Óñëîâèå ïîëíîòû âûïîëíÿåòñÿ äëÿ äàííîé ñõåìû î÷åâèäíî.
Â
ïðîöåññå âûïîëíåíèÿ
ó÷àñòíèê
áåçóñëîâíî ïðèâÿçûâàåòñÿ ê áèòó
, à åñëè îáà ó÷àñòíèêà ñëåäóþò
ïðîòîêîëó, òî îí êîððåêòíî çàâåðøèòñÿ ñ âåðîÿòíîñòüþ 1.
Óñëîâèå îäíîçíà÷íîñòè âûïîëíÿåòñÿ òîãäà è
òîëüêî òîãäà, êîãäà ñïðàâåäëèâà ãèïîòåçà
ïðîòèâíîì ñëó÷àå, åñëè
ìîæåò
вложения,
èçâëå÷ü ëîãàðèôì
òàêîé, ÷òî
), òî îí ìîæåò íàéòè òàêèå
è
, ÷òî
àêèì îáðàçîì, ó÷àñòíèê
ïðè îäíîì è òîì æå çíà÷åíèè
ìîæåò ïî ñâîåìó
óñìîòðåíèþ îòêðûòü ó÷àñòíèêó
àê êàê ôóíêöèÿ
) ïðè óêàçàííûõ êðèïòîãðàôè÷åñêèõ
ñîãëàøåíèÿõ ÿâëÿåòñÿ îäíîñòîðîííåé ïåðåñòàíîâêîé, ëþáîé ýëåìåíò èç ãðóïïû
ìîæåò óñïåøíî
èñïîëüçîâàòüñÿ êàê äëÿ ïðèâÿçêè ê 0, òàê è äëÿ ïðèâÿçêè ê 1. Ýòî îáúÿñíÿåòñÿ åùå è
òåì, ÷òî
âûáðàí ñëó÷àéíî, ðàâíîâåðîÿòíî è íåçàâèñèìî îò äðóãèõ ñîáûòèé.
îýòîìó ó÷àñòíèê
íå ìîæåò îòëè÷èòü ïðèâÿçêó ê 0 îò ïðèâÿçêè ê 1.
î åñòü íåðàçëè÷èìîñòü ðàññìàòðèâàåòñÿ
çäåñü â
òåîðåòèêî-èíôîðìàöèîííîì ñìûñëå – ïðîòèâíèêó «ïðîñòî íå õâàòàåò» èíôîðìàöèè äëÿ
íàõîæäåíèÿ îòëè÷èé ìåæäó ïðèâÿçêîé ê 0 è ïðèâÿçêîé ê 1.
Èíòåðàêòèâíûå ñèñòåìû äîêàçàòåëüñòâ ñ íóëåâûì ðàçãëàøåíèåì
äàííîé ðàáîòå áóäåò èñïîëüçîâàòüñÿ
èíòåðàêòèâíàÿ ñèñòåìà äîêàçàòåëüñòâ ñ
àáñîëþòíî íóëåâûì ðàçãëàøåíèåì
èç ðàáîò [12, 13], ãäå ó÷àñòíèê
äîêàçûâàåò ó÷àñòíèêó
íåðàâåíñòâî äâóõ äèñêðåòíûõ ëîãàðèôìîâ: log
log
, ãäå
– îáðàçóþùèé ãðóïïû âû÷åòîâ
ïî ìîäóëþ
äàííîì ïðîòîêîëå
äîêàçûâàåò, ÷òî log
log
ëåäóþùèå øàãè âûïîëíÿþòñÿ
1. Ó÷àñòíèê
âûáèðàåò
1,
2. Ó÷àñòíèê
ïðîâåðÿåò ñîîòíîøåíèå
ρ) ≡
ñëè îíî âûïîëíÿåòñÿ, òî
= 0, â
3. Ó÷àñòíèê
Ó÷àñòíèê
ïðîâåðÿåò, ÷òî âûïîëíÿþòñÿ ñîîòíîøåíèÿ èç ñëåäóþùèõ äâóõ èõ ïàð:
(mod
) è
(mod
).
ñëè äà, òî ïîñûëàåò
çíà÷åíèå
5. Ó÷àñòíèê
ïðîâåðÿåò, ÷òî
ñëè âî âñåõ
öèêëàõ ïðîâåðêà â ï. 5 âûïîëíåíà óñïåøíî, òî ó÷àñòíèê
ïðèíèìàåò
Òåîðåìà
ÿâëÿåòñÿ ïðîòîêîëîì äîêàçàòåëüñòâ ñ àáñîëþòíî íóëåâûì
ðàçãëàøåíèåì.
2.3.ДДД Ñõåìà ïîäïèñè ñ âåðèôèêàöèåé ïî çàïðîñóВВВÂ ðàáîòàõ Ä.
(ñì., íàïðèìåð:
[14, 15]) âïåðâûå áûëà ïðåäëîæåíà
ñõåìà
âåðèôèêàöèåé ïî çàïðîñó
, â êîòîðîé ó÷àñòíèê
(ïðîâåðÿþùèé ïîäïèñü) íå ìîæåò îñóùåñòâèòü
âåðèôèêàöèþ ïîäïèñè áåç ïîìîùè ó÷àñòíèêà
(ïðîñòàâëÿþùåãî ïîäïèñü).
àêèå ñõåìû ìîãóò
ýôôåêòèâíî èñïîëüçîâàòüñÿ â òîì ñëó÷àå, êîãäà ôèðìà-èçãîòîâèòåëü ïîñòàâëÿåò ïîòðåáèòåëþ
íåêîòîðûé èíôîðìàöèîííûé ïðîäóêò (íàïðèìåð, ïðîãðàììíîå îáåñïå÷åíèå) ñ
ïðîñòàâëåííîé íà
íåì ïîäïèñüþ óêàçàííîãî âèäà.
äíàêî ïðîâåðèòü ýòó ïîäïèñü, êîòîðàÿ ãàðàíòèðóåò ïîäëèííîñòü
ïðîãðàììû èëè îòñóòñòâèå åå ìîäèôèêàöèé, ìîæíî, òîëüêî óïëàòèâ çà íåå.
îñëå ôàêòà îïëàòû
ôèðìà-èçãîòîâèòåëü äàåò ðàçðåøåíèå íà âåðèôèêàöèþ êîððåêòíîñòè ïîëó÷åííûõ ïðîãðàìì.
õåìà ñîñòîèò èç òðåõ ýòàïîâ (ïðîòîêîëîâ), ê êîòîðûì îòíîñÿòñÿ íåïîñðåäñòâåííî ýòàï
ãåíåðàöèè ïîäïèñè, ýòàï âåðèôèêàöèè ïîäïèñè ñ îáÿçàòåëüíûì ó÷àñòèåì ïîäïèñûâàþùåãî (ïðîòîêîë
âåðèôèêàöèè) è ýòàï îñïàðèâàíèÿ, åñëè ïîäïèñü èëè öåëîñòíîñòü ïîäïèñàííûõ äàííûõ ïîäâåðãëàñü
Дорджиев,
ñîìíåíèþ (îòâåðãàþùèé ïðîòîêîë
ïîñëåäíåì
äîêàçûâàåò
, ÷òî log
log
. Ýòî
äåëàåòñÿ ïðè ïîìîùè äîêàçàòåëüñòâà íåðàâåíñòâà äâóõ ëîãàðèôìîâ, ïðèâåäåííîãî âûøå [12, 13].
Òåîðåìà 2.3.
òâåðãàþùèé ïðîòîêîë
ÿâëÿåòñÿ ïðîòîêîëîì äîêàçàòåëüñòâà ñ àáñîëþòíî
íóëåâûì ðàçãëàøåíèåì.
2.4.ДДД Êîíâåðòèðóåìàÿ è ñåëåêòèâíî êîíâåðòèðóåìàÿ ñõåìû ïîäïèñè ñ âåðèôèêàöèåé ïî
ðàáîòå
[16] ïîêàçàíî, êàê ñòðîèòü
êîíâåðòèðóåìóþ è ñåëåêòèâíî êîíâåðòèðóåìóþ
ñõåìû ïîäïèñè ñ âåðèôèêàöèåé ïî çàïðîñó,
à â ðàáîòå
[13] ïðåäëîæåíû òàêèå ñõåìû äëÿ
ÃÎÑÒ Ð
òàêèõ ñõåìàõ îòêðûòèå îïðåäåëåííîãî ñåêðåòíîãî ïàðàìåòðà íåêîòîðîé ñõåìû ïîäïèñè ñ
âåðèôèêàöèåé ïî çàïðîñó ïîçâîëÿåò òðàíñôîðìèðîâàòü ïîñëåäíþþ â îáû÷íóþ ñõåìó ýëåêòðîííîé
ïîäïèñè.
ðè ýòîì îòêðûòèå ñåêðåòíîãî ïàðàìåòðà â êîíâåðòèðóåìîé ñõåìå ïîäïèñè ñ âåðèôèêàöèåé
ïî çàïðîñó äàåò âîçìîæíîñòü âåðèôèöèðîâàòü âñå èìåþùèåñÿ è
ñãåíåðèðîâàííûå â äàëüíåéøåì
ïîäïèñè, â òî âðåìÿ êàê â
ñåëåêòèâíî êîíâåðòèðóåìûõ ñõåìàõ ïîäïèñè ñ âåðèôèêàöèåé ïî çàïðîñó
ìîæíî âåðèôèöèðîâàòü ëèøü êàêóþ-ëèáî îäíó ïîäïèñü [16].
Êîíâåðòèðóåìàÿ è ñåëåêòèâíî êîíâåðòèðóåìàÿ ñõåìû ïîäïèñè ñ âåðèôèêàöèåé ïî
Ïðîòîêîë ñ ðàñïðåäåëåííûìè äîêàçûâàþùèìè
– ñèñòåìà äîêàçàòåëüñòâ, â
ïîëèíîìèàëüíî îãðàíè÷åííûé äîêàçûâàþùèé çàìåíÿåòñÿ ìíîãèìè äîêàçûâàþùèìè, êàæäûé èç
êîòîðûõ èìååò ëèøü ÷àñòè÷íóþ èíôîðìàöèþ î äîêàçûâàåìîì ñâèäåòåëüñòâå, ïðèíàäëåæàùåì
îðèãèíàëüíîìó äîêàçûâàþùåìó.
ðèìåíåíèå òàêèõ ïðîòîêîëîâ âîçìîæíî â ñöåíàðèè, êîãäà
ïîäïèñûâàþùèé ìîæåò ðàñïðåäåëèòü ÷àñòü ñâîåãî ñåêðåòíîãî êëþ÷à ïîäïèñè ñðåäè
ó÷àñòíèêîâ
) èç íèõ ìîãëè â äàëüíåéøåì åå ïðîâåðèòü.
î÷òè âî âñåõ îáëàñòÿõ ïðèìåíåíèÿ ñõåì ïîäïèñè ñ âåðèôèêàöèåé ïî çàïðîñó çíà÷èòåëüíîé
ïðîáëåìîé ÿâëÿåòñÿ îáÿçàòåëüíîå ïðèñóòñòâèå ïîäïèñûâàþùåãî ïðè âåðèôèêàöèè ïîäïèñè.
ëåäîâàòåëüíî, äëÿ ïðîâåðÿþùåãî âàæíî, ÷òîáû ëèáî ïîäïèñûâàþùèé, ëèáî àãåíò, óïîëíîìî÷åííûé
ïîäïèñûâàþùèì, âñåãäà ïðèñóòñòâîâàë ïðè ýòîì ñîáûòèè.
àêîé àãåíò ìîæåò îêàçûâàòü ïîìîùü
ïîäïèñûâàþùåìó, òàê êàê, åñëè ïîñëåäíèé ïîäïèñûâàåò î÷åíü ìíîãî ñîîáùåíèé, îí áûñòðî ìîæåò
áûòü «ïåðåãðóæåí», êàæäûé ðàç âåðèôèöèðóÿ ïîäïèñè.
ñõåìàõ ïîäïèñè ñ âåðèôèêàöèåé ïî çàïðîñó
ïîäïèñûâàþùèé ìîæåò äîâåðèòü àãåíòó âåðèôèêàöèþ âñåõ ïîäïèñåé, à åñëè ïîäïèñè ÿâëÿþòñÿ
ñåëåêòèâíî êîíâåðòèðóåìûìè, òîãäà àãåíò ìîæåò áûòü óïîëíîìî÷åí ïðîâåðÿòü òîëüêî îòäåëüíûå
ëþáîì ñëó÷àå òðåáóåòñÿ, ÷òîáû ïîäïèñûâàþùèé áåçóñëîâíî äîâåðÿë ýòîìó àãåíòó.
ñëè ïîäïèñûâàþùèé íå õî÷åò äîâåðÿòü îäíîìó ÷åëîâåêó, òîãäà îí ìîæåò ðàçðåøèòü
îñóùåñòâëÿòü ïðîöåññ âåðèôèêàöèè ïîäïèñè
àãåíòàì òàê, ÷òîáû ïðîâåðêà ïîòðåáîâàëà
ñîòðóäíè÷åñòâà, ïî êðàéíåé ìåðå,
èç íèõ äðóã ñ
äðóãîì. Äëÿ ýòîãî ïîäïèñûâàþùèé äîëæåí
ðàñïðåäåëèòü êëþ÷è ïîäïèñè òàê, ÷òîáû êàæäûé àãåíò ìîã ïðîâåðèòü, ÷òî îí ïîëó÷èë êîððåêòíûå
äîëè ýòèõ êëþ÷åé, à çàòåì äàòü àãåíòó âîçìîæíîñòü ïðîâåðèòü èëè îñïîðèòü ïîäïèñè.
ïèñàíèå êîíâåðòèðóåìîé è ñåëåêòèâíî êîíâåðòèðóåìîé ñõåì ïîäïèñè ñ
âåðèôèêàöèåé ïî
çàïðîñó ñ ðàñïðåäåëåííûìè äîêàçûâàþùèìè è äîêàçàòåëüñòâî åå áåçîïàñíîñòè ðàññìàòðèâàåòñÿ â
ðàáîòå
[17], ãäå ñõåìà ðàçäåëåíèÿ ñåêðåòà (è åå âàðèàíò – ïðîâåðÿåìàÿ ñõåìà ðàçäåëåíèÿ ñåêðåòà)
îñíîâûâàåòñÿ íà èíòåðïîëÿöèîííûõ ïîëèíîìàõ Øàìèðà
3.ДДД Âëîæåíèÿ ïðèìèòèâîâВВВÂñå ïðèâåäåííûå âûøå ñõåìû è
ïðîòîêîëû îïðåäåëåííûì îáðàçîì âçàèìîñâÿçàíû.
àæäûé
èç íèõ ÿâëÿåòñÿ îäíèì èç îñíîâíûõ ýëåìåíòîâ ïîñòðîåíèÿ ñëåäóþùåé â èåðàðõèè ñõåìû èëè
вложения,
ïðîòîêîëà. Óñëîâíî íàçîâåì èõ
è
ïðîòîêîëàìè â
êîìïîçèöèè êðèïòîãðàôè÷åñêèõ ïðîòîêîëîâ
.
îæíî òàêæå îòìåòèòü, ÷òî ñòîéêîñòü
àññìîòðèì ñëåäóþùèå âëîæåíèÿ îïèñàííûõ â ðàçäåëå
2 êðèïòîãðàôè÷åñêèõ ïðîòîêîëîâ
ñõåìà ïðèâÿçêè ê áèòó
ïðîòîêîë äîêàçàòåëüñòâà íåðàâåíñòâà äâóõ
äèñêðåòíûõ ëîãàðèôìîâ
îòâåðãàþùèé ïðîòîêîë
ñõåìà ïîäïèñè ñ âåðèôèêàöèåé ïî
êîíâåðòèðóåìàÿ è ñåëåêòèâíî êîíâåðòèðóåìàÿ ñõåìà ñ âåðèôèêàöèåé ïî çàïðîñó
êîíâåðòèðóåìàÿ è ñåëåêòèâíî êîíâåðòèðóåìàÿ ñõåìà ñ âåðèôèêàöèåé ïî çàïðîñó ñ
ïàðàìåòð
ïðîòîêîëà
ñõåìû ïðèâÿçêè ê
áèòó








ñõåìà ïîäïèñè ñ âåðèôèêàöèåé ïî çàïðîñó.

Êîíâåðòèðóåìàÿ è ñåëåêòèâíî êîíâåðòèðóåìàÿ ñõåìà ïîäïèñè ñ âåðèôèêàöèåé ïî
Ïðîòîêîë (ñõåìà)
: êîíâåðòèðóåìàÿ ñõåìà ïîäïèñè ñ âåðèôèêàöèåé ïî çàïðîñó è ñåëåêòèâíî
êîíâåðòèðóåìàÿ ñõåìà ïîäïèñè ñ âåðèôèêàöèåé ïî çàïðîñó.

Êîíâåðòèðóåìàÿ è ñåëåêòèâíî êîíâåðòèðóåìàÿ ñõåìû ïîäïèñè ñ âåðèôèêàöèåé ïî

Ñòîéêîñòü:  
àêèì îáðàçîì, îäíèì èç ïðèåìîâ äîêàçàòåëüñòâà ñòîéêîñòè ïðè ïîñòðîåíèè äîñòàòî÷íî
ñëîæíûõ êðèïòîãðàôè÷åñêèõ ïðîòîêîëîâ ÿâëÿåòñÿ èõ äåêîìïîçèöèÿ íà áîëåå ïðîñòûå,
ñëè ðàññìàòðèâàòü êðèïòîãðàôè÷åñêèå ïðîòîêîëû êàê èåðàðõè÷åñêèå âëîæåíèÿ
íèæåñòîÿùèõ ïðîòîêîëîâ â âûøåñòîÿùèå, òî îäèí èç îñíîâíûõ âîïðîñîâ, âîçíèêàþùèõ ïðè
òàêîì ïîäõîäå, ìîæåò áûòü ñëåäóþùèì: «
×òî ÿâëÿåòñÿ äîñòàòî÷íûì óñëîâèåì äëÿ
äîêàçàòåëüñòâà ñòîéêîñòè êðèïòîãðàôè÷åñêèõ ïðîòîêîëîâ (ñõåì), â îñíîâå êîòîðûõ
ëåæàò áîëåå ïðîñòûå êðèïòîãðàôè÷åñêèå ïðèìèòèâû?
ðîìå òîãî, åñòåñòâåííî, âñòàåò
âîïðîñ: «
Íàñêîëüêî óíèôèöèðîâàííûì äîëæåí áûòü ìàòåìàòè÷åñêèé àïïàðàò îïèñàíèÿ
Дорджиев,
àïðèìåð, âñå ðàññìîòðåííûå â äàííîé ðàáîòå ïðîòîêîëû (ñõåìû) îñíîâàíû íà
âû÷èñëåíèÿõ â ìóëüòèïëèêàòèâíîé ãðóïïå (ïîäãðóïïå) âû÷åòîâ ïî ìîäóëþ áîëüøîãî ïðîñòîãî
÷èñëà, à ñòîéêîñòü ïðåäëîæåííûõ ñõåì îñíîâûâàåòñÿ íà ãèïîòåçå î ñóùåñòâîâàíèè îäíîñòîðîííåé
ôóíêöèè äèñêðåòíîãî ýêñïîíåíöèðîâàíèÿ.
òî æå âðåìÿ ïðîâåðÿåìàÿ ñõåìà ðàçäåëåíèÿ ñåêðåòà,
èñïîëüçóåìàÿ äëÿ ïîñòðîåíèÿ ñõåìû ïîäïèñè ñ âåðèôèêàöèåé ïî çàïðîñó ñ ðàñïðåäåëåííûìè
äîêàçûâàþùèìè, îñíîâûâàåòñÿ íà âû÷èñëåíèÿõ íàä ïîëèíîìàìè â ïîëå âû÷åòîâ ïî ìîäóëþ
, íàêîíåö, îñòàåòñÿ îòêðûòûì è ñëåäóþùèé âîïðîñ: «
Êàêîâû âîîáùå ïóòè äîêàçàòåëüñòâà
ñòîéêîñòè ñëîæíûõ êðèïòîãðàôè÷åñêèõ ïðîòîêîëîâ, êðîìå äîêàçàòåëüñòâà ñòîéêîñòè
ïðè èõ äåêîìïîçèöèè íà áîëåå ïðîñòûå, è, â öåëîì, ÿâëÿåòñÿ ëè äåêîìïîçèöèÿ íåêèì
äàííîé ðàáîòå ïðåäïðèíÿòà ïîïûòêà èññëåäîâàíèÿ íåêîòîðûõ àñïåêòîâ ïîñòðîåíèÿ
êðèïòîãðàôè÷åñêèõ ïðîòîêîëîâ.
åàëèçàöèÿ ïðèíöèïà èåðàðõè÷åñêîé êîìïîçèöèè/äåêîìïîçèöèè
(èåðàðõè÷åñêèõ âëîæåíèé) êðèïòîãðàôè÷åñêèõ ïðîòîêîëîâ ìîæåò ñòàòü õîðîøèì èíñòðóìåíòîì êàê
äëÿ èõ ýôôåêòèâíîãî ïîñòðîåíèÿ, òàê è äëÿ äîêàçàòåëüñòâà ñòîéêîñòè ïðîòîêîëîâ è áåçîïàñíîñòè
ðàáîòå ïðèâîäÿòñÿ êðèïòîãðàôè÷åñêèå ïðîòîêîëû, ðåàëèçóþùèå èäåþ ñõåì ïîäïèñè
ñ âåðèôèêàöèåé ïî çàïðîñó è èõ ðàçíîâèäíîñòåé.
åæàùèå â èõ îñíîâå êðèïòîãðàôè÷åñêèå
ïðèìèòèâû, òàêèå êàê áëîá, ñõåìà ïðèâÿçêè ê áèòó, èíòåðàêòèâíûå ñèñòåìû äîêàçàòåëüñòâ
íóëåâûì ðàçãëàøåíèåì è äð., èìåþò ñâîå ñàìîñòîÿòåëüíîå çíà÷åíèå è ñâîé äîñòàòî÷íî ðàçâèòûé
ìàòåìàòè÷åñêèé àïïàðàò äëÿ äîêàçàòåëüñòâà èõ ñòîéêîñòè. Ýòî çíà÷èò, ÷òî ïðè ïîñòðîåíèè íîâûõ
êðèïòîãðàôè÷åñêèõ ïðîòîêîëîâ ñ èñïîëüçîâàíèåì èçâåñòíûõ ïðèìèòèâîâ ìîæåò íå ïîíàäîáèòüñÿ
«èçîáðåòàòü âåëîñèïåä» äëÿ äîêàçàòåëüñòâà èõ ñòîéêîñòè, à çíà÷èò, ìîæíî ñóùåñòâåííî ñîêðàòèòü
âðåìÿ è èçáåæàòü ìíîãèõ îøèáîê, òèïîâûõ è ðóòèííûõ ïðîöåäóð ïðè äîêàçàòåëüñòâå áåçîïàñíîñòè
Äëÿ ðåøåíèÿ ïðîáëåìû äîêàçàòåëüñòâà ñòîéêîñòè ïðîèçâîëüíîé êîìïîçèöèè ïðîòîêîëîâ,
ïî ìíåíèþ àâòîðîâ, ìîæíî èñïîëüçîâàòü ìîäåëü ñ
îïðåäåëåíèÿìè áåçîïàñíîñòè ñèìóëÿöèåé â
íåèçâåñòíîì îêðóæåíèè
, íàïðèìåð
ãèáðèäíóþ ìîäåëü Êàíåòòè

hybrid UC-ìîäåëü
universally
composable model
) [19].
äàííîé ìîäåëè èçíà÷àëüíî çàëîæåí ìîäóëüíûé ïðèíöèï äîêàçàòåëüñòâà
ñòîéêîñòè ïðîòîêîëîâ [20], à ñàìî äîêàçàòåëüñòâî ïðîâîäèòñÿ ÷åðåç äîêàçàòåëüñòâî ýêâèâàëåíòíîñòè
èäåàëüíîé è ðåàëüíîé ôóíêöèîíàëüíîñòè (ñì., íàïðèìåð, àíàëîã èç ðàáîòû [21]).
ËÈÒÅÐÀÒ
Backes
M., Pfitzmann
B., Waidner
A universally composable cryptographic library. URL: http://citeseer.ist.psu.edu (äàòà
Berger
R., Kannan
S., Peralta
framework for study of cryptographic protocols //
Lecture Notes in Computer Science. Advances
in Cryptology – CRYPTO’85. V. 218. P. 87–103.
Boulton
P. I. P., Lee
E. S., Thompson
B., Soper
R. E.
вложения,
Needham
R. M., Schroeder
M. D.

Приложенные файлы

  • pdf 83624681
    Размер файла: 289 kB Загрузок: 0

Добавить комментарий