Tag Info

3

The expression $c' = \lfloor w^{-i} c \rfloor$ is a slight abuse of notation. What it technically means is to interpret each coefficient of $c$ as real number, divide by $w^i$, round the result to the nearest integer, and then interpret it as an element of $\mathbb{Z}_q$ again. This is equivalent to expressing each $\mathbb{Z}_q$ coefficient of the ...

3

The SV scheme made some significant simplifications that turned out to hurt security. Specifically, it's known how to break the scheme in subexponential time (roughly $2^{n^{2/3}}$) in the dimension $n$ of the lattice defined by the public key. Moreover, it's known that the scheme can be broken in polynomial time by a quantum computer. In short, the ...

0

This scheme is additively homomorphic and supports one multiplication. So if you multiply the ciphertext with itself you can get a square. I don't know if it helps.

7

While @j.p. is correct that the scale-invariant scheme encodes the plaintext a bit differently than in other FHE schemes, this is mostly just a syntactic point that doesn't really get to the heart of scale invariance. (Indeed, it is easy to switch between the two encodings of the plaintext, simply by multiplying the ciphertext by an appropriate scalar. See ...

3

As poncho comments, a homomorphic encryption scheme that only supports the XOR operation would not be fully homomorphic, i.e., it would not allow evaluation of all functions. However, you can try to optimize the implementation of a function in order to minimize the number of AND's at the cost of extra XOR's. This is not only relevant for FHE but also in ...

1

What's the point to build a cheap NAND gate ? Because it's a complete operation; you can build any circuit with a sufficiently large pile of them. Maybe to build cheaper AND and OR gates based on this NAND gate and then follow the approach of Regev's type cryptosystems? You could build AND and OR gates with them (and INVERT; AND and OR by ...

6

Let me try to answer your second question, and hopefully shed some light on the first one in doing so. When we encrypt a message, it's because we want to keep something about that message secret. But what is it that we actually want to protect? Let's say the message we're encrypting is AGENT DOE REPORTS 23 UNITS ON BOARD SHIP TO BASE ALPHA, DEPARTED ON ...

Top 50 recent answers are included