![]()
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||
Доведення без розголошення6.1. Доведення квадратичності.В якості першого прикладу ми розглянемо доведення факту, що деяке число Припустимо, що на відміну від Аліси, Боб знає якийсь квадратний корінь з х за модулем п. Позначимо цей корінь через у: Найпростіший спосіб, у який Боб може переконати Алісу. що х Вхід: (х, п), де ж • Боб вибирає випадковий елемент v в • Аліса посилає Бобові випадковий біт b • Боб посилає Алісі число Якщо b = 0, то Аліса перевіряє, чи справді Все вищеописане повторюється m = [logn]разів, щоразу із незалежним вибором випадкових величин. Якщо результат перевірки у кожному циклі був успішним, то Бобові вдається переконати Алісу, що х 1) Повнота. Якщо справді х 2) Обгрунтованість. Якщо ж х Щоб довести цю властивість, розглянемо два випадки. Випадок 1: Перше повідомлення Боба Алісі u не є квадратичним лишком за модулем п. Тоді Боба буде викрито при ь = 0, що трапиться з імовірністю 1/2. Випадок 2: Повідомлення u є квадратичним лишком за модулем п. Тоді хu не є квадратичним лишком і Боба буде викрито при ь = 1, що теж трапиться з імовірністю 1/2. 3) Відсутність розголошення. Якщо справді х Для того, щоб формалізувати це спостереження, позначимо через VIEWx,n всю інформацію, яку сприймає Аліса упродовж одного циклу протоколу на вході (х,п), а саме, VIEWx,n = <u,ь,w>. Аліса спостерігає кожну конкретну трійку <u, ь, w> з певною ймовірністю, тобто VIEWx,n є випадковою величиною. Для довільного ймовірнісного алгоритму М результат його роботи на вході (х, п) позначимо через М(х, п). Слід звернути увагу на те, що М(х, п) є випадковою величиною, значення якої залежить від випадкової послідовності алгоритму. Абсолютно строго властивість відсутності розголошення можна сформулювати так: існує поліноміальний ймовірнісний алгоритм М такий, що при х Нам залишається описати алгоритм М, який симулює діалог Аліси і Боба на входах (х, п) при х Насправді наведений протокол володіє властивістю відсутності розголошення у значно сильнішій формі. Зауважимо, що випадкова величина VIEWx,n залежить від дій Аліси. Ми виходили з того, що Аліса притримується протоколу. Але ж вона може хитрувати в надії вивідати у Боба чим більше інформації. Наприклад, Аліса може посилати Бобові біт ь, вибраний не рівноймовірно, а за якимось іншим розподілом. З врахуванням цієї можливості, властивість відсутності розголошення розглянутого протоколу можна сформулювати у підсиленому варіанті, Нехай Аліса вибирає своє повідомлення ь як результат роботи деякого поліноміального ймовірнісного алгоритму А на вході <х,п,u> (це вся інформація, доступна Алісі на момент вибору). Тоді існує поліноміальний ймовірнісний алгоритм МA такий, що при х Протокол з такою властивістю відсутності розголошення називають досконалим доведенням без розголошення. 6.2. Доведення неквадратинності.Тепер розглянемо доведення без розголошення того факту, що х Вхід: (х,п), де х • Аліса вибирає випадковий елемент v в Далі Аліса обчислює
і посилає w Бобові. • Боб визначає, чи w є квадратичним лишком за модулем п і посилає Алісі у відповідь біт
• Аліса перевіряє, чи b = b'. Якщо це не так, Аліса припиняє спілкування з Бобом і оголошує йому недовіру. Все повторюється m = [logn] разів, щоразу із незалежним вибором випадкових величин. Якщо результат перевірки у кожному циклі був успішним, то Бобові вдається переконати Алісу, що х Читайте також:
|
||||||||
|