論文の概要: Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell
- arxiv url: http://arxiv.org/abs/2508.14568v1
- Date: Wed, 20 Aug 2025 09:40:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-21 16:52:41.419029
- Title: Leuvenshtein: Efficient FHE-based Edit Distance Computation with Single Bootstrap per Cell
- Title(参考訳): Leuvenshtein: 単一ブートストラップによるFHEを用いた効率的な編集距離計算
- Authors: Wouter Legiest, Jan-Pieter D'Anvers, Bojan Spasic, Nam-Luc Tran, Ingrid Verbauwhede,
- Abstract要約: 編集距離計算は、DNAシークエンスアライメントのようなファイナンスやゲノム学にまたがる応用において不可欠である。
本稿では,Leuvenshteinと呼ばれる距離計算の編集コストを大幅に削減する最適化アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 9.554839026375568
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper presents a novel approach to calculating the Levenshtein (edit) distance within the framework of Fully Homomorphic Encryption (FHE), specifically targeting third-generation schemes like TFHE. Edit distance computations are essential in applications across finance and genomics, such as DNA sequence alignment. We introduce an optimised algorithm that significantly reduces the cost of edit distance calculations called Leuvenshtein. This algorithm specifically reduces the number of programmable bootstraps (PBS) needed per cell of the calculation, lowering it from approximately 94 operations -- required by the conventional Wagner-Fisher algorithm -- to just 1. Additionally, we propose an efficient method for performing equality checks on characters, reducing ASCII character comparisons to only 2 PBS operations. Finally, we explore the potential for further performance improvements by utilising preprocessing when one of the input strings is unencrypted. Our Leuvenshtein achieves up to $278\times$ faster performance compared to the best available TFHE implementation and up to $39\times$ faster than an optimised implementation of the Wagner-Fisher algorithm. Moreover, when offline preprocessing is possible due to the presence of one unencrypted input on the server side, an additional $3\times$ speedup can be achieved.
- Abstract(参考訳): 本稿では、TFHEのような第3世代のスキームを対象とするFHE(Fully Homomorphic Encryption)の枠組み内でのLevenshtein(edit)距離を計算するための新しい手法を提案する。
編集距離計算は、DNAシークエンスアライメントのようなファイナンスやゲノム学にまたがる応用において不可欠である。
本稿では,Leuvenshteinと呼ばれる距離計算の編集コストを大幅に削減する最適化アルゴリズムを提案する。
このアルゴリズムは、計算のセルあたりに必要なプログラム可能なブートストラップ(PBS)の数を具体的に減らし、従来のワグナー・フィッシャーアルゴリズムで要求される約94の操作からわずか1に減らした。
さらに,文字の等価性チェックを効果的に行う手法を提案し,ASCII文字比較を2PBS操作に短縮する。
最後に,入力文字列の1つが暗号化されていない場合にプリプロセッシングを活用することで,さらなるパフォーマンス向上の可能性を検討する。
我々のLeuvenshteinは、最高のTFHE実装と比較して最大278\times$パフォーマンスを実現し、Wagner-Fisherアルゴリズムの最適化実装よりも最大39\times$パフォーマンスを実現しています。
さらに、サーバ側で暗号化されていない入力が1つあるため、オフラインのプリプロセッシングが可能になった場合、さらに$3\times$のスピードアップが達成できる。
関連論文リスト
- Replicable Learning of Large-Margin Halfspaces [46.91303295440005]
我々は,大マージンハーフスペースを学習する問題に対して,効率的なアルゴリズムを提供する。
Impagliazzo, Lei, Pitassi, Sorrellによるアルゴリズム [STOC 2022] の改良を行った。
論文 参考訳(メタデータ) (2024-02-21T15:06:51Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳(メタデータ) (2022-10-14T01:42:05Z) - 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) - Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for
Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
本稿では,d-次元単純複素数 K 上で定義される入力片方向線形スカラー場 f を与えられた永続図計算の効率的なアルゴリズムを提案する。
我々はこのアルゴリズムを離散モース理論の設定内で表現し、考慮すべき入力単純さの数を著しく削減する。
また、この問題に対して「サンドウィッチ」と呼ばれる階層化アプローチを導入する。
論文 参考訳(メタデータ) (2022-06-27T10:54:24Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳(メタデータ) (2022-06-14T08:14:14Z) - Private Frequency Estimation via Projective Geometry [47.112770141205864]
そこで本研究では,局所微分型(LDP)周波数推定のための新しいアルゴリズムであるProjectiveGeometryResponse (PGR)を提案する。
私たちの$varepsilon$-LDPアルゴリズムは、プライベートコイン設定で$lceillogkrceilビット、パブリックコイン設定で$varepsilonlog e + O(1)$の通信コストを持っています。
実際に使用される多くのパラメータ設定では、これは最近のPIによって達成されるO(n+k2)$Optimalコストよりも大幅に改善されている。
論文 参考訳(メタデータ) (2022-03-01T02:49:55Z) - Efficient Matrix-Free Approximations of Second-Order Information, with
Applications to Pruning and Optimization [16.96639526117016]
Inverse-Hessian Vector Products (IHVPs) の行列のない線形時間アプローチについて検討する。
これらのアルゴリズムは、既存の2階法と比較して計算オーバーヘッドが低いネットワークプルーニングと最適化の最先端結果をもたらす。
論文 参考訳(メタデータ) (2021-07-07T17:01:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。