Finite Field Implementations

A Study Club Talk

Algorithms for Fast Multiplication and Modular Reduction

​

​

If something isn’t clear, ask.

​

You can use the “raise hand” button or the chat window, but feel free to interrupt

Flashback… Intro to Finite Fields

Motivation

Why Finite Fields?

• Finite fields are the basis for (almost) all math we do in cryptography
• All operations in zero-knowledge proof systems are in finite fields
• Digital circuits use boolean operations (AND, OR, NOT)
• Arithmetic circuits use finite field operations (addition, multiplication, negation)

Implementations for Real Computers

• Real computers don’t have finite field circuitry
• ADD rax, rbx
• MUL rax
• SHR rax, CL
• …
• We need to build finite fields from these operations

Why is Speed Important?

• Proving cost is one of the largest barriers to ZKP availability
• Almost all of the proving time is spent on finite field operations
• Reduce the number of field operations (e.g. more efficient NTT or MSM algorithms).
• Make the field operations more efficient (e.g. by using optimized field representations).

Overview

In this study club we are going to talk about:

• BigInts
• Addition of BigInts
• Multiplication of BigInts
• Modular reduction (Barrett method)
• Montgomery form
• Multiplication and reduction (Montgomery method)
• Additional methods for multiplication

Big Integers

A.k.a BigInt or Multiprecision Integers

BigInt

• Real computers operator over words
• Almost all modern computers use 64-bit words
• 32-bit words are not completely gone
• You never know what you will find in the IoT world…
• Representing larger fields (e.g. 256 bits) is done by breaking it into words

BigInt

• Commonly you might have a 256-bit number in 4x 64-bit words.
• Let’s work with 8 (base-10) digit number and 4x 2-digit words.

BigInt

• Commonly you might have a 256-bit number in 4x 64-bit words.
• Let’s work with 8 (base-10) digit number and 4x 2-digit words.

BigInt Addition

BigInt Addition

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

BigInt Multiplication

BigInt Multiplication

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

BigInt Multiplication

Modular Reduction

• Both addition and multiplication result in larger values
• We want to reduce values back to their canonical representation

Modular Reduction

• We will talk about two methods:
• Barrett reduction
• Montgomery multiplication and reduction
• Montgomery multiplication and reduction is the most widely used
• Barrett reduction is useful when you can’t change representations

Barrett Reduction

• An obvious method for reduction is to use division
• However, division is expensive and may not be constant time

From the Wikipedia (Barrett Reduction)

def reduce(u uint) uint {

q := u / N # Division implicitly returns the floor of the result.

return u - q * N # N is the modulus

}

Barrett Reduction

• We can approximate division by the modulus (1/n) by (R/b^2n)
• We can calculate the R value to be be used as b^2n/N

From the Wikipedia (Barrett Reduction)

def mostly_reduce(a uint) uint {

q := (u * R) >> 2*n # ">> 2*n" denotes bitshift by 2*n.

return u - q * N

}

Barrett Reduction

• The result will be in the range [0, 3N)
• In order to get the fully reduced result in [0, N), we may need to subtract n.

From the Wikipedia (Barrett Reduction)

def reduce(a uint) uint {

q := (u * R) >> 2*n

u -= q * N # Reduce to an approximate answer.

while u >= N { # Final few additions to get fully-reduced answer.

u -= N

}

return u

}

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

Montgomery Form

• Montgomery Form is an alternative finite field representation.
• It enables a fast combined multiplication and reduction algorithm.

Montgomery Form

• So far we have represented finite field elements as:

​

​

​

​

• Montgomery representation is defined as:

Montgomery Reduction

• We’ll now define the Montgomery Reduction algorithm
• Note that it does not calculate the same reduction as before

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

Montgomery Reduction

• REDC is a very versatile formula
• Converting from Classical to Montgomery:

​

• Converting from Montgomery to Classical:

​

• Multiplication

Montgomery Multiplication and Reduction

From the Handbook of Elliptic and Hyperelliptic Curve Cryptography

A Quick Comparison of Finite Field Multiplication

Additional Multiplication Methods

• Multiplication was believed to have an asymptotic runtime of O(n^2)
• Karatsuba discovered a divide-and-conquer method with runtime O(n^1.58)
• Toom–Cook multiplication is similar and achieve slightly better results.
• Schönhage–Strassen later discovered an NTT method with
• Concretely slower until we get to large integers (e.g. in 4096-bit RSA keys)

Thanks for coming!

Feel free to ask any more questions!