Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






Доведення без розголошення

6.1. Доведення квадратичності.В якості першого прикладу ми розглянемо доведення факту, що деяке число є квадратичним лишком за модулем п. Як зазначалось в § IV.4, задача розпізнавання квадратичних лишків є важкою, якщо тільки не є відомим розклад модуля n на прості множники. Тому Аліса за парою (х,п) неспроможна (за поліноміальний від log n час) визначити, чи справді ж є квадратичним лишком.

Припустимо, що на відміну від Аліси, Боб знає якийсь квадратний корінь з х за модулем п. Позначимо цей корінь через у: . Нас не цікавить яким саме чином Боб добув корінь з х. Найправдоподібнішим поясненням таких виняткових обчислювальних здібностей може бути те, що Боб або власноручно вибрав n і знає його розклад на множники, або спершу вибрав у, а вже потім обчислив х = у2 mod n.

Найпростіший спосіб, у який Боб може переконати Алісу. що х Qn, це просто показати їй у. А наступний протокол дозволяє переконати Алісу не лише без пред'явлення їй коренів, але й без надання їй жодної інформації, яку Аліса не змогла б здобути самотужки.

Вхід: (х, п), де ж і існує у таке, що .

• Боб вибирає випадковий елемент v в , підносить його до квадрату і результат u= v2 mod n посилає Алісі.

• Аліса посилає Бобові випадковий біт b{0,1}.

• Боб посилає Алісі число

Якщо b = 0, то Аліса перевіряє, чи справді , а якщо ь = 1, то перевіряє, чи справді . Якщо результат перевірки негативний, то Аліса припиняє діалог і звинувачує Боба в ошуканстві.

Все вищеописане повторюється m = [logn]разів, щоразу із незалежним вибором випадкових величин. Якщо результат перевірки у кожному циклі був успішним, то Бобові вдається переконати Алісу, що х Qn-Перелічимо три основні властивості цього протоколу.

1) Повнота. Якщо справді хQn, а Боб справді знає квадратний корінь у і діє згідно з протоколом, то він переконує Алісу з імовірністю 1. Цю властивість легко перевірити, безпосередньо прослідкувавши за перебігом протоколу.

2) Обгрунтованість. Якщо ж х Qn, то як би винахідливо Боб не діяв, тобто які б хитрі повідомлення u і w не посилав Алісі, вона викриє його нещирість з імовірністю 1/2 в кожному із циклів, і з ймовірністю 1 – 2-m хоча б в одному з т циклів. Таким чином, Боб може переконати Алісу у справедливості хибноготвердження з імовірністю щонайбільше 1/п, що єекспоненційно малою величиною в порівнянні з довжиною входу.

Щоб довести цю властивість, розглянемо два випадки.

Випадок 1: Перше повідомлення Боба Алісі u не є квадратичним лишком за модулем п. Тоді Боба буде викрито при ь = 0, що трапиться з імовірністю 1/2.

Випадок 2: Повідомлення u є квадратичним лишком за модулем п. Тоді хu не є квадратичним лишком і Боба буде викрито при ь = 1, що теж трапиться з імовірністю 1/2.

3) Відсутність розголошення. Якщо справді х Qn, то Аліса не отримує від Боба ніякої інформації. Це твердження досить переконливе інтуїтивно. Справді, якщо Аліса вибирає біт ь = 0, то отримує випадковий квадратичний лишок u і корінь з нього w. Якщо ж ь = 1, то Алісі дістається квадратний корінь w з хu, причому хu також є випадковим квадратичним лишком за модулем п (див. пункт а вправи ПІ.3.8).

Для того, щоб формалізувати це спостереження, позначимо через VIEWx,n всю інформацію, яку сприймає Аліса упродовж одного циклу протоколу на вході (х,п), а саме, VIEWx,n = <u,ь,w>. Аліса спостерігає кожну конкретну трійку <u, ь, w> з певною ймовірністю, тобто VIEWx,n є випадковою величиною.

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

Абсолютно строго властивість відсутності розголошення можна сформулювати так: існує поліноміальний ймовірнісний алгоритм М такий, що при х Qn випадкові величини М(х, п) і VIEWx,n однаково розподілені. Таким чином, VIEWx,n нe містить для Аліси ніякої нової інформації в тому сенсі, що Аліса могла б отримати все абсолютно те ж саме, запустивши алгоритм М на вході (х, п).

Нам залишається описати алгоритм М, який симулює діалог Аліси і Боба на входах (х, п) при х Qn Спочатку слід вибрати випадковий елемент w і випадковий біт b (0,1). Якщо b = 0, то покласти u = w2mod n. Якщо ь = 1, то покласти u = w2x-1mod n. Трійку <u, b, w>. подати на вихід.

Насправді наведений протокол володіє властивістю відсутності розголошення у значно сильнішій формі. Зауважимо, що випадкова величина VIEWx,n залежить від дій Аліси. Ми виходили з того, що Аліса притримується протоколу. Але ж вона може хитрувати в надії вивідати у Боба чим більше інформації. Наприклад, Аліса може посилати Бобові біт ь, вибраний не рівноймовірно, а за якимось іншим розподілом. З врахуванням цієї можливості, властивість відсутності розголошення розглянутого протоколу можна сформулювати у підсиленому варіанті, Нехай Аліса вибирає своє повідомлення ь як результат роботи деякого поліноміального ймовірнісного алгоритму А на вході <х,п,u> (це вся інформація, доступна Алісі на момент вибору). Тоді існує поліноміальний ймовірнісний алгоритм МA такий, що при х Qn випадкові величини MA(х,п} і VIEWx,n однаково розподілені.

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

6.2. Доведення неквадратинності.Тепер розглянемо доведення без розголошення того факту, що х не єквадратичним лишком за модулем п. Зразу обмежимось випадком, коли , тобто х Jn, бо інакше доведення давалося б простим обчисленням символу Якобі (див. пункт 5 твердження IV.1.7). Отже Боб, який вміє розпізнавати квадратичність за модулем п (наприклад, знаючи розклад п на прості множники), хоче переконати Алісу, що х не є квадратичним лишком, тобто належить множині псевдоквадратів Qn.

Вхід: (х,п), де х Qn.

• Аліса вибирає випадковий елемент v в і випадковий біт b {0,1}.

Далі Аліса обчислює

,

і посилає w Бобові.

• Боб визначає, чи w є квадратичним лишком за модулем п і посилає Алісі у відповідь біт

 

• Аліса перевіряє, чи b = b'. Якщо це не так, Аліса припиняє спілкування з Бобом і оголошує йому недовіру.

Все повторюється m = [logn] разів, щоразу із незалежним вибором випадкових величин. Якщо результат перевірки у кожному циклі був успішним, то Бобові вдається переконати Алісу, що х Qn.


Читайте також:

  1. Аналоговий рівень доведення
  2. Відмінність дійового каяття від добровільної відмови від доведення злочину до кінця.
  3. Доведення від супротивного
  4. Доведення до банкрутства
  5. Доведення до самогубства
  6. Доведення до споживачів інформації про вид об’єкта туристичної інфраструктури та вид його категорії
  7. Доведення і доказування у цивільному процесі та обставини, які не підлягають доказуванню (доведенню).
  8. Доведення.
  9. Доведення.
  10. Доведення.
  11. Доведення.




Переглядів: 1047

<== попередня сторінка | наступна сторінка ==>
Розподіл таємниці | Ідентифікація

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.006 сек.