Equality of ElGamal plaintext & Pedersen commitment message

Seed Barret

8/24/24, 10:21 AM

Let's imagine two entities: Bob and Alice. Bob's public key is $B = bG$. Alice's public key is $A = aG$.
Alice encrypts her number $n$ with Bob's public key so Bob could decrypt it ($n$ is small enough to be brute-forced):
$$E = nG + r_0B$$ $$R = r_0G$$ where $r_0$ is a random nonce. Alice sends $(E, R)$ to Bob.
Bob decrypts $(E, R)$: $$D = E - bR$$ $$D = nG$$ Then Bob gets $n$ by brute-forcing $D = G*n$. Then he constructs a Pedersen Commitment as follows: $$C = nG + r_1H$$ Note that $r_0 ≠ r_1$ and $r_0$ is unknown to Bob. The question is: how can Bob prove to the third party that the message of commitment $C$ is the same as the plaintext of encryption $(E, R)$, without revealing $n$?

The rationale for this would be, for example, a consequent range proof which can be done on the $C$ commitment, since Bob knows $r_1$ and proved that $E ≈ C$ (plaintext is equal to commitment message).

116

0 + 7

elliptic-curves

elgamal-encryption

zero-knowledge-proofs

commitments

zero-knowledge

knaccc

8/25/24, 6:15 PM

Why is it important that $r_0$ is not disclosed to Bob? This is a much simpler problem if Alice creates a commitment to $n$, and then discloses the blinding factor to Bob by encrypting it with Bob's public key (e.g. using ECIES or NaCl box).

knaccc

8/26/24, 1:39 AM

(Just in case it isn't clear - since $n$ is brute-forceable, Alice can send a commitment along with an encrypted blinding factor, and Bob can use that information to determine $n$.)

Seed Barret

8/26/24, 3:16 AM

Unfortunately, this is not suitable for my case. The amount of users who can add their encrypted numbers to Bob's is not limited. This would require Bob to store all these commitments. Encryption and usage of DHKE in my case is also prohibitive

knaccc

8/26/24, 10:27 AM

In your question, Alice would send 2 El Gamal EC points to Bob. I'm proposing that instead, Alice sends a commitment EC point, an ephemeral public key EC point, and and encrypted $r_0$ value. It's 50% more data to send. I don't understand what you mean by "The amount of users who can add their encrypted numbers to Bob's is not limited." Also, solutions to the question as stated would require much more storage and EC operation complexity than the initial transmission from Alice to Bob. How come you can do complex things like range proofs but not a simple scalarmult and XOR to encrypt $r_0$?

Seed Barret

8/26/24, 2:26 PM

Okay, but in this case Alice would have to prove that she encrypts $r_1$ such that Bob can correctly decrypt it, because Bob does not store every $(E', R')$ tuple sent to him, so he can not verify whether he can or not get a valid nonce for $R'$ - every time he receives $(E, R)$ he simply adds it to his current points.

Seed Barret

8/26/24, 3:09 PM

I need something similar to what is used in [here](https://crypto.stanford.edu/~buenz/papers/zether.pdf) in Appendix G, but without complex Bulletproof circuits.

Seed Barret

8/26/24, 3:22 PM

Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/148103/discussion-between-seed-barret-and-knaccc).

Elon Musk

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

EN: Equality of ElGamal plaintext & Pedersen commitment message

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.