Головна

Blob-об'єкти

Рядки, які Аліса посилає Бобу для вручення біта, іноді називають blob-об'єктами.Blob-об'єкт-це послідовність бітів, хоча протоколи цього і не вимагають. Як сказав Жиль Брассар (Gilles Brassard), "Вони могли б бути зроблені і з чарівного пилу якби це було корисним" [236]. Blob-об'єкти мають такими чотирма властивостями:

1. Аліса може вручити blob-об'єкти. Вручаючи blob-об'єкт, вона вручає біт.

2. Аліса може відкрити будь-який blob-об'єкт, який вона вручила. Коли вона відкриває blob-об'єкт, вона може переконати Боба в значенні біта, який був вручений разом з blob-об'єктом. Отже, вона не може відкрити довільний blob-об'єкт, наприклад, нуль або одиницю.

3. Боб не може знати, яким чином Аліса може відкрити blob-об'єкт, який вона вручила. Це залишається справедливим, навіть коли Аліса відкриє інші blob-об'єкти.

4. Blob-об'єкти не несуть ніякої інформації, крім документа, що вручається Алісою біта. Самі по собі blob-об'єкти, також як і процес, за допомогою якого Аліса вручає і відкриває їх, не пов'язані ні з чим іншим, що Аліса хотіла б зберегти в секреті від Боба.

4.10 Підкидання "чесної" монети

Настав час процитувати Джо Киліана (Joe Kilian) [831]:

Аліса і Боб хотіли зіграти в "орла і решка", але монети у них не було. Аліса запропонувала простий спосіб підкидати монетку подумки.

"Спочатку ви замислюєтеся випадковий біт, потім я задумаю випадковий біт. Потім ми виконуємо над бітами" виключає або ", - запропонувала вона.

"Але якщо один з нас не буде замислюватися біти випадковим чином?", - Запитав Боб.

"Це не важливо. Якщо хоча б один з бітів дійсно випадковий, то і" виключне або "бітів повинно бути дійств і-кові випадковим", - відповіла Аліса, і після хвилинного роздуму Боб погодився.

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

"Якщо отриманий біт буде 0, то ти візьмеш книгу, а якщо 1 - то я", - сказала Аліса. "Який у тебе біт?"

Боб відповів: "1".

"Ну ось, і у мене такий же", - лукаво зауважила Аліса. - "Я думаю, у тебе сьогодні невдалий день".

Очевидно, у протоколу підкидання монетки є серйозний дефект. Хоча це правда, що "виключає або" дейс т-вительно випадкового біта, х, і будь-якого незалежно розподіленого біта, .у, дає в результаті дійсно випадковий біт, протокол Аліси не гарантує, що два біта будуть розподілені незалежно. Насправді неважко переконатися, що ні з у-ществует уявного протоколу, який дозволить двом незалежним сторонам підкидати "чесну" монету. Аліса і Боб сумували, поки не отримали лист від невідомого студента з дипломом по криптографії. Інформація в листі була занадто теоретичної, щоб її можна було застосувати для чогось земного, але конверт, в якому прийшов лист, оказа л-ся надзвичайно корисним.

Коли Аліса і Боб в наступний раз захотіли підкинути монетку, вони змінили первісний протокол. Спочатку біт задумав Боб, але замість того, щоб відкрити його негайно, він записує свій біт на листку паперу і кладе листок в конверт. Потім Аліса оголошує свій біт. Нарешті, Аліса і Боб дістають біт Боба з конверта і обчислюють випадковий біт. Цей біт вже дійсно випадковий, незалежно від чесності грають. Аліса і Боб отримали працюючий протокол, з про-ціально значуща мрія криптографов здійснилася, і всі вони жили довго і щасливо.

Ці конверти виглядають вельми схожими на blob-об'єкти вручення біта. Коли Мануель Блам (Manuel Blum) зіткнувся з проблемою підкидання "чесної" монети по модему [194], він вирішив її, використовуючи протокол вручення біта:

(1) Аліса вручає випадковий біт, використовуючи будь-яку з схем вручення біта, описану в розділі 4.9.

(2) Боб загадує свій біт.

(3) Аліса розкриває біт Бобу. Боб виграє кидок, якщо він правильно загадав біт. У загальному випадку, нам потрібен протокол з наступними властивостями:

- Аліса повинна "кинути монету" до того, як Боб загадає свій біт.

- Аліса не повинна мати можливості змінити результати свого кидка, дізнавшись біт Боба.

- У Боба не повинно бути можливості дізнатися результат кидка перед тим, як він зробить свою предпол о-ються.

Існує кілька можливостей виконати це.




Спільне використання секрету без Трента | Спільне використання секрету з викреслюванням зі списку | проміжні протоколи | Рішення з посередником | протокол зв'язку | Розподілений протокол | подальша робота | Підписи, вільні від підсвідомого каналу | Групові підписи з надійним посередником | Підписи з виявленням підробки |

© um.co.ua - учбові матеріали та реферати