Learning with Aleo. Implementation of a ZK Protocol Based on the Open Key Agreement Scheme Using Mersenne Primes
Cyclic groups of prime order can be represented by the multiplicative groups of finite fields GF(2^s) of binary polynomials for certain values of the degree s. The order of the multiplicative group of such fields equals
The value 2^s — 1 is prime if s is a Mersenne exponent (a prime number s for which 2^s — 1 is also a prime number).
For the following values of the degree s ≥ 1024, we have prime values of q: 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, etc. Many more values of s ≥ 44497 have been found that define Mersenne primes, but they are currently of less interest for use in ZK protocols due to the significant increase in computational complexity. The multiplication operation in GF(2^s) fields is carried out by polynomial multiplication modulo an irreducible polynomial of degree s. To reduce the computational complexity of multiplication in GF(2^s), an irreducible polynomial of degree s with a small weight (few non-zero coefficients) should be chosen, and modular polynomial multiplication performed. Table 1 shows examples of irreducible binary trinomials of Mersenne degrees. These polynomials are of interest for use in implementing authentication protocols with zero secret disclosure based on open key agreement schemes.
Table 1: Dependence of Irreducible Binary Polynomials of Small Weight on the Mersenne Degree
Values of degree s = 1279 and s = 2203 are of practical interest for implementing a ZK protocol. Examples of irreducible binary trinomials of these degrees are:
and
as well as the pentanomial:
Using these trinomials η1(x) and η2(x) as the modulus, the modular multiplication of binary polynomials in GF(2¹²⁷⁹) can be carried out by one operation of arithmetic multiplication of polynomials, two operations of arithmetic shift, and six operations of addition. The operation of polynomial division is not required, significantly reducing the complexity of computations in GF(2¹²⁷⁹) and increasing the protocol’s performance. In GF(2²²⁰³), multiplication can also be performed without polynomial division, as it is implemented by one operation of arithmetic multiplication of polynomials, six operations of arithmetic shift, and ten operations of addition.
In the two-step authentication protocol based on the difficulty of discrete logarithm problems in GF(2¹²⁷⁹), the public key is formed using the formula:
where s is the secret key and α(x) is a specified polynomial. The protocol is described as follows:
1. The verifier generates a random number k and computes the polynomial request
and the polynomial:
then transmits the binary polynomial u(x) to the prover as their request.
2. The prover calculates:
and sends it back to the verifier as a response.
If z’(x) = z(x), the verifier concludes the authenticity of the prover. In this version of the protocol, there is no need to verify the correctness of the request, as any non-zero bit string interpreted as an element of GF(2¹²⁷⁹) has an order equal to the prime number 2¹²⁷⁹ — 1, i.e., no requests from the verifier can be used to obtain even a single bit of key information.
Practical interest lies in implementing this protocol using ideal elliptic curves (all points of which, except the point at infinity, have the same order value equal to a prime number) instead of finite multiplicative groups of binary polynomials. Such a replacement of the used finite group of prime order significantly reduces the computational complexity of the protocol while maintaining a given level of robustness.
Stay curious, keep learning, and delve deeper into the Aleo ecosystem — the journey is just beginning. Join the community here:
