# Tag Info

6

In "I take 3072 for Paillier's $n$", 3072 is surely the bit size of $n$. Thus I'll read the question as: How wide should be OU's $n=p^2q$ to be as safe as Paillier's $n=pq$ of 3072 bits? The best known attack against both cryptosystems is the factorization of $n$. The best known factorization method for $n=pq$ with $p$ and $q$ random primes of ...

5

TLDR: The size of the group/ring is dictated by the fastest currently-known attack (as explained in this Wikipedia article). Details. For the case of discrete-log in $\mathbb{Z}_p^*$ and factoring $\mathbb{Z}_N^*$, the fastest currently-known algorithm is the general number field sieve (GNFS). GNFS has a run-time of (roughly) $L_n(1/3,2)$, where L_n(\alpha,...

4

If we choose $n$ to be the product of two strong primes $p=2r+1$ and $q=2s+1$ with $r$ and $s$ prime, note that $p$ and $q$ are 3 mod 4 and that $\mathrm{LCM}(p-1,q-1)=2rs$. Choosing a random $a$ and raising it to the power $2n$ gives an element of order $\lambda/2=rs$ (there is a vanishingly small chance of getting order $r$, $s$ or $1$) and which is ...

3

Yes, it is often necessary to consider overflows in Paillier encryption. The reason is simple: even though in most situations, the values are supposed to be way too small to cause any overflow issue, what does prevent malicious users to cause overflows in order to cheat? Without a specific scenario, it is hard to be more precise, but there are many ...

3

In the most common variant of Paillier encryption with public modulus $n$, any plaintext in $[0,n)$ can be encrypted and decrypted (though sometime the interval is slightly reduced, or centered on zero). To be secure, Pailler encryption needs $n$ to have unknown factorization. That means like at least 1024-bit $n$ (with 2048-bit or more highly recommendable)....

2

Goldwasser Micali encrypts a 0 by sending a quadratic residue and a 1 by sending a non-quadratic residue. So, to prove that the encrypted bit is 0 what you need is a zero-knowledge proof of quadratic residuosity: for a given $b,N$, does there exist an $a$ such that $a^2 = y \bmod N$. There exist such proofs, and it should be easy to find online. However, for ...

2

Stream Ciphers A stream cipher produces key streams usually small sizes as bits (or bytes or words,...) that are x-ored with the message bits to produce the encrypted stream ( or call it the ciphertext). A stream cipher stores an internal state and updates it for the next output. They are also called state ciphers since the encryption depends on not only key ...

2

You need to know The size $s$ of the public modulus $n$ in bits. The number $c$ of cryptograms. If the code uses the CRT, or not; and in the affirmative, the number $k$ of prime factors in $n$ (usually $k=2$ for $n=p\,q$, with $p$ and $q$ distinct primes). And of course, some benchmark of the code and hardware! Each cryptogram is $2s$-bit, thus for 4kbyte ...

2

Is it yet proofed that Paillier is secure against chosen-ciphertext attack. The original Paillier paper mentions that it is not. It is indeed not - CCA security is incompatible with the property of partially homomorphic encryption. If we have a ciphertext $C$ and an Oracle that will decrypt any ciphertext (other than $C$), what an attacker can do to decrypt ...

1

Paillier is a CPA-secure cipher, thus anything we can deduce from ciphertexts requires the private key. Thus "I want to find…" requires that "I" has the private key, and then "I have an encrypted array" implies "I" can decipher each of the ciphertexts, which makes the question as stated moot. We'll therefore change the ...

1

Semantic security in that setting reduces to semantic security for the standard scheme if and only if a certain low-entropy distribution in the “zero ciphertext” subgroup is computationally indistinguishable from random. In the case of ElGamal, the assumption is that $(g^r, h^r)$ for random small $r$ is computationally indistinguishable from a standard DH ...

1

Each algorithm's n-bit security is calculated via "best attack method". For example RSA is based on factorization problem and it can be solved with "Number Field Sieve" algorithm, so we use NFS's "calculation complexity" to determine RSA's n-bit security level. For cryptographic hash functions we use "birthday attack" ...

1

So in general ElGamal encryption is only homomorphic wrt. multiplication. However with a few tweeks one can transform ElGamal to exponential ElGamal (and I guess that is what you are referring to). The main difference between ElGamal and exponential ElGamal is that instead of a message: $m$ you have to encrypt $g^{m}$. On decryption that means that one has ...

1

In standard Paillier encryption Property 1 really is: $m_1=D(c_1)\text{ and }m_2=D(c_2)\implies D(c_1\cdot c_2\bmod n^2) = m_1+m_2\bmod n$. Property 2 does not hold (but see final off-topic note). As a consequence of property 1, for all $k$ in $\mathbb Z$, it holds $D({c_1}^k\bmod n^2)\ =\ m_1\cdot k\bmod n$. Proof for positive $k$ can be by induction, ...

1

First, we simplify $\mu$. \begin{align*} g &= (1+n)^{\alpha}\beta^{n} \bmod n^{2} \\ g^{\lambda} &= (1+n)^{\alpha\lambda}\beta^{n\lambda}\bmod n \\ &= (1+n)^{\alpha\lambda}\bmod n^{2} \\ &= (1+n\alpha\lambda)\bmod n^{2} \\ L(g^{\lambda}\bmod n^{2}) &= (\alpha\lambda)\bmod n^{2} \end{align*} Then, let's take a look at \$...

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