Tag Info

Hot answers tagged

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


5

No, it is not possible to compute $\lambda$ easily. Specifically, if you have a black box that, given a random instance $c$, $c^\lambda \bmod n^2$, was able to recover $\lambda$ with nontrivial probability, you can use that to factor $n$ with nontrivial probability. Hence, if we believe the factorization problem is hard, we must also believe that this ...


5

Yes (and always). Given $\mathsf{Enc}(a)$ and $b$, you can compute $\mathsf{Enc}(a \cdot b^{-1} \bmod{n})$ by simply computing $\hat{b}=b^{-1} \bmod{n}$ and $Enc(a)^\hat{b} \bmod{n^2}$. Paillier encryption is built on the bijeective mapping from $(x,y)\in \mathbb{Z}_n \times \mathbb{Z}_n^*$ to: $E_{g,n}(x,y)=g^x y^n \bmod{n^2}$. Generator $g$ is chosen ...


4

No, exactly equal length of primes $p$ and $q$ is not mandatory for security (or proper functioning) in the Pailler cryptosystem. Sufficient requirements are that $p$ and $q$ are prime, $N=p q$ is hard to factor, and $\gcd(p q,(p-1)(q-1))=1$. The requirement that $p$ and $q$ are of exactly equal size is usually made in the Pailler cryptosystem because this ...


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


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

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


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, as you note, multiplication in the ciphertext domain translates to addition in the plaintext domain. Thanks to the algebraic structure behind Paillier what you can do to get subtraction is use the multiplicative. This works fine when the result is positive. When the result is negative, however, you would like to return that value, but what ...


1

In your question, you already pointed out, that the necessary condition is More generally largest prime minus one does not consists of smallest prime as a prime factor therefore, it is sufficient to just check if $p$ divides $q-1$ by computing division. You can just verify this condition during the key generation. I don't know of a more efficient ...


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


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


1

Easy solution is to use a large $r$. You are correct that if the $r$'s were small primes we would have a problem, ergo randomness is essential. However, if the $r$'s are generated randomly then their product doesn't help in guessing one. (Think about guessing $x,y$ random given $x+y$ in an abelian group).


1

Revealing $r$ would then allow the verifier to prove to someone else (another verifier) that $c$ encodes $i$. The verifier could also prove other things knowing $r$ to a different verifier (any other proof using a paillier ciphertext, the corresponding plaintext, and the random value $r$). With the ZKP, the verifier cannot prove anything to anyone else ...


1

In general, no. There are, however, specific conditions that, when met, make it possible. Working Mod $\phi(N^2)$ If given $D^{-1} \bmod{\phi(N^2)}$, then $\mathcal{E}(M/D)$ can be computed. So the question remains, when is computing $D^{-1} \bmod{\phi(N^2)}$ possible? It is only possible if $gcd(D, \phi(N^2))=1$. Note that $\phi(N^2)=N\cdot ...


1

Yes. $r^n$ needs to be coprime with $n^2$. The only elements which have don't an inverse modulo $p^2 q^2$ are all multiples of $p$ and all multiples of $q$, so we just require $\gcd{(r^n, p)} = \gcd{(r^n, q)} = 1$. $\implies \gcd{(r^n, n}) = 1$ Clearly, if $r$ is coprime to $n$, then $r \times r \times \cdots \times r ~ (n ~ \mathrm{times})$ will also be ...


1

Let us briefly recall the Paillier encryption. Let $k_{pub} = (N = PQ, g)$ be a public key, where $N$ is the RSA modulus. The secret key is $\lambda = \mathrm{lcm}(P-1,Q-1)$ (or $P,Q$). The encryption of $p \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_N^*$ is $C = g^p r^N \bmod{N^2}$. You can verify $\mathbb{Z}_{N^2}^* \simeq \mathbb{Z}_N \times ...


1

One alternative that hasn't been mentioned, which may possibly be of interest, is doing plain old integer division in Paillier. The protocol is non-trivial, but, perhaps surprisingly, can be done somewhat efficiently. There was a paper at FC12: On Secure Two-party Integer Division [PDF]


1

I'm doing this as another answer since my first answer was incorrect. Your calculation of s2 is incorrect. In python I did it as s2 = pow(m*pow(inverse(G,N),s1,N), inverse(N,Lambda), N) Mathematically it would be $((G^{-1})^{s1}\bmod{N})$ for the term $G^{-s1}$ or equivalently $(G^{s1})^{-1}\bmod{N}$. In words, the inverse of $G$ (modulo $N$) raised to ...



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