論文の概要: Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE
- arxiv url: http://arxiv.org/abs/2611.16818v1
- Date: Thu, 12 Nov 2026 13:54:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.482149
- Title: Signed Dyadic Path Encoding for Efficient Non-Interactive Private Decision Tree Evaluation over TFHE
- Title(参考訳): TFHEを用いた高能率非能動的私的決定木評価のための符号付きダイアドパス符号化
- Abstract要約: プライベートな決定ツリー評価により、サーバは入力を学習することなくクライアントの暗号化クエリを分類できる。
我々はこのコストをほぼ半分に抑える符号付きdyadic path-sum符号化を提案する。
リング度は, 消費深度範囲とともに直線的に増加することを示す。
- 参考スコア(独自算出の注目度): 9.222548177470886
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Private decision-tree evaluation lets a server classify a client's encrypted query without learning the input. In the non-interactive, path-based setting over TFHE, the server returns a single encrypted prediction by aggregating per-path comparison outcomes, and the standard per-leaf formulation pays one programmable bootstrap (PBS) per leaf, which dominates the cost. We propose a signed dyadic path-sum encoding that nearly halves this cost: each internal node receives a signed dyadic label so that every root-to-leaf path accumulates a distinct integer sum, which lets the two children of a leaf-parent be packed into a single test polynomial and resolved by one PBS, reducing the PBS count from the number of leaves to the number of leaf-parents. We formalize the distinct-sum property and prove that the dyadic labeling is the range-minimal encoding satisfying it, and its half-symmetric signed form is magnitude-optimal, tightening the comparison-stage noise bound at fixed parameters. We derive the two conditions under which the encrypted evaluation returns the exact prediction and instantiate parameters with per-inference failure below $2^{-64}$ at 128-bit security. We show that the ring degree grows linearly with the consumed plaintext range, which confines the profitable regime to depths $\leq 4$, where our method stays faster even when each scheme runs at its own cost-optimal parameters. We further extend the encoding to gradient-boosted ensembles. On standard UCI benchmarks at depths 1-4, our method reduces single-tree latency by $1.51\times$-$1.92\times$ and ensemble latency by $2\times$, without accuracy loss, while preserving the compact, non-interactive response.
- Abstract(参考訳): プライベートな決定ツリー評価により、サーバは入力を学習することなくクライアントの暗号化クエリを分類できる。
TFHE上の非インタラクティブなパスベースの設定では、サーバはパスごとの比較結果を集約して単一の暗号化予測を返却し、標準のリーフごとの定式化は1葉あたり1個のプログラム可能なブートストラップ(PBS)を支払う。
各ノードが符号付きダイアディックラベルを受信し、各ルートからリーフまでのパスが個別の整数和を蓄積し、葉親の2人の子供を1つのテスト多項式に詰め込んで1つのPBSで解決し、PBS数を葉の数から葉親の数に還元する。
我々は、差分sum特性を定式化し、ダイアディックラベリングがそれを満たす範囲最小の符号化であり、その半対称符号形式は等級最適であり、固定パラメータで拘束された比較段階ノイズを締め付ける。
暗号化された評価が正確な予測を返却する2つの条件を導出し、128ビットのセキュリティで2^{-64}$未満の推論障害を持つパラメータをインスタンス化する。
リング次数は使用済み平文範囲と直線的に増加し,各スキームがそれぞれのコスト最適パラメータで実行された場合でも,その手法はより高速に維持され,利益を$\leq 4$に抑えられることを示す。
我々はさらにエンコーディングを勾配ブーストアンサンブルに拡張する。
深さ1-4の標準UCIベンチマークでは、コンパクトで非インタラクティブな応答を保ちながら、シングルツリーのレイテンシを1.51\times$-$1.92\times$とアンサンブルのレイテンシを2.92\times$に短縮する。
関連論文リスト
- Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure [50.58119214447535]
マスク付き生成モデルは並列トークン予測を提供するが、正確な並列サンプリングはトークンを考慮しなければならない。
本研究は,発見を含む全評価がシーケンス長$N$のサブ線形であるかどうかを考察する。
本研究では, 森林構造を隠蔽した離散分布を, 固定された近似条件オラクルを通してアクセスする。
論文 参考訳(メタデータ) (2026-09-29T15:39:50Z) - Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots [9.539275654775706]
大規模言語モデルの記憶は、形式的関係が不明な定義の動物園を通じて測定される。
差分プライバシー(DP)は,これらすべてに対して同時にプロキシとして扱われることを示す。
論文 参考訳(メタデータ) (2026-08-27T23:28:08Z) - Sub-Quadratic Bisimulation Metrics via Approximate Nearest Neighbors: Coverage-Augmented Guarantees and Computable Two-Sided Certificates [1.2891210250935148]
我々は,境界遷移をサポートするMPPに対して,証明書を搬送するサブクワッドラティックな方法を提案する。
近似アレスト近傍指数は、正確に制限された演算子によって更新されたペアを選択する。
ローカルインデックスの品質だけでは、グローバルエラーを制御できない。
論文 参考訳(メタデータ) (2026-08-07T03:32:40Z) - SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
Subsampled TurboQuant (SSTQ) は、オーバーコンプリートな等幅のタイトフレーム、座標サブサンプリング、プライバシ対応量子化を組み合わせたフレームワークである。
SSTQは平均2乗誤差スケーリングを実現し、クライアントあたり$lceil log N il + b$ bitsを使用する。
また、コードブックに依存したMSEスケーリングを$O(4b)$から$O(2b)$に削減する、プライバシを意識したコードブックの目的も導出します。
論文 参考訳(メタデータ) (2026-08-05T17:51:25Z) - Representation Without Reward: A JEPA Audit for LLM Fine-Tuning [1.2691047660244335]
JEPA(Joint-embedding predictive Architectures)は、モデルが観測された出力よりも遅延表現を予測できるように訓練された時に、より有用な抽象化を学ぶべきであることを提案している。
自己回帰型言語モデルの微調整には、この原理はより厳密な要件を必要とする。
我々は、Llama-3.2-1B-Instruct LoRA を用いて、自然言語からレジェックス生成におけるその要件を検証した。
論文 参考訳(メタデータ) (2026-05-14T20:27:32Z) - Efficient Test-Time Inference via Deterministic Exploration of Truncated Decoding Trees [68.04613115686509]
自己整合性は、複数の推論トレースを並列にサンプリングし、投票することで、推論時間のパフォーマンスを向上させる。
そこで本研究では,切り落された標本を伐採木として扱う決定論的復号法であるDLE(Distinct Leafion)を提案する。
DLEは高品質な推論トレースを調査し、数学、コーディング、一般的な推論タスクのパフォーマンスを向上させる。
論文 参考訳(メタデータ) (2026-04-22T12:42:03Z) - A Partition Cover Approach to Tokenization [24.595558878756787]
トークン化とは、文字列を一定の語彙サイズのトークンに符号化するプロセスである。
Byte-Pair corpora (BPE) は、トークン化問題を圧縮問題として定式化し、マージのシーケンスを実行することでそれに取り組む。
GreedTokは圧縮においてBPEやUnigramよりも優れており、GreedWMCに匹敵するカバースコアが得られることを示す。
論文 参考訳(メタデータ) (2025-01-08T17:07:07Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳(メタデータ) (2023-11-22T06:06:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。