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 0145th Meeting - April 13th 14:15-16:00
Location: Turing 014
Jesper on outsourcing of computation (short proofs that computations are correct)
Related reading:- 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
Related reading:- 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
Related reading:- ...
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
Related reading:- 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.