Minimize the Randomness in Rasta-Like Designs: How Far Can We Go? Application to PASTA

Die Rasta-Designstrategie ermöglicht den Aufbau von Chiffren mit niedrigem Durchgang, da sie statistische Angriffe und algebraische Angriffe durch die Randomisierung der Chiffre wirksam verhindert, was sie besonders für die hybride homomorphe Verschlüsselung (HHE), auch bekannt als Transciphering, geeignet macht. Eine solche Randomisierung wird durch pseudozufällige Stichproben neuer invertierbarer Matrizen für jede Runde jeder neuen Chiffrierauswertung erreicht. Die naive Entnahme einer zufälligen invertierbaren Matrix für jede Runde hat jedoch erhebliche Auswirkungen auf die Laufzeit der reinen Auswertung, nicht aber auf die Kosten der homomorphen Auswertung. Um dieses Problem zu lösen, wurde auf der ToSC 2020 dasta vorgeschlagen, um die Kosten für die Erzeugung der Zufallsmatrizen zu reduzieren.

In dieser Arbeit gehen wir das Problem aus einer anderen Perspektive an: Wie weit kann die Zufälligkeit in Rasta-ähnlichen Designs reduziert werden, um die reine Auswertungslaufzeit zu minimieren, ohne die Sicherheit zu beeinträchtigen? Um diese Frage zu beantworten, haben wir die wichtigsten Bedrohungen für rasta-ähnliche Chiffren und die Rolle von Zufallsmatrizen bei der Gewährleistung der Sicherheit sorgfältig untersucht. Wir wenden unsere Ergebnisse auf die kürzlich vorgeschlagene Chiffre PASTA an und schlagen eine modifizierte Version namens PASTA2 vor, die mit einer anfänglichen Zufallsmatrix und festen linearen Schichten - die durch die Kombination zweier MDS-Matrizen mit dem Kronecker-Produkt erhalten werden - für die anderen Runden instanziiert wird.

Im Vergleich zu PASTA, der State-of-the-Art-Chiffre für BGV- und BFV-artiges HHE, zeigt unsere Evaluierung, dass PASTA2 bei gleicher homomorpher Laufzeit in der homomorphen Verschlüsselungsbibliothek SEAL um bis zu 100 % schneller in plain ist und in HElib eine bis zu 30 % schnellere Evaluierungszeit aufweist.