Questions tagged [paillier]
A public-key cryptosystem invented by Pascal Paillier in 1999.
149
questions
2
votes
1
answer
58
views
Is the discrete log in general hard in Paillier groups?
https://en.wikipedia.org/wiki/Paillier_cryptosystem
Paillier cryptosystem exploits the fact that certain discrete logarithms can be computed easily.
If I were to select $g \in \mathbb{Z}_{n^2}^*$ ...
1
vote
1
answer
27
views
Internal direct product of group of invertible elements in a Paillier modulus
Let $p$ and $q$ are Sophie-Germain primes such that $p=2p'+1$ and $q=2q'+1$. Also let $n=pq$ and $n'=p'q'$. In Section 8.2.1 of this paper, the internal direct product of $\mathbb{Z}_{n^2}^*$ is shown ...
0
votes
1
answer
71
views
How to prove that paillier encryption is positive (zero-knowledge)?
Is it possible that the plaintext encrypted in a ciphertext using paillier encryption is positive without using a zero knowledge range proof?
2
votes
1
answer
56
views
Is this a safe zero knowledge proof that two paillier encryptions are equal?
We have encryptions $c_1$ and $c_2$, the person who knows the plaintext and randomness in both wants to prove that they know it. Let $r_1$ and $r_2$ be the randomness values in $c_1$ and $c_2$ ...
0
votes
0
answers
35
views
In paillier homomorphism, how is the randomness r changed during addition?
Two add the plaintexts encrypted in a ciphertext, you would just multiply the ciphertext and modulo it. However, how does the randomness value of the new ciphertext change? Assuming you the encryptor ...
2
votes
0
answers
53
views
Why is asked that gcd(pq,(p-1)(q-1))=1 in the Paillier encryption scheme?
I don't see this property $\gcd(p\,q,(p-1)(q-1))=1$ used in the scheme. And in Paillier's original paper, I don't find this requirement.
Is it required just for the difficulty of factoring $n$?
Or is ...
0
votes
1
answer
35
views
Searching in Paillier Cryptosystem
I have implemented Paillier Cryptosystem. Lets say, I have an encrypted array E(x) = [2,4,5,10,0,20] and I want to find that if 0 exist in that array. Due to the limitations of Paillier cryptosystem I ...
1
vote
1
answer
46
views
Short randomness in ElGamal and Paillier
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}$.
My question is, what if short (E.g. 512bits) $r$ is used? ...
1
vote
1
answer
37
views
Generation of the order $\lambda$ (which is lcm((p-1),(q-1))) element g in modified paillier, why $-a^{2n}$?
As the question states, in variants of paillier cryptosystem, such as CS01 and DT-PKC, when they want an element $g$ of order $\lambda$, they choose a random number $a$ from group $Z^*_{n^2}$ and ...
1
vote
1
answer
96
views
Do we need to consider overflow in paillier encryption?
Homomorphic multiplication of plaintexts in Paillier cryptosystem can be
constructed as follow:
Dsk(E(x1)^x2 mod N^2) = x1x2 mod N.
So after the decryption, we get the result of multiplication x1x2. ...
3
votes
1
answer
110
views
$n=pq$ and $n=p^2q$. How to take the value of two $n$ is the same in security
For example, Paillier's RSA modulus is $n=pq$, but OU's RSA modulus is $p^2q$. I think when two $n$ are the same, the security of the two cryptographic schemes must be different. So for example, if I ...
3
votes
3
answers
220
views
How to calculate the n in n-bit security of a crypto algorithm?
I think I'm likely missing the term because searching for this is coming up with not so precise results. I'm looking to calculate the n-bit security of say Paillier vs ElGamal vs EC ElGamal, when I ...
2
votes
1
answer
129
views
Paillier versus Lifted ElGamal for homomorphic addition for e-voting
I'm looking to create an anonymous e-Voting system which will assign a certain number of bits to each candidate during a vote, e.g. 010000 for Alice, 000100 for Bob, and 000001 for Charlie. It works ...
1
vote
1
answer
53
views
Encrypting full word using Paillier Scheme
I am using Paillier scheme to encrypt a message however, I have divided the words into alphabets and then convert each alphabet to ASCII code encrypting the final result. It works fine, but I want to ...
0
votes
1
answer
48
views
How to know the exact result in Paillier cheaper-constant multiplication
The encryption function $E_{k^+}: Z_n \rightarrow Z_{n^2}$.
The decryption function $D_{k^-}: Z_{n^2} \rightarrow Z_n$.
$m_1 = 42, k = 15, n=77$.
After encryption, exponentiation and decryption, I get:...
1
vote
1
answer
104
views
What is the difference between Paillier additive homomorphic property and addition of two paillier ciphers
Paillier has additive homomorphic property that states:
if two ciphers c1 and c2, are multiplied, and the result is decrypted, it is equal to addition of the two plaintexts.
D(c1*c2)= m1+m2
...
1
vote
1
answer
80
views
How to prove correct decryption in Goldwasser-Micali cryptosystem
In How to prove correct decryption in Paillier cryptosystem, it was asked whether Alice (in sole possession of the secret key) can convince Bob that a given plaintext is the decryption of a ciphertext ...
3
votes
0
answers
60
views
Optimisation of Pailler decryption
In this article applying Pailler encryption and decryption to image bitmaps, Table II is reported to give
Execution Time (sec) of the Paillier encryption/decryption of image using different key sizes ...
0
votes
0
answers
86
views
Paillier scheme : Encoding floats into integers impact on computations
In Privacy Preserving Processing Over Encrypted Images, I could understand that appropriate encoding of floats into integers (required in Paillier) only incur negligible error in computations.
Any ...
1
vote
1
answer
98
views
Is Paillier a stream or block encryption
Does Paillier follow a stream encryption or block encryption technique.
If it’s a block encryption then what is the size of the block in bits or bytes.
2
votes
0
answers
136
views
Efficiently prove the correctness of Paillier encryption in or "outside" a zk-SNARK
I'm working with a zk-SNARK library [1] that allows me to prove the correctness of arbitrary arithmetic circuits, and I now want to use these zk-SNARKs to prove that some Paillier [2] ciphertext $c$ ...
0
votes
1
answer
77
views
Evaluate the time of Paillier decryption
If I have 4 kilobytes of Paillier encrypted data, how can I know the time needed to decrypt it?
1
vote
1
answer
219
views
Security of Paillier against chosen ciphertext attack
Is there a proof by now that Paillier is secure against chosen-ciphertext attack? The original Paillier paper mentions that it is not.
1
vote
1
answer
129
views
Prove the correctness of decryption process of Paillier cipher
The definition of Paillier cryptosystem is the same as the one on wikipedia.
Now the random integer $g$ is chosen of the form $$g=(1+n)^{\alpha}\beta^{n}\bmod n$$, where $\alpha$ and $\beta$ are in $\...
1
vote
2
answers
116
views
can we know the sign of a ciphertext (homomorphic)
Is it possible to know the sign (positive or negative) of an homomorphic ciphertext particularly under paillier scheme ?
2
votes
0
answers
43
views
Possibility of computing a and b values from the ciphertext?
Using paillier encryption, $N$ is the product of two large prime numbers, $s$ is sampled randomly from $Z_{N^2}$ we get $ C \leftarrow g^ms^N \bmod N^2 $ where $g=1+N$, By multiplying the cipher $c$ ...
1
vote
0
answers
85
views
Elliptic curve subgroup with $p$ elements in field of characteristic $p$
Are there any elliptic curves defined over a finite field $\mathrm{GF}(p^k)$ with a subgroup of order $p$ where the discrete log (and preferably DDH) problem is hard? Elliptic curve with prime ...
0
votes
0
answers
24
views
Identify the value of the plaintext from a noised expression
Having the following instructions:
Using Paillier encryption to encrypt $m$. So, we get $Enc(m)$
Multiply $Enc(m)$ and $A$ to Get $C$. So, $C = Enc(m).A $
Decrypt $C$ using Paillier Decryption ...
1
vote
0
answers
66
views
How to store the ciphertext generated by the paillier encryption in a pixel?
Goal:
I want to implement a paillier algorithm to encrypt images and hide some data reversibly.
This is the paper that proposed this algorithm:
https://www.sciencedirect.com/science/article/abs/pii/...
3
votes
1
answer
150
views
Proof of lemma 1 Paillier encryption
In the original paper of Paillier, lemma 1 shows why $n$ must divide the order of $g$. What I don't understand in the proof of this lemma is why $g^{x_2-x_1}(y_2/y_1)^n$ implies $g^{\lambda(x_2-x_1)}$....
1
vote
1
answer
80
views
Paillier scheme and noise growth
Does the problem of noise growth exist in the Paillier homomorphic scheme ?
4
votes
2
answers
193
views
Do any probabilistic hashing algorithms have additive homomorphism?
What I am looking for is a function that meets the following criteria:
For each possible input (assume integers from [0, 255]), there must be trillions of possible outputs so as to prevent preimage ...
1
vote
0
answers
79
views
Homomorphic encrypted streams (Paillier)
Situation: Alice (violin) and Bob (drums) play music together and want to (real-time) stream the concert to Carol. In order for Carol to save bandwidth, the stream is sent through a server which ...
1
vote
1
answer
145
views
random mask reversible after homomorphic encryption
I would like to know if this process is feasible under homomorphic encryption, ideally under paillier or any other additive scheme
Apply a mask X to obfuscate a message A ie. Am = A (op) X where (op)...
5
votes
1
answer
252
views
Advantages of Paillier vs Goldwasser-Micali
It is easy to see that both Paillier and Goldwasser-Micali are homomorphic addition schemes and are secure, but what would be the advantages of choosing one over the other?
0
votes
1
answer
47
views
A modified question of Hazay & Lindell's Efficient Secure Two-Party protocols Book
Based on the question proposed on page 27, we propose a modified question as follows:
Suppose the protocol is based on Paillier cryptosystem and $P_2$ has generated related public and private keys ($...
1
vote
1
answer
142
views
Paillier's Cryptosystem - Homomorphism
I'm lacking quite some mathematical knowledge here, but could anyone please explain to me why the Paillier cryptosystem is still (additive/multiplicative) homomorphic despite introducing a random ...
2
votes
1
answer
140
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) \...
1
vote
1
answer
100
views
Paillier Complex Residuosity problem?
Paillier Cryptosystem depends on both the factorization where $n = p.q$ and the complex residuosity problem which is defined in the original paper as:
The problem of deciding n-th residuosity, i.e. ...
1
vote
1
answer
101
views
Is it possible to calculate the random factor $r$ from a encrypted message and the private key in a Paillier cryptosystem?
I have already done my research and found various sources that state that it is possible but there are also a lot of them that says it is not possible to recover $r$. This Q/A on this site for example ...
2
votes
0
answers
84
views
Compute ln function of a Paillier encrypted value [closed]
If I have an encrypted value $Enc(x)$ with Paillier cryptosystem, is it feasible to compute an encryption form of $\ln(x)$ or its approximation using homomorphic properties? The input $x$ is always ...
-1
votes
1
answer
53
views
Deterministic procedure for mapping an arbitrary value into a 𝑝,𝑞 pair for public key cryptography
I want public key cryptosystem to used for re-encryption as describe in Can Paillier ,RSA or any other schemes be used for universal re-encryption like elGamal?
Now i have little solution for ...
2
votes
1
answer
212
views
Can Paillier ,RSA or any other schemes be used for universal re-encryption like elGamal?
ElGamal, RSA, and Paillier cryptosystem have homomorphic property, and can be used fro re-encryption purposes. I want to use the encryption to re-encrypt ciphertext(as in proxy re-encryption but ...
0
votes
0
answers
34
views
Can Paillier Encryption has independent decryption key?
As Pailliear cryptosystem secret key $\lambda$, depends on primes $p$ and $q$. As $\lambda = \operatorname{lcm}(p-1,q-1)$.
I want decryption key to independent from $p$ and $q$.
It can be possible ...
1
vote
1
answer
226
views
How Paillier cryptosystem can be used practically to encrypt and decrypt big messages "m"?
I want to use the Paillier cryptosystem for encryption and decryption purposes in my research work. But i haven't found a way to encrypt big input messages;
As i want to encrypt the message i,e m :
<...
1
vote
1
answer
91
views
Is there any relationship between Paillier Cryptosystem's random r and other factors
I want to try run an example of Paillier cryptosystem(Algorithm), So i just started with some basic examples, but cannot obtain correct result/decryption.
I just change random factor ...
1
vote
1
answer
1k
views
Comparison of values in Paillier homomorphic encryption
For a project, I am using homomorphic encryption with the Paillier cryptosystem, and I have to compare two values...
Can this be done using homomorphic encryption?
And I know subtraction can be done ...
3
votes
1
answer
2k
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 ...
1
vote
1
answer
162
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 ...
5
votes
1
answer
234
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 ...