Розробка імовірнісної моделі криптографічних протоколів (стр. 13 из 19)
Розглянемо введені поняття на прикладі протоколу інтерактивного доказу приналежності підгрупі (Протокол 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 Î { ƒ (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 = { ƒ(x) = ƒ(1)x | х Î Zn}
є циклічною групою (оскільки вона породжується елементом ƒ(1)), Б нелегко перевірити умову # Ln ≟ n. Для цього він повинен розкласти число п на прості множники. Б може відповісти ТАК, не вступаючи в контакт з А, тільки якщо #Ln = п (оскільки число ƒ(1) повинно породжувати всі п елементів множини Ln). Таким чином, завдання про приналежність елементу підгрупі зводиться до факторизації великого цілого числа. Отже, щоб затруднити рішення цієї задачі, ціле число п в протоколі повинне бути достатньо великим. Саме з цієї причини параметр безпеки в протоколі повинен мати довжину log n.
Нульове розголошування.
Припустимо, що на Питання 1 існує ідеальна відповідь (Р, V) – протокол з нульовим розголошуванням, тобто користувач V переконується у коректності твердження користувача Р, не дізнавшись нічого нового про закриті вхідні дані.
Для того, щоб протокол (Р, V) володів цією властивістю, необхідно обмежити обчислювальну потужність користувача V поліномом, що залежить від розміру його вхідної інформації. Очевидно, що без цього обмеження неможна гарантувати нульове розголошування, оскільки користувач V, що володіє необмеженими обчислювальними ресурсами може самостійно розкрити секретні вхідні дані користувача Р.
Для будь-якого речення х Î L виконання протоколу (Р, V)(х) приводить не тільки до виведення результату Прийняти, але і породжує стенограму доказу, в якому чергуються елементи стенограм сторони, що доводить і сторони, що перевіряє. Елементи стенограми доказу є випадковими величинами, що залежать від всіх вхідних даних, включаючи випадкові вхідні дані протоколу (Р, V).
Очевидно, що доказ (Р, V)(х) розкриває будь-яку інформацію про закриті вхідні дані користувача Р тільки в тому випадку, якщо стенограма доказу допускає виток інформації.
Проте, якщо випадкові величини в стенограмі доказу є рівномірно розподіленими по відповідному імовірнісному простору і не залежать від загальних вхідних даних, то безглуздо стверджувати, ніби вони допускають виток інформації. Вважатимемо, що у цій ситуації (тобто коли стенограма доказу складається з рівномірно розподілених випадкових величин, не залежних від загальних вхідних даних) сторона, що доводить спілкується зі стороною, що перевіряє, на мові, що не володіє властивістю надмірності, тобто що має найбільшу ентропію. Отже, не має значення, наскільки розумним (або могутнім) є користувач, що перевіряє. Навіть вивчаючи цю мову дуже довгий час, він не зможе витягнути ніякої додаткової інформації.
Доведемо тепер, що протокол, який ми вище розглянули є ідеальним ZК-протоколом.
Стенограма доказу, створена при виконанні протоколу (А, Б)(Х), виглядає таким чином.
Commit1, Challenge1, Response1,..., Commitm, Challengem, Responsem,
де для і = 1,2..., m виконуються наступні умови.
• Commitі = ƒ(ki), де kiÎ Zn.
Очевидно, оскільки сторона А витягує числа kiз рівномірно розподіленої генеральної сукупності, величини Commitі також рівномірно розподілені по простору значень функції ƒ і не залежать від загальних вхідних даних Х.
• Challengei Î {0,1}.
Сторона Б повинна витягувати біт оклику із генеральної сукупності рівномірно розподілених величин, але цю вимогу можна зняти.
• Responsei = ki+ z Challenge(mod n).
Очевидно, що завдяки рівномірному розподілу чисел ki, величина Responsei рівномірно розподілена по групі Zn при всіх значеннях Challengei {0,1} (навіть якщо Challenge не є рівномірно розподіленою випадковою величиною) і не залежить від загальних вхідних даних Х.
Отже, дані, що передані стороною А у процесі виконання протоколу є рівномірно розподіленими і не представляють для сторони Б ніякої додаткової інформації про її закриті дані. Таким чином цей протокол є ідеальним протоколом з нульовим розголошенням.
З цього прикладу виходить, що елементи стенограми А є рівномірно розподіленими незалежно від того, як Б вибирає випадкові біти оклику. Інакше кажучи, Б не може вплинути на розподіл чисел у стенограмі сторони А. Отже, протокол є ідеальним протоколом з нульовим розголошуванням, навіть якщо сторона Б веде нечесну гру.
Протокол ідентифікації Шнорра.
В протоколі, який ми вище розглянули сторона Б використовує біти оклику. Це призводить до великої імовірності суперечності протоколу: δ = 1/2. Отже для того, щоб зменшити помилку до 2-m необхідно повторити протокол m разів. Для запобігання шахрайства з боку А достатньо прийняти m = 100. Але необхідність великої кількості раундів знижує ефективність протоколу.