Can I prove that from a set of ciphertexts one is encrypting $g^0$ and the others are encrypting $g^b$ where $b$ is a negative value?

Μενέλαος Κοκάρας

9/9/23, 11:26 AM

Consider for example this set of encrypted values under the Elgamal keys $y_0$,$y_1$,$y_2$: $$ Enc_{y0}(g^0),Enc_{y1}(g^{-20}),Enc_{y2}(g^{-10}) $$ Can I prove that one value is $g^0$ and the others are $g^b$ where b is negative without revealing which one is who?

0 + 0

elgamal-encryption

zero-knowledge-proofs

Manish Adhikari

9/9/23, 11:58 AM

You are encrypted not 0 but 1, $g^0$. Anyway 0 itself is not an element of domain group and thus does not work with El gamal, the ciphertext will always be 0. But the main problem with your question is it does not clarify what counts as negative. $g$ lies between 0 and the group order $q-1$, one way is shifting it back by $(q-1)/2$ and define domain between 0$(q-1)/2$ and $(q-1)/2$. Either way, you must make it clear first

Manish Adhikari

9/9/23, 12:10 PM

Well there are protocols for AND and OR composition of sigma protocols and one naive solution is proving $ ([0] \land [-ve] \land [-ve]) \lor ([-ve] \land [0] \land [-ve]) \lor ([-ve] \land [-ve] \land [0]) $ but others might have better solution

Μενέλαος Κοκάρας

9/9/23, 12:38 PM

@ManishAdhikari thanks I fixed it.What i mean is the power of g

ming alex

9/10/23, 10:15 AM

For $g^0$, the corresponding ciphertext is $(g^r, 1\cdot h^r)$, you can prove that $PK\{r: c_1=g^r , c_2=h^r\}$. But for the negative number, I have no idea.

Elon Musk

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

EN: Can I prove that from a set of ciphertexts one is encrypting $g^0$ and the others are encrypting $g^b$ where $b$ is a negative value?

TH: ฉันสามารถพิสูจน์ได้หรือไม่ว่าจากชุดของข้อความเข้ารหัสชุดหนึ่งกำลังเข้ารหัส $g^0$ และชุดอื่นกำลังเข้ารหัส $g^b$ โดยที่ $b$ เป็นค่าลบ

RO: Pot demonstra că dintr-un set de texte cifrate unul criptează $g^0$ iar ceilalți criptează $g^b$ unde $b$ este o valoare negativă?

RU: Могу ли я доказать, что из набора шифротекстов один шифрует $g^0$, а другие шифруют $g^b$, где $b$ — отрицательное значение?

VI: Tôi có thể chứng minh rằng từ một bộ bản mã, một bản mã đang mã hóa $g^0$ và các bản mã khác đang mã hóa $g^b$ trong đó $b$ là giá trị âm không?

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.