A Gentle Introduction of NTT - Part I: Polynomial Multiplications as Convolutions

Polynomials are everywhere. In fact, in Computer Science, they are really just fancy lists of numbers that have a particular way of doing arithmetic.

For example, adding two polynomials is as simple as just summing up their coefficients. Multiplying a polynomial by a constant is just multiplying every coefficient by that constant.

However, when we want to multiply polynomials, things get slightly more complicated.

Read more...

PKPDSS: Permuted-Kernel-Problem-based Digital Signature Scheme

Based on: PKP-IDS, Permutation based identification protocol.

Idea: PKP is a problem where one is give a random matrix $A$ and a vector $v$. Then they are asked to find a permutation $\pi$ such that $A v_\pi = 0$, i.e. $v_\pi$ is the right kernel of $A$.

Finding such permutation $\pi$ is an NP-hard problem. However, we could use a 5-round public-coin interactive protocol to prove knowledge of the secret permutation $\pi$.

We will try to explore how PKP-IDS works, and then follow Beullens et. al. 2018 to compress PKP-IDS into PKP-DSS.

Read more...

Hello, Crypto

Bitcoin?

def mine_btc(block):
  while True:
    nonce = random.randbytes(32)
    if hashlib.sha256(block + nonce).digest().hex()[:8] == "00000000":
      print("I'm rich!")
      return

Or maybe some $\mathcal{math}$ helps:

Fully Homomorphic Encryption Part Three: Three Strawmans for the FHE Scheme

In my previous post, I went over how Lattice-based crypto works, as well as what Learning With Error (LWE) Problem is. In the end, we looked at how Regev Encryption works by putting the LWE problem together with an encryption scheme.

Hopefully, everyone should have a pretty solid understanding about these fundamental building blocks. Now we are finally ready to battle the archnemesis - building the actual FHE scheme.

Read more...

Fully Homomorphic Encryption Part Two: Lattice-based Crypto and the LWE Problem

Last time, we went through the overview of what FHE is, the different stages towards FHE, and the brief history of it. I think at this point, we should be pretty comfortable with understanding what FHE is and its potential applications.

We concluded the last post by alluding to this GSW FHE Scheme. It’s the 3rd Gen FHE Scheme based on the LWE Problem assumption which stems from Lattice-based Cryptography.

Although these topics might sound pretty archaic and distant, I claim that it’s actually not that hard to understand. In fact, with just simple knowledge in linear algebra, we can fully grasp the idea of the GSW FHE Scheme.

In this post, let’s together review some fundamental concept of Lattice-based Crypto and the LWE Problem so we can build up our knowledge to the actual GSW Scheme later.

Read more...