NIST Additional Digital Signature Schemes: trzecia runda selekcji PQC

Wraz z publikacją NIST IR 8610, do trzeciej rundy “Additional Digital Signature Schemes” przechodzi 9 kandydatów na schematty podpisów cyfrowych dla kryptografii postkwantowej (PQC).

Choć to jeszcze nie jest ostateczna decyzja, jest przypomnieniem, że NIST aktywnie prowadzi ewaluację nowych schematów, które wzmocnią rodzinę ML-DSA, SLH-DSA oraz FN-DSA. Jednocześnie jednak, jeśli zredukujemy listę kandydatów do 2-4, masz w sumie 5-7 schematów tylko do podpisów cyfrowych. Każdy z nich o innych cechach i żaden z nich nie zbliżający się cechami do wariantów pre-quantum (rodziny ECC czy RSA). Jednym istotnym wyjątkiem jest SQIsign, schemat oparty o Isogenies, który oferuje bardzo kompaktowe klucze publiczne i podpisy. Zastrzeżenie jest jednak takie, że kryptografia oparta o Isogenies ma za sobą znaną historię kompromitacji, czego najbardziej znanym przykładem jest schemat KEM SIKE.

Całkiem nieźle problem obrazuje poniższy wykres: Źródło: NIST Signatures Zoo

Innym wykresem wartym rzucenia okiem jest porównanie cykli dla issuance/verification, które daje perspektywę na zasoby obliczeniowe potrzebne przy rozważaniu konkretnego schematu (i tu SQIsign nie wygląda już tak kolorowo).

W “Call for Proposals” wskazano, że zgłoszenia powinny spełniać co najmniej jedno z poniższych kryteriów:

• Schematy lattice-based powinny oferować przynajmniej jedną istotną przewagę wydajnościową względem ML-DSA i FN-DSA.
• Schematy non-lattice-based powinny zapewniać przynajmniej jedną istotną przewagę wydajnościową względem SLH-DSA.

Istotne (nowe) rodziny algorytmów analizowane w tej rundzie to: Isogenies, Multivariate oraz MPC-in-the-Head (MPCitH). Szczególnie ta ostatnia grupa jest interesująca, ponieważ buduje schematy podpisu w oparciu o stosunkowo nowy model koncepcyjny: lokalnie symulowane obliczenia wielostronne (multi party computation; MPC) z wirtualnymi uczestnikami oraz dowodami wiedzy zerowej (ZKP).

MPCitH możesz sobie wyobrazić jako podział sekretu (klucza prywatnego) pomiędzy wirtualnych uczestników, z których każdy utrzymuje własny lokalny stan wykonania i generuje zobowiązania (commitments) do tego stanu. Lista wszystkich interakcji danego uczestnika z pozostałymi nazywana jest widokiem (view, czyli taki log interakcji). Następnie podpisujący agreguje zobowiązania do tych widoków i selektywnie ujawnia ich fragmenty weryfikatorowi w formie ZKP.

Rola weryfikatora jest, przez analogię, w pewnym sensie zbliżona do repliki (węzła) w systemie rozproszonym typu practical Byzantine Fault Tolerance (pBFT), który poszukuje niespójności w dostarczonych dowodach. Weryfikator podpisu MPCitH robi dokładnie to samo, szuka niespójności.

W porównaniu do SLH-DSA, warianty MPCitH oferują mniejsze podpisy oraz lepszą wydajność weryfikacji.

Źródło/source: NIST Signatures Zoo

Porównaj np. SLH-DSA 128f vs. FAEST 128f. Paradoks z SLH-DSA jest taki, że często najlepiej pasuje do wszelkiego rodzaju zastosowań infrastrukturalnych z racji relatywnie prostej konstrukcji (więcej tutaj), która jednocześnie jest jego pięta achillesową w aspekcie wydajności i wymagań mocy obliczeniowej. Z kolei MPCitH to relatywnie nowy koncept, przychodzący z kosztem znacznie bardziej złożonych systemów dowodowych, nie wspominając już o potencjalnych wektorach side-channel wynikających właśnie ze złożoności koncepcji i nietrywialnej implementacji.

Trade-offs. Dzień dobry.