How to decrypt a homomorphically modified ciphertext in Elgamal cryptosystem?

user77340

9/7/23, 8:51 AM

From the wiki, we know that to encrypt a message $M$ using Elgmal encryption, one should firstly map the message $M$ to an element $m$ of G using a reversible mapping function, then run the ElGamal encryption algorithm to get the ciphertext $C$. To decrypt $C$, one should run the decryption algorithm to get $m$, and finally, map the $m$ back to $M$ using a reversible mapping function.

As we know that Elgamal encryption is also a multiplicative holomorphic encryption scheme. My question is how to decrypt a homomorphically modified ciphertext? For example, now I have two ciphertexts, $C_1,C_2$, encrypting $M_1, M_2$ respectively with the same recipient public key. I compute $C^{\prime}=C_1C_2$. CanI decrypt $C^{\prime}$ to get the message $M_1\times M_2$ using a reversible mapping function? If we can, what is the reversible mapping function? Thanks!

0 + 0

elgamal-encryption

user77340

9/7/23, 9:52 AM

@knaccc Yes, the same recipient public key. I am looking to encrypt message from $Z_p$.

user77340

9/7/23, 9:57 AM

What I mean by $Z_p$ is just the order of the group. I don't mean the order of the underlying finite field(i.e., the order of the x-coordinate). To avoid confusion, let me denote the order of the underlying finite field $Z_q$.

user77340

9/7/23, 10:01 AM

Yes, I am just wondering if it is possible to make a homomorphic reversible mapping function to achieve my goal?

user77340

9/7/23, 10:04 AM

If not, then what is the point of the multiplicative homomorphic property of Elgamal? Doesn't it just mean enc(m1)enc(m2)=enc(m1m2)?

user77340

9/7/23, 10:05 AM

It will not give $(m_1+m_2) mod \ell$, but $m_1\times m_2 mod \ell$ because of the multiplicative homomorphic property, rather than additive holomorphic one.

user77340

9/7/23, 10:06 AM

Do you mean we can achieve my goal with the help of commitment?

user77340

9/7/23, 10:14 AM

ok, I get it. Thanks.

knaccc

9/7/23, 11:40 AM

Btw my comments were about EC El Gamal, and I only meant to indicate that what you are describing isn't possible with the EC variant. I haven't thought through the implications of the regular version as described in wikipedia. I was confused as to which variant you were referring to, and I'm still not sure since you've mentioned x-coordinates.

user77340

9/8/23, 2:17 AM

ok, I see. Thank you anyway!

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to decrypt a homomorphically modified ciphertext in Elgamal cryptosystem?

TH: จะถอดรหัสข้อความเข้ารหัสที่แก้ไขแบบโฮโมมอร์ฟิคในระบบเข้ารหัส Elgamal ได้อย่างไร

RO: Cum se decriptează un text cifrat modificat homomorf în criptosistemul Elgamal?

RU: Как расшифровать гомоморфно модифицированный шифротекст в криптосистеме Эльгамаля?

VI: Làm cách nào để giải mã một bản mã đã được sửa đổi đồng hình trong hệ thống mật mã Elgamal?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.