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...

Fully Homomorphic Encryption Part One: A Gentle Intro

Recently I have taken CS355 (Topics in Cryptography) at Stanford. This was a comprehensive course on advanced crypto topics.

Throughout the 3-month course, the instructors covered various topics that span the history of Cryptography, starting from One-way Functions, PRFs all the way to applied cryptosystems such as MPC, Zero-Knowledge, and PIR. This was really a great course to take, and I’ve surely learned a lot about modern cryptosystems.

In order to strengthen my understanding of these topics, I’ve decided to start a series of blog posts that (gently) introduces these cool crypto topics. I’ll be summarizing lecture notes and paraphrase them into my own words. Hopefully, it should be an interesting (and not obscure) read that helps you understand these topics as well.

For the first series of posts, I want to talk about Fully Homomorphic Encryption (FHE), a fairly hot topic in the security industry.

Note that I’ll try to make my explanation as simple as possible, but still make sure that you have some security/cryptography context before continuing…

Read more...