Public-key Encryption and LWE: Foundations and Security Theorems
Covering topics such as public-key encryption from LWE, homomorphic encryption, LWE with small secrets, and security theorems. The lecture explores the complexities and applications of cryptographic systems built on lattice-based assumptions, delving into encryption schemes, key generation, decryption processes, and the security implications of decisional LWE. Mathematical proofs and principles are illustrated through visual aids and explanation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
MIT 6.875 Foundations of Cryptography Lecture 19
TODAY: 1. Public-key Encryption from LWE and 2. Homomorphic Encryption
LWE with Small Secrets s and e A Given: A + GOAL: Find s. Parameters: dimensions ? and ?, modulus ?, error distribution ? = uniform in some interval [ ?, ,?]. ? ?, s from A is chosen at random from ? ??and e from ??.
LWE with Small Secrets s and e A Given: A + GOAL: Find (the small secret) s. Theorem: LWE with small secrets is as hard as LWE. Proof on the board.
Public-key Encryption [Regev05, Micciancio 10, Lyubashevsky-Peikert-Regev 10] Secret key sk = Small secret sfrom ?? Public key pk: for ? ???? 1 ?? ? ??= (??, ??,? + ??)
Public-key Encryption [Regev05, Micciancio 10, Lyubashevsky-Peikert-Regev 10] Secret key sk = Small secret sfrom ?? Public key pk: for ? ???? 1 ?? ? , A s+e A (?,? = ?? + ?) Encrypting a message bit ?: pick a random vector ? from ?? (?? + ? ,?? + ? + ? ?/2 ) Decryption: compute (?? + ? + ? ?/2 ) ?? + ? ? and round to nearest multiple of q/2.
Correctness Encrypting a message bit ?: pick a random vector ? from ?? (?? + ? ,?? + ? + ? ?/2 ) Decryption: (?? + ? + ? ?/2 ) ?? + ? ? = ?(?? + ?) + ? + ? ?/2 ?? + ? ? = ?? + ? ? ? + ? ?/2 Decryption works as long as |?? ? ? + ? | <? ?.
Security Theorem: under decisional LWE, the scheme is IND- secure. In fact, even more: a ciphertext together with the public key is pseudorandom. We show this by a hybrid argument. Let s stare at a public key, ciphertext pair. ?,? = ?? + ? ,? = ??? ??,? = ?? + ? ,?? + ? + ? ?/2 ) ?? = Call this distribution Hybrid 0.
Security Theorem: under decisional LWE, the scheme is IND- secure. In fact, even more: a ciphertext together with the public key is pseudorandom. Hybrid 1. Change the public key to random (from LWE). ?? = ?,? , ? = ??? ??,? = ?? + ? ,?? + ? + ? ?/2 ) Hybrids 0 and 1 are comp. indist. by decisional LWE.
Security Theorem: under decisional LWE, the scheme is IND- secure. In fact, even more: a ciphertext together with the public key is pseudorandom. Hybrid 2. Change ?? + ? ,?? + ? into random. ?? = ?,? , ? = ??? ??,? = ? ,? + ? ?/2 ) Hybrids 1 and 2 are comp. indist. by LWE.
Security Theorem: under decisional LWE, the scheme is IND- secure. In fact, even more: a ciphertext together with the public key is pseudorandom. Hybrid 2. Change ?? + ? ,?? + ? into random. ?? = ?,? , ? = ??? ??,? = ? ,? + ? ?/2 ) Now, we have the message ? encrypted with a one-time pad which perfectly hides ?.
Public-key Encryption [Regev05] Secret key sk = Small secret sfrom ?? Public key pk: for ? ???? 1 ?? ? (?,? = ?? + ?) Encrypting a message bit ?: pick a random vector ? from ?? (?? + ? ,?? + ? + ? ?/2 ) Decryption: compute (?? + ? + ? ?/2 ) ?? + ? ? and round to nearest multiple of q/2.
Application 1. Secure Outsourcing Input: x Program: P Enc(x) x Enc(P(x)) P(x) Client Server (the Cloud) A Special Case: Encrypted Database Lookup also called private information retrieval (next lec)
Application 2. Secure Collaboration Hospital ID Genome ID Phenotype Parties learn the genotype-phenotype correlations and nothing else
Homomorphic Encryption: Syntax (can be either secret-key or public-key enc) 4-tuple of PPT algorithms (???,???,???,????) s.t. ??,?? ??? 1?. PPT Key generation algorithm generates a secret key as well as a (public) evaluation key. Encryption algorithm uses the secret key to encrypt message ?. ? ??? ??,? . Homomorphic evaluation algorithm uses the evaluation key to produce an evaluated ciphertext ? . ? ???? ??,?,? . Decryption algorithm uses the secret key to decrypt ciphertext ?. ? ??? ??,? .
Homomorphic Encryption: Correctness ???(??,???? ??,?,???(?)) = ?(?). ?(?) ? ??? ??? ? ? ????( ,?, )
Homomorphic Encryption: Security Input: x Function: f Enc(sk,x) Enc(f(x)) ? Client Server (the Cloud) Security against the curious cloud = standard IND- security of secret-key encryption Key Point: Eval is an entirely public algorithm with public inputs.
Here is a homomorphic encryption scheme ??, ??? 1?. Use any old secret key enc scheme. Just the secret key encryption algorithm ? ??? ??,? . Output ? = ? || ?. So Eval is basically the identity function!! ? ???? ??,?,? . Parse ? = ?||? as a ciphertext concatenated with a function description. Decrypt ? and compute the function ?. ? ??? ??,? . This is correct and it is IND-secure.
Homomorphic Encryption: Compactness The size (bit-length) of the evaluated ciphertext and the runtime of the decryption is independent of the complexity of the evaluated function. A Relaxation: The size (bit-length) of the evaluated ciphertext and the runtime of the decryption depends sublinearly on the complexity of the evaluated function.
How to Compute Arbitrary Functions For us, programs = functions = Boolean circuits with XOR (+ ??? 2) and AND ( ??? 2) gates. ???((?1+ ?2)?3?4) X ???(?3?4) ???(?1+ ?2) X + ???(?3) ???(?4) ???(?1) ???(?2) Takeaway: If you can compute XOR and AND on encrypted bits, you can compute everything.
