Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
0answers
35 views

Applying Chinese RemainderTheorem and Paillier Homomorphic encryption

I'm trying to optimize the decryption process for Paillier Homomorphic Encryption (PHE) using the Chinese Remainder Theorem (CRT). However, I want to check if there's a different way of applying CRT ...
2
votes
1answer
36 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
2answers
60 views

Bijective encryption function in Paillier cryptoststem

In Paillier cryptoststem many ciphertexts can correspond to the same plaintext. How can I modify the scheme so to make the correspondence between ciphertexts and plaintexts a one to one correspondece? ...
1
vote
1answer
62 views

In a specific Paillier implementation, why is r prime?

I have a question about an implementation of the Paillier cryptosystem. In the description of Paillier above, encryption of a plaintext message $m$ on $\mathbb {Z}_{n^{2}}$, $0\leq m<n$, proceeds ...
1
vote
1answer
318 views

Paillier: guessing the message when knowing the cipher and the random number

I cannot get my head around this. In Paillier, the ciphertext is calculated using $c = g^m.r^n\ mod\ n^2$ where $(n,g)$ forms the public key and $r$ is a random number $0<r<n$. Assuming an ...
1
vote
1answer
34 views

Paillier addition with plain text

$A$ sends $B$ the encryption $E_{pkA}(m)$. $B$ computes $R=xE_{pkA}(m) + y$ and sends $R$ back to $A$, but tells him nothing about the parameters $x$ and $y$. $A$ performs $D_{pkA}(R)$ and recovers ...
1
vote
1answer
37 views

Verification in Threshold RSA or Threshold Paillier

In the key generation of the threshold version of RSA or the threshold version of the Paillier cryptosystem (e.g. "Shoup - 2000 - Practical threshold signatures" or "Fouque et al. - 2000 - Sharing ...
-1
votes
1answer
42 views

The way to calculate $r$ from $c=r^t\mod{n}$ where $(c,t,n)$ is known

I want to know if there is a easy way to calculate $r$ from $c=r^t\mod{n}$ where $(c,t,n)$ is known and $t=pq$ is an RSA? If $n=t^2$, is it more easier?
2
votes
1answer
81 views

Question about Damgård–Jurik crypto system

I am reading the paper about Damgård–Jurik cryptosystem. In the proof, I found this equation $c^d = (g^mr^{n^s})^d = (\boxed{(1+n)^{j m}x^m}r^{n^s})^d = \boxed{(1+n)^{j md\pmod{n^s}}}(\boxed{...
2
votes
1answer
99 views

Is there any way to prove two numbers that are equal after Paillier encryptions?

I have two numbers $x_1$ and $x_2$, and there are two Paillier homomorphic encryption (public, private) key pairs $(p_1,r_1)$ and $(p_2, r_2)$. I only know $p_1, r_1$ and $p_2$. Suppose $C_1=E_{p_1}(...
0
votes
1answer
39 views

Is it possible to manage an encrypted dataset for face recognition?

Im in my final year of PhD in computer vision and my supervisor has given me a task that I am not very familiar with. So I am teaching myself homomorphic encryption everyday. This question is mostly ...
0
votes
1answer
90 views

Calculating distance between two vectors using Paillier homomorphic encryption [closed]

I am basically trying to perform euclidean distance calculation in the encrypted domain (Paillier encryption). Using the homomorphic properties of Paillier, the squared euclidean distance formula can ...
1
vote
1answer
74 views

Paillier's scheme generalisation

Paillier's scheme assume has message and ciphertext space equal to $\mathbb{Z}_N$ with $N=pq$, that is $N$ is the product of two different primes. Is there a way to generalise this for $N$ that is ...
3
votes
1answer
100 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 ...
1
vote
1answer
58 views

Paillier subtraction for negative result

I am trying to figure out subtraction on Paillier. From what I read so far, given $m_1$ smaller than $m_2$ ($m_1<m_2$) I can compute $E(m_2-m_1)$ as $E(m_2)\cdot E(m_1)^{-1}$ where $E(m_1)^{-1}$ ...
2
votes
1answer
40 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 ...
0
votes
1answer
71 views

Paillier Homomoprhic addition overflows after a certain value

I'm new to encryption and am trying to implement Paillier encryption from the wikipedia page here: https://en.wikipedia.org/wiki/Paillier_cryptosystem I managed to implement the encryption and am ...
2
votes
1answer
44 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 ...
1
vote
0answers
76 views

Is it possible to re-cipher with Paillier?

I know that with ElGamal we can re-cipher and get a second ciphertext equal to the first. Is it possible with Paillier too? When saying "re-cipher", I mean "A sends me a message, that is encrypted ...
0
votes
1answer
49 views

algorithmic scheme to compare these two number encrypted using paillier cryptosystem

I have been going through https://eprint.iacr.org/2006/287.pdf (Conjunctive, Subset, and Range Queries on Encrypted Data by Dan boneh) I am trying to implement the paillier system to create a secure ...
0
votes
0answers
39 views

Theoretical cost of Paillier cryptosystem

How can we estimate the theoretical cost of Paillier cryptosystem? Examples can be found here https://en.wikipedia.org/wiki/Paillier_cryptosystem ? Can any please discuss the cost in terms of big O ...
1
vote
2answers
297 views

Paillier VS RSA

I was wondering if there are major pros or cons of choosing the Paillier algorithm over RSA except for Pailliers being additively homomorphic and RSA multiplicative?
2
votes
1answer
30 views

How do I choose blind sizes?

I am currently developing a service that calculates statistics (currently only sum/average) on homomorphically encrypted user data, and then gives the results to a third party. Because encryption is ...
0
votes
1answer
35 views

How to apply two consecutive Paillier encryptions?

The plaintext space for Paillier encryption is $\mathbb{Z}_n$ and the ciphertext space is $\mathbb{Z}_{n^2}$. How can I apply two consecutive encryptions? I mean, if $c$ is the ciphertext of $m$, how ...
0
votes
0answers
92 views

Division of a number in Paillier encrytion which yields decimal result

I am very new to start with Paillier encryption system. I have used the homomorphic nature of this scheme, which allows addition of two encrypted numbers. I was wondering is it possible to divide two ...
0
votes
1answer
119 views

Lagrange Gauss Reduction Algorithm

Sorry if my question is trivial. My question is related to a post "Paillier Homomorphic encryption to calculate the means" where a member suggests Lagrange Gauss Reduction Algorithm for reducing a ...
3
votes
1answer
132 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
2answers
577 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: ...
0
votes
1answer
61 views

In Paillier homomorphic encryption, do we need to take modulo after multiplication of 2 ciphertexts?

The multiplication of 2 ciphertexts generated using Paillier encryption will result in encryption of sum of corresponding plaintexts. I need to do a linear combination operation of N integers in ...
0
votes
1answer
61 views

Taking $p$ and $q$ to be the same value in paillier cryptosystem

I was implementing Paillier cryptosystem when I came across the fact that as soon as I take the primes $p$ = $q$, I start getting incorrect decryption results. As far as I can understand, when I take $...
1
vote
1answer
139 views

Can McEliece cryptosystem be used as an additively homomorphic encryption scheme?

Since McElice cryptosystem is linear, if matrix G is kept constant for different plaintexts, it can be used for linearly combining the corresponding ciphertexts. In that case, what are the advantages ...
0
votes
0answers
57 views

Simulating cloud computing for Partially Homomorphic Cryptosystem

Actually I am a new comer to cryptography and for now I want to simulate Partially Homomorphic Cryptosystem (modified) on cloud computing. If you want some clarity, maybe you would check this paper. ...
0
votes
0answers
70 views

Viewing elements in $\mathbb Z/n$ as elements in the extension field of $\mathbb{F}_2$

In this article, it is mentioned that in order to use the articles results on field $\mathbb F_2$, one must work on the extension field of $\mathbb F_{2^k}$ (page 6). That is in order to compute the ...
4
votes
2answers
410 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$ ...
0
votes
0answers
213 views

Is there a way to encrypt a ANY string using homomorphic algorithm?

I have a database which consists of strings as well as numbers, I have to use homomorphic scheme to encrypt fields. I am using Pailliers algorithm for the purpose, but I just find it for numbers or ...
4
votes
1answer
121 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
2answers
477 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 ...
0
votes
1answer
237 views

Zero-Knowledge proof with the paillier cryptosystem

For a paillier cryptosystem how can I perform a zero-knowledge proof? Given a set of values: 0001 0010 0100 1000 This would be for use in a voting system where we want to ensure we where given a ...
2
votes
1answer
292 views

Paillier's Cryptosystem - Secure Key Size

Given Paillier's Cryptosystem. What size in bits would be considered secure for now and the near future? I know it differs for every cryptosystem. For reference, the most important part of my ...
1
vote
1answer
110 views

PHE/FHE add and compare attack

I am aware of this attack that applies to PHE (partially homomorphic encryption) given the attacker has access to a trusted oracle that can Convert (i.e decrypt and ...
5
votes
2answers
239 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
2answers
415 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 ...
3
votes
1answer
592 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 ...
1
vote
1answer
143 views

Oblivious Polynomial Evaluation and Encoding Payload

I am trying to parse this paper. I think I do come to understand the general concepts go into this type of Private Set Intersection, based on Oblivious Polynomial Evaluation. I was able to produce a ...
3
votes
1answer
74 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 $...
2
votes
1answer
167 views

a homomorphic operation on Paillier encryption

Assume $N=pq$, where $p$ and $q$ are two strong prime numbers. Also, assume we have finite field $\mathbb{F}_u$ where $u$ is a $112$ bit prime number. Let $r_i$ be a uniformly random element of $\...
-1
votes
1answer
508 views

Why does Paillier have poor performance?

Can anyone explain to me why Paillier crypto system does not provide good performance? I read here (pdf) that RSA and ElGamal provide better performance than Paillier algorithm.
3
votes
2answers
667 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 ...
1
vote
2answers
325 views

In Paillier homomorphism how do you substract?

I'm trying to learn homomorphism so the problem may also be in my code (which I will include). I want to compute $a - b$ where $a$ is bigger then $b$. In order to do this I tried to compute $\frac{a}...
0
votes
1answer
127 views

In Paillier homomorphism, how do you deal with bit length? [closed]

I'm trying to figure out homomorphic encryption and would like to multiply two paillier encrypted numbers. Like so: [a].[b]=[a+b] To try this I got this Paillier.java and tried the following: <...