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

10

Niech k>0 będzie stałą stałą. Biorąc pod uwagę liczbę całkowitą n , chcemy skonstruować permutację σSn 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[n] , σ(i) można obliczyć w stałym czasie i przestrzeni.

  3. Permutacja σ jest niezależna od k , tzn. Dla wszystkich i1,,ik zmienne losowe σ(i1),,σ(ik) 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 σ(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(logn)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σ(x)=i=0k+2)zajaxjamodpp n a i [ p ] σ ( 1 ) , σ ( 2 ) , , σ ( n ) k n ( 1 - 1 / e ) [ n ]ppnai[p]σ(1),σ(2),,σ(n)kn(11/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]

Sariel Har-Peled
źródło
1
Nie. W stałym czasie możesz podać tylko stałą wartość wyjściową, więc dla każdego algorytmu o stałym czasie, dla wystarczająco dużego , wsparcie zmiennych losowych w warunku 3 będzie ścisłym podzbiorem [ n ] .n[n]
2
Potrzebuję stałej ilości obliczeń na pozycję permutacji - więc całkowity czas obliczeń może być liniowy dla całej permutacji.
Sariel Har-Peled
1
Jeśli chodzi o przestrzeń - zakładam model słów - więc każde słowo zajmuje stałą ilość miejsca, nawet jeśli ma logarytmiczną liczbę bitów.
Sariel Har-Peled
1
Częściowe rozwiązanie: załóżmy, że jest siłą pierwszą i k = 2 . Niech F będzie polem z | F | = n . Zestaw σ ( x ) = x + b losowego a , b F z 0 . Zatem σ jest parą niezależną permutacją n elementów, które można obliczyć w „stałym czasie”. Może to się uogólnia. nk=2)fa|fa|=nσ(x)=zax+bza,bfaza0σn
Thomas
1
Yeh Wiedziałem to ;). Problem polega na tym, że musi być znacznie większy, a tylko wielomiany liniowe są permutacjami, a nie kombinacjami wyższego stopnia. k
Sariel Har-Peled

Odpowiedzi:

3

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σkkk

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.σk:[n][n]n2128σk(i)iO(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 ).kkkn1/4kk

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).nO(lgn)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 przezm2nG(Z/mZ)+1π:solsol

π(x)=x3modm.

Następnie zdefiniuj przezσ

σ(i)=g(π(f(i)),

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 kkππ(xy)=π(x)π(y)kππ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.kk

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,solsol(Z/mZ)O(1)σ(ja)jafa,sol

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.)lgnO(1)nnn

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 ksolπ(x)=mixsolsolsolπ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 .solfa,solk

DW
źródło
To bardzo interesujące - podróżuję przez kilka następnych tygodni, ale przyjrzałbym się temu, kiedy wrócę. Dzięki!
Sariel Har-Peled,