8.1 Elliptic Curves over Finite Fields

Definition 8.1.1

An elliptic curve \(E\) over a field \(K\) is given by the Weierstrass equation:

\[ y^2 = x^3 + ax + b \]

where \(a, b \in K\) and \(4a^3 + 27b^2 \neq 0\)

Example: ECDSA Implementation

Consider the elliptic curve \(y^2 = x^3 + 2x + 2\) over \(\mathbb{F}_{17}\):

  1. First, we find a generator point \(G\)
  2. Generate private key \(d\)
  3. Compute public key \(Q = dG\)

8.2 Lattice-Based Cryptography

Definition 8.2.1: Lattices

A lattice \(\mathcal{L}\) is a discrete subgroup of \(\mathbb{R}^n\):

\[ \mathcal{L} = \left\{\sum_{i=1}^n x_i\mathbf{b}_i : x_i \in \mathbb{Z}\right\} \]

where \(\{\mathbf{b}_1, \ldots, \mathbf{b}_n\}\) is a basis of \(\mathcal{L}\)

Current Research

NIST’s Post-Quantum Cryptography standardization process has selected several lattice-based schemes as finalists:

  • CRYSTALS-Kyber (Key Encapsulation)
  • CRYSTALS-Dilithium (Digital Signatures)
  • FALCON (Digital Signatures)

Exercises

Theoretical Exercises

  1. Prove that the points on an elliptic curve form an abelian group under point addition.
  2. Show that the discrete logarithm problem is hard in the group of points on an elliptic curve.
  3. Analyze the security implications of quantum computers on RSA vs. elliptic curve cryptography.

Programming Projects

  1. Implement point addition on an elliptic curve over a finite field.
  2. Create a simple ECDSA implementation.
  3. Develop a basic lattice-based encryption scheme.

Self-Assessment Rubric

Topic Basic Intermediate Advanced
Elliptic Curves Understand curve equations Implement point operations Design cryptographic protocols
Lattices Define basic concepts Solve lattice problems Analyze security proofs

References

[1] Silverman, J. H. (2009). The Arithmetic of Elliptic Curves.

[2] Micciancio, D., & Goldwasser, S. (2002). Complexity of Lattice Problems.

[3] Bernstein, D. J., & Lange, T. (2020). Post-quantum cryptography.

[4] Washington, L. C. (2008). Elliptic Curves: Number Theory and Cryptography.