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

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 ...

3

You probably don't need to re-encrypt using the Paillier crypto system. 1) Alice encrypts $c_1=g^{m_1} r_1^n$ und $c_2=g^{m_2} r_2^n$ and computes $r_3=r_1 \cdot r_2$ and $m_3=m_1+m_2$, then sends $c_1$, $c_2$, $m_3$ and $r_3$ to Bob 2) Bob computes $c_3=c_1 \cdot c_2=g^{m_3} r_3^n$ - If the homomorphically computed sum matches the re-encryption Bob will ...

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

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 ...

1

Yes. This can be solved through standard methods. Alice can prove she decrypted the ciphertext correctly by revealing the decrypted message and the random coins that would be used in encryption to obtain this ciphertext from this message. Suppose we have a ciphertext $c$, and Alice decrypts it to obtain the message $m$. It follows that \$c = g^m r^n \bmod ...

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