Background

Let’s first set the stage and talk about a couple things.

• Cyclic Groups
• Discrete Log Problem

Cyclic Groups

We need to understand what cyclic groups are and why they’re important.

Imagine you have a number g, and you start raising it to powers - modulo some prime number p.

Eventually, due to the wrapping nature of modular arithmetic, the results loop back around, and you’ll get 1 again. The set of all these results is a cyclic group, and the number g that generates them is called a generator of the group.

There are three properties that must hold true for g to be a generator of a group \mathbb{G}.

• g must be an element within \mathbb{G}
• Repeated multiplication (exponentiation) of g must produce a cyclic subgroup
• The cyclic subgroup generated by g must be equal to \mathbb{G}

where n is the size of the group. All powers are computed modulo some number, usually a prime.

If you’re working with integers modulo a prime p, the group \mathbb{Z}_p^\times = \{1, 2, 3, ..., p - 1\} is a multiplicative cyclic group of order p - 1. Some number g \in \mathbb{Z}_p^\times is a generator if:

This means that just by knowing g, you can reach any number in the group by raising it to the right power.

This property is important for the concepts we’re exploring in this post. Raising g to a power x is easy:

But given y, trying to figure out x is hard. This is the core of the Discrete Logarithm Problem (DLP), and it’s what makes schemes like Pedersen commitments and ElGamal encryption secure.

You can think of it like a hash function - one-way, deterministic, and extremely hard to invert.

A couple more thoughts on cyclic groups regarding cryptography:

They are useful since they are both compact and efficient; you only need to store one number g to define the whole group, and you can jump to any element with exponentiation.

Not all groups are “good” when it comes to security. Some groups are not cyclic, they don’t have a single generator that can reach every element in the set. Others are cyclic but not secure (either the group is too small or DLP is easy). That’s why cryptographic applications use very specific kinds of cyclic groups:

• Multiplicative groups where p is a (very) large prime
• Elliptic curve groups, but those are for another blog post.

Discrete Log Problem

I’ve mentioned DLP a few times now, but let’s take a moment to understand what is so important about it. At the heart of many cryptographic systems is one simple question:

If I give you y = g^x \bmod p, can you figure out what x is?

In everyday math, this would be like solving:

But in modular arithmetic, logarithms behave very differently. Given:

There is no shortcut for recovering x, for a large enough p, the only option is to test every possible element of the set.

When encrypting or signing, schemes use exponentiation as discussed in the cyclic groups section. There are algorithms for this that have logarithmic complexity in relation to the power by which we’re exponentiating: \mathcal{O}(log(x)).

For a brute-force style attack, which doesn’t know x, the time complexity spikes dramatically to \mathcal{O}(|{\mathbb{G}} \cdot log(\mathbb{G})|). For a secure cyclic group, this means that it is practically unsolvable for our modern computational resources. However, it is of course possible to have an insecure group, where the DLP is relatively speaking “easy” to solve, or possible in polynomial time.

The simplest way to make your group more secure is to have a very large order (the number of elements in the set). 256-bit primes are a common way to achieve this, with the famous Curve25519 having the order 2^{255}-19. Unfortunately, there exist other properties that can weaken the group, one of the most common being “weak subgroups”.

A subgroup is simply a smaller set of elements within a group that still follows the same group rules. That is, if you take any two elements from the subgroup and multiply them together, you stay within the subgroup.

For example, suppose you’re working with the multiplicative group \mathbb{Z}_p^\times. A subgroup might be a smaller set of numbers within \mathbb{Z}_p^\times that also loop around nicely when you raise them to powers. Every subgroup has a generator - just like with the full group - and an order.

Small subgroups are a big problem in cryptography because they shrink the space an attacker has to search when brute forcing. If an attacker can trick your system into operating inside a small subgroup, they might only need to try a handful of values to brute-force secrets like exponents or keys.

There are plenty of sources that go into further detail about this problem:

• Logjam Attack
• CVE-2002-20001
• RFC 2785
• CVE-2017-9248

To avoid these security issues, it’s important to perform subgroup membership checks for groups where the order isn’t a prime number.

Pedersen Commitments

In cryptography, a commitment scheme lets you lock in a value while keeping it hidden - like storing a message in a safe. Later, you can open the safe to reveal what you committed to. This simple idea is a foundational building block in many cryptographic protocols, from zero-knowledge proofs to secure voting systems.

A good commitment scheme must have two important properties:

• Hiding: The commitment doesn’t reveal anything about the value being committed. Until you open it, it should look completely random.
• Binding: Once you’ve committed to a value, you can’t change your mind. You’re “locked in.”

These two properties are in tension. Hiding ensures the commitment gives away no information about the underlying value; binding ensures you can’t cheat and claim you committed to a different value later.

In the digital world, the “safe” is a short piece of cryptographic data (a commitment) - typically much smaller than the original value - but it plays the same role.

Going through the math

Now let’s take a look at Pedersen commitments from a mathematical point of view. The magic of this scheme comes from using a second element to mask away the first one.

A Pedersen commitment to a value m (the number you want to commit to) is computed as:

• G is a generator of the group
• H is an element of the group. It may be a generator, however it’s important that it is chosen independently of G. It’s common to apply a hash such as SHA-3 to G, so that the relationship is harder to follow.
• r is a random value (called the blinding factor), chosen to hide m
• p is a large prime, and the group is typically a multiplicative subgroup of \mathbb{Z}_p^\times or a point group on an elliptic curve

The commitment C looks random to anyone who doesn’t know both m and r, but you can “open” the commitment later by revealing those two values.

Now you may be wondering, why do we need two elements? Shouldn’t the Discrete Log Problem be enough to mask the value of the commitment if we just used:

The issue is that m is a user-defined value, and could be anything. Commonly in confidential transactions, m is a relatively small number such as the account balance, which would lead to brute-force attacks being easy.

A second generator point “masks” m behind the randomness of r. Now, even if m is 0, 1, 2, or some small-ish number, the commitment looks random unless you know what r is. Thanks to the unknown discrete log between G and H, there’s no way to remove the blinding factor from the commitment without solving the two DLPs at once, which is still hard. This becomes what’s called the computational Diffie-Hellman problem (CDH).

Example of Vulnerable Pedersen Commitment

Let’s look at what would happen if you did know the discrete log between H and G, with a real-number example. This could enable vulnerabilities such as double-spending, value forgery, cheating zero-knowledge proofs, breaking fairness in auctions or voting, and cause issues anywhere where Pedersen Commitments are used.

We’ll define the group \mathbb{G} as \mathbb{Z}_{101}^\times. The modulo of the group is 101. A generator of this multiplicative cyclic group is 2.

Now let’s define:

• a = 13, which will be the coefficient between H and G
• H = G^a = 2^{13} \bmod 101 = 11

We’ll commit to x = 42 and r = 7. Remember, the prover has control over the constants used to create the proof, so the verifier wouldn’t know if the numbers used weren’t actually random.

We can easily double check the value of C in this example, simply compute (2^{42} * 11^7) \bmod 101.

Now to perform an attack, the prover wants to find another pair (x', r') that opens the same commitment.

By substituting and simplifying, we can see that the value for the commitment becomes a single power of G once we know the discrete log (a):

So the attack sees:

for some z = x + 13r

Since the prover knows z, they can just pick any x', and solve for r':

(since the order of the multiplicative group is p - 1, we use 100 here)

Let’s try:

• x' = 30
• z = 30 + 13 * 7 = 133
• a^{-1} = 13^{-1} \bmod 100 = 77
• r' = (133 - 30) * 77 \bmod 100 = 31

and then finally, the faked commitment:

Now we have an opening (x' and r') which falsely claims we committed to the value 30, even though the original commitment was to 42.

This means a malicious user can claim to have committed to one value (e.g., their true balance), but then reuse the same commitment to prove a different value, thereby cheating the system.

Homomorphism

Pedersen commitments have a nifty property: they are homomorphic. This means you can combine two commitments, resulting in a commitment to the sum.

Let’s say:

Then, applying the property of additive \Rightarrow multiplicative homomorphism:

So C_1 \cdot C_2 is a valid commitment to m_1 + m_2 using blinding factor r_1 + r_2.

This property makes Pedersen commitments especially useful in protocols where you want to prove things about hidden values without revealing them. For instance, showing that the sum of committed inputs equals the sum of committed outputs in a confidential transaction.

Why is it secure?

The binding property depends on a very important assumption:

Given a commitment C = G^m \cdot H^r, it should be infeasible to find two different pairs (m_1, r_1) and (m_2, r_2) such that:

Unless you know the discrete log between G and H, you cannot find two valid openings. And without the ability to find another valid opening after creating the first one, you’re unable to later claim you committed to something else.

This means the commitment scheme is computationally binding - it’s secure against these sorts of attacks as long as DLP is hard. If an attacker had infinite time, they would potentially be able to find a second opening for the same commitment.

The flip side of this is perfectly-binding, meaning even if an attacker had infinite time, they wouldn’t be able to find a second opening. For this to be the case, each value of m would need to have a single opening, which is not the case for Pedersen commitments.

The hiding property ensures that the commitment doesn’t leak any information about m - not even partial hints. With Pedersen commitments:

As long as the blinding factor r is chosen randomly and independently, the commitment C = g^m \cdot h^r is perfectly hiding.

What does that mean?

• For any two possible messages m_1 and m_2, the commitments C_1 and C_2 look identically distributed if the random r values are chosen uniformly.
• This is true regardless of how powerful the attacker is - even if they had infinite time, they couldn’t distinguish whether C hides m_1 or m_2.

This property is called information-theoretic hiding or perfectly-hiding: the message is completely masked by the randomness, not just “hard to guess” via brute-force methods.

Something to note is that commitment schemes cannot be both perfectly-hiding and perfectly-binding. It’s physically impossible. In order to be perfectly-hiding, two different messages must be able to produce the same commitment. But if that were to be the case, then the commitment can be opened in two ways, so the scheme is not perfectly binding.

Pedersen commitments are perfectly-hiding and computationally binding.

ElGamal Encryption

ElGamal encryption is a public-key encryption scheme built on the Discrete Logarithm Problem - the same hard problem that underpins the previously discussed Pedersen commitments.

At its core, ElGamal lets someone encrypt a message so that only the recipient (who knows a secret key) can decrypt it - and it does so in a way that allows us to reuse much of the math we’ve already seen in this post.

Where Pedersen commitments let us hide a value in a way that can be later revealed, ElGamal lets us send a value in a way that can later be decrypted - but only by the intended recipient.

It uses the same kind of group:

• A generator G
• A secret key x
• A public key pk = g^x

ElGamal is similar to Pedersen commitments because they share a useful property. ElGamal is homomorphic. This means you can add or multiply encrypted values together, and the result will still decrypt properly. This makes it useful for privacy-preserving computation, voting protocols, threshold decryption, and a ton of other things.

If you understand Pedersen commitments, ElGamal encryption will feel very similar.

Both use exponentiation in a cyclic group - either a multiplicative group like \mathbb{Z}_p^\times, or an elliptic curve group - both rely on the assumption that DLP is hard in that group.

When used with elliptic curves (EC), ElGamal simply switches from exponentiation g^x to scalar multiplication x \cdot G. The mathematical structure is the same, but EC offers much smaller key sizes for the same security level.

The best known attacks (such as number field sieve) scale sub-exponentially with the size of p, so to get strong security, 256-bit symmetric equivalent, you’d need a group with order in the thousands of bits (3072, 7680, 15360 bits).

ElGamal Decryption Example

Let’s quickly go through an example of the decryption process for ElGamal to get a better understanding of the algorithm overall.

Let’s assume you’re working in a group \mathbb{G} with generator G.

Quick note: \overset{\$}{\leftarrow} means “a random scalar uniformly sampled from the set”.

• Private key: x \overset{\$}{\leftarrow} \mathbb{Z}_{p - 1}^\times. It’s important that p - 1 isn’t included in the set, since there wouldn’t be much work for the adversary if your private key results in a public key equivalent to the generator.
• Public key: h = G^x

To encrypt a message m \in \mathbb{G}, the sender picks a random element r \overset{\$}{\leftarrow} \mathbb{Z}_p, and sends the ciphertext:

• c_1 = g^r
• c_2 = m \cdot h^r

The ciphertext is the pair (c_1, c_2)

The receiver (who knows the secret key x) gets the ciphertext (c_1, c_2), where again:

• c_1 = g^r
• c_2 = m \cdot h^r = m \cdot (g^x)^r = m \cdot g^{xr}

To recover the message m, they compute:

This works because:

The sender “blinds” the message by multiplying it with a one-time pad h^r. The receiver knows how to “unwind” that one-time pad via their private key. The security of the algorithm comes from not being able to compute x from h = g^x.

What is Twisted ElGamal

As discussed in the previous chapter, ElGamal encryption operates by encrypting messages that are elements of the cyclic group \mathbb{G}. The main limitation of this approach which becomes particularly apparent with integrating in zero-knowledge proofs is handling of messages not naturally residing in \mathbb{G}.

Twisted ElGamal encryption addresses these limitations by combining the previously discussed ideas and restructing the ciphertext into two compontents:

• A Pedersen Commitment: C = r \cdot H + m \cdot G
• A Decryption Handle: D = r \cdot P

In this setup:

• G and H are fixed, independent generators of the group \mathbb{G}
• s \overset{\$}{\leftarrow} \mathbb{Z}_p is the secret key, uniformly sampled from the group
• P = s^{-1} \cdot H is the public key, derived from the private key s
• r \overset{\$}{\leftarrow} \mathbb{Z}_p is a random scalar used for creating the ciphertext
• And finally, m is the plaintext message, represented as a scalar

This idea decouples the message from the group elements, allowing messages to be arbitrary scalars rather than requiring embedding into \mathbb{G}.

By structuring the ciphertext as (C, D), where C contains both the message and randomness, and D contains only the randomness tied to the public key, it becomes easier to construct proofs about the message without revealing it.

The decryption process of Twisted ElGamal encryption is by far the hardest part to understand. I like to think of it as two separate steps. Assume in this example that C and D are the ciphertext components and s is the secret key generated before.

First our goal is to remove the randomness. The ciphertext includes a random scalar r, which is unknown to the decrypter. The decrypter’s goal is to remove the r from the commitment C = r \cdot H + m \cdot G leaving only m \cdot G, from which the scalar m can be recovered.

We can’t directly remove r \cdot H since r is unknown - but we can compute it indirectly using the decryption handle provided in the ciphertext.

Remember that the decryption handle is computed as:

We can compute:

and then subtract this from the commitment C:

and there you go: you’ve isolated the component m \cdot G. Because G is a known generator and m is assumed to be in a small enough space (e.g. between 0 \leq x \leq 2^{32}), you can brute-force m by checking multiples of G. That is, find the scalar m such that:

For the exact method by which to solve it, I recommend reading The Twisted ElGamal Encryption Chapter 3.

The encryption is hiding, not obfuscating. You aren’t relying on the hardness of the discrete log here, but instead rely on the hiding provided by the randomizer r, and the binding provided by the commitment.

So why does any of this matter?

Pedersen commitments and ElGamal-style encryption aren’t just mathematical curiosities - they’re the bedrock of many cutting-edge cryptographic systems. Because of the unique properties these tools have, they serve as building blocks for protocols that require trustless interaction over untrusted networks.

Zero-knowledge proofs, such as Bulletproofs, rely heavily on Pedersen commitments to allow someone to prove knowledge of a secret (like a number in a range), without revealing the secret itself. Likewise, Twisted ElGamal enables users to encrypt data like transaction amounts or votes while still allowing computations and verification on that data - essential for privacy-preserving blockchain protocols like Monero, ZCash, and confidential transaction in general.

Beyond blockchains, these ideas extend to secure voting systems, multi-party computation, and decentralized identity frameworks, where both privacy and the ability to verify arguments of knowledge is paramount.

Anyways, I hope you enjoyed the explanations in this post, maybe I’ll make another one in the future going into the practical implementations and cool optimizations that can be done in this space.