# Questions tagged [paillier]

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

113 questions
Filter by
Sorted by
Tagged with
8k views

### What are some disadvantages of homomorphic encryption schemes?

I'm doing some self-teaching / research for my own benefit in homomorphic cryptography. I've studied both additive and multiplicative schemes (Paillier and RSA respectively), but all I can seem to ...
2k views

### Division in paillier cryptosystem

Is division possible in the Paillier Cryptosystem? i.e. given a the cipher-text $C$ of an integer $M$ the plain-text divisor $D$, and only the public key, can one compute the cipher-text of $M/D$ ?
4k views

### Homomorphic (encrypted) comparison to an integer

When working with an additive homomorphic encryption scheme (say Pallier's), is there an efficient way to get the encrypted value of a comparison test to an integer value (I realise that an ...
3k views

### Paillier can add and multiply, why is it only partially homomorphic?

I've seen that it's widely accepted that before Gentry's breakthrough (which is not practical yet) in 2009 there were no known full homomorphic encryption scheme. I've read here in another answer ...
928 views

### Paillier Homomorphic encryption to calculate the means

Paillier Homomorphic encryption supports addition and multiplication with plaintext value. Can I use these properties to calculate the means of cipher-text values? I try to use the following steps: ...
409 views

### Equality checking using additive homomorphic encryption

Given two ciphertexts $c_1 = enc(p_1)$ and $c_2= enc(p_2)$ using any additive homomorphic encryption scheme (or specifically Paillier). Can we find out whether the underlying plaintexts $p_1,p_2$ ...
255 views

### What if the p and q used in keys generation of Pailler cryptosystem are composite?

I've seen a few implementations of Paillier cryptosystem that uses probable primes to choose $p$ and $q$. Assuming that a keypair is generated with $p$ and $q$ that are coprime and that $pq$ is ...
396 views

### SPDZ for the 2-party case

There exist protocols for 2-party computation e.g., GMW that use Boolean circuits. I could also use Paillier and arithmetic circuits for a 2 party computation. However after reading about SPDZ is my ...
2k views

### How to select $g$ in Paillier Cryptosystem

For my cryptography class project in university I have selected Paillier Cryptosystem as a course project http://en.wikipedia.org/wiki/Paillier_cryptosystem#...
188 views

### Making Pascal Paillier' output absolute

Can we make subtraction result of cipher texts encrypted by Pascal Paillier absolute. Just like we use method Math.abs() in Java ? For example, if we subtract 0 from 1: 1-0 = 1, it is positive but 0-1 ...
556 views

### Showing the decrypted sum of encrypted values

Is there a system that would allow to encrypt values with one or more keys, sum the encrypted values, and reveal a key which could only decrypt the sum. Essentially would be able to show encrypted ...
804 views

### Zero-knowledge proof for the product of additive Paillier ciphers

Suppose that Alice received the cipher values: $E(x_1), E(x_2), ..., E(x_n)$ that are encrypted using Paillier cryptosystem by $n$ entities with Bob's public key. Alice computes $E(\sum x_i)$ from ...
290 views

### Usefulness of Damgård–Jurik

I am trying to understand what are the benefits of using Damgård–Jurik over Paillier. I understand that expansion factor decreases as s increases. But isn't it the ...
2k views

### Why is Paillier Cryptosystem called probabilistic?

The definition of Paillier Cryptosystem says that it is a probabilistic asymmetric key algorithm for public key cryptography. Can some body explain why it is called "probabilistic"?
145 views

### Paillier paper: Number Theoretic Lemma doesn't seem to work

I'm reading the original Paillier paper. I've reached Lemma 3: If the order of $g$ is a nonzero multiple of $n$, then $\varepsilon_g(x,y) = g^x y^n \mod n^2$ is a bijection, where $x \in \mathbb{Z}_n$...
447 views

### Logical OR operation in a homomorphic additive cryptosystem

Suppose we have a cryptosystem homomorphic for addition (say Paillier's). Is there a way to perform a logical OR operation between two binary values (with a binary result). We can, of course, obtain ...
104 views

### Prove that some Cyphertext C encrypts some plaintext D

I have a Paillier Cyphertext C and a counterparty that controls the keypair that was used to encrypt the data D to arrive at C. How can they prove to me that the Cyphertext C is actually the ...
667 views

### Calculating ciphersize of Paillier, SSE and OPE

If I have to encrypt a 32 bit plaintext in each of Paillier, SSE and OPE, how can I make an estimate of the ciphertext sizes respectively in order to reserve the amount of space in a database?
243 views

936 views

### Are Paillier and El Gamal encryption schemes secure against quantum attacks?

I was wondering if there is a security difference between Lattice based homomorphic encryption schemes versus an partially homomorphic encryption scheme like Paillier, and El Gamal encryption schemes ...
662 views

### Does Paillier Homomorphic Encryption Work only with numbers?

Paillier homomorphic encryption enables us to combine two messages such as $D\left(E(m_1,r_1) \cdot E(m_2,r_2) \mod n^2\right) = m_1+m_2 \mod n$ My question is what are the specification of $m_1$ ...
214 views

### How hard are discrete logarithms problems in $\mathbb Z^{*}_{n}$ and $\mathbb Z^{*}_{n^2}$, where $n$ is the RSA $n=pq$

Use the notations form the Wikipedia article Paillier Cryptosystem , assume that the chipertext $c$ and $c^{\lambda} \mod n^2$ are both given, is it possible to compute $\lambda$ easily?
1k views

### How to prove correct decryption in Paillier cryptosystem

Bob sends a ciphertext obtained by Paillier encryption to Alice. Alice has the private key. She decrypts the ciphertext and returns the plaintext to Bob. How can Alice convince Bob that the ...
136 views

### How to calculate Enc(-m) from Enc(m) in Paillier cryptosystem?

The encryption in Paillier cryptosystem is like this according to Wikipedia: Let $m$ be a message to be encrypted where $m \in \mathbb{Z}_n$ Select random $r$ where $r \in \mathbb{Z}_n^*$ Compute ...
590 views

### Paillier Cryptosystem - Practical applications?

I wonder: are there any real-world practical applications using the Paillier cryptosystem , as introduced in , or some derivations of it? I'm aware of quite a few schemes proposed in literature ...
331 views

### Does the Paillier system remain secure if it is used to encrypt only binary values, i.e. {0, 1}?

Is there any security compromises if the Paillier system was used to encrypt only binary message in {0, 1}? i.e., plaintexts are either 0 or 1.
111 views

### Zero-knowledge proof for Paillier parameters

For RSA one can give a non-interactive zero-knowledge proof that RSA with parameters $(e,N)$ form a permutation and a proof of knowledge of the associated RSA secret key. For example, such a proof can ...
177 views

### How to compute Lambda in a Threshold Paillier scheme

I am evaluating a threshold Paillier scheme as described in the paper: Ivan Damgard, Mads Jurik, Jesper Buus Nielsen, "A Generalization of Paillier’s Public-Key System with Applications to Electronic ...
354 views

### identifying presence of encryption of zero in additive homomorphic encryption

Lets say the server has corpus of ciphertext contains $enc(a),enc(b),enc(c), \dotsc enc(x)$. The encryption function is an additive homomorphic scheme (like Paillier). The server knows only the public ...
415 views

### Paillier cryptosystem preserve ordering of sums for two integer sequences

According to Paillier cryptosystem the product of two ciphertexts will decrypt to the sum of their corresponding plaintexts. I have two separate integer sequences X and Y that have same number of ...
99 views

### Order of g in Paillier Scheme

I'm trying to understand the Paillier Scheme but there's something I can't understand in the keyGen algorithm: Ensure $n$ divides the order of $g$ by checking the existence of the following ...
708 views

### Questions about proof of correct encryption in the Paillier cryptosystem

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}$. A proof of correct encryption could look like presented in ...
137 views

### Homomorphic properties of Paillier

I'm curious about the homomorphic properties of Paillier. So, basically if I have $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk}, \alpha) \cdot \textsf{Enc}(\textsf{pk}, \alpha^{-1}))$, I will ...
2k views

### How can I do minus on plaintexts in the Paillier cryptosystem?

We have $E(a)$, $E(b)$ encrypted under the same Paillier key. As we all know, we can get $E(a+b)$ by calculating $E(a)*E(b)$. But can we get $E(a-b)$, by calculating $E(a)/E(b)$? I tried to ...
130 views

### Is Paillier secure from known plaintext attack for single character message?

Assuming I have three messages m1,m2,m3 where m1=m2=m3=1 and I compute c1,c2 and c3. Does that mean that c1=c2=c3 in cipher-text from ? If not, how many times can I encrypt a message m=1 and still ...
166 views

173 views

### How to calculate random factor in Paillier cryptosystem?

I am currently learning paillier cryptosystem,and have two questions about random r.I use the characteristics of homomorphic addition to obtain the product of two ciphertexts C and the corresponding ...
135 views

### Paillier encryption problem when q or p divides r

I am having a problem with Paillier encryption as described on Wikipedia. It says to pick $0 < r < n$, where $n=pq$ for large, equally sized primes $p$ and $q$. However, I've been testing ...