Czy możemy skonstruować k-mądrą niezależną permutację na [n], używając tylko stałego czasu i przestrzeni?

Niech $k>0$ będzie stałą stałą. Biorąc pod uwagę liczbę całkowitą $n$ , chcemy skonstruować permutację $\sigma \in S_n$ tak aby:

1. Konstrukcja wykorzystuje stały czas i przestrzeń (tj. Wstępne przetwarzanie zajmuje stały czas i przestrzeń). Możemy użyć randomizacji.

2. Biorąc pod uwagę $i\in[n]$ , $\sigma(i)$ można obliczyć w stałym czasie i przestrzeni.

3. Permutacja $\sigma$ jest niezależna od $k$ , tzn. Dla wszystkich $i_1, \ldots, i_k$ zmienne losowe $\sigma(i_1), \ldots, \sigma(i_k)$ są niezależne i równomiernie rozmieszczone w $[n]$ .

Jedyne, co obecnie wiem, to wykorzystanie przestrzeni logarytmicznej i czasu obliczania wielomianów dla wartości $\sigma(i)$ przy użyciu generatorów pseudolosowych.

tło

Potrzebowałem czegoś takiego jak wyżej do niektórych ostatnich prac, a skończyło się na czymś słabszym: zezwalałem na wielokrotne wpisy i sprawdzałem, czy wszystkie liczby, których potrzebowałem, były pokryte (tj. Bałagan). W szczególności otrzymałem sekwencję niezależną od $k$ , którą można obliczyć w czasie $O(1)$ i używając stałej przestrzeni. Byłoby miło mieć coś prostszego lub po prostu wiedzieć, co wiadomo.

Założenia

Zakładam model pamięci RAM o koszcie jednostkowym. Każde słowo w pamięci / rejestrze ma rozmiar , a każda podstawowa operacja arytmetyczna zajmuje czas O ( 1 ) . Jestem gotów przyjąć wszelkie uzasadnione założenia kryptograficzne (funkcja jednokierunkowa, dyskretny dziennik itp.).$O(\log n)$$O(1)$

Obecna sprawa

Jak sugeruje Kaveh, oto „łatwy” hack, który obecnie mam (jest to dość standardowy): Niech będzie wielomianem nad liczbą pierwszą ( pomyśl o jako o ). Tutaj każdy jest pobierany równomiernie i losowo z . Łatwo zauważyć, że jest sekwencją, która ma powtórzenia, ale jest niezależna od i w przybliżeniu$\sigma(x) = \sum_{i=0}^{k+2} a_i x^i \bmod p$p n a i [ p ] σ ( 1 ) , σ ( 2 ) , … , σ ( n ) k n ( 1 - 1 / e ) [ n $p$$p$$n$$a_i$$[p]$$\sigma(1), \sigma(2), \ldots, \sigma(n)$$k$$n(1-1/e)$liczb pojawia się w tej sekwencji. Należy jednak pamiętać, że ponieważ liczby powtarzają się w tej sekwencji, nie jest to permutacja.$[n]$

Jeśli chcesz zastosować techniki kryptograficzne i polegać na założeniach kryptograficznych oraz zaakceptować obliczeniową niezależność -wise, możliwe, że szyfrowanie zachowujące format (FPE) może być pomocne. Pozwól mi naszkicować kilka różnych konstrukcji tego rodzaju.$k$

(Przez „obliczeniowej pojęcia niezależności -wise”, to znaczy, że żaden przeciwnik z rozsądnym czasie biegu potrafi odróżnić σ z k -wise niezależnego permutacji, z wyjątkiem nieznacznej przewagi. Systemy te nie będą informacje teoretycznie k -wise niezależne, ale będą „zasadniczo tak dobre, jak k -niezależne”, zakładając, że wszystkie obliczenia w zasięgu wzroku są ograniczone obliczeniowo.)$k$$\sigma$$k$$k$$k$

Praktyczny schemat dla mniejszych $n$

W szczególności użyj konstrukcji FPE do zbudowania szyfru blokowego (permutacja pseudolosowa, PRP) z podpisem . Dla wartości n, które są mniejsze niż 2 128 , prawdopodobnie najlepszym schematem jest użycie konstrukcji Feistela ze stałą liczbą rund (powiedzmy 10) i funkcją rundy, która jest PRF pochodzącym z AES. Czas wykonywania oceny σ k ( i ) dla pojedynczej wartości i będzie wynosił O ( 1 ) AES. Każde wywołanie AES działa w stałym czasie.$\sigma_k : [n] \to [n]$$n$$2^{128}$$\sigma_k(i)$$i$$O(1)$

Wreszcie należy pamiętać, że każda permutacja pseudolosowych jest automatycznie -wise niezależny. W szczególności, Luby-Rackoff twierdzenie gwarantuje, że co najmniej 3 rundy, można uzyskać (przybliżona) k -wise niezależność jeśli k « n 1 / 4 , zakładając AES jest bezpieczna. Przy większej liczbie rund prawdopodobne jest, że wynik będzie silniejszy, ale twierdzenia są trudniejsze do udowodnienia i stają się bardziej techniczne, chociaż powszechnie uważa się, że stała liczba rund powinna wystarczyć do uzyskania bardzo wysokiego poziomu bezpieczeństwa (a tym samym idealnego k - mądra niezależność dla wszystkich rozsądnych wartości k ).$k$$k$$k \ll n^{1/4}$$k$$k$

Uogólniając to na większe $n$

Gdy jest większe, rzeczy stają się dziwniejsze, ponieważ model pamięci RAM w cenie jednostkowej domyślnie pozwala na równoległość do O ( lg n ) za darmo. Nie jest dla mnie jasne, jaki powinien być koszt programów warunków wstępnych w tym modelu (stały? Rosnący z n ? Nie wiem).$n$$O(\lg n)$$n$

Trzecia możliwa konstrukcja

Niech będzie modułem RSA, który jest nieco większy niż 2 n . Zdefiniuj G jako podgrupę ( Z / m Z ) ∗ zawierającą elementy, których symbolem Jacobiego jest + 1 . Zdefiniuj π : G → G przez$m$$2n$$G$$(\mathbb{Z}/m\mathbb{Z})^*$$+1$$\pi : G \to G$

Następnie zdefiniuj przez$\sigma$

gdzie to losowe bijectywne 2-niezależne funkcje skrótu.$f,g$

Podejrzewam, że ta konstrukcja ma szansę być (w przybliżeniu) niezależna względem , przy założeniu podobnym do RSA. Nie mam dowodu, tylko intuicję. Główną znaną regularnością π jest to, że jest multipomatywnie homomorficzna: π ( x y ) = π ( x ) π ( y ) . Nie znam żadnych innych istotnych prawidłowości, nawet zależności „ k” . Zastosowanie 2-niezależnego skrótu przed i po π eliminuje tę prawidłowość: jeśli π jest $k$$\pi$$\pi(xy) = \pi(x) \pi(y)$$k$$\pi$$\pi$$k$-wise niezależność wyjątkiem multiplikatywnego homomorphicity, następnie 2-wise niezależne hashe wyglądać powinny one zapewnić pełną -wise niezależności. Ale to jest super-szkicowy i lat świetlnych od dowodu k niezależności -wise.$k$$k$

Pamiętaj, że musisz użyć technik szyfrowania zachowujących format (np. Techniki cyklicznej), aby upewnić się, że działa na G, a nie na ( Z / m Z ) . Schemat ten powinien mieć czas O ( 1 ) (oczekiwany) do oceny σ ( i ) na danym wejściu i , z odpowiednim wyborem f , g .$f,g$$G$$(\mathbb{Z}/m\mathbb{Z})$$O(1)$$\sigma(i)$$i$$f,g$

Ponadto, w pewnym sensie, ta kandydująca konstrukcja nadużywa modelu kosztu jednostkowego, polegając na możliwości działania na liczbach bitowych w czasie O ( 1 ) , dla dużych wartości n , co w praktyce nie jest rozsądne . (Ta ostatnia konstrukcja nie będzie bezpieczna dla małych wartości n , więc to ostatnie podejście zasadniczo zależy od reżimu dużego n , aby miał szansę na działanie ... dokładnie reżimu, w którym model kosztu jednostkowego jest najbardziej wątpliwy.)$\lg n$$O(1)$$n$$n$$n$

Przyznaję, że ta wersja jest dość długa, ale wspominam o niej, na wypadek gdyby zainspirowała ją do lepszego rozwiązania.

Na przykład może być możliwe zastąpienie odpowiednią grupą krzywych eliptycznych, tak że mamy π ( x ) = e x ponad G (pamiętaj, że grupy krzywych eliptycznych zwykle używają notacji addytywnej zamiast notacji multiplikatywnej). Dobrą rzeczą jest to, że nie jest całkowicie nierozsądne przypuszczenie, że jeśli grupa krzywej eliptycznej G zostanie wybrana właściwie, G będzie zachowywać się jak „grupa czarnych skrzynek”, co moim zdaniem może skutecznie sugerować, że π będzie $G$$\pi(x) = e x$$G$$G$$G$$\pi$$k$- niezależny pod względem „z wyjątkiem efektów implikowanych przez multiplikatywny homomorfizm”. Nie mam kompletnej konstrukcji gotowej do zaproponowania (brakującym elementem jest jak wybrać i jak skonstruować f , g i jak udowodnić niezależność k -tego od tego), ale być może uda się jakoś połączyć te elementy .$G$$f,g$$k$