Prosjekt med Morten og Semira (og Orr?). [Overleaf](https://www.overleaf.com/project/679a0ac45f0c1f816992fdb0) Basert på [Quantum advantage from soft decoders](https://arxiv.org/abs/2411.12553) og [Rubato](https://eprint.iacr.org/2022/537.pdf). Skjermbilde fra [[NaCl]]-møte [[12025-02-24]]: ![[Pasted image 20250224143513.png]] ## Neste steg - [ ] 💻 Se over Overleafen før neste møte (ons 26/2) - [ ] 💻 Strukturer tanker basert på møtenotater, og finn prioritert leseliste - [ ] 📖 Les (...) #### Fullførte steg - [x] 📱 Avtal tid for neste møte ### Litteratur - [Rubato](https://eprint.iacr.org/2022/537.pdf) - [Quantum advantage from soft decoders](https://arxiv.org/abs/2411.12553) - [Alessandro Budroni og Erik Mårtensson (faktisk) – Improved Estimation of Key Enumeration with Applications to Solving LWE](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10206474), og oppfølgeren [Further Improvements of ...](https://eprint.iacr.org/2023/1547) - Kan angrepsteknikkene vi kommer opp med også anvendes her (se p. 11, "Arora-Ge Attack against Variant 1"): [Homomorphic Evaluation of Lattice-Based Symmetric Encryption Schemes](https://eprint.iacr.org/2018/653.pdf) ### Møter ##### [[12025-02-26]] Zoommøte med Morten, Semira og Orr. Dream scenario: Vi klassifiserer en klasse med angrep, og viser som anvendelse at 1. [Rubato](https://eprint.iacr.org/2022/537.pdf) er *sikrere* enn forfatterne anslo. 2. MLWR-SYM fra [Homomorphic Evaluation of Lattice-Based Symmetric Encryption Schemes](https://eprint.iacr.org/2018/653.pdf) er *mindre* sikkert (og kanskje helt knukket?) via angrepene. ##### [[12025-01-17]] - [ ] 📱 Legg inn bilder av notatene jeg tok Angående guessing entropy (og generalisering til kvanteverden, se: [May et al. – Entropy Suffices for Guessing Most Keys](https://eprint.iacr.org/2023/797.pdf); [Albrecht et al. – Quantum Augmented Dual Attack](https://eprint.iacr.org/2023/139) ##### [[12025-01-10]] - I kvantepaperet, så er som sagt Problem 5 en univariat versjon av problemet vi ønsker å se på. Nøyaktig hvilken del av [Rubato-paperet](https://eprint.iacr.org/2022/537.pdf) bruker den multivariate versjonen av problemet? - To recap: Ønsker å ordne det Rubato-paperet *ikke* gjorde, nemlig isolere et generelt problem ut av det, være litt dristig i sikkerhetspåstanden, og stille det som en (litt gøy) utfordring til kryptanalysecommunityet. ![[Pasted image 20250110143613.png]] I angrepene under GCD, Gröbner, Lattice, og Arora-Ge, så ser de egentlig på dette som et tilfeldig Noisy Multivariate Interpolation (NMI)-problem. LC (Linear Cryptanalysis) er (så vidt Morten kan se) den eneste som er chiffer-*spesifikk*, altså som spesialiserer angrepet i større grad enn bare å se på det som et tilfeldig NMI-problem. "I denne delen av fagfeltet så er det sånn at du må alltid *nevne* lineær og differensiell kryptanalyse, men det er sjeldent der skoen trykker (som man også ser fra tabellen)." Morten gjetter at kosten til angrepene de kaller Gröbner og Arora-Ge fort i praksis fort havner på nivå med LC-kolonnen. ![[Pasted image 20250110145327.png]] (Når du skal forstå Problem 5, hvis du antar $q$ er et primtall så kan du bare bruke $Z_q$.) Angående $k$, underforstått, så antar man $k$ mye mindre enn $q$. $S$ er gjerne også liten. Hvis du ikke gir noen skranke på graden av $P$, og $S$ bare har ett element (e.g. $S=\{0\}$) så er dette et interpoleringsproblem: da bare løser du $P(\alpha) = y_\alpha$ for alle $\alpha$. alle funksjoner mellom to endelige kropper lar seg beskrive av et polynom av grad maks $p-1$; altså så *må* det finnes en $P$ som interpolerer fra $\alpha$ til $y_\alpha$ for alle $\alpha \in \{0, \dots, q-1\}$. Men hvis $k$ er *liten*, så har du mest sannsynlig *ikke* et polynom som løser dette problemet. Men som et promise-problem, er dette fortsatt løst for $|S|=1$. Men det øyeblikket $S$ blir større, blir dette raskt et problem som blir vanskeligere å løse. (Man kan da se på $|S| > 1$ som at løsningene har noe støy i seg.) Eksempel: La $S = \{-1,0,1\}$. Kan da konstruere en løsning med høyere grad ved å definere polynomet: $(y_\alpha - P_\alpha)(y_\alpha - P_\alpha + 1)(y_\alpha - P_\alpha - 1) = 0$ (hvor $P_\alpha \coloneqq P(\alpha)$). La oss si at $P$ er multivariat med $t$ variabler, $P(x_1, \dots, x_t)$. **Input:** $(y_0, (\alpha^0_1, \dots, \alpha^0_t)), \dots, (y_\ell, (\alpha_1^\ell, \dots, \alpha_t^\ell))$ **Kan anta:** $q \approx 2^{20}, k << q << \ell << q^t =$ antall mulige verdier. **Finn:** $P(x_1, \dots, x_t)$ slik at $P(a_1^i, \dots, a_t^i) - y_i \in S = \{-\varepsilon, \dots, \varepsilon\}$ (hvor $\varepsilon$ er "small integer"). Vi ser at tidligere så fikk vi "hele kodeboken", men det får vi ikke nå. (Igjen, da kunne du bare interpolert.) **Spørsmål:** Er det kritisk for kvantealgoritmen at vi har akkurat $q$ samples, eller bare gjør det livet lettere? (Litt redd for at det *er* kritisk, siden man skal drive og Fouriertransformere ... urealistisk å få tilgang på $2^{20 \cdot k}$ samples hvis, e.g. (typisk), $k=12$ -> $2^{240}$ samples. Brute-forcing koster også $q^k$ nemlig.) *Hvis* svaret er ja, er det *likevel* noe kult å si om tilfellet hvor du *kan* få tilgang på $q^k$ samples? Hva hvis, la oss si, $q = 2^{20}$, $k=5$, men *nøkkelen* er veldig lang, keyspace $K = F_q^{2k}$. La denne lange nøkkelen være master key, og så beregner du round keys fra key schedule: $K_1, K_2$ etc. Får polynomer $P_{K_1} = \sum g(K_1, \cdot, K_k) \cdot X_i X_j$. Da klarer du ikke bruteforce masterkey (for stor), klarer ikke gjette koeffisientene $g$ (ville kostet $O(q^{q^k})$?) I en sånn, veldig spesialisert case som dette, så kunne noe sånt som denne kvantealgoritmen kanskje enda vært interessant ... *selv* om du må ha $q^k$ samples? *Hvis* vi finner noen kule resultater rundt dette så kunne det vært verdt å skrive om også, *selv* om koblingen til brukbar krypto blir litt tvilsom. **Ok, tilbake til Rubato.** Trenger kanskje ikke finne så *mange* koeffisienter av $P$ før du er good. Note: $\alpha_i$ er en nonce, og $y_i$ er keystream (som du xor-er med plaintekst for å lage ciphertext; dette er en stream cipher). **Spørsmål fra meg:** Kan du omforme ethvert multivariat problem til et *større* univariat problem? Svar: $F_q[x_1, \dots, x_t]$ er (vektorroms-)isomorf til $F_{q^t}$. Så e.g.hvis du har et multivariat polynom $f$ av *homogen* grad 2 (dvs du tillater ikke ting av grad 1), så kan du omforme denne til $F(X) = \sum_i a_i X^{q^{i_1} + q^{i_2}}$. E.g. for $q = 2$, så får du $a X^6 + b X^{10} + \dots$. Så graden kan fortsatt være høy. Så du får ikke et polynom med lav grad ... men du *får* noe som er veldig "sparse". Kanskje interessant å utforske denne retningen som et første steg. Annen retning: La (maks) grad være 2, og to variabler; da er mulige polynomer på formen: $a X_1 X_2 + b X_1^2 + c X_2^2 + d X_1 + e X_2 + f$, og du skal finne $a, b, c, d, e, f$. Kan *linearisere*, ![[IMG_9970.jpeg]] og da løse med standard Gaussian elimination, gitt nok samples. Men for å ha en full-rank matrix som lar seg løse må du da ha like mange samples som antall *ledd* i det generelle polynomet (som blir et kombinatorisk høyt tall). Dette er det Rubato-gjengen kaller "base linerization attack" (not to be confused with linear cryptanalysis). Men så er jo spørsmålet, hvis dette er *sparse*, så du ender opp med en sparse matrise, kan man gjøre noe smartere? Hvis $S$ har størrelse 1 er dette problemet "uten støy", og da blir dette lett å løse ... men det er denne $S$-en som tar oss, og det er kanskje der det å gå fra multivariat til univariat representasjon feiler. "Ville vært kult å finne *noe* kvanteaktig, *selv* om det ikke nødvendigvis er direkte kryptoanvendelser ... vi har jo en del frihet; kan være et *matte*paper dette her, og studere problemet for sin egen del, *med* kryptoanvendelser, heller enn et kryptopaper med mattebakgrunn." **"Winterhof-paperet"** tar et mer lattice-basert perspektiv; sannsynligvis koblet til det Rubato-paperet kaller "lattice-angrep". Men *litt* kulturkræsj her kanskje, siden dette er veldig kompleksitetsteoretisk perspektiv, mens lattice-folk i kryptoverden i stor grad baserer seg på heuristikk. I Teorem 1 bruker de Lemma 4 til å si at det eksisterer en polynomtidsalgoritme for problemet ... og hvis man leser Lemma 4, så er dette egentlig bare et statement om at LLL løser CVP med eksponentiell (i dimensjonen) approksimasjonsfaktor. Dette betyr (kanskje) at, dersom vi ønsker oss en heuristikk, så kunne vi prøvd å bare stappe beste heuristikken for CVP inn i det punktet i beviset hvor de anvender Lemma 4, og se hva vi får. Hva sier Rubato-gutta om lattice-angrep? (Latskap, igjen, ifølge Morten; vi kan nok gjøre bedre her også.) "Klarer sikkert å slå resultatene til Winterhoff i *praksis* (heuristisk), om ikke på kompleksitetsteoretiske premisser." ##### [[12024-12-18]] - Problem 5 is univariate. Can we generalize to the multivariate case? - Attacking Rubato directly would be difficult because the number of samples are as big as the field ($q$), which is too large in Rubato. ($q$ is $O(2^{25})$, but the problem is that you have e.g. 16 variables, so you'd get $O(2^{25 \cdot 16})$ possibilities...?) - You get a lot of random (non-chosen) input-output samples - Table 3 of the Rubato paper (p.13) "is annoying to me" (-Morten). The Gröbner-basis and Aroro-Ge attacks look really competitive, 80-bit security etc. *But* this result is due to a very bad analysis. See p.15, error term $\varepsilon_0$ is taken to the power $-n$, where it "should" be taken to the power $-r$ because that's how many samples you're getting. Reason they're doing it is that it's an easier bound to calculate, but the resulting bound is not at all sharp. "It's a laziness that I'm very annyoed by." - It's fine for a first paper, but the problem is that it doesn't invite for cryptanalysis at all. Say we come up with a better attack and it works in $2^{120}$ time—then in order to claim novelty we would *first* have to show that the attack they claim actually sucks. - In that sense, *such an approach is not serving the community.* - We study the problem on it's own terms, *referring to* but not *relying on* Rubato as an application. - "Based on this analysis, we see that Rubato is actually much more secure than previously claimed given the state of the art of cryptanalysis." - We could then propose updated parameters, but with the caveat that this is new research so don't implement with these parameters right away. But reversing what Rubato did, and opening the door again for the community to try to improve on the attacks that we present. - First, we should check for related literature: Has the problem already been studied? See e.g. the papers linked to in the mail: [Noisy Interpolation of Multivariate Sparse Polynomials in Finite Fields](https://link.springer.com/chapter/10.1007/978-3-642-02181-7_18). (Note, we will likely not be looking at *sparse* polynomials.) - [This one](https://people.csail.mit.edu/madhu/papers/1998/venkat-journ.pdf) looks to be more-or-less a classical version of the quantum paper—but Morten gets the impression that they have very few errors, and they treat them as *unwanted* (and thus want as few as possible), while for our applications we actively *use* the errors (and also have this notion of "closeness"). - These suggest there are works that are not taken into account by the Rubato paper. - Quantumly this also seems relevant—again univariate thingy: [Optimization by Decoded Quantum Interferometry](https://arxiv.org/abs/2408.08292). - "If this is a *really* nice paper, it would be to show that there is *some* non-trivial approach for attacking this, by generalizing previous work on univariate stuff, and it would be *really* cool if there were quantum attacks." - There is a connection between univariate things and Reed-Solomon codes that we should learn. - As a general problem, it would make sense to *both* look at what can be done concretely *and* what the best asymptotic complexities we can get would be. - Might even be that we find a polynomial time attack for *limited* parameter ranges (... in which case we should learn from Sean Hallgren and be careful to check whether there is a known classical attack for the same ranges). - Interesting: Morten et al. already did some cryptanalysis on Rubato, see "Subsequent Analysis" on p.6 of the paper. - "Pretty sure" Rubato is the only cipher based on this (kind of) problem, but we should of course double check if anything new has come since 12 022. - Is there a critique to be had that this problem is "not that interesting" due to only being used by one cipher so far? Could answer that by showing how to construct a new symmetric primitive (e.g. digital signatures? Or easier likely: a pseudorandom function) from the same primitive. And then it's easy to argue that you're studying all of these primitives at the same time by analyzing the problem we defined. - "Keep in mind that I have only done the lightest possible literature search." - Morten. A good first start then is to try to find out if this has already been studied (under a different name). - But the Rubato paper did not mention previous work (although we shouldn't give them too much credit for doing a good work analyzing stuff); but looking at the references of the 2009 paper might be good. - Could be something in these for instance (focus on the multivariate ones though): - [Symbolic-numeric sparse interpolation of multivariate polynomials](https://dl.acm.org/doi/abs/10.1145/1145768.1145792?casa_token=3rgWQb6769oAAAAA:tE4607sRFMQFmgoCZGEn1ta2Nw8WmsaiU4WoyGpG0RsZZhUmqc_UozVLcdalwyN46iy_SNX1zLU) - Men: Floating point arithmetic - [Sparse multivariate function recovery from values with noise and outlier errors](https://dl.acm.org/doi/abs/10.1145/2465506.2465524?casa_token=ClOk0gFKoPoAAAAA:0NuIFSZp-qmjtNeefba1Hv6xubAs_g5Ozeapbxyd6mVRllCpd2lbwniVavk6-twG213StCezD1c) - Men: Rational functions - [Sparse interpolation of multivariate rational functions](https://www.sciencedirect.com/science/article/pii/S0304397510006882) - Men: Rational functions - [Multivariate sparse interpolation using randomized Kronecker substitutions](https://dl.acm.org/doi/abs/10.1145/2608628.2608674?casa_token=OV2tF9mp3gEAAAAA:kI-IWnTHABsBrDKuO0sxwRebCrE0J7rFzax9-p_szqEmAhjqTNAaS0fl7N1snGzVA2g41iVjhjU) - Kanskje relevant? - "We shouldn't dismiss them of course, but based on previous experience they might not be as relevant as the title seems to suggest." - *Can* we show that breaking this problem breaks Rubato? - Follow-up question: Can we show the reverse direction? I.e., can we give a *security proof of Rubato* reducing it to this problem? (Morten thinks this is difficult, would need extra assumptions about "the Rubato function behaving generically" or similar. Ideal cipher proof?) - Alternatively, coming up with a new primitive that *can* be proven secure under this assumption would be just as good. - "I think that is going to be difficult, because you want to construct F with very few multiplications, so you can't argue that it is generic." ##### Opprinnelig email fra Morten > Hi Hans and Semira, > > I wanted to give you some more information about the idea we've been talking a briefly about. Our main motivation will be [Rubato](https://eprint.iacr.org/2022/537), which is a stream cipher targeting a specific type of hybrid homomorphic encryption (HHE). In our case, we can view the stream ciper as a function > > $F_q^{t_1} \to F_q^{t_2}$ > $(K,X) \mapsto F(K,X) + e$ >   > where $t_1 > t_2$, $q$ a prime $\approx 2^{25}$, $e$ is a $t_2$-tuple of Gaussian sampled errors, $K = (k_1,...,k_\ell)$ a secret key, $X = (x_1, \dots,x_s)$ a (known) nonce, and $F(K,X)$ can be seen as a polynomial in $K$ and $X$ of relatively low degree (e.g., degree 4 in one of the suggested parameters). As for attack setting, we can sample a bunch of encryptions under the same key $K$, thus we can treat this as an unknown function $F_K(X)$, where $X$ is known, but cannot be chosen by the attacker. > > Since $F_K(X)$ has such a small degree it would – without the error – be easy for the attacker get a lot of samples and recover $F_K$ (and hence $K$) by interpolation or linearization. However, this is made significantly harder with the error. Indeed, this can be viewed as something between an algebraic and lattice-type (i.e., LWE-style) construction. And it's probably a good idea; algebraic attacks are really bad at accounting for these types of errors. On the other hand, lattice attacks aren't really able to take advantage of the of algebraic structure, and the "linearized lattice" dimension given by the degree 4 (or higher) terms in $t_1$ variables is huge. > > So the authors of Rubato argues that combining building blocks from these two worlds is a good thing. And I would agree with them. In fact, I think they've done a pretty poor job with their security analysis, but (unfortunately for us) they have been way overly cautious. From a first glance at Table 3 in their paper, it would seem that the parameters are rather aggressive, with no security margin against (what they call) Gröbner and Arora-Ge attacks. However, these estimates have vastly undershot the real complexities. I haven't run the numbers yet, but I wouldn't be surprised if we're talking hundreds of bits for some of these parameters.  > > I don't think we can break Rubato. But the problem at the core here, a "noisy multivariate interpolation" (NMI?) of recovering some unknown polynomial $F(x_1, \dots,x_s)$ from noisy samples of the form $F(x_1, \dots, x_s) + e$ is interesting. I don't think it has been studied properly before in the literature. In addition to being the natural generalization of other problems, it has a clear application to (a special type of HHE). Rubato being the prime (and indeed only) example, but it's not hard to imagine throwing in another keyed function $F$ here (the designs of which has been hugely popular in recent years, e.g., Pasta and its variants). So launching a proper study of NMI could be cool. An immediate application would be showing that Rubato is much more secure than previously thought. We could also propose some more aggressive variants (using Rubato or other functions). > > A natural place to start would be to improve the accuracy of what the Rubato paper does. However, the really nice results would be if we can come up with better ideas than what they explored. (I guess a likely such outcome would be that we show other attacks are better than the Gröbner/Arora-Ge of Rubato after the adjustment - again, I think the parameters of Rubato seems out of reach). The following article seems, for instance, very relevant for us: https://link.springer.com/chapter/10.1007/978-3-642-02181-7_18.  > > Also, the univariate case has received much more attention. Given the relation between (normal) univariate and multivariate interpolation, we could hope that there is some ideas we can use here. The following seems relevant in that vein: > - https://people.csail.mit.edu/madhu/papers/1998/venkat-journ.pdf > - https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=45c73d5f8d182e8bdddc0aa05989df6471cd6b8c > - https://dl.acm.org/doi/pdf/10.1145/301250.301312 > > It should be mentioned that some of these papers seem to consider the case where an error occurs very infrequently. From what I recall for Rubato, errors aren't necessarily that infrequent, though you can be fairly sure that the error is small (which I'm not sure the above papers take into account).  > > There's also a couple of recent quantum algorithms that dabble into similar things (for the univariate case): > https://arxiv.org/abs/2408.08292 > https://arxiv.org/abs/2411.12553 > > It would be really cool if we can get a quantum algorithm for NMI. However, these two latter algorithms seem to require a lot of samples (q samples in the univariate case - that would be the whole codebook for us). So any generalization of this may be less applicable to our main motivation, unless we can bring this number of samples down. > > I know that's a lot of information. What do you think?