Several Discrete Logarithm Zero Knowledge Proof

Кирилл Волков

11/15/22, 1:40 PM

According to Wiki there is an approach for proving knowledge of $x$ such that $g^x = y$. How can I prove that I know $x_1, x_2$ such that $g^{x_1} = y_1, g^{x_2}=y_2$. Of course, I can make these proofs separately but I would like to combine them into a single one. My idea is to prove that I know such $x = x_1 + x_2$ that $g^x = y_1 y_2$. But is it safe? Does not it make the system vulnerable?

1 + 0

discrete-logarithm

zero-knowledge-proofs

fiat-shamir

Score:0

Crypto

poncho

11/15/22, 1:50 PM

But is it safe?

Well, knowledge of $x_1 + x_2$ does not imply that you know either $x_1$ or $x_2$.

On the other hand, if you were to prove knowledge of $r_1x_1 + r_2x_2$, for a random (e.g. selected by the verifier or a Random Oracle) $r_1, r_2$ values, that would be a zero knowledge proof of knowledge of both $x_1, x_2$

This can be done by extending the single-exponent zero knowledge proof in a fairly simple way:

Prover sends $g^v$ to the verifier (for some random $v$)
Verifier sends random $c, d$ to the prover
Prover sends $r = v - cx_1 - dx_2$ to verifier
Verifier accepts if $g^v = g^r (g^{x_1})^c (g^{x_2})^d$

0 + 6

Кирилл Волков

11/15/22, 2:04 PM

Can $c$ and $d$ be generated via a hash function?

poncho

11/15/22, 2:05 PM

@КириллВолков: yes; for my example, I did the interactive version - it's straight-forward to turn it into a noninteractive protocol

Кирилл Волков

11/15/22, 2:06 PM

Thank you very much!!

Кирилл Волков

11/16/22, 5:43 AM

Can I extend the algorithm for $x_1, x_2, x_3, \ldots, x_n$ in the same way?

poncho

11/16/22, 11:46 AM

@КириллВолков: yes, it works in the obvious way.

Кирилл Волков

12/3/22, 2:54 PM

Maybe you know, where I can find the proof of the proposed scheme?

Elon Musk

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

EN: Several Discrete Logarithm Zero Knowledge Proof

TH: ลอการิทึมแบบไม่ต่อเนื่องหลายตัวพิสูจน์ความรู้เป็นศูนย์

RO: Mai multe dovezi de cunoștințe logaritmice discrete

RU: Несколько дискретных логарифмов с нулевым разглашением

VI: Một số bằng chứng kiến thức logarit rời rạc

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.