# Questions tagged [paillier]

A public-key cryptosystem invented by Pascal Paillier in 1999.

155 questions
Filter by
Sorted by
Tagged with
1 vote
18 views

### Paillier cryptosystem for verifiable shuffles

I am looking for some algorithm or implementation on Pailler cryptosystem-based verifiable shuffles for mixNet. So far, all the verifiable shuffles and mixNet are available for ElGamal cryptosystems ...
• 31
33 views

### How to prove an RSA ciphertext matches a Paillier ciphertext?

Suppose I know an RSA public key $(n,e)$ and I create two ciphertexts: An RSA ciphertext $C_1 = m^e \mod n$ and a Paillier ciphertext $C_2 = g^m \cdot r^n \mod n^2$. Is there a known efficient method ...
• 166
1 vote
33 views

### Is it possible to use Batching with any of the Partial Homomorphic Cryptosystems?

I'm familiar with the concept of batching in the context of (Fully) Homomorphic Encryption - whereby many values can be encrypted as a single ciphertext and operated on simultaneously in an SIMD/...
• 177
1 vote
56 views

### Additive Homomorphic Encryption scheme with very small ciphertext size

I'm looking for a Additive Homomorphic Encryption scheme which can allow a ciphertext of size smaller than 128 bit. I started studying this topic very recently so I don't have much knowledge, but I ...
27 views

### can I get individual data by paillier decryption if we send aggregated encrypted data?

suppose there are different user data for n Smart meters. we encrypt all the individual data and then add them together. After decrypting the summation, how can we retrieve the original data? We are ...
1 vote
57 views

### Working with Paillier and ECDSA - Order issue

I'm trying to implement two party computation for ECDSA signing using Paillier cryptosystem. But my problem is that the order of Paillier is different from the order of the curve (secp256k1 in my case)...
• 113
92 views

### Is the discrete log in general hard in Paillier groups?

https://en.wikipedia.org/wiki/Paillier_cryptosystem Paillier cryptosystem exploits the fact that certain discrete logarithms can be computed easily. If I were to select $g \in \mathbb{Z}_{n^2}^*$ ...
1 vote
29 views

### Internal direct product of group of invertible elements in a Paillier modulus

Let $p$ and $q$ are Sophie-Germain primes such that $p=2p'+1$ and $q=2q'+1$. Also let $n=pq$ and $n'=p'q'$. In Section 8.2.1 of this paper, the internal direct product of $\mathbb{Z}_{n^2}^*$ is shown ...
• 115
108 views

### How to prove that paillier encryption is positive (zero-knowledge)?

Is it possible that the plaintext encrypted in a ciphertext using paillier encryption is positive without using a zero knowledge range proof?
63 views

### Is this a safe zero knowledge proof that two paillier encryptions are equal?

We have encryptions $c_1$ and $c_2$, the person who knows the plaintext and randomness in both wants to prove that they know it. Let $r_1$ and $r_2$ be the randomness values in $c_1$ and $c_2$ ...
38 views

### In paillier homomorphism, how is the randomness r changed during addition?

Two add the plaintexts encrypted in a ciphertext, you would just multiply the ciphertext and modulo it. However, how does the randomness value of the new ciphertext change? Assuming you the encryptor ...
56 views

### Why is asked that gcd(pq,(p-1)(q-1))=1 in the Paillier encryption scheme?

I don't see this property $\gcd(p\,q,(p-1)(q-1))=1$ used in the scheme. And in Paillier's original paper, I don't find this requirement. Is it required just for the difficulty of factoring $n$? Or is ...
• 103
39 views

### Searching in Paillier Cryptosystem

I have implemented Paillier Cryptosystem. Lets say, I have an encrypted array E(x) = [2,4,5,10,0,20] and I want to find that if 0 exist in that array. Due to the limitations of Paillier cryptosystem I ...
1 vote
52 views

### Short randomness in ElGamal and Paillier

In the Paillier cryptosystem the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$. My question is, what if short (E.g. 512bits) $r$ is used? ...
• 77
1 vote
38 views

### Generation of the order $\lambda$ (which is lcm((p-1),(q-1))) element g in modified paillier, why $-a^{2n}$?

As the question states, in variants of paillier cryptosystem, such as CS01 and DT-PKC, when they want an element $g$ of order $\lambda$, they choose a random number $a$ from group $Z^*_{n^2}$ and ...
• 73
1 vote
110 views

### Do we need to consider overflow in paillier encryption?

Homomorphic multiplication of plaintexts in Paillier cryptosystem can be constructed as follow: Dsk(E(x1)^x2 mod N^2) = x1x2 mod N. So after the decryption, we get the result of multiplication x1x2. ...
• 73
112 views

### $n=pq$ and $n=p^2q$. How to take the value of two $n$ is the same in security

For example, Paillier's RSA modulus is $n=pq$, but OU's RSA modulus is $p^2q$. I think when two $n$ are the same, the security of the two cryptographic schemes must be different. So for example, if I ...
285 views

### How to calculate the n in n-bit security of a crypto algorithm?

I think I'm likely missing the term because searching for this is coming up with not so precise results. I'm looking to calculate the n-bit security of say Paillier vs ElGamal vs EC ElGamal, when I ...
• 155
195 views

### Paillier versus Lifted ElGamal for homomorphic addition for e-voting

I'm looking to create an anonymous e-Voting system which will assign a certain number of bits to each candidate during a vote, e.g. 010000 for Alice, 000100 for Bob, and 000001 for Charlie. It works ...
• 155
1 vote
60 views

### Encrypting full word using Paillier Scheme

I am using Paillier scheme to encrypt a message however, I have divided the words into alphabets and then convert each alphabet to ASCII code encrypting the final result. It works fine, but I want to ...
51 views

### How to know the exact result in Paillier cheaper-constant multiplication

The encryption function $E_{k^+}: Z_n \rightarrow Z_{n^2}$. The decryption function $D_{k^-}: Z_{n^2} \rightarrow Z_n$. $m_1 = 42, k = 15, n=77$. After encryption, exponentiation and decryption, I get:...
1 vote
138 views

### What is the difference between Paillier additive homomorphic property and addition of two paillier ciphers

Paillier has additive homomorphic property that states: if two ciphers c1 and c2, are multiplied, and the result is decrypted, it is equal to addition of the two plaintexts. D(c1*c2)= m1+m2 ...
• 31
1 vote
88 views

### How to prove correct decryption in Goldwasser-Micali cryptosystem

In How to prove correct decryption in Paillier cryptosystem, it was asked whether Alice (in sole possession of the secret key) can convince Bob that a given plaintext is the decryption of a ciphertext ...
• 11
66 views

### Optimisation of Pailler decryption

In this article applying Pailler encryption and decryption to image bitmaps, Table II is reported to give Execution Time (sec) of the Paillier encryption/decryption of image using different key sizes ...
• 126k
97 views

### Paillier scheme : Encoding floats into integers impact on computations

In Privacy Preserving Processing Over Encrypted Images, I could understand that appropriate encoding of floats into integers (required in Paillier) only incur negligible error in computations. Any ...
• 65
1 vote
102 views

### Is Paillier a stream or block encryption

Does Paillier follow a stream encryption or block encryption technique. If it’s a block encryption then what is the size of the block in bits or bytes.
• 31
153 views

### Efficiently prove the correctness of Paillier encryption in or "outside" a zk-SNARK

I'm working with a zk-SNARK library  that allows me to prove the correctness of arbitrary arithmetic circuits, and I now want to use these zk-SNARKs to prove that some Paillier  ciphertext $c$ ...
• 21
82 views

### Evaluate the time of Paillier decryption

If I have 4 kilobytes of Paillier encrypted data, how can I know the time needed to decrypt it?
• 31
1 vote
280 views

### Security of Paillier against chosen ciphertext attack

Is there a proof by now that Paillier is secure against chosen-ciphertext attack? The original Paillier paper mentions that it is not.
• 31
1 vote
168 views

1 vote
148 views

### Paillier's Cryptosystem - Homomorphism

I'm lacking quite some mathematical knowledge here, but could anyone please explain to me why the Paillier cryptosystem is still (additive/multiplicative) homomorphic despite introducing a random ...
• 11