Czy można zaszyfrować CNF?

Czy można przekształcić CNF w inny CNF taki jak? $\mathcal C$ $\Psi(\mathcal C)$

Funkcja może być obliczona w czasie wielomianowym z jakiegoś tajnego parametru losowego . $\Psi$ $r$
ma rozwiązanie wtedy i tylko wtedy, gdy ma rozwiązanie. $\Psi(\mathcal C)$ $\mathcal C$
Każde rozwiązanie z można skutecznie przekształcić w roztwór za pomocą . $x$ $\Psi(\mathcal C)$ $\mathcal C$ $r$
Bez roztwór (lub innych własności ) nie daje żadnych pomocy przy rozwiązywaniu . $r$ $x$ $\Psi(\mathcal C)$ $\mathcal C$

Jeśli istnieje takie , można go wykorzystać do nakłonienia innych do rozwiązania problemów obliczeniowych dla nas (z ewentualnym zastąpieniem rozwiązywania CNF innymi problemami - wybrałem CNF, ponieważ chciałem uszczegółowić problem), w taki sposób że nie mogą skorzystać z możliwego rozwiązania, nawet jeśli wiedzą, jaki problem rozwiązaliśmy. Na przykład moglibyśmy osadzić problem faktoryzacji w grze komputerowej, która pozwala graczom grać tylko wtedy, gdy pracują nad naszym problemem w tle, od czasu do czasu wysyłając dowody obliczeń. Być może oprogramowanie może być nawet „darmowe” w ten sposób, gdzie „darmowe” ukrywa (być może wyższy) koszt w rachunku za energię elektryczną twoich rodziców. $\Psi$

— domotorp
źródło

Literówka „... nie pomaga w rozwiązaniu

”? Nawiasem mówiąc, jeśli nie martwisz się strukturą

tzn. „Gracz” nie ma dostępu do

a jedynie do rozwiązania

, to zwykła losowa permutacja znaku zmiennych (

) i o swobodnym permutacji indeksów zmiennych należy przygotować roztwór

całkowicie bezużyteczna do rozwiązywania

C

$\mathcal C$

Ψ

$\Psi$

Ψ (C)

$\Psi(\mathcal C)$

x

$x$

π_{ℓ} (ℓ_{i}) = \pm ℓ_{i}

$\pi_{\ell}(\ell_i) = \pm \ell_i$

x

$x$

Ψ (C)

$\Psi(\mathcal C)$

C

$\mathcal C$

— Marzio De Biasi

@Marzio Thx, poprawiona literówka. Ale nie rozumiem twojego komentarza - czy zakładasz, że „gracz” nie ma dostępu do

a jedynie do

? Powinno to jasno wynikać z opisu, który ma.

Ψ (C)

$\Psi(\mathcal C)$

x

$x$

— domotorp

tak, proste „tasowanie literałów i indeksów zmiennych” z pewnością działa, jeśli gracz nie ma dostępu do struktury

(moje było tylko szybkim komentarzem). Być może jednak pomysł „losowego” można by rozszerzyć w ten sposób: jeśli

jest 3-CNF, wówczas istnieją tylko

możliwe odrębne klauzule, a znajomość

(przetasowana wersja

) może być pomocna tylko wiedząc skutecznym sposobem na znalezienie izomorfizm między

Ψ (C)

$\Psi(\mathcal C)$

C

$\mathcal C$

(2 n)^{3}

$(2n)^3$

Ψ (C)

$\Psi(\mathcal C)$

C

$\mathcal C$

Ψ (C)

$\Psi(\mathcal C)$

C

$\mathcal C$

— Marzio De Biasi

@Marzio W miarę upływu czasu prawdopodobnie (hiper) grafisomorfizm można szybko rozwiązać.

— domotorp

Spójrz na zaszyfrowaną kompletną hipotezę. Sugeruje to, że twoja propozycja jest wiarygodna. To wskazuje, że istnieje różnowartościową długości zwiększenie

Secure funkcji jednokierunkowej

, tak że SAT i

nie p-izomorficzne.

2^{n^{ϵ}}

$2^{n^\epsilon}$

f

$f$

f (S A T)

$f(SAT)$

— Mohammad Al-Turkistany

Odpowiedzi:

Feigenbaum in, Encrypting Problem Instances , proponuje definicję (Def. 1) funkcji szyfrowania dla problemów NP-zupełnych, która spełnia twoje wymagania. Udowadnia, że NP-zupełny problem Porównawcze nierówności wektorowe dopuszcza taką funkcję szyfrowania. Na zakończenie dochodzi do głównego twierdzenia, że wszystkie problemy z kompletnością NP, które są p-izomorficzne dla CNF-SAT, są szyfrowalne.

— Mohammad Al-Turkistany
źródło

W dalszych pracach stwierdzili, że jest mało prawdopodobne, że problemy z NP-zupełnym szyfrowaniem! doi.org/10.1016/0022-0000(89)90018-4 Te dokumenty były właśnie tym, czego szukałem. Zastanawiam się, dlaczego rozumiem je o wiele lepiej niż ostatnie wyniki w kryptografii - być może dziedzina zbytnio odbiegała od teorii złożoności od tego czasu ...

— domotorp

Wspomniana aplikacja nazywa się w literaturze „dowodem przydatnej pracy”, patrz na przykład ten artykuł .

Możesz użyć w pełni homomorficznego schematu szyfrowania (gdzie tekstem jawnym jest instancja CNF), aby przekazać obliczenia niezaufanemu podmiotowi bez ujawniania danych wejściowych.

To nie odpowiada dokładnie na twoje pytanie, ponieważ taki schemat nie mapuje CNF na inną CNF, ale działa dla zamierzonej aplikacji.

— Diego de Estrada
źródło

Afaik, szyfrowanie homomorficzne służy do obliczeń na niektórych liczbach. Jak dokładnie użyłbyś go do mojego problemu?

— domotorp

FHE jest zdefiniowany dla obwodów boolowskich. Traktuj instancję CNF jak wektor bitowy. Biorąc pod uwagę rozmiar wejściowy, możesz zbudować obwód logiczny, który wyprowadza przypisanie, jeśli takie istnieje (patrz cs.stackexchange.com/q/72289/627 ).

— Diego de Estrada

Myślę, że różnica polega na tym, że w twoim rozwiązaniu, przy zachowaniu prywatności, kodowanie jest dość kosztowne w porównaniu do zadania, które chcemy rozwiązać. Chciałbym zakodować w czasie wielomianowym wykładniczą ilość pracy.

— domotorp

@domotorp Rozumiem. Jest sposób na użycie FHE bez obwodów, patrz eprint.iacr.org/2013/229.pdf

— Diego de Estrada,

Ponieważ coraz więcej użytkowników ocenia Twoją odpowiedź, być może zawiera ona coś, co przeoczyłem. Czy twierdzisz teraz, że to działa na moje pytanie lub tylko na aplikację? Patrzyłem też na papier, ale nie jest to takie łatwe do zrozumienia. Czy mógłbyś mi powiedzieć, jaki konkretny wynik / twierdzenie miałoby zastosowanie w moim przypadku?

— domotorp