Czy zaangażowanie bitowe daje nieświadomy transfer w modelu bezpieczeństwa opartym na teorii informacji?

Załóżmy, że masz dwóch arbitralnie silnych uczestników, którzy sobie nie ufają. Mają dostęp do bitowego zaangażowania (np. Zapieczętowane koperty zawierające dane, które jeden gracz może przekazać drugiemu, ale których nie można otworzyć, dopóki pierwszy gracz nie da drugiemu klucza). Czy możesz to wykorzystać do zbudowania nieświadomego protokołu przesyłania. Czy to prawda, nawet jeśli gracze zgodzą się otworzyć wszystkie koperty na końcu, aby wykryć oszustwo (np. Po rozegraniu ręki pokera wszyscy zgadzają się ujawnić swoje karty)?

Zakładam, że nie można uzyskać nieświadomego przeniesienia z bitowego zaangażowania, ponieważ nieświadomy transfer jest kryptograficznie uniwersalny i nie mogę znaleźć żadnych odniesień, które mówią, że bitowe zobowiązanie jest, ale czy jest jakiś dowód, że nie możesz tego zrobić?

Wreszcie, czy ktoś spojrzał na problem, jeśli gracze są kwantowi?

reference-request cr.crypto-security Peter Shor
źródło

W komentarzu pytanie o mathoverflow, stwierdza się, że kwantowa Nieświadomy Transfer jest równoznaczne z zobowiązaniem kwantowy bit (z odniesieniami): mathoverflow.net/questions/32801/... .

M. Alaggan,

Te dwa artykuły pokazują, że bezwarunkowo bezpieczne zaangażowanie bitów kwantowych jest niemożliwe. Jeśli mógłbyś wykonać kwantowy nieświadomy transfer, oznaczałoby to, że możesz wykonać kwantowe zaangażowanie bitów, więc pokazują one również bezwarunkowo bezpieczny kwantowy nieświadomy transfer jest również niemożliwy. Zastanawiam się, czy jeśli otrzymujesz (jako czarną skrzynkę) bitowe zobowiązanie, które działa w przypadku protokołów kwantowych, czy możesz również zrobić nieświadomy transfer protokołów kwantowych.

Peter Shor,

Może potrzeba trochę więcej tła. Wydaje mi się, że mam dość prosty schemat, który przy odrobinie zaangażowania wykorzystuje go do osiągnięcia nieświadomego transferu w protokole kwantowym. Chciałem (1) wiedzieć, jakie są klasyczne dowody, że nieświadomy transfer jest ściśle potężniejszy, aby upewnić się, że nie dotyczą one przypadku kwantowego, oraz (2), aby wiedzieć, czy ktoś to wcześniej zaobserwował. Literatura na temat kwantowego nieświadomego transferu i zaangażowania bitowego jest trudna do przeszukania, ponieważ kilka dowodów bezpieczeństwa rozpadło się, gdy Mayers, Lo i Chau udowodnili swoje twierdzenie, że nie można tego zrobić.

Peter Shor,

Przeszukując trochę literaturę, istnieje trochę zaangażowania ==> nieprzejrzysty dowód przeniesienia w reżimie kwantowym w artykule z 1991 r. Autorstwa Bennetta, Brassarda, Crépeau i Skubiszewskiej ( springerlink.com/content/k6nye3kay7cm7yyx ), więc jest to znane.

Peter Shor,

@M. Alaggan: Chciałbym przeprosić za tak gwałtowne odrzucenie powyższego komentarza. Autor komentarza MathOverflow, o którym wspominałeś, prawdopodobnie wiedział, że są one równoważne, aw rzeczywistości komentarz ten postawił mnie na ścieżce bibliograficznej, która doprowadziła do dowodu referencyjnego, który znalazłem w powyższym komentarzu. Wielkie dzięki.

Peter Shor,

Odpowiedzi:

Nie, zaangażowanie ma znacznie niższą złożoność niż OT. Myślę, że łatwym sposobem na dostrzeżenie tego jest podejście zastosowane w złożoności problemów obliczeń wielopartyjnych: przypadek 2- stronnej symetrycznej bezpiecznej oceny funkcji przez Maji, Prabhakaran, Rosulek w TCC 2009 (zastrzeżenie: autopromocja!). W tym artykule mamy wynik charakteryzujący to, co możesz zrobić, mając dostęp do idealnego zaangażowania w modelu UC z bezpieczeństwem statystycznym.

Załóżmy, że istniał statystycznie bezpieczny protokół (przeciwko złośliwym przeciwnikom) dla OT korzystający z dostępu do idealnego zaangażowania w bity z czarnej skrzynki. Zatem musi być również zabezpieczony przed uczciwymi, ale ciekawymi przeciwnikami (nie tak trywialne, jak się wydaje, ale też niezbyt trudne do pokazania). Ale możesz skomponować z trywialnym uczciwym, ale ciekawym protokołem zaangażowania i mieć uczciwy, ale ciekawy protokół OT, który jest statystycznie bezpieczny bez konfiguracji. Ale wiadomo, że jest to niemożliwe. $\pi$ $\pi$ $\pi$

Innym sposobem, aby to zobaczyć, jest Impagliazzo-Rudich . Jeśli masz obliczeniowo niepowiązane strony i losową wyrocznię, możesz wykonać zobowiązanie (ponieważ wszystko, czego potrzebujesz, to funkcje jednokierunkowe), ale nie możesz robić takich rzeczy, jak kluczowa zgoda, a zatem nie OT.

mikero
źródło

@Mikero: to naprawdę fajny i prosty dowód.

Peter Shor,

W przypadku OT klasycznych bitów (tj. Klasycznego idealnego świata) argument zostanie omówiony w przypadku protokołów kwantowych / przeciwników. Jeśli OT manipuluje qbitami, mogą wystąpić komplikacje. Krok, który „nie jest tak trywialny, jak się wydaje, ale nie trudny” polega na powiedzeniu, że symulator WLOG zawsze korzysta z danych wejściowych dostarczanych przez środowisko. Jest to właściwość OT, która musi zostać pokazana (gdyby symulator nie wysłał tego, co podano, dane wyjściowe byłyby niepoprawne z zauważalnym prawdopodobieństwem, a zatem symulacja niesłyszalna) i musiałaby zostać ponownie argumentowana, jeśli środowisko może dać / otrzymuj qbity od OT.

mikero

@Mikero: Nie rozumiem twojego poprzedniego komentarza. Co to znaczy, że OT nie manipuluje kubitami? Czy masz na myśli to, że obie strony komunikują się tylko z klasycznymi bitami, ale mogą mieć procesory kwantowe? Wynika to z faktu, że nie istnieje bezpieczny teoretycznie bezpieczny protokół OT, nawet przy niewielkim zaangażowaniu.

Peter Shor,

Zastanawiam się, czy „kwantowy protokół OT” oznacza klasyczny OT (funkcjonalność OT wie tylko o bitach) z ewentualnym protokołem kwantowym, czy OT, w którym środowisko wie o kubitach i OT wysyła / odbiera kubity. W pierwszym przypadku uważam, że ten sam argument jest niezmodyfikowany. Prawdopodobnie masz na myśli ten drugi przypadek. Zatem jeśli naprawdę istnieje kontrprzykład w świecie kwantowym, oznaczałoby to, że OT qubitów nie ma właściwości, że WLOG symuluje odwzorowanie uczciwych, ale ciekawskich przeciwników z prawdziwego świata, do uczciwych, ale ciekawych idealnych przeciwników. Ciekawy!

mikero

Jeśli dobrze rozumiem twoje pytanie, zarówno Bennett i in. papier i mój dowód dotyczą klasycznego OT, z kwantowymi wiadomościami między uczestnikami w celu wdrożenia OT.

Peter Shor,

W przypadku kwantowym pierwszy protokół do zbudowania (klasycznego) nieświadomego transferu opartego na (klasycznym) zaangażowaniu bitów przy użyciu protokołu kwantowego został zaproponowany w 1991 roku przez Bennetta, Brassarda, Crépeau i Skubiszewską (http://www.springerlink.com/content / k6nye3kay7cm7yyx /), ale kompletny dowód bezpieczeństwa został podany dopiero niedawno przez Damgaard, Fehr, Lunemann, Salvail i Schaffner w http://arxiv.org/abs/0902.3918

Aby zapoznać się z rozszerzeniem obliczeń wielostronnych i dowodem na uniwersalne ramy kompasowalności, zobacz pracę Unruh: http://arxiv.org/abs/0910.2912

Christian Schaffner
źródło