Problem 35 - An Introduction to Mathematical Cryptography

Question

Let \(E\) be an elliptic curve over a finite field \(\mathbb{F}_{q}\) and let \(\ell\) be a prime. Suppose that we are given four points \(P, a P, b P, c P \in E\left(\mathbb{F}_{q}\right)[\ell]\). The (elliptic) decision DiffieHellman problem is to determine whether \(c P\) is equal to \(a b P\). Of course, if we could solve the Diffie-Hellman problem itself, then we could compute \(a b P\) and compare it with \(c P\), but the Diffie-Hellman problem is often difficult to solve. Suppose that there exists a distortion map \(\phi\) for \(E[\ell]\). Show how to use the modified Weil pairing to solve the elliptic decision Diffie-Hellman problem without actually having to compute \(a b P\).

Step-by-Step Solution

Answer

Use the Weil pairing to compare \(e(aP, \phi(bP))\) and \(e(P, \phi(cP))\). If equal, then \(cP = abP\).

Step 1: Understand the Problem Context

We are given an elliptic curve \(E\) over a finite field \(\mathbb{F}_{q}\), and four points \(P, aP, bP, cP\) on this curve. The task is to determine if \(cP = abP\) using the Weil pairing without computing \(abP\) explicitly.

Step 2: Introduce the Modified Weil Pairing

The Weil pairing is a bilinear map \(e: E(\mathbb{F}_{q})[\ell] \times E(\mathbb{F}_{q})[\ell] \rightarrow \mu_{\ell}\), where \(\mu_{\ell}\) is the group of \(\ell\)-th roots of unity. The key property we will use is bilinearity: \(e(xQ, R) = e(Q, xR)\) for \(x \in \mathbb{Z}\).

Step 3: Apply the Distortion Map

Assume we have a distortion map \(\phi\) such that \(e(P, \phi(P)) eq 1\). A distortion map is a special type of map used to ensure that the Weil pairing does not degenerate to 1.

Step 4: Use the Pairing to Compare

Calculate the pairings \(e(aP, \phi(bP))\) and \(e(P, \phi(cP))\). The property of the Weil pairing tells us that if \(cP = abP\), then:\[e(aP, \phi(bP)) = e(P, \phi(cP))\]

Step 5: Conclusion of Comparison

By computing and comparing \(e(aP, \phi(bP))\) with \(e(P, \phi(cP))\), we can determine if \(cP = abP\) without directly calculating \(abP\). If the pairings are equal, then \(cP = abP\); otherwise, they are different.

Key Concepts

Weil Pairing

The Weil pairing is a foundational concept in elliptic curve cryptography, providing a powerful tool for working with points on an elliptic curve over finite fields. Essentially, it is a bilinear map denoted as \(e: E(\mathbb{F}_{q})[\ell] \times E(\mathbb{F}_{q})[\ell] \rightarrow \mu_{\ell}\), where \(\mu_{\ell}\) represents the group of \(\ell\)-th roots of unity.

This pairing has several important properties:

• **Bilinearity:** This means that \(e(xQ, R) = e(Q, xR)\) for any integer \(x\), which implies that the pairing respects scalar multiplication.
• **Non-degeneracy:** The Weil pairing will not map all pairs of points to the identity element of \(\mu_{\ell}\), unless one of the points is the identity element.

With these properties, the Weil pairing helps in computations related to elliptic curves, such as in algorithms for decision problems and cryptographic protocols.

Decision Diffie-Hellman Problem

The Decision Diffie-Hellman Problem (DDHP) is a significant problem in cryptography, particularly in the context of elliptic curves. It involves three key group elements \(g, g^a, g^b\) on an elliptic curve and an additional element \(g^c\).

The challenge is to determine whether \(g^c\) corresponds to the product \(g^{ab}\) without knowing \(a\) or \(b\). This decision problem is different from the Computational Diffie-Hellman (CDH) problem, which requires computing \(g^{ab}\).

When this problem is tackled on elliptic curves, it provides the foundation for many cryptographic protocols and ensures the security of key exchange systems by making it difficult to deduce private information from public keys.

Distortion Map

A distortion map is a special function applied within the context of elliptic curves to enhance the effectiveness of operations like the Weil pairing. Typically, if we have points \(P\) and \(Q\) on an elliptic curve, the standard Weil pairing \(e(P, Q)\) might sometimes degenerate, resulting in a trivial outcome, such as 1.

This is where the distortion map \(\phi\) becomes useful. It is designed to adjust the points such that \(e(P, \phi(P)) eq 1\), ensuring that the pairing remains non-trivial.

Utilizing a distortion map enables the pairing to achieve non-degenerate outcomes, which is crucial for certain cryptographic proofs and operations like verifying decision problems in elliptic curve cryptography. In practical terms, applying a distortion map ensures that pairings provide the necessary checks without resulting in identity values.

Finite Fields

Finite fields, also known as Galois fields, are a pivotal component of elliptic curve cryptography. A finite field \(\mathbb{F}_{q}\) is a set of finite elements where arithmetic operations such as addition, subtraction, multiplication, and division (except by zero) can be performed.

The simplicity and systematic structure of finite fields make them an ideal choice for cryptographic systems. They contain exactly \(q\) elements, where \(q = p^n\) for a prime \(p\) and a positive integer \(n\).

These fields possess unique properties:

• **Closure:** Performing an operation on two elements of the field yields another element within the same field.
• **Associativity and Commutativity:** Both addition and multiplication operations are associative and commutative.

These characteristics of finite fields allow them to support the complex arithmetic required for secure and efficient operations on elliptic curves, making them indispensable in the realm of cryptographic protocols and security systems.