Дипломная работа: Розробка імовірнісної моделі криптографічних протоколів

Висновки

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

Розділ 3. Оцінка стійкості криптографічних протоколів на основ мовірнісних моделей

3.1. Методика оцінки стійкості

Формальний доказ стійкості в рамках обчислювальної моделі складається з трьох етапів.

1. Формальна поведінка учасників протоколу і атакуючого алгоритму: моделювання, як правило, здійснюється за допомогою атакуючої гри, в якій беруть участь атакуючий алгоритм і об'єкт атаки.

2. Формальне визначення стійкості: перемога атакуючого алгоритму в атакуючій гр звичайно виражається через (значущу) ймовірність і оцінку (розумної) тимчасово складності.

3. Формальна демонстрація існування поліноміальної редукції, що зводить атаку до рішення задачі, що важко вирішується, як правило, має вид математичної теореми.

3.2. Приклади доказу стійкості деяких протоколів на основі їх імовірнісних моделей

Аналіз стійкост будемо проводити на основі імовірнісної моделі протоколів з нульовим розголошенням.

Одне з основних завдань криптографії представляє собою двосторонню інтерактивну гру, в якій один  учасник (сторона, що доводить) доказує іншому учаснику (стороні, що перевіряє) істинність твердження, не розкриваючи суті доказу. В цьому випадку сторона, що перевіряє не може самостійно оцінити істинність твердження, оскільки йому невідома інформація, яка доступна стороні, що доводить. Ця гра називається протоколом (системою) інтерактивного доказування або ІР-протоколом. Доказування, здійснюване ІР-протоколом, можна назвати «секретним доказуванням». Секретність цього доказу полягає в тому, що по-перше, сторона, що перевіряє, переконавшись в істинності доказуваного твердження, не здатна самостійно повторити доказ, і, по-друге, після завершення протоколу ніхто із сторонніх не здатний зрозуміти жодного повідомлення, якими обмінювалися сторона, що перевіряє і сторони, що доводить.

Уявимо собі, що твердження, яке необхідно довести, не розкриваючи сутності доказу, рішенням якої-небудь відомої невирішеної математичної задачі. В цьому випадку доказуючи сторона побоюючись плагіату, може побажати приховати технічні детал доказу від потенційно нечесного рецензента. Для цього вона повинна провести «секретний» доказ, переконавши рецензента (що грає роль сторони, що перевіряє в ІР-протоколі) в коректності висновків, не даючи ніякої додаткової інформації.

У багатьох реальних системах існують набагато більш серйозні підстави для проведення «секретних» доказів. Як правило, ІР-протоколи  застосовуються для аутентифікації сутностей. На відміну від звичайних протоколів аутентифікації, в яких користувачі ставлять цифрові підписи, в ІР-протоколі сторона, що доводить не бажає, щоб повідомлення стали доступними кому-небудь, окрім сторони, що перевіряє, і виконує «секретну» аутентифікацію. Крім того, ІР-протоколи часто застосовуються для того, щоб довести, що частина прихованої інформації має певну структуру. Це необхідно в деяких секретних системах (наприклад, при проведенні електронних аукціонів), в яких прихований номер (лот) повинен знаходитися в допустимому діапазон (наприклад, необхідно довести, що х > у без розкриття значень Ек(х) і Ек(у), що є пропозиціями ціни).

Розглядаючи ІР-протоколи, необхідно вивчити два питання.

Питання 1. Скільки інформації одержить сторона, що перевіряє в ході інтерактивного доказу?

Питання 2. Скільки раундів повинна виконати сторона, що доводить, щоб переконати сторону, що перевіряє?

Ідеальною відповіддю на перше питання був би "аніскільки", або "нуль". ІР-протокол, що володіє такою властивістю, називається протоколом з нульовим розголошуванням або ZК-протоколом (zero-knowledge). Друге питання важливе не тільки для практичних застосувань, але і для теор обчислювальної складності, оскільки рішення цієї проблеми пов'язане з отриманням нижчої оцінки складності.

Розглянемо обчислювальну модель інтерактивної системи доказу, яку запропонували Голдвассеср, Мікаплі і Раков. Позначимо основну модель протоколу інтерактивного доказу через (Р, V), де Р – сторона, що доводить (prover), а V – сторона, що перевіряє (verifier). Як правило, протокол (Р, V) призначений для перевірки приналежності певного речення мові, заданій над алфавітом {0, 1}.

Хай L – мова над алфавітом {0,1}. Сторони Р і V одержують зразок хÎL, що є загальними вхідними даними. Доказ приналежності зразка позначається як (Р, V)(х). Обидві сторони протоколу пов’язані каналом зв’язку, через який вони обмінюються інформацією.

a1, b1, a2, b2,…, al, bl.

Ця послідовність повідомлень називається стенограмою доказу. У стенограмі доказу дані, що передаються користувачем Р, називаються стенограмою сторони, що доводить. Вони чергуються з даними, що передаються користувачем V, які називаються стенограмою сторони, що перевіряє. Як загальна довжина стенограми доказу l , так довжина кожної стенограми |аі|, |bi| (i = 1,2...,l) обмежена поліномом, що залежить від параметра |х|. Доказ приналежності зразка (Р, V)(х) мові L також повинен бути обмежений поліномом, який залежить від об'єму вхідних даних |х| .

Результат роботи протоколу записується у вигляді

(Р, V)(х) Î { Прийняти, Відхилити}.

Ці два значення означають, що сторона, що перевіряє або підтверджує, або спростову твердження хÎL , висловлене стороною, що доводить Р. Оскільки система (Р, V) мовірнісною, при кожному х результат (Р, V)(х) випадковою величиною, залежною від загальних вхідних даних х, закритих вхідних даних (рrivate input) користувача Р і деяких випадкових вхідних даних (random input), загальних для користувачів Р і V. Більш того, елементи стенограми доказу також є випадковими величинами.

Оскільки протокол (Р, V) є двосторонньою грою, природно припустити, що кожна сторона прагне одержати додаткову перевагу. З одного боку, сторона, що доводить, Р повинна бути зацікавлена в результаті (Р, V)(х) Прийняти, навіть якщо хÏL. Сторона, що доводить, яка керується такою шахрайською стратегією, позначається як Р’. З іншого боку, сторона, що перевіряє V повинна бути зацікавлена в розкритті інформації про закриті вхідні дані гравця Р. Сторона, що перевіряє, яка притримується такої нечесної стратегії позначається як V.

Дамо визначення протоколу інтерактивного доказу.

Хай L - мова, задана над алфавітом {0,1}. IР-протокол (Р,V) називається системою інтерактивного доказу для мови L, якщо

                   Ргоb[(Р, V)(х) = Прийняти | х Î L] ³ e,                                 (3.1)

                   Ргоb[(Р’, V)(х) = Прийняти | х Ï L] £ d,                                (3.2)

де числа e  і d  є константами, що задовольняють умовам

e Î,  d Î.

Імовірнісний простір складається зі всіх вхідних значень протоколу  (Р, V) і всіх випадкових вхідних даних користувачів Р і V.

Оцінка (3.1) характеризує повноту протоколу (Р,V). Величина e називається імовірністю повноти  протоколу (Р, V). Це означає, що якщо хÎL, то сторона, що перевіряє, V приймає припущення х з імовірністю, яка не менше величини e.

Оцінка (3.2) характеризує несуперечність протоколу (Р,V). Величина d  називається імовірністю суперечност протоколу (Р,V). Це означає, що якщо хÏL, то сторона, що перевіряє, V приймає припущення х з імовірністю, що не перевищує величини d.

Оцінку імовірност повноти (відповідно суперечності) можна збільшити (відповідно зменшити), наблизивши її скільки завгодно близько до одиниці (відповідно до нуля), послідовно незалежно повторюючи протокол (Р,V) поліноміально обмежену кількість раз (залежно від розміру вхідного речення). В цьому випадку сторона, що перевіряє, V ухвалює рішення шляхом голосування.

Розглянемо введені поняття на прикладі протоколу інтерактивного доказу приналежност підгрупі (Протокол 3.1) .

Загальн вхідні дані:

1. ƒ: однонаправлена функція, визначена в групі Zn і задовольняюча гомоморфній умові:

"х, уÎ Zn : ƒ (х + у) = ƒ (х) ƒ (у).

2. Х = ƒ (z) для деякого zÎ Zn .

Закрит вхідні дані сторони А:

z < n.

Висновок сторони Б:

Х Î á ƒ (1)ñ, тобто елемент Х породжується елементом ƒ (1).

Наступні кроки виконуються m раз.

1. А генерує число k Î Zn, знаходить число Сommit  ¬ƒ(k) посилає його Б.

2.  Б генерує число Challenge Î {0,1} і посилає його А.

3. А обчислює число Response ¬                      і посилає його Б.

4. Б перевіряє значення ƒ (Response)≟     

Якщо перевірка завершується невдало, Б посилає відмову і завершує роботу протоколу.

Б приймає доказ.

У цьому протоколі А є стороною, що доводить, а Б стороною, що перевіряє. Загальними вхідними даними А і Б є число X = ƒ (z), де функція ƒ однонаправленою і гомоморфною функцією, заданою над групою  Zn. Твердження про приналежність формулюється А і виглядає таким чином: X Î Zn.

Закритими даними А є елемент zÎ Zn прообраз елементу X при однонаправленому і гомоморфному відображенні ƒ.

В даному протоколі обидві сторони вступають в контакт т разів і створюють наступну стенограму доказу.

Commit1, Challenge1, Response1,..., Commitm, Challengem, Responsem.

Протокол виводить результат Прийняти, якщо кожна перевірка, що виконується Б, завершується успішно. Інакше результатом є слово Відхилити. Описаний протокол повним. Інакше кажучи, якщо А знає прообраз z і сліду нструкціям, то Б завжди відповідатиме: Прийняти.

Повнота.

Оцінка імовірност повноти протоколу виконується, причому e = 1, оскільки відповіді  А завжди успішно проходять перевірку у Б, тобто

ƒ (Response)=

 при будь-якому виборі випадкового числа Сhallenge Î {0,1}.

Несуперечливість.

Протокол несуперечливим.

Оцінимо мовірність суперечності d.

Результат перевірки, що виконується Б на етапі 4, залежить від випадкового числа Сhallenge після отримання числа Соmmit від А. Перевірка завершується успішно в двох випадках.

Варіант 1: Challenge = 0: Б бачить, що А відомий прообраз числа Commit.

Варіант 2:  Challenge = 1: Б бачить число

прообраз(Х)= Response – прообраз(Commit)(mod n).

Оскільки сторона А не може передбачити випадковий вибір Б після отримання передачі, якщо число, що передається не дорівнює одиниці, вона повинна знати прообраз(Commit), а значить, і прообраз(Х).

Якщо А не знає число прообраз(Х), вона може зшахраювати, спробувавши вгадати випадковий біт оклику перед відправкою своєї передачі. У «нечесному» доказі А обчислює значення, що передається таким чином.

 •  Вибирає випадкове число Response Î Zn.

 •  Вгадує число Challenge.

 •  Обчислює число Commit ¬

Очевидно, що на кожному кроці Б може відкинути помилковий доказ з імовірністю 1/2. Отже, імовірність суперечності (тобто імовірність успішного обману) рівна d = 1/2. Якщо протягом m ітерацій Б жодного разу не відкинув доказ, мовірність успішного обману не перевершує 2-m. Успішний обман стане практично неможливим, якщо число m достатньо велике, тобто число 2-m дуже малим.

Якщо функція ƒ гомоморфізмом, то ƒ(х) = ƒ(1)х для всіх  х Î Zn. Отже, в протоколі А доводить своє знання дискретного логарифма числа X по підставі ƒ(1). Цей протокол називається «доказуванням приналежност підгрупі», оскільки ця назва має більш загальний характер. Слід підкреслити, що огd[ƒ(1)] є секретним дільником числа n, тобто в загальному випадку елемент ƒ(1) не породжує групу що складається з п елементів. Як правило, Б не може безпосередньо перевірити приналежність елемента підгрупі, не вдаючись до допомоги А.

Рішення задач про приналежність елементу підгрупі є важким завданням. Приведемо ще декілька свідоцтв, підтверджуючих сказане. Відзначимо, що, хоча множина

Ln = х Î Zn

є циклічною групою (оскільки вона породжується елементом  ƒ(1)), Б нелегко перевірити умову # Ln ≟ n. Для цього він повинен розкласти число п на прості множники. Б може відповісти ТАК, не вступаючи в контакт з А, тільки якщо #Ln = п (оскільки число ƒ(1) повинно породжувати всі п елементів множини Ln). Таким чином, завдання про приналежність елементу підгрупі зводиться до факторизації великого цілого числа. Отже, щоб затруднити рішення цієї задачі, ціле число п в протоколі повинне бути достатньо великим. Саме з ц причини параметр безпеки в протоколі  повинен мати довжину log n.

Нульове розголошування.

Припустимо, що на Питання 1  існує ідеальна відповідь (Р, V) – протокол з нульовим розголошуванням, тобто користувач V  переконується у коректност твердження користувача Р, не дізнавшись нічого нового про закриті вхідн дані.

Для того, щоб протокол (Р, V) володів цією властивістю, необхідно обмежити обчислювальну потужність користувача V  поліномом, що залежить від розміру його вхідної інформації. Очевидно, що без цього обмеження неможна гарантувати нульове розголошування, оскільки користувач V, що володіє необмеженими обчислювальними ресурсами може самостійно розкрити секретні вхідні дан користувача Р.

Для будь-якого речення х Î L виконання протоколу (Р, V)(х) приводить не тільки до виведення результату Прийняти, але і породжує стенограму доказу, в якому чергуються елементи стенограм сторони, що доводить і сторони, що перевіряє. Елементи стенограми доказу є випадковими величинами, що залежать від всіх вхідних даних, включаючи випадкові вхідні дані протоколу (Р, V).

Очевидно, що доказ (Р, V)(х) розкриває будь-яку інформацію про закриті вхідні дані користувача Р тільки в тому випадку, якщо стенограма доказу допускає виток інформації.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11