Představte si, že jste ředitelem banky a máte trezor, ve kterém je spousta peněz. K otevření trezoru je potřeba heslo (které znáte jen vy). V bance pracují úředníci, kteří občas potřebují otevřít trezor a uložit nebo vybrat peníze. Vy ale úředníkům příliš nevěříte - pokud by byl úředník u trezoru sám, mohlo by ho napadnout, že peníze sebere a uteče. Proto potřebujete vymyslet bezpečnostní systém, který by zaručoval, že žádný úředník nedokáže trezor otevřít samotný, ale jakákoliv dvojice úředníků už trezor otevřít může (dvojici úředníků už věříte, že vás neokradou - dají jeden na druhého pozor).
Formálně: známe heslo H a máme k úředníků. Chceme každému úředníkovi říct nějakou informaci (přístupové heslo, kód, ...) tak, aby jeden úředník nebyl schopný zjistit H, ale libovolná dvojice by už dokázala H zjistit. Jinými slovy: heslo H je nějaké číslo, úředníkům přidělíme nějakou informaci tak, aby jeden úředník nedokázal spočítat H na základě své informace, ale libovolní dva úředníci by už dokázali spočítat číslo H pokud dají své informace dohromady. Jakou informaci úředníkům přidělíte, je na vás. Může to být jedno číslo, posloupnost čísel, množina čísel, dvojice čísel, množina dvojic čísel, atd.. Záleží na vás. Bylo by samozřejmě vhodné, aby informace, kterou si úředník musí pamatovat, byla co nejmenší.
Při otevírání trezoru zadá nejprve první úředník svou informaci (do počítače) a potom druhý úředník zadá svou. Počítač spočítá číslo H (na základě těchto dvou vstupů) a zkusí s ním otevřít trezor (čili úředníci při otevírání heslo nezjistí, ani nezjistí informaci, kterou má druhý úředník).
Vašim úkolem je navrhnout, jakou informaci budou mít jednotliví úředníci a jakým způsobem se bude počítat číslo H. Úlohu řešte pokud možno obecně - to znamená pro libovolné (předem neznámé) H a k. Dále předpokládejte, že úředníci mají plný přístup k zadávacímu počítači (a ke všem informacím, které jsou v něm uložené) a znají algoritmus, jakým se číslo H počítá. (Tedy číslo H nesmí být přímo uložené v zadávacím počítači.) Dále předpokládejte, že úředníci jsou velmi inteligentní a vynalézaví. Pokud navržený systém bude mít jakoukoliv slabinu, tak ji odhalí a zkusí využít.
Za vyřešení úlohy můžete získat 40 bodů. Součástí řešení by mělo být i zdůvodnění (nejlépe přímo důkaz) správnosti (tzn. proč jeden úředník nedokáže heslo spočítat a proč libovolní dva to už dokážou - při použití vámi navrženého modelu). Měli byste se taky snažit, aby informace, kterou si úředník musí pamatovat, byla co nejmenší. (Za to získáte víc bodů.)
Dalších maximálně 80 bonusových bodů přidělím, pokud vaše řešení splní některé (nejlépe všechny) následující požadavky:
V případě nejasností v zadání mi pošlete e-mail.
Řešení můžete posílat buď e-mailem nebo odevzdat na papíře na cvičení.