Timeline for LWE assumption in cryptographic applications
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 3, 2023 at 13:41 | comment | added | Mark Schultz-Wu♦ | @zpeed78 the simple proof follows from noting that for any $g\in G$, the function $f_g:G\to G$ given by $f_g(h)=g+h$ is always a bijection, and injections preserve the uniform distribution on finite sets (it maps elements of probability $p$ to elements of probability $p$, as all elements have probability $p$) | |
| Aug 3, 2023 at 8:33 | comment | added | Zpeed78 | Hi Mark and once again thanks! Regarding 2.) Yes, I'am interested in a more "formal" proof of your statement $\forall m,k\in G: \Pr_{h\sim \mathcal{D}}[h = k] = \Pr_{h\sim\mathcal{D}}[h +m = k]$, I can only imagine that this is true because the group is closed under addition, but why then the probabilities are equal for a distribution on the group I still don't quite see. I would be interested in the mathematical background. | |
| Aug 2, 2023 at 16:44 | comment | added | Mark Schultz-Wu♦ | Searching "one-time pad for groups" though, you see writing like section 2.2 of this, or section 3 of this. The first one says it works for arbitrary groups though, the second one works for abelian groups. Both should include the implicit assumption that the groups are finite (one can get the OTP argument to work in the case of infinite groups, but the variable-length group encodings are a side channel that make it not worth it). | |
| Aug 2, 2023 at 16:39 | comment | added | Mark Schultz-Wu♦ | 1. No, it's something I derived a few years ago for fun, but it doesn't really have any applications (and, once you know the appropriate math, is "obvious"), so isn't really worth trying to write down anywhere. 2.Do you mean the "shift invariant" statement? I'm just writing down a definition of Haar measure for finite groups. 3. I believe so | |
| Aug 2, 2023 at 11:50 | comment | added | Zpeed78 | Hi Mark and thank you very much. 1.) Do you have a reference for your quote, it looks like it comes from a book? 2.) Do you have a "formal" proof for the statement (about probability) in the quote, I could otherwise only argue here with my example and knowing that it is about finite groups modulo (a rather less "formal" proof). 3.) To your calculation in the comment, you use the theorem of the total probability together with the independence thus concretely $\Pr[g + U(G) = x\mid D = g] = \Pr[g + U(G) = x]$, right? | |
| Aug 1, 2023 at 16:25 | comment | added | Mark Schultz-Wu♦ | Second, you have seen that for any fixed value $g$, $g + U(G) = U(G)$, i.e. shifts of the uniform distribution preserve the uniform distribution. Next, for any second distribution $D$ on $G$ (independent of $U(G)$ --- this is key), we can write $\Pr_{g\gets D}[D+U(G) = x] = \sum_{g\in G}\Pr[g + U(G) = x\mid D = g]\Pr[D = g]$. By our aformentioned shift-invariance, we can replace $\Pr[g + U(G) = x]$ with $\Pr[U(G) = x]$, to get that $\Pr[D + U(G) = x] = \Pr[U(G) = x]$, even when the "message" we are applying a uniform shift to is from an arbitrary distribution (independent of our shift) | |
| Aug 1, 2023 at 16:22 | comment | added | Mark Schultz-Wu♦ | @Zpeed78 First, no continuous distributions exist in cryptography. We are computing things, and need to represent everything in finite space. We (in principle) could represent continuous distributions using a variable-length encoding. This will induce side-channels based on the message length. Everything is finite though. | |
| Aug 1, 2023 at 15:24 | comment | added | Zpeed78 | I would like to believe your last sentence. I try it with a "proof", that goes also into the direction of what Daniel wanted to say (?). Let $U = \{0,1,2,3,4\}$ be uniform distribution on the corresponding set, each element is uniform in $\mathbb{Z}_5$. When we add, say, 2 to $U$, we obtain $U + 2 = \{2,3,4,0,1\}$ and this "keeps" the probabilities it is still a uniform distribution on $\mathbb{Z}_5$. My "issue" was to relate this to continuous distributions (there we would have a "shift" of the uniform distribution). | |
| Jul 31, 2023 at 18:59 | history | answered | Mark Schultz-Wu♦ | CC BY-SA 4.0 |