# Tag Info

5

Well, the problem is with logical OR and subtraction (which Pallier can also do), you've got FHE; that is, you can compute any combinatorial function of encrypted (binary) inputs. Here's how it works, you can construct the NAND function: $NAND(x, y) = (Enc(1) - x)\ OR\ (Enc(1) - y)$ If we limit $x$ and $y$ to being either encrypted 0, or encrypted 1, ...

3

The requirement is that your element $g$ is in $\mathbb{Z}_{n^2}^*$ and not in $(\mathbb{Z}_{n}^*)^2$. The set $\mathbb{Z}_{n^2}^*$ is the set of integers smaller than $n^2$ that are relatively prime to $n^2$, i.e., you require an element $g$ from $\mathbb{Z}_{n^2}$ such that $\gcd(g,n^2)=1$. $(\mathbb{Z}_{n}^*)^2$ on the other hand is the set of pairs ...

3

How to know how much space to reserve? There are two ways: Take an implementation of the scheme, encrypt a 32-bit plaintext, and see how long the resulting ciphertext is. This is the simplest approach. Understand the scheme at a conceptual level, and then use your understanding of the algorithm to predict how long the ciphertext will be. Since it sounds ...

2

I may have found an answer (welcoming any comment on whether I missed something) which works, given certain size restrictions on the input $x$ and $y$: Say, party A has Enc(x) and Enc(y): A flips a coin: b in {-1, 1} A computes: $Enc(c) = (Enc(y) Enc(-x))^{b*r} Enc(-r') = Enc(b*r*(y-x)-r')$ where (r, r') are a pair of random obfuscating values such that: ...

2

Let $c$ denote a ciphertext and let $m$ denote a plaintext. To my best knowledge, researchers in cryptography employ "bandwidth" as different meanings, say, ciphertext expansion ($|c|/|m|$) or a number of bits of plaintexts contained in a ciphertext ($|m|$). @owlstead refers "overhead," which is $|c| - |m|$. For example, Joye and Libert (EUROCRYPT 2013, ...

1

Since $p$ and $q$ are primes, the only factors you needs to rule out are those two numbers. Suppose $p$ divides $(p-1)(q-1)$. Then it divides either $p-1$ (clearly not true) or $q-1$. The latter means $q-1 = p \cdot x$, for some $x \ge 2$ (if $x = 1$ either $p$ or $q$ is even, which is only possible if the numbers are 2 and 3). However, then $q \ge 2p+1$, ...

1

In Paillier, the size of ciphertext is about the double of the plaintext. (Might be interesting for you to read: http://courses.engr.illinois.edu/cs598man/fa2011/slides/ac-f11-lect15.pdf‎) For Order-Preserving symmetric Encryption (OPE), check http://www.cc.gatech.edu/~aboldyre/papers/operev.pdf which describes "Choosing the Ciphertext Space Size" on page ...

1

Without anything to compare Paillier, the list will be small but here goes: Pros: Has seen a fair amount of proposed application in the published literature Thanks to #1 there are a number of special constructions (e.g. zero-knowledge proofs) that have been built for Paillier Is additively homomorphic Cons: Lacks small ciphertexts like what you get ...

Only top voted, non community-wiki answers of a minimum length are eligible