論文の概要: Efficient Ranking, Order Statistics, and Sorting under CKKS

• arxiv url: http://arxiv.org/abs/2412.15126v1
• Date: Thu, 19 Dec 2024 18:06:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-20 13:29:10.312541
• Title: Efficient Ranking, Order Statistics, and Sorting under CKKS
• Title（参考訳）: CKKSにおける効率的なランク付け・順序統計・ソーティング
• Authors: Federico Mazzone, Maarten Everts, Florian Hahn, Andreas Peter,
• Abstract要約: ホモモルフィック暗号化(FHE)は、暗号化されたデータの操作を可能にするため、プライバシ保護アプリケーションに極めて有用である。 計算オーバーヘッドの増大とFHEのネイティブ操作の制限により、これらのタスクの効率的な実装には大きな課題が生じる。 我々は、ランク付け、順序統計、ソートのための解を示し、いずれもO(1)の比較深度を達成している。
• 参考スコア（独自算出の注目度）: 5.543544712471747
• License:
• Abstract: Fully Homomorphic Encryption (FHE) enables operations on encrypted data, making it extremely useful for privacy-preserving applications, especially in cloud computing environments. In such contexts, operations like ranking, order statistics, and sorting are fundamental functionalities often required for database queries or as building blocks of larger protocols. However, the high computational overhead and limited native operations of FHE pose significant challenges for an efficient implementation of these tasks. These challenges are exacerbated by the fact that all these functionalities are based on comparing elements, which is a severely expensive operation under encryption. Previous solutions have typically based their designs on swap-based techniques, where two elements are conditionally swapped based on the results of their comparison. These methods aim to reduce the primary computational bottleneck: the comparison depth, which is the number of non-parallelizable homomorphic comparisons. The current state of the art solution for sorting by Lu et al. (IEEE S&P'21), for instance, achieves a comparison depth of O(log^2(N)). In this paper, we address the challenge of reducing the comparison depth by shifting away from the swap-based paradigm. We present solutions for ranking, order statistics, and sorting, that all achieve a comparison depth of O(1), making our approach highly parallelizable. Leveraging the SIMD capabilities of the CKKS FHE scheme, our approach re-encodes the input vector under encryption to allow for simultaneous comparisons of all elements with each other. The homomorphic re-encoding incurs a minimal computational overhead of O(log(N)) rotations. Experimental results show that our approach ranks a 128-element vector in approximately 2.64s, computes its argmin/argmax in 14.18s, and sorts it in 21.10s.
• Abstract（参考訳）: FHE(Fully Homomorphic Encryption)は、暗号化されたデータの操作を可能にするため、特にクラウドコンピューティング環境では、プライバシ保護アプリケーションに極めて有用である。 このような状況下では、ランキング、順序統計、ソートといった操作は、データベースクエリやより大きなプロトコルのビルディングブロックとして必要とされる基本機能である。 しかし、計算オーバーヘッドの増大とFHEのネイティブ操作の制限により、これらのタスクの効率的な実装には大きな課題が生じる。 これらの課題は、これらすべての機能は、暗号化の下で非常に高価な操作である要素の比較に基づいているという事実によって、さらに悪化している。 従来のソリューションでは、2つの要素を条件付きスワップで比較した結果に基づいて交換するスワップベースの手法が一般的であった。 これらの手法は、非並列化可能な同型比較の数である比較深度という、主要な計算ボトルネックを減らすことを目的としている。 例えば、Lu et al (IEEE S&P'21) による現在の最先端解は、O(log^2(N)) の比較深度を達成する。 本稿では,スワップベースパラダイムから脱却することで比較深度を低減するという課題に対処する。 我々は、O(1)の比較深度を全て達成し、我々のアプローチを高度に並列化できるように、ランク付け、順序統計、ソートのためのソリューションを提案する。 CKKS FHE方式のSIMD機能を活用して, 入力ベクトルを復号化して, 全要素の同時比較を可能にする。 準同型再符号化は、O(log(N)) 回転の最小の計算オーバーヘッドをもたらす。 実験の結果,約2.64秒で128要素ベクトルをランク付けし,14.18秒でargmin/argmaxを計算し,21.10秒でソートした。

関連論文リスト

• Optimized Homomorphic Permutation From New Permutation Decomposition Techniques [1.8911961520222993]
  ホモモルフィックな置換は、バッチエンコーディングのホモモルフィック暗号に基づくプライバシ保存計算の基礎となる。 本稿では,新しい分解手法により,同相置換の効率を向上させる。
  論文  参考訳（メタデータ） (2024-10-29T08:07:22Z)
• Rapid Person Re-Identification via Sub-space Consistency Regularization [51.76876061721556]
  Person Re-Identification (ReID) は、歩行者を分離したカメラで識別する。 実値特徴記述子を用いた既存のReID法は精度が高いが、ユークリッド距離計算が遅いため効率が低い。 本稿では,ReID 処理を 0.25 倍高速化するサブスペース一貫性規則化 (SCR) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-07-13T02:44:05Z)
• Will Bilevel Optimizers Benefit from Loops [63.22466953441521]
  AID-BiOとITD-BiOの2つの一般的な双レベルマトリクスは、自然に1つまたは2つのサブプロブレムを解決する。 AID-BiO と ITD-BiO の両ループ実装選択に適用可能な統合収束解析をまず確立する。
  論文  参考訳（メタデータ） (2022-05-27T20:28:52Z)
• Rank-based Non-dominated Sorting [0.0]
  我々は、高額な支配比較を避けるために、ソート安定性と順序情報を利用した非支配的なソート手法であるランクソートを導入する。 2つのアルゴリズム的変種が提案されている: 1つはRandOrdinal (RO) で、支配性を決定するために順序付き階数比較(英語版)(ordinal rank comparisons)を用いており、O(N) 空間を必要とする。 NSGA2アルゴリズムと合成ベンチマークを用いた実験シミュレーションにおいて,提案手法の有効性を他の手法と比較した。
  論文  参考訳（メタデータ） (2022-03-25T13:59:42Z)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• On the Assessment of Benchmark Suites for Algorithm Comparison [7.501426386641256]
  BBOBスイートのほとんどのベンチマーク関数は、高い難易度(最適化アルゴリズムと比較)と低い差別性を有することを示す。 我々は、ベンチマークスイートの設計を改善することを含む、ベンチマークにおけるIRTの潜在的な使用について論じる。
  論文  参考訳（メタデータ） (2021-04-15T11:20:11Z)
• Constraint-Handling Techniques for Particle Swarm Optimization Algorithms [0.0]
  人口ベースの手法は、従来の方法よりもはるかに複雑な問題を含む、さまざまな問題に対処することができる。 本研究の目的は,アルゴリズムに汎用的な設定を組み込んだPSOに適したCHTを開発し,比較することである。
  論文  参考訳（メタデータ） (2021-01-25T01:49:10Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)
• Fast Differentiable Sorting and Ranking [36.40586857569459]
  我々は、最初の微分可能なソートおよびランキング演算子を$O(n log n)$ time と $O(n)$ space complexity で提案する。 この偉業は、置換の凸包であるペルムタヘドロンへの射影として微分可能作用素を構築し、等方最適化への還元を用いて達成する。
  論文  参考訳（メタデータ） (2020-02-20T17:11:09Z)
• Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
  SOFTトップk演算子は、エントロピック最適輸送(EOT)問題の解として、トップk演算の出力を近似する。 提案した演算子をk-アネレスト近傍およびビーム探索アルゴリズムに適用し,性能向上を示す。
  論文  参考訳（メタデータ） (2020-02-16T04:57:52Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。