publications
See also Google Scholar and DBLP.
Authors are listed in alphabetical order by last name, unless an asterick(*) is indicated. [AMS Statement]
conference & journal articles
2024
- IACR CiCBit Security as Cost to Demonstrate AdvantageKeewoo LeeIACR Communications in Cryptology, 2024
We revisit the question of what the definition of bit security should be, previously answered by Micciancio-Walter (Eurocrypt 2018) and Watanabe-Yasunaga (Asiacrypt 2021). Our new definition is simple, but (i) captures both search and decision primitives in a single framework like Micciancio-Walter, and (ii) has a firm operational meaning like Watanabe-Yasunaga. It also matches intuitive expectations and can be well-formulated regarding Hellinger distance. To support and justify the new definition, we prove several classic security reductions with respect to our bit security. We also provide pathological examples that indicate the ill-definedness of bit security defined in Micciancio-Walter and Watanabe-Yasunaga.
- USENIX SecVeriSimplePIR: Verifiability in SimplePIR at No Online Cost for Honest ServersLeo de Castro, Keewoo LeeIn USENIX Security Symposium, 2024
We present VeriSimplePIR, a verifiable version of the state-of-the-art semi-honest SimplePIR protocol. VeriSimplePIR is a stateful verifiable PIR scheme guaranteeing that all queries are consistent with a fixed, well-formed database. It is the first efficient verifiable PIR scheme to not rely on an honest digest to ensure security; any digest, even one produced by a malicious server, is sufficient to commit to some database. This is due to our extractable verification procedure, which can extract the entire database from the consistency proof checked against each response. Furthermore, VeriSimplePIR ensures this strong security guarantee without compromising the performance of SimplePIR. The online communication overhead is roughly 1.1-1.5x SimplePIR, and the online computation time on the server is essentially the same. We achieve this low overhead via a novel one-time preprocessing protocol that generates a reusable proof that can verify any number of subsequent query-response pairs as long as no malicious behavior is detected. As soon as the verification procedure rejects a response from the server, the offline phase must be rerun to compute a new proof. VeriSimplePIR represents an approach to maliciously secure cryptography that is highly optimized for honest parties while maintaining security even in the presence of malicious adversaries.
2022
- EurocryptLimits of Polynomial Packings for Z_{p^k} and F_{p^k}Jung Hee Cheon, Keewoo LeeIn Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt), 2022
We formally define polynomial packing methods and initiate a unified study of related concepts in various contexts of cryptography. This includes homomorphic encryption (HE) packing and reverse multiplication-friendly embedding (RMFE) in information-theoretically secure multi-party computation (MPC). We prove several upper bounds or impossibility results on packing methods for Z_{p^k} or F_{p^k}-messages into Z_{p^t}[x]/f(x) regarding (i) packing density, (ii) level-consistency, and (iii) surjectivity. These results have implications on recent development of HE-based MPC over Z2k secure against actively corrupted majority and provide new proofs for upper bounds on RMFE.
- JKMSOn the Scaled Inverse of (x^i-x^j) modulo Cyclotomic Polynomial of the form Φ_{p^s}(x) or Φ_{p^s q^t}(x)Journal of the Korean Mathematical Society, 2022
The scaled inverse of a nonzero element a(x)∈Z[x]/f(x), where f(x) is an irreducible polynomial over Z, is the element b(x)∈Z[x]/f(x) such that a(x)b(x)=c mod f(x) for the smallest possible positive integer scale c. In this paper, we investigate the scaled inverse of (x^i-x^j) modulo cyclotomic polynomial of the form Φ_{p^s}(x) or Φ_{p^s q^t}(x), where p, q are primes with p<q and s, t are positive integers. Our main results are that the coefficient size of the scaled inverse of (x^i-x^j) is bounded by p-1 with the scale p modulo Φ_{p^s}(x), and is bounded by q-1 with the scale not greater than q modulo Φ_{p^s q^t}(x). Previously, the analogous result on cyclotomic polynomials of the form Φ_{2^n}(x) gave rise to many lattice-based cryptosystems, especially, zero-knowledge proofs. Our result provides more flexible choice of cyclotomic polynomials in such cryptosystems. Along the way of proving the theorems, we also prove several properties of {x^k} in Z[x]/Φ_{pq}(x) which might be of independent interest.
2021
- CryptoMHz2k: MPC from HE over Z2k with New Packing, Simpler Reshare, and Better ZKPJung Hee Cheon, Dongwoo Kim, Keewoo LeeIn Annual International Cryptology Conference (Crypto), 2021
We propose a multi-party computation (MPC) protocol over Z2k secure against actively corrupted majority from somewhat homomorphic encryption. The main technical contributions are: (i) a new efficient packing method for Z2k-messages in lattice-based somewhat homomorphic encryption schemes, (ii) a simpler reshare protocol for level-dependent packings, (iii) a more efficient zero-knowledge proof of plaintext knowledge on cyclotomic rings Z[X]/Φ_M(X) with M being a prime. Integrating them, our protocol shows from 2.2x upto 4.8x improvements in amortized communication costs compared to the previous best results. Our techniques not only improve the efficiency of MPC over Z2k considerably, but also provide a toolkit that can be leveraged when designing other cryptographic primitives over Z2k.
- IEEE Access*Accelerating Fully Homomorphic Encryption Through Architecture-Centric Analysis and OptimizationWonkyung Jung, Eojin Lee, Sangpyo Kim, Jongmin Kim, Namhoon Kim, Keewoo Lee, Chohong Min, Jung Hee Cheon, Jung Ho AhnIEEE Access, 2021
Homomorphic Encryption (HE) draws a significant attention as a privacy-preserving way for cloud computing because it allows computation on encrypted messages called ciphertexts. Among numerous HE schemes proposed, HE for Arithmetic of Approximate Numbers (HEAAN) is rapidly gaining popularity across a wide range of applications because it supports messages that can tolerate approximate computation with no limit on the number of arithmetic operations applicable to the corresponding ciphertexts. A critical shortcoming of HE is the high computation complexity of ciphertext arithmetic; especially, HE multiplication (HE Mul) is more than 10,000 times slower than the corresponding multiplication between unencrypted messages. This leads to a large body of HE acceleration studies, including ones exploiting FPGAs; however, those did not conduct a rigorous analysis of computational complexity and data access patterns of HE Mul. Moreover, the proposals mostly focused on designs with small parameter sizes, making it difficult to accurately estimate their performance in conducting a series of complex arithmetic operations. In this paper, we first describe how HE Mul of HEAAN is performed in a manner friendly to computer architects. Then we conduct a disciplined analysis on its computational and memory access characteristics, through which we (1) extract parallelism in the key functions composing HE Mul and (2) demonstrate how to effectively map the parallelism to the popular parallel processing platforms, multicore CPUs and GPUs, by applying a series of optimization techniques such as transposing matrices and pinning data to threads. This leads to the performance improvement of HE Mul on a CPU and a GPU by 42.9x and 134.1x, respectively, over the single-thread reference HEAAN running on a CPU. The conducted analysis and optimization would set a new foundation for future HE acceleration research.
2020
- FCCM*Hardware Architecture of a Number Theoretic Transform for a Bootstrappable RNS-based Homomorphic Encryption SchemeIn 2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), 2020
Homomorphic encryption (HE) is one of the most promising solutions to secure cloud computing. The number theoretic transform (NTT) that is widely used for convolution operations in HE requires a large amount of computation and has high parallelism, and therefore it has been a good candidate for hardware acceleration. Nevertheless, prior NTT hardware solutions for HE-based applications are impractical in most applications because they do not seriously consider the critical bootstrapping procedure that allows unlimited homomorphic operations on encrypted data. In this paper, we suggest practical bootstrappable parameters, specifically for an established residue number system (RNS)based HE scheme, and apply them to our NTT hardware design. In addition, to limit the size of internal memory for roots of unity increased by the bootstrappable parameters, only a few roots of unity are stored and others are generated on the fly. In our NTT hardware architecture, multiple NTT butterfly units (BUs) are efficiently deployed for high throughput and high resource utilization. In particular, several groups of BUs for respective moduli work in a parallel and pipelined manner, which is effective in an RNS-based HE scheme with a number of moduli. Our implementation on a Xilinx UltraScale FPGA with the bootstrappable parameters achieves a 118× faster processing speed than a software implementation, and it further provides various trade-off choices such as the number of DSP slices against BRAMs based on available FPGA resources.
2019
- AsiacryptNumerical Method for Comparison on Homomorphically Encrypted NumbersIn International Conference on the Theory and Application of Cryptology and Information Security (Asiacrypt), 2019
We propose a new method to compare numbers which are encrypted by Homomorphic Encryption (HE). Previously, comparison and min/max functions were evaluated using Boolean functions where input numbers are encrypted bit-wise. However, the bit-wise encryption methods require relatively expensive computations for basic arithmetic operations such as addition and multiplication. In this paper, we introduce iterative algorithms that approximately compute the min/max and comparison operations of several numbers which are encrypted word-wise. From the concrete error analyses, we show that our min/max and comparison algorithms have Θ(α) and Θ(α\logα) computational complexity to obtain approximate values within an error rate 2^{-α}, while the previous minimax polynomial approximation method requires the exponential complexity Θ(2^{α/2}) and Θ(\sqrt{α}⋅2^{α/2}), respectively. Our algorithms achieve (quasi-)optimality in terms of asymptotic computational complexity among polynomial approximations for min/max and comparison operations. The comparison algorithm is extended to several applications such as computing the top-k elements and counting numbers over the threshold in encrypted state. Our method enables word-wise HEs to enjoy comparable performance in practice with bit-wise HEs for comparison operations while showing much better performance on polynomial operations. Computing an approximate maximum value of any two \ell-bit integers encrypted by HEAAN, up to error 2^{\ell-10}, takes only 1.14 milliseconds in amortized running time, which is comparable to the result based on bit-wise HEs.
- ReConFig*FPGA-based Accelerators of Fully Pipelined Modular Multipliers for Homomorphic EncryptionIn 2019 International Conference on ReConFigurable Computing and FPGAs (ReConFig), 2019
Homomorphic encryption (HE) is an important cryptographic primitive which allows privacy preserving computations. Current HE schemes are all based on modular arithmetic. Modular multiplication (ModMult) is one of the most frequently used modular operations, but in practice it is often prohibitively slow due to a reduction operation with high computational complexity. To address this speed problem, we demonstrate a set of novel FPGA-based accelerators for fully pipelined ModMults in this paper. For a high-throughput integer multiplier (IntMult) in the ModMult designs, digital signal processing (DSP) slices on FPGAs are efficiently exploited with optimized IntMult designs. For the full RNS-HEAAN scheme, which is our target HE scheme, our proposed Barrett ModMult design is optimized using specific moduli and extended to the Shoup ModMult algorithm. Our proposed Barrett and Shoup ModMult designs implemented on a Xilinx Virtex UltraScale FPGA show a 2x shorter delay, 14x higher throughput at the same frequency, and 3× higher throughput/DSP than the previous non-fully pipelined Barrett ModMult design on average. In particular, our Barrett ModMult design with the specific moduli shows the highest throughput/DSP value although precomputation required in the Shoup ModMult design is not used. Compared with a reference software implementation, our ModMult designs show 679× faster average processing speeds when we deploy multiple ModMult cores that fully use DSP slices on our target FPGA.
- BMC*A Secure SNP Panel Scheme using Homomorphically Encrypted K-mers without SNP Calling on the User SideSungjoon Park, Minsu Kim, Seokjun Seo, Seungwan Hong, Kyoohyung Han, Keewoo Lee, Jung Hee Cheon, Sun KimBMC genomics, 2019
[BACKGROUND] Single Nucleotide Polymorphism (SNP) in the genome has become crucial information for clinical use. For example, the targeted cancer therapy is primarily based on the information which clinically important SNPs are detectable from the tumor. Many hospitals have developed their own panels that include clinically important SNPs. The genome information exchange between the patient and the hospital has become more popular. However, the genome sequence information is innate and irreversible and thus its leakage has serious consequences. Therefore, protecting one’s genome information is critical. On the other side, hospitals may need to protect their own panels. There is no known secure SNP panel scheme to protect both. [RESULTS] In this paper, we propose a secure SNP panel scheme using homomorphically encrypted K-mers without requiring SNP calling on the user side and without revealing the panel information to the user. Use of the powerful homomorphic encryption technique is desirable, but there is no known algorithm to efficiently align two homomorphically encrypted sequences. Thus, we designed and implemented a novel secure SNP panel scheme utilizing the computationally feasible equality test on two homomorphically encrypted K-mers. To make the scheme work correctly, in addition to SNPs in the panel, sequence variations at the population level should be addressed. We designed a concept of Point Deviation Tolerance (PDT) level to address the false positives and false negatives. Using the TCGA BRCA dataset, we demonstrated that our scheme works at the level of over a hundred thousand somatic mutations. In addition, we provide a computational guideline for the panel design, including the size of K-mer and the number of SNPs. [CONCLUSIONS] The proposed method is the first of its kind to protect both the user’s sequence and the hospital’s panel information using the powerful homomorphic encryption scheme. We demonstrated that the scheme works with a simulated dataset and the TCGA BRCA dataset. In this study, we have shown only the feasibility of the proposed scheme and much more efforts should be done to make the scheme usable for clinical use.
2018
- BMC*Logistic Regression Model Training based on the Approximate Homomorphic EncryptionBMC medical genomics, 2018
Security concerns have been raised since big data became a prominent tool in data analysis. For instance, many machine learning algorithms aim to generate prediction models using training data which contain sensitive information about individuals. Cryptography community is considering secure computation as a solution for privacy protection. In particular, practical requirements have triggered research on the efficiency of cryptographic primitives. This paper presents a practical method to train a logistic regression model while preserving the data confidentiality. We apply the homomorphic encryption scheme of Cheon et al. (ASIACRYPT 2017) for an efficient arithmetic over real numbers, and devise a new encoding method to reduce storage of encrypted database. In addition, we adapt Nesterov’s accelerated gradient method to reduce the number of iterations as well as the computational cost while maintaining the quality of an output classifier. Our method shows a state-of-the-art performance of homomorphic encryption system in a real-world application. The submission based on this work was selected as the best solution of Track 3 at iDASH privacy and security competition 2017. For example, it took about six minutes to obtain a logistic regression model given the dataset consisting of 1579 samples, each of which has 18 features with a binary outcome variable.
2017
- WAHCPrivacy-Preserving Computations of Predictive Medical Models with Minimax Approximation and Non-Adjacent FormJung Hee Cheon, Jinhyuck Jeong, Joohee Lee, Keewoo LeeIn International Conference on Financial Cryptography and Data Security, 2017
In 2014, Bos et al. introduced a cloud service scenario to provide private predictive analyses on encrypted medical data, and gave a proof of concept implementation by utilizing homomorphic encryption (HE) scheme. In their implementation, they needed to approximate an analytic predictive model to a polynomial, using Taylor approximations. However, their approach could not reach a satisfactory compromise so that they just restricted the pool of data to guarantee suitable accuracy. In this paper, we suggest and implement a new efficient approach to provide the service using minimax approximation and Non-Adjacent Form (NAF) encoding. With our method, it is possible to remove the limitation of input range and reduce maximum errors, allowing faster analyses than the previous work. Moreover, we prove that the NAF encoding allows us to use more efficient parameters than the binary encoding used in the previous work or balaced base-B encoding. For comparison with the previous work, we present implementation results using HElib. Our implementation gives a prediction with 7-bit precision (of maximal error 0.0044) for having a heart attack, and makes the prediction in 0.5 s on a single laptop. We also implement the private healthcare service analyzing a Cox Proportional Hazard Model for the first time.
book chapters
2021
- Gimme That Model!: A Trusted ML Model Trading ProtocolLaia Amorós, Syed Mahbub Hafiz, Keewoo Lee, M Caner TolProtecting Privacy through Homomorphic Encryption, 2021
We propose a HE-based protocol for trading ML models and describe possible improvements to the protocol to make the overall transaction more efficient and secure.