Questions tagged [paillier]
A public-key cryptosystem invented by Pascal Paillier in 1999.
3
votes
1answer
54 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
53 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
65 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
31 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
75 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
95 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
84 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 ...
5
votes
1answer
89 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
46 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
118 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
64 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
69 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
82 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
343 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
66 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
53 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
61 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
106 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
126 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
41 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
147 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
99 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
125 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
91 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
62 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
118 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
65 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
88 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
83 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
votes
0answers
71 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
672 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
37 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
41 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
159 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
184 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)$
...
5
votes
2answers
784 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
88 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
71 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
168 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 ...
4
votes
2answers
527 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
133 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
666 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
347 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
437 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
127 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
319 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
485 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
656 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
173 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
80 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 $...
