Higashi.blog Random notes on cryptography and engineering

Hello, Crypto


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

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

\[e = mc^2\]

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.


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.

water droplets on glass window


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…


Mesmerizing Chameleon Signatures

This is a mirror of my post at https://medium.com/@stevenyue/mesmerizing-chameleon-signatures-4cdb3c8ab1c3.

For the past year, I having been taking classes at Stanford under Professor Dan Boneh and learning about different topics in the field of Cryptography. It has truly become an amazing journey. There are so many marvelous ideas in this field and a lot of them essentially reshaped the world.

Therefore I decided to start writing about what I have learned in a series of posts. This first post is actually a summary of an old paper that I recently read.


Signature schemes are essential to our daily lives. Before computers have existed, we have been signing off papers and documents with our names for a long time. A proper signature simply represents identity and authenticity. Digital Signature is essentially the same idea but in the world of computers. A signature proves the validity of what we say.

Aside from signatures, there’s also this idea of a Commitment scheme. A hash function is a commitment scheme, as long as it’s hard to produce collisions. Similar to signatures, a commitment proves that we are “committed” to some value. But on the other hand, it also hides the value of it. A valid commitment scheme should satisfy two properties:

  • Binding: A commitment can only bind to one value. It’s impossible to produce another value that also aliases to the same commitment.
  • Hiding: A commitment should hide its committed value. By just looking at the commitment itself, the observer should have no way to regain knowledge of the committed value.

Signatures and commitments are equally important in our digital lives. Today I want to talk about a special kind of signatures that leverages a beautiful commitment scheme — Chameleon Signatures.