<style> .reveal { font-size: 26px; font-family: { "Helvetica Neue", "Microsoft JhengHei"}; } </style> ++Group report on 12/8++ # CKKS: a leveled HE scheme ### Chun-Yu Lin -- - [[CKKS16]](https://eprint.iacr.org/2016/421) HE for Arithmetic of Approximate Numbers - [[CKKS_rns18]](https://eprint.iacr.org/2018/931) A Full RNS Variant of Approximate HE - [[MK_SIMD19]](https://eprint.iacr.org/2019/524) Efficient **Multi-Key** HE with **Packed Ciphertexts** with Application to Oblivious NN Inference - HE SIMD [[GHS_pack11]](https://eprint.iacr.org/2011/566) [[HE_SIMD11]](https://eprint.iacr.org/2011/133) [USE case](http://homomorphicencryption.org/wp-content/uploads/2018/10/CCS-HE-Tutorial-Slides.pdf) ### Shamir's Secret Sharing - Idea: N-point uniquly define a ploy(N-1) --- ### SVP - Close conectin with LWR - [Definition](https://web.eecs.umich.edu/~cpeikert/lic13/lec02.pdf) - LWE is hard for given q with large dimensions. --- ### Multi-party FHE: Threshould FHE - Round 1: A of key generation completed. - Joint public key for (s_a + s_b) is generated... - Joint evaluation multiplication key for (s_a + s_b) is generated... - Joint evaluation multiplication key (s_a + s_b) is transformed into s_b*(s_a + s_b)... - Joint evaluation summation key for (s_a + s_b) is generated... Round 3 (party A) started. - Joint key (s_a + s_b) is transformed into s_a*(s_a + s_b)... - Computing the final evaluation multiplication key for (s_a + s_b)*(s_a + s_b)... (Ref: https://palisade-crypto.org/wp-content/uploads/2020/10/PALISADE-10-30-MULTIPARTY.pdf) --- ## IBM's HELib: * Based on RLWE problem (cf. Gentry's original scheme based on ideal lattices) * [Github](https://github.com/homenc/HElib) * [Algorithm paper](https://eprint.iacr.org/2014/106.pdf) * [Bootstrapping paper](https://eprint.iacr.org/2014/873.pdf) * Implement * Brakerski-Gentry-Vaikuntanathan (BGV) scheme with bootstrapping * Approximate Number scheme of CKKS * Smart-Vercauteren ciphertext packing techniques * Gentry-Halevi-Smart optimizations * Secure Gaussian randomness distribution not yet implemented --> no security proofs ?!? * In 2015 iDASH Secure Genome Analysis Contest --- ## PALISADE * Support * BFV/BGV for integer arithmetic * CKKS for real-number arithmetic * Ducas-Micciancio (FHEW) and Chillotti-Gama-Georgieva-Izabachene (TFHE) for Boolean circuit evaluation * Stehle-Steinfeld scheme for limited integer arithmetic * Multi-Party Extensions of FHE (for multi-key FHE) * Threshold FHE for BGV, BFV, and CKKS schemes * Proxy Re-Encryption for BGV, BFV, and CKKS schemes * Digital Signature... * Identity-Based Encryption (cf. grid secure infra ) ... * Ciphertext-Policy Attribute-Based Encryption (can do implicit authorization)... --- ## Related to other concepts: * Obfuscation: (that key in the black box may have secure issue) * Functional Encryption: --- ## Improved RNS * [RNS variant of BFV](https://eprint.iacr.org/2018/117.pdf) * Involve operation on large cyclotomic ring --- ## Limitations: * Multiple users -- multi-key FHE * Complex algorithms (HE of Turing machines instead of circuits?) * FHE does not imply secret function evaluation? (it's obfuscation or circuit privacy that keep algorithm secure..) --- ## Applications * Non-interactive Zero Knowledge Proofs * Delegation, Oursourcing of Computation * Signatures * Multiparty Computation --- ## Reference: * Courses: * [Lattices Algorithms and Applications](https://cseweb.ucsd.edu/classes/wi10/cse206a/) * http://tau-crypto-f13.wikidot.com/course-schedule * [An Intensive Introduction to Cryptography](https://intensecrypto.org/public/index.html) by Boaz --- ## Example: Multiparty computation * What's the adversary? (Assume Honest but curious ) --- ## Senario: * Single-key HE (Data owner outsources computing with a single key.) * For multiple data owner senerio: * Multi-key: each party (data/model owner) has its own pk/sk, and decrypt the final answer collectively. * Threshould HE: all interact to gen joint $pk=pk_1+pk_2+...$ w/ sk for each party. The "full-sk" is unseem by anyone. --- ## Threshould HE * RNS (Residul Number System): x represented by $x_i$ that $x = x_i \mod m_i$, allowing efficient computation in 64-bit CPU.