Numerical Method for Comparison on Homomorphically Encrypted Numbers

Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun Hee Lee, Keewoo Lee

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

88 Scopus citations

Abstract

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 (formula presented) computational complexity to obtain approximate values within an error rate (formula presented), while the previous minimax polynomial approximation method requires the exponential complexity (formula presented), 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 (formula presented)-bit integers encrypted by HEAAN, up to error (formula presented), takes only 1.14 ms in amortized running time, which is comparable to the result based on bit-wise HEs.

Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
EditorsSteven D. Galbraith, Shiho Moriai
PublisherSpringer Science and Business Media Deutschland GmbH
Pages415-445
Number of pages31
ISBN (Print)9783030346201
DOIs
StatePublished - 2019
Event25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 - Kobe, Japan
Duration: 8 Dec 201912 Dec 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11922 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
Country/TerritoryJapan
CityKobe
Period8/12/1912/12/19

Keywords

  • Comparison
  • Homomorphic Encryption
  • Iterative method
  • Min/Max

Fingerprint

Dive into the research topics of 'Numerical Method for Comparison on Homomorphically Encrypted Numbers'. Together they form a unique fingerprint.

Cite this