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

• arxiv url: http://arxiv.org/abs/2412.15126v2
• Date: Mon, 10 Feb 2025 12:57:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-11 14:23:22.792924
• Title: Efficient Ranking, Order Statistics, and Sorting under CKKS
• Title（参考訳）: CKKSにおける効率的なランク付け・順序統計・ソーティング
• Authors: Federico Mazzone, Maarten Everts, Florian Hahn, Andreas Peter,
• Abstract要約: ホモモルフィック暗号化(FHE)は、暗号化されたデータの操作を可能にするため、プライバシ保護アプリケーションに極めて有用である。 計算オーバーヘッドの増大とFHEのネイティブ操作の制限により、これらのタスクの効率的な実装には大きな課題が生じる。 比較深度を最大2(コンスタント)まで向上させるランキング、順序統計、ソートのためのソリューションを提案する。
• 参考スコア（独自算出の注目度）: 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 in the algorithm. The current state of the art solution for sorting by Hong et al. (IEEE TIFS 2021), for instance, achieves a comparison depth of k log_k^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 achieve a comparison depth of up to 2 (constant), making our approach highly parallelizable and suitable for hardware acceleration. 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. Experimental results show that our approach ranks a 128-element vector in approximately 5.76s, computes its argmin/argmax in 12.83s, and sorts it in 78.64s.
• Abstract（参考訳）: FHE(Fully Homomorphic Encryption)は、暗号化されたデータの操作を可能にするため、特にクラウドコンピューティング環境では、プライバシ保護アプリケーションに極めて有用である。 このような状況下では、ランキング、順序統計、ソートといった操作は、データベースクエリやより大きなプロトコルのビルディングブロックとして必要とされる基本機能である。 しかし、計算オーバーヘッドの増大とFHEのネイティブ操作の制限により、これらのタスクの効率的な実装には大きな課題が生じる。 これらの課題は、これらすべての機能は、暗号化の下で非常に高価な操作である要素の比較に基づいているという事実によって、さらに悪化している。 従来のソリューションでは、2つの要素を条件付きスワップで比較した結果に基づいて交換するスワップベースの手法が一般的であった。 これらの手法は、アルゴリズムにおける非並列化可能な同型比較の数である比較深度という、主要な計算ボトルネックを減らすことを目的としている。 例えば、Hong et al(IEEE TIFS 2021)による現在最先端のソートソリューションでは、k log_k^2 Nの比較深度を実現している。 我々は,比較深度を最大2(コンスタント)まで向上させるランキング,順序統計,ソートのためのソリューションを提案し,ハードウェアアクセラレーションに適した並列化を実現した。 CKKS FHE方式のSIMD機能を活用して, 入力ベクトルを復号化して, 全要素の同時比較を可能にする。 実験の結果,約5.76秒で128要素ベクトルをランク付けし,12.83秒でargmin/argmaxを計算し,78.64秒でソートした。

関連論文リスト

• 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)
• 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)
• Rank-based Non-dominated Sorting [0.0]
  我々は、高額な支配比較を避けるために、ソート安定性と順序情報を利用した非支配的なソート手法であるランクソートを導入する。 2つのアルゴリズム的変種が提案されている: 1つはRandOrdinal (RO) で、支配性を決定するために順序付き階数比較(英語版)(ordinal rank comparisons)を用いており、O(N) 空間を必要とする。 NSGA2アルゴリズムと合成ベンチマークを用いた実験シミュレーションにおいて,提案手法の有効性を他の手法と比較した。
  論文  参考訳（メタデータ） (2022-03-25T13:59:42Z)
• On the Assessment of Benchmark Suites for Algorithm Comparison [7.501426386641256]
  BBOBスイートのほとんどのベンチマーク関数は、高い難易度(最適化アルゴリズムと比較)と低い差別性を有することを示す。 我々は、ベンチマークスイートの設計を改善することを含む、ベンチマークにおけるIRTの潜在的な使用について論じる。
  論文  参考訳（メタデータ） (2021-04-15T11:20:11Z)
• Structured Inverted-File k-Means Clustering for High-Dimensional Sparse Data [2.487445341407889]
  本稿では,大規模かつ高次元スパースデータセットのためのアーキテクチャフレンドリーなk-meansクラスタリングアルゴリズムsivfを提案する。 性能解析の結果,sivfはキャッシュミス数と分岐予測の精度低下係数を低減し,高い速度を実現していることがわかった。
  論文  参考訳（メタデータ） (2021-03-30T07:54:02Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)
• Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
  SOFTトップk演算子は、エントロピック最適輸送(EOT)問題の解として、トップk演算の出力を近似する。 提案した演算子をk-アネレスト近傍およびビーム探索アルゴリズムに適用し,性能向上を示す。
  論文  参考訳（メタデータ） (2020-02-16T04:57:52Z)

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

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