QUAD (szyfr)

KWADRAT
Ogólny
Projektanci Côme Berbain, Henri Gilbert i Jacques Patarin
Opublikowane po raz pierwszy 28 maja 2006 (w Eurocrypt)
Szczegóły szyfru
Kluczowe rozmiary 80 bitów
Struktura wielowymiarowy układ równań kwadratowych

W kryptografii szyfr QUAD jest stosunkowo nowym szyfrem strumieniowym , który został zaprojektowany z myślą o możliwych do udowodnienia argumentach bezpieczeństwa.

Opis

QUAD opiera się na iteracji losowo wybranego wielowymiarowego układu kwadratowego S=(Q 1 , ..., Q m ) m=kn równań z n niewiadomymi na skończonym ciele GF(q). Proces generowania strumienia klucza polega po prostu na iteracji trzech następujących kroków w celu wygenerowania (k -1) n wartości strumienia klucza GF(q) w każdej iteracji.

  • Oblicz krotkę kn wartości GF(q) S(x) = (Q 1 (x),..., Q kn (x)) gdzie x jest bieżącą wartością stanu wewnętrznego;
  • Wyprowadź sekwencję (Q n+1 (x),..., Q kn (x)) (k-1)n wartości strumienia klucza GF(q)
  • Zaktualizuj stan wewnętrzny x sekwencją n GF(q) pierwszych wygenerowanych wartości (Q 1 (x),..., Q n (x))

QUAD jest nowoczesnym szyfrem strumieniowym, tj. wykorzystuje klucz i wartość inicjującą (IV) do utworzenia sekwencji strumienia klucza. Zdefiniowano również konfigurację klucza i IV, która również opiera się na wielowymiarowym układzie kwadratowym.

Bezpieczeństwo

Bezpieczeństwo generowania strumienia klucza w QUAD można w sposób udowodniony sprowadzić do przypuszczalnej nierozwiązywalności problemu MQ, a mianowicie rozwiązania wielowymiarowego układu równań kwadratowych. Pierwszy dowód przeprowadzono na polu GF(2) dla staromodnego szyfru strumieniowego (gdzie kluczem jest stan początkowy). Został on później rozszerzony przez Berbaina i Gilberta, aby uwzględnić procedurę konfiguracji współczesnego szyfru (z etapem konfiguracji wyprowadzającym stan początkowy z klucza). Bezpieczeństwo całego szyfru jako funkcji pseudolosowej można powiązać z przypuszczalną nierozwiązywalnością problemu MQ. Autorzy zbadali także odporność szyfru na ataki klasyczne.

Parametry zalecane

Autorzy zalecają stosowanie wersji QUAD z kluczem 80-bitowym, IV 80-bitowym i stanem wewnętrznym n = 160 bitów. Wysyła 160 bitów strumienia klucza (m = 320) w każdej iteracji, aż do wygenerowania 2 40 bitów strumienia klucza.

Na konferencji Eurocrypt 2006 zaprezentowano raporty szybkości dla instancji QUAD ze 160-bitowym stanem i blokiem wyjściowym w polach GF(2), GF(16) i GF(256). Te raporty dotyczące szybkości były częścią analizy „Efficient Implementations of Multivariate Quadratic Systems”, opublikowanej przez Berbaina, Billeta i Gilberta na konferencji SAC 2006. Analiza ta (która obejmuje również kilka wielowymiarowych schematów klucza publicznego, a także szyfr strumieniowy QUAD ) częściowo zbadali wpływ zmiany wielkości pola na wydajność, nie biorąc pod uwagę aspektów bezpieczeństwa.

Dyskusja na temat parametrów

Początkowe twierdzenie o bezpieczeństwie dla QUAD obowiązuje tylko dla pola GF(2), a zalecane parametry nie pozwalają uzyskać sprzeczności z dowodem bezpieczeństwa. Autorzy QUAD, którzy podali twierdzenie o bezpieczeństwie, przyznali, że złamanie QUAD przy sugerowanych przez nich parametrach nie jest sprzeczne z twierdzeniami o dowodzie bezpieczeństwa, kiedy proponowali ten schemat na konferencji Eurocrypt 2006. Jednakże wydawało się, że autorzy uznali je za wystarczające do zapewniają pożądany poziom bezpieczeństwa około 2 80 .

Yang, Chen, Bernstein i Chen zbadali bezpieczeństwo różnych zestawów parametrów w dokumencie „Analiza Quad” i stwierdzili, że niektóre z nich są bardzo niepewne. W ich artykule omówiono zarówno teoretyczne, jak i praktyczne aspekty ataku na QUAD oraz ataku na leżący u jego podstaw trudny problem. Na przykład w tym artykule pokazano, jak użyć XL-Wiedemanna do złamania instancji GF(256) QUAD (256, 20, 20) w około 266 cyklach Opterona i złamania podstawowego trudnego problemu w około 245 cyklach , co było przeprowadzone pomyślnie. Jednak według tego artykułu zajęłoby to około 2 110 osób rozwiązać instancję wersji QUAD(2,160,160) zalecanej przez autorów QUAD przy użyciu XL-Wiedemanna.

Badanie Yang i in. Podkreślił fakt, że twierdzenia o bezpieczeństwie często opierają się na redukcjach ze współczynnikiem luzu, a po uwzględnieniu tego żaden ze zbiorów parametrów sugerowanych wersji nie jest wystarczający do dowodu bezpieczeństwa. Przykładem, który będzie możliwy do udowodnienia, będzie QUAD(2,320,320), czyli dwa razy szerszy niż pierwotnie zaproponowano.

Twierdzenie o bezpieczeństwie można również udowodnić dla GF (q), aczkolwiek z większym współczynnikiem luzu; to i rozszerzenia QUAD dla bardziej wydajnych wdrożeń proponują Liu i in. (patrz odniesienie „Bezpieczne PRNG ze specjalistycznych map wielomianowych na dowolnym F q ”).

  • „QUAD: praktyczny szyfr strumieniowy z możliwym do udowodnienia bezpieczeństwem” (PDF) . Źródło: 18.03.2008 .
  • „Efektywne implementacje wielowymiarowych układów kwadratowych” (PDF) . Źródło: 18.03.2008 .
  • „O bezpieczeństwie szyfrów strumienia zależnego IV” (PDF) . Źródło: 18.03.2008 .
  • „Analiza QUAD” (format Adobe Acrobat) . 2007-03-03 . Źródło : 2008-02-05 .
  • „Analiza wielowymiarowych funkcji skrótu” (PDF) .
  • „Bezpieczne PRNG ze specjalistycznych map wielomianowych za pomocą dowolnych $ F_q $” (PDF) .
Pobrano z „ https://en.wikipedia.org/w/index.php?title=QUAD_(cipher)&oldid=1084911638 ”