16 Feb 2022
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...

14 Feb 2022
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:

\[e = mc^2\]

02 Jul 2020
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...

22 Jun 2020
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...

16 Jun 2020
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...