Questions tagged [paillier]

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

Filter by
Sorted by
Tagged with
6 votes
2 answers
335 views

Efficient multiplication modulo a square

Can anyone point me to techniques for efficient computation of modular multiplication/exponentiation modulo a square, as comes up, e.g., in the context of Paillier encryption? The standard references ...
user432944's user avatar
-1 votes
2 answers
65 views

How to calcualte the average of several plaintexts with Paillier homomorphic encryption?

I am trying to do some calculations with the Paillier Homomorphic encryption scheme. Specifically, given three plain text integers, x1, x2,and ...
Sea_'s user avatar
  • 1
1 vote
1 answer
55 views

Threshold Paillier encryption key generation time

I have used the threshold version of Paillier encryption without a trusted dealer in an application. I have tested the key generation phase with different security key sizes such as 80, 512, 1024, and ...
Tooba's user avatar
  • 11
7 votes
1 answer
264 views

Generating suitable prime numbers for Paillier key pair in GG18

I am working on MPCs (multi party computation) in crypto, and now I am developing a implementation of GG 18. In sign phase, algorithm needs MtA (Multiplicative to Additive) and uses a Paillier key ...
user109261's user avatar
2 votes
0 answers
63 views

To prove equality/inequality of plaintexts of 2 ciphertexts encypted under different encryption schemes

We have 2 ciphertexts, one encrypted using Paillier and another encrypted under Elgamal encryption schemes. Is there a way to design ZK-proof to prove equality of the underlying plaintexts of these 2 ...
G Pavithra 's user avatar
3 votes
0 answers
43 views

Variant of CCA security for Paillier with blinded decryption oracle

Consider a variant of the Paillier encryption scheme where the message space is restricted to $\mathbb{Z}_q$ such that the RSA modulus $N$ of the Paillier cryptosystem satisfies $N > q + q^2$. I am ...
Prashant Agrawal's user avatar
1 vote
2 answers
103 views

Reencrypting in Homomorphic Encryption

I am getting started with Homomorphic Encryption libraries. I am trying to port a codebase written in Python to Haskell. I see that there is a re-encryption operation happening in one part of the code....
Abhiroop Sarkar's user avatar
4 votes
2 answers
156 views

Paillier cryptosystem break with random number

In the Paillier cryptosystem we choose $n=p\,q$ where $p$ and $q$ are primes, $g=n+1$, $\lambda=\phi(n)$, $\mu=\lambda^{-1}\bmod n$. The public key is: $(n,g)$. The private key is: $(\lambda,\mu)$. ...
legends_never_die's user avatar
3 votes
0 answers
101 views

Zero Knowledge Proofs for Microsoft SEAL (Homomorphic Encryption)

I am working on a system involving multiple parties performing homomorphic cryptographic operations using Microsoft SEAL (BFV). Because of the nature of the system, it would be preferable for the ...
Andrei Florian's user avatar
0 votes
1 answer
160 views

How to proof Two CipherTexts holding same value with Zero Knowledge Proof?

I am a beginner in cryptography. I wonder is it possible to create by Zero Knowledge Proof, to prove Two cipherTexts that are encrypted by same Public Key with Paillier Encryption have the same value ...
Bertug's user avatar
  • 3
0 votes
0 answers
31 views

Question about homomorphic property of Paillier cryptosystem breaks after modulus n are taken

Hi I am watching this slide about threshold signature: http://cyber.biu.ac.il/wp-content/uploads/2021/11/Threshold_Sinature_Schemes_Rosario_Gennaro.pdf And in page 39 it said that the homomorphic ...
js wang's user avatar
  • 173
2 votes
1 answer
79 views

How to factorize $N$ in OU cryptosystem under chosen ciphertext attack?

OU cryptosystem: $N = p^2q$, the secret key is the factorization of $N$, the public key is $g\leftarrow \mathbb{Z}_N$, $g^{p-1} \neq 1\mod p^2$, to encrypt an element $m $ $\in$ $\mathbb{Z}_p$, ...
Bob's user avatar
  • 499
0 votes
0 answers
50 views

Sigma protocol for proof of encrypted content

Suppose I have a device which encrypt my fix plaintext (On request) using Paillier algorithm. So this device every time generate a new random number (used in Paillier algorithm) and a new ciphertext (...
abbas's user avatar
  • 165
1 vote
0 answers
32 views

Paillier cryptosystem for verifiable shuffles

I am looking for some algorithm or implementation on Pailler cryptosystem-based verifiable shuffles for mixNet. So far, all the verifiable shuffles and mixNet are available for ElGamal cryptosystems ...
Nomana's user avatar
  • 41
2 votes
0 answers
40 views

How to prove an RSA ciphertext matches a Paillier ciphertext?

Suppose I know an RSA public key $(n,e)$ and I create two ciphertexts: An RSA ciphertext $C_1 = m^e \mod n$ and a Paillier ciphertext $C_2 = g^m \cdot r^n \mod n^2$. Is there a known efficient method ...
Zarquan's user avatar
  • 188
1 vote
1 answer
79 views

Is it possible to use Batching with any of the Partial Homomorphic Cryptosystems?

I'm familiar with the concept of batching in the context of (Fully) Homomorphic Encryption - whereby many values can be encrypted as a single ciphertext and operated on simultaneously in an SIMD/...
slickboy's user avatar
  • 177
1 vote
0 answers
85 views

Additive Homomorphic Encryption scheme with very small ciphertext size

I'm looking for a Additive Homomorphic Encryption scheme which can allow a ciphertext of size smaller than 128 bit. I started studying this topic very recently so I don't have much knowledge, but I ...
Key Heon Lee's user avatar
1 vote
1 answer
53 views

Can I get individual data by paillier decryption if we send aggregated encrypted data?

Suppose there are different users data for $n$ Smart meters. We encrypt all the individual data and then add them together. After decrypting the summation, how can we retrieve the original data? We ...
Farzana Kabir's user avatar
1 vote
1 answer
111 views

Working with Paillier and ECDSA - Order issue

I'm trying to implement two party computation for ECDSA signing using Paillier cryptosystem. But my problem is that the order of Paillier is different from the order of the curve (secp256k1 in my case)...
Ron's user avatar
  • 123
3 votes
1 answer
155 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}^*$ ...
user101299's user avatar
1 vote
1 answer
35 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 ...
kentakenta's user avatar
-1 votes
1 answer
200 views

How to prove that paillier encryption is positive (zero-knowledge)? [closed]

Is it possible that the plaintext encrypted in a ciphertext using paillier encryption is positive without using a zero knowledge range proof?
Manglemix's user avatar
2 votes
1 answer
101 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$ ...
Manglemix's user avatar
0 votes
0 answers
48 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 ...
Manglemix's user avatar
2 votes
0 answers
78 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 ...
mactep Cheng's user avatar
0 votes
1 answer
50 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 ...
Haroon Malik's user avatar
1 vote
1 answer
86 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? ...
vince.h's user avatar
  • 97
1 vote
1 answer
48 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 ...
rzxh's user avatar
  • 73
2 votes
2 answers
123 views

Paillier cryptosystem safety

I am working on system which can calculate average salary for different positions in large companies I want to use Paillier schema to do such calculation. I have 3 fields which I want to encrypt: ...
sorror's user avatar
  • 31
1 vote
1 answer
141 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. ...
rzxh's user avatar
  • 73
3 votes
1 answer
129 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 ...
ShallMate's user avatar
3 votes
3 answers
492 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 ...
ystark's user avatar
  • 155
2 votes
1 answer
418 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 ...
ystark's user avatar
  • 155
1 vote
1 answer
84 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 ...
Haroon Malik's user avatar
0 votes
1 answer
53 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:...
superuser's user avatar
0 votes
2 answers
143 views

ElGamal and Paillier combined

currently I am working on some secure accounting application. I have few requirements: Application should store items which can be searched by name. Every item has price and tax. Every invoice ...
sorror's user avatar
  • 31
4 votes
1 answer
429 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 ...
Mimi's user avatar
  • 61
1 vote
1 answer
157 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 ...
Neil's user avatar
  • 11
0 votes
0 answers
126 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 ...
witdev's user avatar
  • 75
1 vote
1 answer
119 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.
Mimi's user avatar
  • 61
2 votes
0 answers
210 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$ ...
rogermb's user avatar
  • 21
0 votes
1 answer
101 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?
Mimi's user avatar
  • 61
1 vote
1 answer
442 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.
Mimi's user avatar
  • 61
1 vote
1 answer
256 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 $\...
Bella's user avatar
  • 21
1 vote
2 answers
196 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 ?
witdev's user avatar
  • 75
2 votes
0 answers
45 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$ ...
sof's user avatar
  • 61
1 vote
0 answers
102 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 ...
qbt937's user avatar
  • 258
0 votes
0 answers
26 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 ...
sof's user avatar
  • 61
1 vote
0 answers
83 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/...
Am473ur's user avatar
  • 11
3 votes
1 answer
170 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)}$....
mip's user avatar
  • 327