Constant-Time Big Numbers: An Introduction

submited by
Style Pass
2021-05-21 12:30:06

Over the past couple months, I’ve been working on a library for constant-time Big Numbers in Go. I think it’s about time that I presented a bit of this work.

In this post, I’ll try to explain what exactly this work is about, and why you might care about it. This post is intended to be an introduction, and shouldn’t require any background in Cryptography.

This work is being done as a BSc project at EPFL’s DEDIS lab, under the supervision of Professor Bryan Ford, and would not be possible without their generous help.

As the title suggests, the main concept here is a “Big Number”. Essentially, Big Numbers are nothing more than a way to program with arbitrarily large integers.

The usual integers you use in programming have a fixed size. Big Numbers, on the other hand, have to be dynamically sized. For example, a uint64 type represents integers from $0$ up to $2^{64}$, consuming $64$ bits of memory. A Big Natural Number type would instead be able to represent all numbers in $\mathbb{N}$. This requires a type that grows in size to represent larger numbers.

Big Numbers are actually a familiar concept. As programmers, we’re used to working with fixed size integers. This is an acquired taste. The natural way you’d think about numbers isn’t constrained in this way. Most people don’t see numbers as having an arbitrary upper bound; numbers seem to go on forever:

Leave a Comment