Homomorphic Encryption and RLWE Schemes Overview

Homomorphic encryption allows computation on encrypted data, enabling privacy in outsourced computing services and applications like spam filters for encrypted mail. The Ring Learning With Errors (RLWE) scheme and its properties are discussed, along with symmetric encryption from RLWE and fully homomorphic encryption (FHE) that allows unlimited computation on encrypted data. Various encryption schemes and their capabilities are highlighted in this comprehensive overview.

• Encryption
• Homomorphic
• RLWE
• Schemes
• Privacy

galletta_n Follow

Uploaded on Sep 14, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Homomorphic Encryption from RLWE Schemes and Parameters Joppe W. Bos Microsoft Research Contains joint work with Kristin Lauter, Jake Loftus and Michael Naehrig

2. Computing on Encrypted Data Motivation Outsource data and computation to an external computing service. http://www.wickedreport.com/images/Dangerous-Beauty09.jpg Applications Spam filter for encrypted mail Searching on encrypted data Building block in crypto protocols

3. Homomorphic Encryption RSA multiplicatively homomorphic ?1= ?1 ?1 ?2= ?1 Multiplying ?1,?2 gives encryption of ?1 ?2 ?mod ? ?= ?1 ?2 ?mod ?, ?2= ?2 ? ?2 ?mod ? Benaloh additively homomorphic ?1= ??1?1 ?1 ?2= ??1+?2 ?1?2 Multiplying ?1,?2 gives encryption of ?1+ ?2 ?mod ? ?mod ?, ?2= ??2?2 ?mod ?

4. Fully Homomorphic Encryption (FHE) Enables unlimited computation on encrypted data Need scheme with unlimited add and mult capability Idea: Rivest, Adleman, Dertouzos (1978) Boneh-Goh-Nissim (2005): unlimited add + 1 mult Breakthrough: Gentry (2009) showed such schemes exist A lot of progress since then Gentry, Halevi, Smart (2012): homomorphic evaluation of AES 5 minutes per block (16 bytes)

5. Ring Learning With Errors (RLWE) (Lyubashevsky, Peikert, Regev 2010) Ring (?,+, ), modulus ?, ??= ?/??, probability distribution on ? (for sampling small elts) Problem: distinguish between two distributions 1. Uniform distribution (?,?) ?? 2. The distribution that for a fixed ? samples ? ?? uniformly, error e and outputs (?,? ? + ?) 2 Assumption: The RLWE problem is hard, i.e. ?,? ? + ? ~ ?,? looks random

6. (Symmetric) Encryption from RLWE Message ? 0,1 ? secret key BV (Brakerski, Vaikuntanathan 2010) encryption: Sample ? ?? uniform, ? error/noise b = ? + ? ? + 2? mod ?, ciphertext c = a,b (? + 2?) mod 2 = ? decrypts correctly if ? <? decrypt: ? ? ? mod 2 = 2 m 2e q

7. Homomorphic Properties c1= a1,?1+ ?1 ? + 2?1, c2= a2,?2+ ?2 ? + 2?2 Addition: ?1+ ?2= (?1+ ?2, ?1+ ?2 + (?1+ ?2) ? + 2(?1+ ?2)) Multiplication (BV): ?1 ?1 ? ?2 ?2 ? = (?1+2?1)(?2+2?2) = ?1?2+ 2(?1?2+ ?2?1+ 2?1?2) ?1 ?1 ? ?2 ?2 ? = ?1?2 ?1?2+ ?2?1? + ?1?2?2 New ciphertext: (?1?2, ?1?2+ ?2?1, ?1?2) now 3 elements!

8. Noise Growth Initial noise: ? Addition: noise terms add up, ? 2? Multiplication: noise terms are multiplied, ? ?2 ? ?4 ?4> 2 ?1?2?3?4 ? ?2 ?3?4 ?2> 2 ?1?2 ? ?> 2 ?1 ?2 ?3 ?4 ? ?2 ?4, ?4 ?8, ,?2? 1 ?2?(L levels of mult)

9. Exponential Improvement Brakerski, Gentry, Vaikuntanathan (BGV, 2010) Modulus Switching: Switch to a smaller modulus after each mult Need a chain of moduli ? = ?0,?? ?? 1 ? ?3=?2 ? ? ?> 2 ?1?2?3?4 ?2=?1 ? ?3?4 ? ?> 2 ?1?2 ? ?=?0 ?1 ?2 ?3 ?4 ? ?> 2 ?2 ?3 ?4, , ??(L levels of mult) Leveled fully-homomorphic encryption

10. Annoying Things in BGV Ciphertexts expand upon multiplication Need a complicated relinearization step (key switching) Need modulus switching to get reasonably small noise growth Can we do without modulus switching? Can we avoid ciphertext expansion? Can we achieve both at the same time?

11. Avoiding Modulus Switching Message ? 0,1 ? secret key Regev (2005) encryption: Sample ? ?? uniform, ? error or noise ? = 2? + ? ? + ? mod ?, ciphertext c = a,b ? ? ? = 2? + ?, decrypt: decrypts correctly if ? <? ? ? 2 q(? ? ?) 4. (q/2)m e q

12. Scale-invariant Multiplication Multiplication (Regev 05): ?1 ?1 ? ?2 ?2 ? = ( ? 2 2 ?1 ?1 ? ?2 ?2 ? = ? 2?1+ ?1)( ? 2?2+ ?2) 2 ? 2(?1?2+ ?2?1) + ?1?2 ? 2?1?2 ? 2 = ?1?2+ 1 ? 1 + ?1?2+ ?2?1 + ?1?2 New noise term is of size ? ?, after ? levels ?? ? ? independent of ?

13. Keeping Ciphertexts at One Element Message ? 0,1 Sample ? ,? key, ? = 1 + 2? secret key, public key =2? (asymmetric scheme) ? NTRU-like encryption (Stehl , Steinfeld 2011): Encryption: Sample s,? err c = ? 2? + ? + ? mod ? ? = q? ? mod 2, since ? ? = 2? + ?, decrypts correctly if ? <? 2 Decryption: ? 2.

14. New Leveled Homomorphic Scheme What we have been doing over the summer No modulus switching: only one modulus Ciphertexts have only one element (half the size of BGV) No ciphertext expansion after homomorphic multiplication Still secure under RLWE (good security properties) Parameters comparable to BGV

15. Parameters Correctness via noise bounds Security via estimating runtime of attack on scheme in time 280 ? = ? ? / ?? , ? = 2,? = (?) of the polynomial ??

16. Thank you! Questions?