Ostrzeżenie: ten algorytm ulegnie samozniszczeniu po użyciu

Wyobraź sobie dwóch milionerów — Alicję i Boba — którzy chcą decydować, kto jest bogatszy, ale bez ujawniania swojego bogactwa. Jak rozwiązują swoją zagadkę? To jest problem milionera Yao, opracowany przez informatyka Andrew Yao w 1982 roku.

Jednym z potencjalnych rozwiązań jest jednorazowy program komputerowy. Ten program pozwala Alicji i Bobowi na prywatne wprowadzanie swoich danych, jednorazowo wykonuje obliczenia, udziela odpowiedzi, a następnie niszczy się. Gwarantuje to, że nikt nie ma dostępu do oryginalnych danych ani sposobu ich przetwarzania. Daje odpowiedź Alicji i Bobowi bez narażania ich szczegółów finansowych.

Eksperci ds. bezpieczeństwa komputerowego twierdzą, że jednorazowe programy są niezwykle ważnym narzędziem w cyberbezpieczeństwie. Albo byłyby, gdyby ktoś mógł je zbudować.

Okazuje się, że nie da się zbudować idealnego jednorazowego programu, który uruchamia się raz, a potem sam się niszczy. Klasyczny komputer tego rodzaju musiałby zostać fizycznie zniszczony, aby nie mógł być ponownie użyty, a nie ma znanego sposobu, aby to zagwarantować.

Komputer kwantowy może wydawać się oferować większy potencjał, ponieważ informacje kwantowe można łatwo zniszczyć i skopiować. Okazuje się jednak, że komputer kwantowy nie może dać deterministycznej odpowiedzi na jednorazowe obliczenia.

Tak więc marzenie o jednorazowym programie, który samoistnie się zniszczy po jednej kalkulacji, wydaje się skazane na niepowodzenie.

Wejdź do Marie-Christine Roehsner z Uniwersytetu Wiedeńskiego i Joshua Kettlewell z National University of Singapore i kilku kumpli. Dziś mówią, że znaleźli sposób na zbudowanie jednorazowego programu i po raz pierwszy zbudowali i zademonstrowali urządzenie sprawdzające się w praktyce.

Nowa metoda polega na innym sposobie myślenia o programach jednorazowych wykonywanych przez komputery kwantowe. Do tej pory eksperci ds. bezpieczeństwa zawsze oczekiwali ostatecznego rozwiązania: wartość Boba jest albo mniej, albo więcej niż Alice.

Ale mechanika kwantowa jest z natury procesem probabilistycznym, a to oznacza, że ​​może dać poprawną odpowiedź tylko w pewnych granicach prawdopodobieństwa, powiedzmy w 75 procentach przypadków. Dopóki Alicja i Bob są gotowi zaakceptować możliwość błędu w obliczeniach, można zagwarantować, że ich informacje pozostaną bezpieczne, że program uruchomi się tylko raz, a następnie sam się zniszczy.

Naukowcy twierdzą, że rozluźniamy definicję programów jednorazowych, aby uwzględnić pewne prawdopodobieństwo wystąpienia błędu w danych wyjściowych i pokazać, że mechanika kwantowa oferuje przewagę w zakresie bezpieczeństwa nad czysto klasycznymi zasobami.

Podejście jest proste. Alicja potajemnie koduje swoje bogactwo w stanach zestawu kubitów przechowywanych w komputerze kwantowym. Ten komputer jest zaprogramowany, aby porównać tę liczbę z liczbą wprowadzoną przez Boba i powiedzieć mu, czy jego majątek jest większy czy mniejszy niż Alicji.

To przetwarzanie kwantowe jest samo w sobie procesem nieodwracalnym, co uniemożliwia Bobowi wprowadzanie innych liczb w celu określenia bogactwa Alicji.

Ale sprzęt jest naprawiony, a potencjalną słabością tego podejścia jest to, że Bob może dokonać inżynierii wstecznej programu, analizując sposób podłączenia bramek logicznych.

Roehsner i spółka mają jednak sztuczkę, aby temu zapobiec. Chociaż nie mogą ukryć fizycznego okablowania, mogą ukryć tabele prawdy, które regulują zachowanie każdej bramki logicznej. Dzieje się tak, ponieważ nasze podejście polega na zakodowaniu tabeli prawdy dla poszczególnych bramek jako jednorazowego programu, mówią.

Dzięki temu informacje Alicji mogą być zakodowane w precyzyjnym wyborze bramek logicznych, a nie w połączeniach między nimi. W ten sposób pozostaje ukryty przed Bobem.

Roehsner i spółka przetestowali ten pomysł w eksperymencie sprawdzającym zasadę. Koduje informacje w polaryzacji fotonów i przetwarza je za pomocą różnego rodzaju optycznych bramek logicznych. Średnie prawdopodobieństwo sukcesu dla każdej z bram wynosi 75 procent, co zdaniem zespołu jest zgodne z oczekiwaną wartością.

Zespół wykorzystał następnie tę konfigurację do rozwiązania problemu milionera Yao dla liczb składających się z czterech bitów, które różnią się jednym bitem. Program działa porównując każdy bit, aby zdecydować, który jest większy.

Wyniki stanowią ciekawą lekturę. Zespół twierdzi, że prawdopodobieństwo sukcesu wzrasta wraz z liczbą bitów wykorzystywanych do korekcji błędów, ale zmniejsza to również bezpieczeństwo systemu. Istnieje więc wyraźny kompromis między dokładnością a bezpieczeństwem. Niemniej jednak zespół twierdzi, że bezpieczeństwo jest lepsze niż to, które można osiągnąć za pomocą samych klasycznych komputerów.

Nasze wyniki pokazują, że fizyka kwantowa pozwala na lepsze kompromisy w zakresie bezpieczeństwa dla pewnych bezpiecznych zadań obliczeniowych, niż jest to możliwe w klasycznym świecie, nawet jeśli nie można osiągnąć idealnego bezpieczeństwa.

Co więcej, metoda ta działa przy obecnej technologii, a stosunkowo niewielkie postępy powinny jeszcze bardziej zwiększyć bezpieczeństwo.

To interesująca praca, która pokazuje potencjał technologii kwantowych w radykalnym zwiększeniu bezpieczeństwa przy użyciu dostępnej obecnie technologii. Uważamy, że zaprezentowana praca silnie wskazuje na bogatą dziedzinę protokołów kwantowych, które zwiększają bezpieczeństwo klasycznych obliczeń, nawet przed wdrożeniem komputerów kwantowych na dużą skalę, twierdzą Roehsner i spółka.

Ciekawie będzie zobaczyć, jak odbierana jest praca.

Nr ref.: arxiv.org/abs/1709.09724 : Przewaga kwantowa dla probabilistycznych programów jednorazowych

ukryć