Niech będzie stałą stałą. Biorąc pod uwagę liczbę całkowitą , chcemy skonstruować permutację tak aby:
Konstrukcja wykorzystuje stały czas i przestrzeń (tj. Wstępne przetwarzanie zajmuje stały czas i przestrzeń). Możemy użyć randomizacji.
Biorąc pod uwagę , można obliczyć w stałym czasie i przestrzeni.
Permutacja jest niezależna od , tzn. Dla wszystkich zmienne losowe są niezależne i równomiernie rozmieszczone w .
Jedyne, co obecnie wiem, to wykorzystanie przestrzeni logarytmicznej i czasu obliczania wielomianów dla wartości 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 , którą można obliczyć w czasie 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.).
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żeniup n a i [ p ] σ ( 1 ) , σ ( 2 ) , … , σ ( n ) k n ( 1 - 1 / e ) [ n ]liczb pojawia się w tej sekwencji. Należy jednak pamiętać, że ponieważ liczby powtarzają się w tej sekwencji, nie jest to permutacja.
źródło
Odpowiedzi:
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 σ k k k
Praktyczny schemat dla mniejszychn
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 ] n 2)128 σk( i ) ja 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 ≪ n1 / 4 k k
Uogólniając to na większen
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 ( 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 przezm 2 n sol ( Z / m Z )∗ + 1 π:G→G
Następnie zdefiniuj przezσ
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.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 sol ( Z / m Z ) O ( 1 ) σ( i ) ja fa, 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.)lgn 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 ksol π( x ) = e x sol sol sol π 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 .sol fa, g k
źródło