論文の概要: Injective Rank Metric Trapdoor Functions with Homogeneous Errors
- arxiv url: http://arxiv.org/abs/2310.08962v1
- Date: Fri, 13 Oct 2023 09:12:25 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-19 02:33:12.359383
- Title: Injective Rank Metric Trapdoor Functions with Homogeneous Errors
- Title（参考訳）: 均一な誤差を有するインジェクティブランクメトリックトリップドア関数
- Authors: Étienne Burle, Philippe Gaborit, Younes Hatri, Ayoub Otmani,
- Abstract要約: ランクメトリック暗号において、有限体上の有限次元線型空間からのベクトルは、その入射によって広がる線型空間と見なされる。
入射型片道トラップドア関数の新規構築について紹介する。
私たちのソリューションは、エラー訂正コードから公開鍵プリミティブを構築する頻繁な方法から離れています。
- 参考スコア（独自算出の注目度）: 2.117778717665161
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In rank-metric cryptography, a vector from a finite dimensional linear space over a finite field is viewed as the linear space spanned by its entries. The rank decoding problem which is the analogue of the problem of decoding a random linear code consists in recovering a basis of a random noise vector that was used to perturb a set of random linear equations sharing a secret solution. Assuming the intractability of this problem, we introduce a new construction of injective one-way trapdoor functions. Our solution departs from the frequent way of building public key primitives from error-correcting codes where, to establish the security, ad hoc assumptions about a hidden structure are made. Our method produces a hard-to-distinguish linear code together with low weight vectors which constitute the secret that helps recover the inputs.The key idea is to focus on trapdoor functions that take sufficiently enough input vectors sharing the same support. Applying then the error correcting algorithm designed for Low Rank Parity Check (LRPC) codes, we obtain an inverting algorithm that recovers the inputs with overwhelming probability.
- Abstract（参考訳）: ランクメトリック暗号において、有限体上の有限次元線型空間からのベクトルは、その入射によって広がる線型空間と見なされる。
ランダムな線形符号を復号する問題の類似である階数復号問題は、秘密解を共有するランダムな線形方程式の集合を摂動するために用いられたランダムなノイズベクトルの基底を復元するものである。
この問題の難易度を仮定し, 単方向トラップドア関数を新たに構築する。
私たちのソリューションは、公開鍵プリミティブをエラー訂正コードから頻繁に作り出す方法から外れています。
提案手法は,入力を復元する秘密を構成する低重みベクトルとともに,十分な入力ベクトルを共有するトラップドア関数に注目することを目的としている。
そこで,低ランクパリティチェック(LRPC)符号に対して設計された誤り訂正アルゴリズムを適用し,圧倒的な確率で入力を復元する反転アルゴリズムを得る。
関連論文リスト
- Linear Codes for Hyperdimensional Computing [9.7902367664742]
ランダムな線形符号は、キー-値ストアを形成するために使用できるリッチなサブコード構造を提供する。
筆者らが開発しているフレームワークでは、ランダムな線形符号は単純なリカバリアルゴリズムを(束縛あるいは束縛された)構成表現に含めていることが示される。
論文 参考訳（メタデータ） (2024-03-05T19:18:44Z) - Reduction from sparse LPN to LPN, Dual Attack 3.0 [1.9106435311144374]
全く異なるアプローチに依存する RLPN-decoding と呼ばれる新しいアルゴリズムが導入された。
コードレートが 0.42 より小さい場合、ISD と RLPN を著しく上回っている。
このアルゴリズムは、格子ベースの暗号における最近の二重攻撃の従兄弟であるコードベース暗号と見なすことができる。
論文 参考訳（メタデータ） (2023-12-01T17:35:29Z) - An Upper-Bound on the Decoding Failure Probability of the LRPC Decoder [0.0]
低ランクパリティチェック(LRPC)符号は、意図的に公開鍵暗号方式の設計に導入されたランクメトリックの誤り訂正符号のクラスである。
LRPCコードは、大きな有限体の比較的低次元ベクトル部分空間に属するパリティチェック行列から定義される。
論文 参考訳（メタデータ） (2023-09-25T10:47:04Z) - Iterative Sketching for Secure Coded Regression [66.53950020718021]
分散線形回帰を高速化する手法を提案する。
具体的には、方程式の系の基礎をランダムに回転させ、次にサブサンプルブロックを回転させ、情報を同時に確保し、回帰問題の次元を小さくする。
論文 参考訳（メタデータ） (2023-08-08T11:10:42Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
論文 参考訳（メタデータ） (2021-08-10T15:00:20Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Learning algorithms from circuit lower bounds [0.0]
構成回路下界の様々な概念から効率的な学習アルゴリズムの既知の構成を再考する。
難しい問題を解こうとする多くのpサイズの回路の誤りを、特定のインタラクティブな方法で効率的に見つけることができれば、pサイズの回路は一様分布を通じてPACを学ぶことができることを証明します。
論文 参考訳（メタデータ） (2020-12-28T04:47:36Z) - Activation Relaxation: A Local Dynamical Approximation to
Backpropagation in the Brain [62.997667081978825]
活性化緩和(AR)は、バックプロパゲーション勾配を力学系の平衡点として構成することで動機付けられる。
我々のアルゴリズムは、正しいバックプロパゲーション勾配に迅速かつ堅牢に収束し、単一のタイプの計算単位しか必要とせず、任意の計算グラフで操作できる。
論文 参考訳（メタデータ） (2020-09-11T11:56:34Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - Encoder blind combinatorial compressed sensing [5.177947445379688]
線形測定のみからスパース符号の集合を復元するデコーダを設計する際の問題点を考察する。
本稿では,Decoder-Expander Based Factorisationという計算効率のよいデコードアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-10T16:26:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。