Questions tagged [paillier]
A public-key cryptosystem invented by Pascal Paillier in 1999.
100
questions
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 ...
0
votes
1answer
73 views
Homomorphic/Paillier crypto system for use case?: overflow for multiple counter exponent possible? Different cipher factor needed all the time?
Recently I read about homomorphic cryptosystem. They might solve a problem. To do this there need to be some modifications from standard version.
Using Paillier here but a solution for other also ...
3
votes
1answer
84 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 ...
2
votes
0answers
65 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 ${\displaystyle n}$ divides the order of $g$ by checking the existence of the ...
0
votes
0answers
79 views
homomorphic division with scaling/Paillier
Let's say that I have to use fractions instead of integers and I am using Paillier cryptosystem. So, I use scaling to obtain integers. Assume that I have a secure division protocol. What happens if ...
1
vote
0answers
33 views
Pseudorandomness based on homomorphic multiplication property of Paillier cryptosystem
Given the instance $(n, g, \lambda)$ of Paillier cryptosystem with $\text{ord}(g) = n \lambda$ (symbols have their usual meaning), and $c = g^{na}$, is it possible to distinguish (computationally) $c' ...
1
vote
1answer
112 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
2answers
115 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 ...
4
votes
1answer
98 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
1answer
105 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 ...
1
vote
0answers
53 views
Combining share decryption on Paillier threshold scheme
I am trying to implement the Paillier threshold scheme described by Fouque, et al, but I am having an issue when combining share decryptions.
The scheme calculates the plaintext $M$ with the formula:
...
2
votes
1answer
147 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
91 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
76 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
97 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
359 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
84 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
60 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
70 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
120 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
0answers
138 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
46 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
200 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
104 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
152 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
106 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
91 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
157 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
82 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
106 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
99 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 ...
1
vote
2answers
850 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
40 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
44 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
1answer
199 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 ...
4
votes
1answer
226 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)$
...
6
votes
2answers
858 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
111 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
77 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
183 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 ...
3
votes
2answers
593 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$ ...
4
votes
1answer
142 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$...
3
votes
2answers
947 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
420 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
517 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
139 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
369 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 ...
4
votes
2answers
514 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
700 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
191 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 ...
