Sharing with you my paper with high-level overview of RingCT transactions in Monero. It covers the Pedersen commitments, Confidential assets, stealth addresses, ring signatures and the form of RingCT transaction.
Enjoy: RingCT explained
I can celebrate today cause my paper in co-author with Mike Sokolov and Alex Kurbatov has been released. Enjoy by the link https://distributedlab.com/whitepaper/Bulletproofs-Construction-and-Examples.pdf.
In addition to the post about Edwards curves, lats take a look on a useful feature that this curves allow. As I said earlier, the Ed25519 for example, is defined over \(F_{2^{255}-19}\) field, where every value requires 255 bit for the binary representation. So every point will take about 510 bit. Using the point compression algorithm, we can encode every point using only 256 bits by transferring only the \(y\) coordinate.
Using the Edwards curves equation \(ax^2 + y^2 = 1 + dx^2y^2\) we can express the \(x\) coordinate (with an assumption that \(a = -1\)) as \(x^2 = \frac{y^2 - 1}{dy^2 + 1}\), which means that \(x\) can have two possible solutions (+ and -). In the modular terms (since we have an odd modulo \(q\)) it means that \(x\) can have the odd and even representations. This information can be encoded into one bit.
Then, to decode the point coordinates, after separating parity bit from \(y\) coordinate, we have to calculate the root square. There are several methods to deal with the square root in \(F_q\). One of them is to use the feature that \(q = 2^{255} - 19 \equiv 5 (mod 8)\). In the \(F_q\) multiplicative group we have \(q - 1\) elements (then for every \(x \in F_q: x^q = x\)), so for every square \(\alpha = \beta^2\) we have \(\alpha^4 = \beta^8 \rightarrow \alpha^{p+3} = \beta^8 \rightarrow \alpha^\frac{p+3}{8} = \beta\). From the equation \(\alpha^4 = \beta^8\) we can observe that there can be two possible solutions \(\pm\alpha = \beta^2\). In the case when calculated \(\beta\) satisfies \(\beta^2 = -\alpha\) we should multiply it on \(\sqrt{-1}\).
For the \(\sqrt{-1}\) we can follow the same transformations: \(x^2 = -1 \rightarrow x^4 = 1 \rightarrow x^4 = 2^{q-1} \rightarrow x = 2^\frac{q-1}{4}\). The base \(2\) element was selected as the most comfortable element for multiplication.
So finally, for the equation \(x^2 = \frac{u}{v}\) we can calculate \(x' = \sqrt{u/v}\) and check that \(v\cdot x' = -u\) and if so multiply the \(x'\) on \(\sqrt{-1}\). On the final stage, we use the parity bit to check that we’ve recovered same coordinate with same parity.
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. So, it is obvious that our elliptic group has two subgroups and for the cryptography purposes wew always may select the group defined by the large prime \(l\).
Nevertheless, an attacker can select points from smaller subgroup and this points will be eligible for using in group operations. To ensure that this never can happen, in EdDSA protocol verifier additionally uses the \(2^c\) cofactor to increase the security of the equation \(2^c\cdot rG = 2^c\cdot aG + 2^c t \cdot K\). It ensures that all points are in the lager prime curve subgroup, otherwise multiplication by the cofactor results with infinite point.
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:
\(y^2 = x^3\) (when there is a triple root 0) 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)\) (when there is a double root 0) 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.
