22 Apr 2024
Twisted Edwards curves has a form of \(ax^2 + y^2 = 1 +
dx^2y^2\) (for fields with characteristic not 2) where
the curve order can be represented as \(l \cdot 2^c\),
where
\(c\) is a natural number, \(l\) is a big prime number.
For the classical EdDSA signature algorithm it uses the Ed25519 curve over the prime field \(F_{2^{255}-19}\) with
definition: \(-x^2+y^2=1-\frac{121665}{121666}x^2y^2\). The reason of this another one curve creation is the
optimization
of this curve efficiency compared to the other popular curves. And, while talking about EdDSA algorithm it’s required to
highlight that it does not require any PRNG because the signature one-time keys is deterministically generated using
message and private key.
Let me show you how EdDSA protocol is related to the classical Schnorr authentication protocol.
The Schnorr authentication protocol was presented in 1991 with the
following form:
- Alice owns a secret value \(k\) and shares the public key \(K = kG\), where \(G\) is the group generator. Alice’s goal
is to prove to the Bob the knowledge of \(k\) that corresponds to the provided public key \(K\) without revealing any
private information.
- Alice generates random key \(a\) and sends \(A = aG\) to Bob.
- Bob generates random challenge \(c\) and sends it to Alice.
- Alice calculates the response \(r = a + kc\) and sends is back to the Bob.
- Bob checks that \(rG = A + cK\).
Later, after presenting of the Fiat-Shamir heuristics, where for the challenges generation prover can use the hash of
input data such that verifier can also calculate, it becomes able to describe Schnorr authentication protocol in the
non-interactive form:
Alice’s flow:
- Generate random key \(a\) and public \(A = aG\).
- Calculate challenge \(c = Hash(A)\).
- Calculates the response \(r = a + kc\).
- Send \((A, r)\) to the Bob.
Bob’s flow:
- Calculate challenge \(c = Hash(A)\).
- Check that \(rG = A + cK\).
Obviously, using such algorithm we can add the message to the challenge generation and get the signature algorithm.
So, later, using the Ed25519 curve, the EdDSA signature protocol has been presented:
Alice’s flow:
- Calculate \(a = Hash(Hash(k), m)\), \(ch = Hash(aG, K, m)\) and \(r = a + ch\cdot k\).
- Send signature \((aG, r)\).
Bob’s flow:
- Calculate \(ch = Hash(aG, K, m)\).
- Check that \(2^c\cdot rG = 2^c\cdot aG + 2^c ch\cdot K\). The \(2^c\) cofactor is used to increase the security of the
equation: it ensures that all points are in the lager prime curve subgroup.
05 Apr 2024
The Weierstrass normal form of elliptic curves (in fields with characteristic != 2 and != 3) \(y^2 = x^3 + ax + b\)
over \(Z_p\) field has found many applications in cryptography. But this curve form has also two types: non-singular (
that can be used in crypto) and singular (that can’t). Let’s take a look why singular curves causes problems in
cryptography.
Singular curves is the curves where discriminant is equal to zero, so \(4a^3 + 27b^2 = 0\)
In such cases, this curve can be represented in two forms (after variable replacement):
-
\(y^2 = x^3\) where using mapping \((x, y) \rightarrow \frac{x}{y}\) it gives an isomorphism to additive group (
with same order \(p\)) where discrete logarithm is trivial.
-
\(y^2 = x^2(x + c)\) where using mapping \((x, y) \rightarrow \frac{y + xc}{y - xc}\) it gives an isomorphism to
multiplicative group (with order \(p^2\)) where discrete logarithm problem is easy to solve for default elliptic key
sizes.
This both cases are perfectly overviewed in Section 2.10 of Washington’s Elliptic Curves: Number Theory and
Cryptography.
Here is an example how to solve discrete
logarithm problem for such curves.
01 Apr 2024
Zero-knowledge range proofs can be shortly introduced as one of the most important algorithms for confidential
transactions. After Bitcoin launch lots of cryptographers started to create the solutions to make blockchain
transactions more and
more anonymous and one of such solution was to hide user balances in cryptographic commitments (in particular - Pedersen
commitments). This approach requires the way to check that amounts in transaction corresponds to each other without
group order overflowing. That is why a wide variety of range proof protocols appeared.
The Bulletproofs protocol published in 2017 introduced how to verify value
range committed in Pedersen commitment. Later, Blockstream cryptographers introduces more efficient
protocol Bulletproofs+ that currently implemented in many different platforms
e.g - Monero.
The last protocol generation (Bulletproofs++) that is designed to be more efficient the ‘+’ version was introduced in
2022 paper. My partner, Mykhailo Sokolov, and I have spent the last three months
thoroughly studying this document in order to develop implementation libraries in Go and Rust that are suitable for use
in production projects.It was unexpected to find errors in the original document, rendering the described protocol
unusable in its current form. Consequently, we have developed a corrected version of the Bulletproofs++ protocol and are
currently in the process of drafting an article to showcase our revisions.
In conclusion, our solution has \(2G\) points advantage over existing Bulletproofs and Bulletproofs+ protocols on proving
of one 64-bit value and this advantage will increase for more values per proof.
| Protocol |
G |
F |
| BP |
16 |
5 |
| BP+ |
15 |
3 |
| Our BP++ |
13 |
3 |
Our implementation can be found here:
21 Mar 2024
Before blog creation, I used to share my experience via Medium articles, here are some of them:
Also, subscriptions are welcomed: @oleg.fomenko2002.