# Code-based Cryptography and Fully Homomorphic Cryptosystems

This is the homepage for the crypto study group taking place in the spring 2010 at Århus University

Here can be found schedules of meetings, and links to reading material connected to each meeting. The [L] links are local caches of the papers, in case this page should outlive some of the linked ones.

## Schedule

### 1st Meeting - February 26th

Ivan on

- Error Correcting codes
- Goppa Codes
- The McEliece public key cryptosystem (correctness, security, relation to NLP-problem, random padding for chosen plaintext security).

- Definition of McEliece cryptosystem and proof of semantic security of the version with random padding: Ryo Nojima, Hideki Imai, Kazukuni Kobara, Kirill Morozov: Semantic security for the McEliece cryptosystem without random oracles[L]. Des. Codes Cryptography 49(1-3): 289-305 (2008)
- On the LPN problem: Jonathan Katz, Ji Sun Shin: Parallel and Concurrent Security of the HB and HB+ Protocols.[L] EUROCRYPT 2006: 73-87 contains in section 2.1-2.2 a proof that if LPN is hard, then LPN instances are indistinguishable from random.
- On definition of Goppa codes, see e.g. Dan Bernstein: List Decoding of Goppa codes[L] gives a review of Goppa codes and how they are defined. Gives also a (very compactly written) proof of the minimum distance. If you read it and get stuck, you can ask me (Ivan), I deciphered it once, can probably do it again..

### 2nd Meeting - March 5th

Jesper on *Fully Homomorphic Encryption over the Integers*

Subjects:

- Fully homomorphic encryption
- Correctness
- Circuit privacy
- Yao's garbled circuits
- Compacness
- Bootstrapping in Gentry's scheme
- Integer encryption, based on the approximate GCD problem (Regev 04)
- From a symmetric homomorphic scheme to assymetric homomorphic scheme (Isha's construction)
- Mention that we still need to "squash the decryption circuit" to make it bootstrappable

- A Proof of Security of Yao’s Protocol for Two-Party Computation[L]by Yehuda Lindell and Benny Pinkas.
- Fully homomorphic enryption over the integers[L] by Gentry et al.
- Gentry's PhD thesis[L]

### 3rd Meeting - March 12th

Sarah on *Public-Key Cryptographic Primitives
Provably as Secure as Subset Sum*

Location: **DI 5523-129**

Related reading:

- The paper from eprint[L] by Vadim Lyubashevsky, Adriana Palacio, and Gil Segev. (Published version[L], with a better layout.)

### 4th Meeting - March 19th

Location: **Ada 018**

Ivan on: classical additive homomorphic encryption
schemes, such as **Paillier** and (variants of) **El-Gamal**.

Related reading:

- A generalization of Paillier's Public-Key system with applications to electronic voting[L] by Damgård, Jurik and Nielsen. (Not the original published version, but perhaps more readable)

### QUARTER BREAK

After the quarter break we meet**Tuesdays**at

**14:15-16:00**always in

**Turing 014**

### 5th Meeting - April 13th 14:15-16:00

Location: Turing 014

Jesper on **outsourcing of computation** (short proofs that computations are correct)

- Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers[L] by Rosario Gennaro and Craig Gentry and Bryan Parno

### 6th Meeting - April 20th

Location: Turing 014

Sigurd on **public key crypto from LPN**

- More on average case vs approximation complexity[L] by Michael Alekhnovich
- On lattices, learning with errors, random linear codes, and cryptography[L] by Oded Regev

### 7th Meeting - April 27th

Location: Turing 014

Jesper on **fully homomorphic enryption continued**

- ...

### 8th Meeting - May 4th

Location: Turing 014

Ivan on the **BGN** scheme which is an elliptic curve based variant, which is additive
but allows for a single multiplication.

Related reading:

- Evaluating 2-DNF Formulas on Ciphertexts. TCC 2005: 325-341[L] by Boneh, Go and Nissim.

### May 11th

Due to Martins PhD defense, there will be no meeting this week

### 9th Meeting - May 17th

Location: Turing 014

Peter on **i-Hop Homomorphic Encryption Schemes**

Related reading:

- i-Hop Homomorphic Encryption Schemes[L] by Craig Gentry, Shai Halevi and Vinod Vaikuntanathan.

### 10th Meeting - May 25th

Location: Turing 014

Rikke on **A Simple BGN-type Cryptosystem from LWE**

- A Simple BGN-type Cryptosystem from LWE[L] by Craig Gentry and Shai Halevi and Vinod Vaikuntanathan.

## Participants

- Caro
- Claudio
- Gert
- Ivan
- Jesper
- Jakob
- Marcel
- Peter
- Rikke
- Sarah
- Sigurd
- Tomas

*Please contact Sigurd about the contents of this page.*