Delta 12/2023

Tym razem się nie uda...

Tomasz Kazana
informatyka kryptologia

Epilog sagi kryptologicznej w odcinkach.
W tej części: o tajnych głosowaniach elektronicznych

Tajne wybory to sól demokracji.

Najwyższy rangą dokument obowiązujący w Polsce – Konstytucja RP – wspomina o nich kilkakrotnie (art. 96, 97, 127, 169), podając dość konkretne wymagania, takie jak powszechność, równość, bezpośredniość czy właśnie tajność. W tym artykule spróbujemy zastanowić się, czy w świecie cyfrowym możliwe jest uzyskanie tego ostatniego, a więc, czy realne jest przeprowadzenie tajnych wyborów elektronicznych.

Model analogowy

Zanim jednak wejdziemy w świat elektroniki, na chwilę jeszcze zostańmy na ziemi i spróbujmy rzucić okiem na klasyczne wybory li tylko od strony ich bezpieczeństwa proceduralnego. Już w tym przypadku zapewnienie tajności wymaga precyzyjnej analizy. Oczywiście jest jasne, że główna idea polega na tym, że po prostu wchodzimy do kabiny pojedynczo i tam samodzielnie, bezpiecznie głosujemy. Ale czy na pewno nie ma tam ukrytych kamer? A czy długopis nie zostawia jakiegoś identyfikującego nas śladu?

Dalsze pytania można tylko mnożyć: Czy na pewno powinniśmy pozwalać wchodzić do kabin w dwie osoby, nawet jeśli są małżeństwem? A może jedna z nich jest pod presją drugiej? Czy nie jest problemem, gdy ktoś zrobi zdjęcie swojego głosu? A może chce ten głos sprzedać i udowodnić kupującemu, jak zagłosował?

Ktoś może powiedzieć, że to brzmi paranoicznie, gdyż oczywiście niby wiadomo, że istnieją takie zagrożenia, ale skomplikowanie ich wykonania oraz niewielki wpływ pojedynczego incydentu na ostateczny wynik pozwala założyć, że wszystko na koniec dnia i tak jest w porządku. Z opiniami tego typu, dotyczącymi wyborów tradycyjnych, akurat w tym miejscu polemizować nie będziemy. Zwróćmy jednak uwagę na ważną kwestię: nawet jeśli wierzymy, że w świecie niecyfrowym pojedyncze incydenty nas nie ruszają, to musimy sobie uświadomić, że w świecie elektroniki tak to nie działa. Tutaj wszelkie podatności i niedopatrzenia da się zwykle łatwo wykorzystać – i to najczęściej stosunkowo tanio – na skalę masową. Przecież gdy raz stworzymy wirusa, który potrafi odtajnić czyjś głos, to zadziała on nie na jednym, ale na tysiącach komputerów stosujących podobne oprogramowanie, którego jakąś lukę wykorzystujemy.

Model cyfrowy

Nie ukrywamy, że drobiazgowość i plastyczność sekcji wyżej miały na celu zatrucie głowy Czytelnika jedną konkretną myślą: otóż w przypadku potencjalnych głosowań elektronicznych skrupulatność granicząca z paranoją w podejściu do bezpieczeństwa nie jest zwyczajową manierą matematyków, ale potrzebą totalnie bezwzględną i musi być postawiona absolutnie na pierwszym miejscu.

W szczególności już na starcie powinniśmy odrzucać jakiekolwiek pomysły związane z obecnością tzw. zaufanego serwera. To znaczy każdy model, w którym istnieje jakiś jeden wyróżniony Ważny Komputer, do którego np. dostarczane są cyfrowo podpisane głosy wszystkich wyborców, następnie ten komputer zlicza wynik, po czym skutecznie usuwa informacje o głosujących (utajnia wybory), jest modelem kryptologicznie nie do przyjęcia. Zauważmy bowiem, że przy takim podejściu całe zaufanie spoczywa tak naprawdę na administratorze tego komputera. Musimy przecież uwierzyć, że ów administrator niczego sobie nie zapamięta z rzeczy, które ma usunąć, niczego nie usunie z rzeczy, które mają być policzone itp. Nie o taki system nam chodzi.

Gdy realnie myślimy o bezpiecznym tajnym głosowaniu elektronicznym, zastanawiamy się, czy da się je tak zaprojektować, aby całe bezpieczeństwo było oparte o prawa matematyki, które działają pod spodem, a nie o zaufanie do nawet najbardziej nieskalanego administratora, ważnego sądu czy innego podobnego organu. W kryptologii bowiem zawsze paranoicznie (a może zdroworozsądkowo) zakładamy, że w systemie są obecni (a najlepiej: przejęli pełną kontrolę nad całą infrastrukturą techniczną) złoczyńcy, którzy nieustannie sposobią się do sfałszowania wyborów bądź ich odtajnienia.

Czytelnicy Delty (a szczególnie Czytelnicy serii ,,A jednak się da” ukazującej się w latach 2018–2019) orientują się jednak, że nie takie cuda oferuje współczesna kryptologia. Jakie są więc najlepsze protokoły kryptologiczne do tajnych głosowań elektronicznych?

Już tytuł tego artykułu przebił balon napięcia, więc nie będziemy udawać: świat kryptologów nie wierzy w wybory elektroniczne. I to nawet nie na zasadzie, że istnieją jakieś trudności, których do tej pory nie udało się pokonać, ale wciąż jest otwarte pytanie: czy się uda w przyszłości? Nie. Umiemy udowodnić, że nie da się lepiej, niż tak jak umiemy. A tak jak umiemy – choć i tak ma prawo zachwycać – większości fachowców nie zadowala. Dalsza część tego artykułu będzie więc próbą wyeksponowania najważniejszych cyfrowych ograniczeń tej dziedziny oraz pokazania, co jednak się da.

Królestwo za tajność

Okazuje się, że największym wyzwaniem jest właśnie tajność (a nie np. poprawność obliczonego wyniku) wyborów. Da się bowiem – i to dość zaskakująco prostym rozumowaniem – pokazać, że jeśli całkowicie nie ufamy systemowi – nieważne jak zaawansowany matematycznie by on nie był – to po prostu nie da się jej w pełni zapewnić. Dlaczego?

Rozważmy Jasia, który o wszystkim zapomniał i teraz szuka laptopa, aby zdążyć zagłosować tuż przed końcem. Jak to z Jasiem, możliwości będą tylko dwie: albo (a) Jaś nie zdąży, (b) Jaś będzie ostatnią osobą głosującą w wyborach. Zauważmy jednak, że poprawny system będzie w stanie podać wyniki wyborów w obu przypadkach. W systemie muszą więc być zawarte wszystkie informacje, które na to pozwalają. A to oznacza, że ktoś mający ciągły dostęp do wszystkich danych systemu będzie w stanie obliczyć obie te wartości: przed i po wizycie Jasia. Ale przecież z tych dwu danych da się odtworzyć głos Jasia!

Czy więc wszystko stracone? Czy cokolwiek możemy zrobić?

Możemy, o ile nieco poluzujemy założenia. Przy czym „nieco” nie jest tu bynajmniej eufemizmem. Otóż da się zapewnić tajność, gdy zaufanie do systemu jest z naszej strony naprawdę minimalne, a w zasadzie dowolnie małe, byle niezerowe. Bardziej konkretnie: załóżmy, że system działa w modelu rozproszonym i tworzy go nie jeden, ale np. tysiąc czy nawet milion komputerów. Wówczas, jeśli tylko ufamy w uczciwość choć jednego z nich (np. obsługiwanego przez nas samych albo przez przedstawicieli naszego obozu politycznego), to już tajność naszego głosu może zostać zapewniona!

Dokładnie na takim założeniu opiera się system głosowania elektronicznego, który zaprojektowali Ronald Cramer, Matt Franklin, Berry Schoenmakers i Moti Yung. Spróbujemy naszkicować ten dość skomplikowany protokół z lotu ptaka (i to niestety raczej takiego o wysokim pułapie lotu).

Protokół Cramer–Franklin–Schoenmakers–Yung, 1996

Zanim system zostanie uruchomiony, należy wybrać pewne parametry: skupimy się na dwóch najważniejszych: N i K, które spełniają nierówności 1≤K≤N.

System będzie składać się z N komunikujących się ze sobą komputerów (oznaczmy je jako s1,…,sN), co do których zakładamy, że uczciwych jest co najmniej K spośród nich. Przypadek K=1 wydaje się więc najatrakcyjniejszy, ale jest tu też druga strona medalu – aby system zawiesić (nie dopuścić do wiarygodnego opublikowania wyników wyborów), wystarczy zmowa bądź awaria K komputerów. Tak więc zbyt małe K ma też swoje istotne wady.

Dalej wszystko będzie dość skomplikowane, ale jednak się uda:

  • Jaś, aby oddać swój głos X, musi:

    • opublikować zobowiązanie Commit(X) do swojego głosu (zob. Δ1811); zauważmy, że ten pozornie podejrzany krok bynajmniej nie zdradza wartości głosu (opublikowane zobowiązanie nigdy nie zostanie otwarte) – jest natomiast potrzebny później przy weryfikacji wyników;

    • opublikować dowód poprawności Proof(X) swojego głosu (to znaczy udowodnić protokołem zero-knowledge (zob. Δ191), że jego głos jest oddany w poprawnym formacie, np. ma wartość ,,NIE” lub ,,TAK”);

    • dokonać podziału swojego głosu protokołem Shamira (zob. Δ112) na kawałki X1,…,XN;

    • wysłać kawałek Xi do komputera si.

  • gdy wszystkie głosy zostaną oddane, wówczas wszystkie komputery tworzące system do głosowania:

    • pracując razem (według protokołu MPC podobnego do opisanego w Δ198), są w stanie obliczyć wynik wyborów, nie ucząc się przy tym (o ile nie więcej niż (N−K) spośród nich jest nieuczciwych) niczego na temat wartości jakiegokolwiek oddanego głosu.

    • publikują nie tylko ostateczny wynik wyborów, ale i dowód (protokół jest tak zaprojektowany, że jest to możliwe), że jest on poprawny. Każdy, kto ma dostęp do tego dowodu oraz kompletu nieotwartych zobowiązań (takich jak Commit(X) Jasia), jest w stanie upewnić się, czy ostateczny wynik jest poprawny. Jest to niezwykle silna cecha omawianego protokołu. Oznacza ona bowiem, że nawet gdy liczba oszustów przekracza pułap (N−K), to wyniku wyborów i tak nie da się sfałszować (!), a tylko wywołać zamieszanie i konsternację – wszyscy przecież i tak się zorientują, że ostateczny wynik nie jest zgodny z oddanymi głosami.

Epilog epilogu

W tym artykule chcieliśmy pokazać smak wyzwań i skalę problemów przy projektowaniu protokołów do głosowania. Jak na razie, tajność wyborów została wyeksponowana jako główny i w zasadzie dowodliwie nierozwiązywalny problem. Piszemy ,,w zasadzie”, bo wszystko zależy od subiektywnej opinii co do tego, na jakie założenia się godzimy. Choćby w rozważanym protokole – można dyskutować, które parametry (N,K) dają wiarygodną tajność oraz pozwalają wierzyć, że protokół wyborczy kiedykolwiek zakończy się bez zawieszenia. Wybór K=1 oraz N≃30000000 (wówczas każdy uprawniony głosujący stałby się jednym z komputerów si, co niewątpliwie pozwala założyć, że każdy ufa przynajmniej jednej części systemu – mianowicie, samemu sobie) może i teoretycznie daje pełną tajność, ale przecież trudno uwierzyć, że taki protokół udałoby się przeprowadzić bez zakłóceń ze strony chociaż jednego komputera.

Co więcej, okazuje się, że – oprócz powyższego – istnieją jeszcze inne, trochę pozamatematyczne, ale niestety równie fundamentalne problemy, o których tutaj ledwie wspomnimy:

Po pierwsze – gigantycznym problemem jest potencjalny handel głosami (albo zastraszanie i wymuszanie – matematycznie to podobne zagadnienia). W świecie cyfrowym wydaje się on niestety znacznie łatwiejszy niż w świecie tradycyjnym. Głosujący może przecież zainstalować sobie kamerkę w domu i pozwolić komuś z zewnątrz na bieżąco upewniać się, że głosuje on zgodnie z jego wolą. Jest to na pewno wygodniejsze i bezpieczniejsze niż wszelkie podobne działania w rzeczywistym lokalu wyborczym.

Po drugie – pamiętajmy, że w świecie cyfrowym człowiek nie wykonuje obliczeń w głowie, ale korzysta z osobistego komputera, który pamięta za niego tajne dane, dokonuje wrażliwych obliczeń itp. Ten element jest zawsze podkreślany jako potencjalne ważne źródło problemów – nikt przecież tak do końca nie wie, jakie wirusy czy programy szpiegujące ma w swoim komputerze zainstalowane lub też nawet fabrycznie wbudowane. Oznacza to w szczególności, że pułap (N−K) dotyczy nie tylko świadomych oszustów, ale też nieświadomych właścicieli podejrzanego sprzętu.

Melancholijne podsumowanie

Saga ,,A jednak się da” miała na celu przekonanie Czytelnika, że wiele z tego, co wydaje się cyfrowo niemożliwe do zrealizowania, nauka jednak zrealizowała i stworzyła protokoły, które dla zwykłego śmiertelnika są w zasadzie nieodróżnialne od magii. Ale niestety – pychą byłoby wierzyć (może trochę jak Hilbert?), że udawać się tak będzie zawsze…

W przypadku głosowań tajnych, mimo że te najlepsze protokoły aż jeżą się od zastosowanych perełek kryptologii, po prostu w pełni nie udało się. Musimy więc albo zrezygnować z głosowania cyfrowego, albo pogodzić się z którymś ze zgniłych kompromisów dotyczących definicji bezpieczeństwa takiego głosowania.

Wir müssen nicht alles wissen.