論文の概要: 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 18:44:16.243696
• 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: http://creativecommons.org/licenses/by/4.0/
• 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秒でソートした。

関連論文リスト

• CIPHERMATCH: Accelerating Homomorphic Encryption-Based String Matching via Memory-Efficient Data Packing and In-Flash Processing [8.114331115730021]
  ホモモルフィック暗号化(HE)は、元のデータを公開せずに暗号化されたデータのセキュアな計算を可能にする。 多くのクラウドコンピューティングアプリケーション(例えば、DNA読み取りマッピング、バイオメトリックマッチング、Web検索)は、正確な文字列マッチングをキー操作として使っている。 ホモモルフィック暗号を用いた従来の文字列マッチングアルゴリズムは、高い計算遅延によって制限される。
  論文  参考訳（メタデータ） (2025-03-12T00:25:58Z)
• Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
  プライベート・セット・ユニオンでは、ユーザーは非有界宇宙からのアイテムのサブセットを保持する。 目標は、ユーザレベルの差分プライバシーを維持しながら、ユーザセットの統一から可能な限り多くのアイテムを出力することである。 そこで本研究では,プライバシに必要なしきい値よりもはるかに重い項目からより少ない項目へ適応的に重みを還元するアルゴリズムであるMaximumDegree (MAD)を提案する。
  論文  参考訳（メタデータ） (2025-02-13T01:27:11Z)
• A Practical Exercise in Adapting SIFT Using FHE Primitives [0.0]
  CKKS完全同型暗号を用いたスケール不変特徴変換の実装における課題は、現在のFHEパラダイムにおけるいくつかのグラリング制限を明らかにしている。 これらの制限には、標準比較演算子がないことと、それに依存する特定の操作が含まれる。
  論文  参考訳（メタデータ） (2024-12-09T08:52:57Z)
• Optimized Homomorphic Permutation From New Permutation Decomposition Techniques [1.8911961520222993]
  ホモモルフィックな置換は、バッチエンコーディングのホモモルフィック暗号に基づくプライバシ保存計算の基礎となる。 本稿では,新しい分解手法により,同相置換の効率を向上させる。
  論文  参考訳（メタデータ） (2024-10-29T08:07:22Z)
• Efficient Approximate Kernel Based Spike Sequence Classification [56.2938724367661]
  SVMのような機械学習モデルは、シーケンスのペア間の距離/相似性の定義を必要とする。 厳密な手法により分類性能は向上するが、計算コストが高い。 本稿では,その予測性能を向上させるために,近似カーネルの性能を改善する一連の方法を提案する。
  論文  参考訳（メタデータ） (2022-09-11T22:44:19Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。 これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。 我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
  論文  参考訳（メタデータ） (2022-07-26T04:38:47Z)
• 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)
• On the Assessment of Benchmark Suites for Algorithm Comparison [7.501426386641256]
  BBOBスイートのほとんどのベンチマーク関数は、高い難易度(最適化アルゴリズムと比較)と低い差別性を有することを示す。 我々は、ベンチマークスイートの設計を改善することを含む、ベンチマークにおけるIRTの潜在的な使用について論じる。
  論文  参考訳（メタデータ） (2021-04-15T11:20:11Z)
• 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)

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

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