Homomorphic Secret Sharing with Polynomial-Modulus LWE
"Explore homomorphic secret sharing using polynomial-modulus LWE, including share correctness, security considerations, additive reconstruction, branching programs, BKS multiplication procedure, share conversion, and correctness errors analysis."
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
On Homomorphic Secret Sharing from Polynomial-Modulus LWE Thomas Attema, Pedro Capit o and Lisa Kohl 9thMay 2023
Homomorphic Secret Sharing (HSS) ? Share Correctness: Correctness: Rec Eval?(??,Eval?(??)) = ? ? Security: Security: ??hides ?; ??hides ? Alice Alice Bob Bob ?? ?? A strong and useful form of reconstruction is additive reconstruction additive reconstruction: Rec ??,?? = ??+ ?? Eval? Eval? ?? ?? Example Example Linear functions: Linear functions: ? = ??+ ?? Eval?(??) = ?(??) Rec ??,?? = ??+ ?? Rec ?(?)
Branching programs Computational model: Computational model: Arithmetic circuits with restricted multiplication intermediate values intermediate values can only be multiplied by input values input values + Includes classes LOGSPACE, NC1 2-Party HSS for branching programs from DDH [Boyle,Gilboa,Ishai 16], LWE LWE [ [Boyle,Kohl,Scholl 19 Paillier [Orlando,Scholl,Yakoubov 21] Boyle,Kohl,Scholl 19] ],
BKS multiplication procedure [B Boyle,K Kohl,S Scholl 19] Input values ? encoded as ??= Enc(??,? ??); Intermediate values ? encoded as [? ??]?, [? ??]?: ? ?? = [? ??]?+[? ??]? Local multiplication procedure for ? ?: ?? ? ? ? (? ? ??) + ? [? ??]?,??= ? ? ??? ? [? ??]? Share conversion
Share conversion (simplified) Problem: Problem: How can we locally go from plaintext modulus ??+ ??=? ? < ? ?? + ? (mod?) to ciphertext/LWE modulus ??+ ??= ? (mod?) ?
BKS share conversion ? = Round(?)= ? ?/? ? = Lift(?)= ? ??+ ??=? ?? + ? (mod?) Round ??+ ??= ? (mod?) Lift ??+ ??= ? (mod?)
Correctness errors: Round Suppose ? ????, ? = 0, ??+ ??=? ?? + ? (mod?). If ??,?? BAD we can have R(??) + R(??) = 1 + 0 ? (mod?) Pr[?? BAD ] =| |BAD| | ? ?. = ???? ?
Correctness errors Error probability (per multiplication operation) is ? ?+???? ? . ? from lifting from rounding Negligible error requires ? ? ???? if we want additive reconstruction if we want additive reconstruction superpolynomial gaps
Our work: Alternative Rounding Alice: Alice: RoundDown(??)= ?? ?/? Bob: Bob: RoundUp(??)= ?? ?/? I m in I m in BAD I m in I m in BAD I was in I was in BAD Succeeds even for shares in BAD (but fails for shares close to a multiple of ?/?)
| |BAD| | = 2| |BAD| | = 2???? ? Alternative Rounding Alice: Alice: Bob: Bob: Note: Note:?? BAD ?? BAD both can use Round
| |BAD| | = 2| |BAD| | = 2???? ? Alternative Rounding Alice: Alice: ?? BAD? Bob: Bob: ?? BAD ? No Yes No Yes Round(??) RoundUp(??) RoundDown(??) Round(??) Round(??) ? ? Probability of this case is 2???? Note: Note:?? BAD ?? BAD both can use Round Similar procedure for Lifting!
Reconstruction Bob Bob Alice Alice ??,1,000000 ??,2,000001 ??,3,001000 ??,4,001010 (??,001000) ?? sequence of flags (0 for near rounding, 1 for up/down rounding) Output ? = ??+ ??,3
Summary of Results 2-party HSS for branching programs from LWE with small modulus New technique for error prevention Perfect correctness at the cost of variable running time Relaxed reconstruction, suitable for e.g. 2-server private database queries Efficiency improvement over [BKS19] (4x shorter shares)
