FHE Meeting #1: kickoff

Education FHE kindergarten
1

Date: 17.08.23
Time: 4pm CEST
Reading materials:

1 Like
2

Let’s skip the last paper from the list, it doesn’t seem to be super relevant. If you want to read more stuff, consider taking a look at the fresh FHE blogposts (optional):

3

For the skipped paper, this one looks like (one of) the main contribution(s).

Let g\colon M \to V be a nonconstant function m. Assume that the message space M has some probability distribution. Accordingly, let p_v = \mathrm{prob}\bigl(g(m) = v \mid m \in M\bigr) for each v \in V, and let \bar v \in V be such that p_{\bar v} = \max_{v \in V} p_v. Then, without any special ability, an adversary given the cyphertext, can always guess the value of g over the cleartext and be correct with probability p_{\bar v}. We prove that for a probabilistic encryption scheme, an adversary, given the cyphertext, cannot guess the value of g over the cleartext with probability better than p_{\bar v}. Note that g needs not be polynomially computable, or even recursive. Thus, our encryption model passes a polynomially bounded version of Shannon’s perfect secrecy definition […].

This property enabled Goldwasser and Micali [11] to device a scheme for Mental Poker for which, under the Quadratic Residuosity Assumption, no partial information about cards that should remain hidden can be easily computed.

1 Like
4

Here’s a course for modern cryptography in general.

https://www3.cs.stonybrook.edu/~omkant/CSE594_S17G_Modern_Cryptography.html

1 Like
5

We had the first FHE kindergarten meeting today! :tada:

Attendees: Terence, Park, Patrick, Tobias, Yulia, James (partially)

Notes

Introduction to HE

Homomorphic encryption refers to encryption schemes that allow performing operations on encrypted data. Usually we talk about addition and multiplication.

There are three types of FHE algorithms:

  • partial HE - can do addition or multiplication, but not both (e.g. El Gamal, Paillier).
  • somewhat HE - can do both, but limited amount of times (e.g. Boneh et al.).
  • fully HE - can do both unlimited amount of times (e.g. Gentry09).

The problem with FHE is that performing addition and multiplication on encrypted data increases the amount of noise in the data. After a certain point the amount of noise is so high that it starts to interfere with plaintext and decryption might give a wrong result. Bootstrapping is way to reduce the noise in encrypted data.

On data banks and privacy homomorphisms

Imagine a loan company that is sharing a computer with other companies. How to protect the data processed on this computer? The authors come up with 4 options, which include HE, which they refer to as privacy homomorphisms.

So privacy homomorphism is a homomorphism that translates data between the algebraic systems of a user and a computer so that there is a mapping between operations of these systems and it preserves privacy.

Fact: if there is a way to compare encrypted data to known constants, privacy homomorphism doesn’t preserve privacy.

Open questions:

  • Can we see FHE as a category?
  • Do we want to have homework? Tobias volunteered to prepare exercises, so far they are optional