j.p.
Reputation
583
Top tag
Next privilege 1,000 Rep.
 Apr 14 comment Confusion about definition of homomorphic encryption You surely know that $e^{x+y} = e^x\cdot e^y$. If you take $x\mapsto e^x$ as "encryption", then the first citation says that addition on the "plaintexts" $x$ and $y$ corresponds to the multiplication of the "ciphertexts" $e^x$ and $e^y$. The second citation says that multiplication is an oracle that returns given $e^x$ and $e^y$ the encryption of the result of the operation addition applied to the two plain texts, which is just the equation you hopefully know. Dec 4 comment Could Riemann hypothesis solve certainly RSA? People that say "Riemann hypothesis could break RSA" do not know what they are talking about. Dec 4 comment Is there any opensource white-box implementation of AES or DES? @user29587: The AES implementation you link to is not a white-box implementation? Dec 2 comment How can I factorize a 350 bit (106 decimal digits) number in two prime factors? You can take also a look at Factoring as a Service. On page 2 of their paper they link to their github repository containing their code. Nov 16 comment Generating random vector for Full Homomorphic Cryptography @AlanWolfe: The two blog posts didn't help me much either. Are you interested in a particular FHE scheme or are you fine with learning any of them? Then you could take a look at Homomorphic Evaluation of the AES Circuit. Just skip the pieces about AES, and you have a nice introduction to BGV. Nov 12 comment How do I check if the secret key polynomial of the ATV-FHE (NTRU based) scheme is invertible? Your 2nd "option" to select the secret key is not an option at all. It is part of the security proof, in which one assumption "$h=2gf^{(-1)}$ with $f, g$ Gaussian and $f$ secret" is replace by another assumption "$h'$ is uniformly sampled". Distinguishing $h$ from $h'$ is the DSPR-problem, and it's assumed to be hard. Nov 10 comment Generating random vector for Full Homomorphic Cryptography @AlanWolfe: As mentioned at the end of the first part the cited blog post is about an FHE scheme by Zvika Brakerski (which is - relatively seen - much more practical than Gentry's original proposal). Nov 6 comment What is scale-invariance notion of a fully homomorphic encryption scheme? OK, thanks, I see where I'm wrong. I just scanned the beginning of the paper and got the wrong idea from looking at page 872 and not looking what's going on later. I thought it is a non-ring version of FV. All my comments were referring to scale-invariant and non-scale-invariant versions of the same FHE (like FV vs. BGV or YASHE vs. NTRU), not about comparing completely different systems. Nov 6 comment What is scale-invariance notion of a fully homomorphic encryption scheme? After looking at Brakerski's Crypto'12 paper I do not understand your last comment. My understanding is that if the system is ring-based you multiply polynomials, if not you take a tensor product of vectors. The difference between scale-invariant or not is only which error term grows most by multiplying. For scale-invariant this term is bounded by the norm of the secret key, so you do bit-decomposition to get it dependent on $n$ instead of $q$. For BGV a similar error term depending on the ciphertext shows up, when trying to switch back to the original key, and is handled accordingly. Nov 6 comment What is scale-invariance notion of a fully homomorphic encryption scheme? Thanks for answering my comment. I do not understand why write that multiplication is quite different. (I'm starting to get comfy with BGV, and my knowledge if FV is just its formulas next to BGV's in ia.cr/2015/889.) To me the formulas for multiplication and SwitchKey of BGV and FV look very much alike. I'll try to understand the differences over the weekend. (I've read the blog post before, but even rereading it didn't help much. Splitting the operation in Multiplication with a result in a different key format and then SwitchKey is easier to grasp for me.) Nov 6 comment What is scale-invariance notion of a fully homomorphic encryption scheme? Thanks for the nice explanation! Looking at the formulas of BGV and its scale-invariant version FV I wonder what makes the latter system scale-invariant. Do I understand it correctly that this effect is caused exclusively by moving the plaintext info from the bottom to the top by multiplying the scalar (and adapting the formulas)? Can one interpret this also as switching from working in $\mathbb{Z}$ (modulo a big number) to working in $\mathbb{Q}/\mathbb{Z}$ (times a big number) which frees one from looking at two different kind of errors (relative vs. absolute)? Or is my understanding wrong? Nov 5 awarded Good Answer Nov 5 comment What is scale-invariance notion of a fully homomorphic encryption scheme? Rereading my comment I realize that I should have mentioned that the modulus switching operation is also called scaling. Nov 5 comment What is scale-invariance notion of a fully homomorphic encryption scheme? The difference between BGV and its scale invariant version FV is where the plaintext is hidden in the scalar product between ciphertext and secret key: Normally you can recover it by reducing mod $p$ ($p$ being the plaintext modulus). For FV you have to multiply with $p/q$ and round to integer instead ($q$ being the ciphertext modulus). Functionally you do not need to do the modulus switching for the scale invariant version to keep the noise level down (but you might do it anyway for efficiency). For comparison between the systems look also at ia.cr/2015/889. Nov 3 comment What is the bound for the probability distribution for ATV-FHE scheme? The last third of the paper (Appendix E.6) are just tables describing the parameters for various number of levels and plaintext moduli. No need to read the rest if you travel "on the low road". Nov 2 comment What is the bound for the probability distribution for ATV-FHE scheme? As I already commented to another question from you, the easiest way to obtain parameters for ATV=LTV is Which Ring Based Somewhat Homomorphic Encryption Scheme is Best? by Ana Costache and Nigel Smart. They call the scheme NTRU. Oct 29 comment How to test a FHE implementation? Take a look at the paper Which Ring Based Somewhat Homomorphic Encryption Scheme is Best? by Ana Costache and Nigel Smart. They show how to derive secure parameters for four different FHE schemes, two of them being based on NTRU. For the security of the underlying LWE problem you can use the online LWE security estimation tool by Lauren De Meyer. Oct 29 comment How to use this homNAND gate? The main point of the paper is to show that bootstrapping per se doesn't require the high latency (at least few minutes for a packed ciphertext) seen in all implementations before, therefore giving hope that other systems might become more practical, too. By the way, Gentry-Halevi ([17] in the paper you linked) still needed 1/2 hour for bootstrapping a single bit in 2011. Oct 22 comment Galois Field ($2^{16}$) for encryption in place of $GF(2^8)$ in AES Looking at the evaluation criteria of the AES competition, one sees that the algorithm should be efficiently implementable on different platforms including 8-bit platforms (for smart cards). Using a field of size $2^{16}$ and therefore tables of size 128kB would have killed the Rijndael as AES-candidate. Oct 15 comment Data Switching and Information Leakage If $w=0$ then $c=a$, but no information about $-z$ and hence $x$ is given by knowing $c$. Otherwise $w\ne 0$ allows you to write $a = c+zw$ as well as $z=w^{-1}(a-c)$ showing that there is a one-to-one correspondence between $a$ and $z$ for any choice of $c$ and $w(\ne 0)$. This is consistent with the fact that both $z$ and $a$ are drawn uniformly from $\mathbb{F}_p$. I do not know now, how to finish the proof that the server learns nothing about $x$, but it should follow from the one-to-one correspondence between $z$ and $a$.