Questions tagged [paillier]

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

Filter by
Sorted by
Tagged with
11
votes
3answers
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 ...
10
votes
3answers
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$ ?
10
votes
1answer
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 ...
7
votes
1answer
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 ...
6
votes
2answers
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: ...
6
votes
1answer
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$ ...
6
votes
1answer
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 ...
5
votes
2answers
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 ...
5
votes
1answer
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#...
5
votes
1answer
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 ...
5
votes
2answers
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 ...
5
votes
2answers
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 ...
5
votes
1answer
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 ...
4
votes
2answers
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"?
4
votes
1answer
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$...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
2answers
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?
4
votes
1answer
243 views

Why multiple homomorphic operations on a ciphertext leaks no information about the plaintext?

Scenario: Assume I encrypt message $m$ using Paillier encryption, so I would get $c=E(m)$. I give the identical $c$ to two different parties, parties $D$ and $E$. Party $D$ computes: $c_{D}= E(m)^{...
4
votes
2answers
871 views

How to verify a number encrypted with an unknown key

Alice and Bob are going to follow the protocol below. Are there any crypto-constructions to help Bob verify the correctness of the answer he gets?: Alice encrypts a set of numbers using some ...
4
votes
1answer
126 views

Can the CRT speed-up Paillier decryption by more than a factor of two?

In the Pailler cryptosystem, decryption goes $m\gets\displaystyle\left\lfloor\frac {\left(c^\lambda\bmod n^2\right)-1}n\right\rfloor\mu\bmod n$ with $\mu<n$ being a part of the private key just ...
4
votes
1answer
249 views

Zero knowledge proof for Paillier addition under multiple keys

Suppose $m_0, m_1, m_2 \in \mathbb{N}$ such that $m_0 = m_1 + m_2$, $m_i > 0$ (none of them can be 0 or lower) Under a Paillier cryptosystem, set $e_0 = E(m_0, r_0)$ for a public key $(g_0, n_0)$ ...
4
votes
0answers
345 views

Additively homomorphic cryptosystem with non-interactive zero-knowledge proof of non-negativity

I need a cryptosystem that is additively homomorphic. Paillier preferably, but not neccessarily. Also, for every ciphertext the private key holder must be able to prove non-interactively that the ...
4
votes
0answers
81 views

Are there any real-world E-voting systems in use with the Paillier cryptosystem?

There are a lot of theories of Paillier cryptosystem with references to e-voting. Are there any real-world E-voting systems in use with the Paillier cryptosystem?
3
votes
1answer
1k views

In which public key encryption algorithms are the private and public key not reversible?

The RSA public key encryption system has the characteristic that the public key and the private key can be reversed. That is, information encrypted with the public key can be decrypted with the ...
3
votes
1answer
735 views

Paillier encryption: Many private keys for a public key

Assume $N$ is a public key for paillier encryption, generated by a third party. Question: Given $N$ can each client generate its own private key, such that its public key is $N$? So all parties ...
3
votes
1answer
88 views

Homomorphic $\bmod p$ operation

Let $E(m)$ a be the encryption operation using Paillier encryption scheme. Let $N$ be the public key and $p$ be a large prime number, such that $p<N$. Question: Is there any protocol, that given $...
3
votes
2answers
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 ...
3
votes
2answers
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$ ...
3
votes
1answer
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?
3
votes
2answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
590 views

Paillier Cryptosystem - Practical applications?

I wonder: are there any real-world practical applications using the Paillier cryptosystem , as introduced in [1], or some derivations of it? I'm aware of quite a few schemes proposed in literature ...
3
votes
2answers
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.
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
708 views

Questions about proof of correct encryption in the Paillier cryptosystem

In the Paillier cryptosystem [1] 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 ...
2
votes
2answers
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 ...
2
votes
3answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
166 views

How bad would it be to reuse the random blinding factor in a scheme like Paillier?

A secure and somewhat fast way to "re-encrypt" (refresh? anonymise?) a Paillier ciphertext, $c$, is to multiply it by an exponentiated random value: $c \gets c \cdot r^n \mod n^2$ (with $r \in \...
2
votes
1answer
144 views

Is equal length of primes in Paillier cryptosystem is mandate for security reasons?

In continuation to this question about length of primes , I am in doubt about the restriction on length of primes itself . In Paillier cryptosystem , equal length of primes are used . My doubt is ...
2
votes
1answer
99 views

Paillier Private $\mu$ and $\lambda$

The Paillier CryptoSystem has a public key that $(g,n)$ and the private key which can be exclusive to $\lambda$, where the decryption scheme is: $m = L(c^\lambda \bmod n^2)/L(g^\lambda \bmod n^2) \...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
88 views

I'm getting a non-integer (float) private key in Paillier encryption

I'm trying to implement the Paillier cryptosystem in Matlab using the key generation guidance available here: https://en.wikipedia.org/wiki/Paillier_cryptosystem#Key_generation, but the problem is ...
2
votes
2answers
165 views

Formal security of recycled random blinding in a Paillier scheme

This question is a follow-up/variant on a previous question. Supposing that we are trying to generate a large number of (indistinguishable) ciphertexts of a given plaintext and want to avoid the ...