# Tag Info

5

The problem is that you're getting an "overflow" of the errors relative to the secret key. We have $10 \bmod 9 = 1$, and $114100 \bmod 9 = 7$, so the "errors" in your ciphertexts are $1$, $1$, and $7$, which are all odd, hence the plaintext bits are $1$ (as desired). When you add the ciphertexts, the errors add correspondingly, so you get a ciphertext with ...

-1

Here is another, very stupid answer. Use discrete logarithms. Have first the participants select some public cyclic group $G$, of order greater than all the secrets, with a generator $g$. Then each one of them, with the secret $x_i$, publishes $g^{x_i}$. (You could also use any OWF, or add some tweak, if needed).

0

It turns out that just like the question linked to in the question, the key needs to be an odd number so that the encrypted number doesn't have the same parity (odd or even-ness) as the plain text value. When it has the same parity, the encryption failed because you can tell exactly what the plaintext bit was! As for why the high bit needs to be set, I'm ...

0

The "omitted part of this upside down algorithm" is like dynamic programming, since it computes node values before getting to the point at which those values will be used. Unlike my original thought, the recursive approach certainly can be better; the canonical example of that would be using their scheme for PIR. $\:$ However, for the application your ...

0

One can do bounded-length "composition of permutations on the ciphertext" by Evaluating Branching Programs on Encrypted Data. Public key length and ciphertext length both scale linearly with the number of permutations. Leveled FHE can evaluate arbitrary-length compositions of permutations, since iterated composition of permutations can be carried out in ...

3

Essentially any IND-CPA-secure lattice-based cryptosystem offers additive homomorphism, up to a predetermined number of operations. I don't know of any IND-CCA1-secure post-quantum candidate that offers any homomorphic property, except Loftus-May-Smart-Vercauteren SAC'11, which is based on a nonstandard "knowledge of error" lattice assumption.

1

There should be plenty of them. Off the top of my head, I'm thinking of the provable secure version of NTRU by Stehlé and Steinfeld [1], which is IND-CPA secure. In this scheme, ciphertexts are of the form: $$c = pk \cdot s + p\cdot e + \operatorname{encode}(m)$$ where $s$ and $e$ are random polynomials, $p$ is a small prime, ...

5

Actually, most of the primitives that are currently believed to be secure FHE methods would appear to be quantum resistant; a partial list would include Craig Gentry's original scheme based on ideal lattices, BGV (based on ring-LWE), and this NTRU-based approach. All three are based on hard problems that are not susceptible to Shor's algorithm.

0

After thinking about it here's what I think. Let me know what you think. First, I generate a random vector of floats and figure out what the dot product is. I then pick one of the elements of the float vector that correspond to a 1 in the binary array (randomly?), and then adjust that value the necessary amount to make the dot product come out to the ...

Top 50 recent answers are included