論文の概要: Lossy Cryptography from Code-Based Assumptions

• arxiv url: http://arxiv.org/abs/2402.03633v1
• Date: Tue, 6 Feb 2024 02:17:08 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-18 07:48:02.404045
• Title: Lossy Cryptography from Code-Based Assumptions
• Title（参考訳）: コードに基づく推測に基づくロッシー暗号
• Authors: Quang Dao, Aayush Jain,
• Abstract要約: 高度な暗号プリミティブの拡散は、複雑性クラス$SZK$の難しい問題を暗示している。 これは、コードベースの仮定から高度なプリミティブを構築するための障壁となる。 我々は、Dense-Sparseという、複雑性クラス$BPPSZK$に該当する新しいコードベースの仮定を提案する。
• 参考スコア（独自算出の注目度）: 7.880958076366762
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Over the past few decades, we have seen a proliferation of advanced cryptographic primitives with lossy or homomorphic properties built from various assumptions such as Quadratic Residuosity, Decisional Diffie-Hellman, and Learning with Errors. These primitives imply hard problems in the complexity class $SZK$ (statistical zero-knowledge); as a consequence, they can only be based on assumptions that are broken in $BPP^{SZK}$. This poses a barrier for building advanced primitives from code-based assumptions, as the only known such assumption is Learning Parity with Noise (LPN) with an extremely low noise rate $\frac{\log^2 n}{n}$, which is broken in quasi-polynomial time. In this work, we propose a new code-based assumption: Dense-Sparse LPN, that falls in the complexity class $BPP^{SZK}$ and is conjectured to be secure against subexponential time adversaries. Our assumption is a variant of LPN that is inspired by McEliece's cryptosystem and random $k\mbox{-}$XOR in average-case complexity. We leverage our assumption to build lossy trapdoor functions (Peikert-Waters STOC 08). This gives the first post-quantum alternative to the lattice-based construction in the original paper. Lossy trapdoor functions, being a fundamental cryptographic tool, are known to enable a broad spectrum of both lossy and non-lossy cryptographic primitives; our construction thus implies these primitives in a generic manner. In particular, we achieve collision-resistant hash functions with plausible subexponential security, improving over a prior construction from LPN with noise rate $\frac{\log^2 n}{n}$ that is only quasi-polynomially secure.
• Abstract（参考訳）: 過去数十年にわたって、二次的残留性、決定的ディフィー・ヘルマン(Decisional Diffie-Hellman)、Learning with Errors(Learning with Errors)といった様々な仮定から構築された、欠落または同型の性質を持つ高度な暗号プリミティブが急増してきた。 これらのプリミティブは、複雑性クラス$SZK$(統計的ゼロ知識)の難しい問題を暗示している。 このことは、コードベースの仮定から先進的プリミティブを構築するための障壁となる。そのような仮定が唯一知られているのは、準多項式時間で破られる非常に低いノイズレート$\frac{\log^2 n}{n}$のLearning Parity with Noise (LPN)である。 そこで本研究では,複雑性クラス$BPP^{SZK}$に該当するDense-Sparse LPNというコードベースの仮定を提案する。 我々の仮定は、平均ケース複雑性において、McElieceの暗号システムとランダム$k\mbox{-}$XORにインスパイアされたLPNの変種である。 我々はこの仮定を利用して、損失の少ないトラップドア関数(Peikert-Waters STOC 08)を構築する。 これは、最初の論文で格子ベースの構造に取って代わる最初の量子後代替を与える。 基本的な暗号ツールであるロッシートラップドア関数は、ロッシープリミティブと非ロッシープリミティブの両方の幅広いスペクトルを可能にすることが知られている。 特に,音速$\frac{\log^2 n}{n}$のLPNからの事前構成よりも,準ポリノミクス的にのみ安全な衝突耐性ハッシュ関数を実現する。

関連論文リスト

• On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography [3.298620737848292]
  最も効率的な提案は、構造化符号の復号化の難しさを前提としている。 HQCは2つの巡回ブロックからなる行列によって生成される準循環符号に基づいている。 準巡回符号の平均ケース削減に対する本結果の影響を考察する。
  論文  参考訳（メタデータ） (2025-01-05T18:43:08Z)
• New constructions of pseudorandom codes [23.22566380210149]
  Pseudorandom error-correcting codes (PRCs) は、生成AIモデルをウォーターマークする新しい暗号プリミティブである。 BKR23]で導入された植込みハイパーループ仮定とGoldreichのPRGホールディングのセキュリティの両方が、効率の良い敵がランダムなコードワードを識別できない公開鍵PRCが存在することを示す。 これは$textitunconditionally$ indistinguishable random by $textpoly()である。
  論文  参考訳（メタデータ） (2024-09-11T19:14:39Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• Crooked indifferentiability of the Feistel Construction [53.572703605492904]
  Feistelの構築は擬似乱数置換とブロック暗号を構築するための基本的な技術である。 本稿では, アルゴリズム置換攻撃に対しても, 簡単な構成法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-15T04:29:24Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• Efficient quantum algorithms for some instances of the semidirect discrete logarithm problem [2.90985742774369]
  SDLPは,いくつかの重要な症例においてさらに容易であることを示す。 SDLPのハードネスを前提としたセキュリティ仮定を前提としたSPDH-Signと類似の暗号系が量子攻撃に対して安全でないことを示す。
  論文  参考訳（メタデータ） (2023-12-21T16:58:59Z)
• Signatures From Pseudorandom States via $\bot$-PRFs [0.11650821883155184]
  我々は $bot$-PRG と $bot$-PRF の新たな定義を導入する。 私たちの主な応用は、古典的な公開鍵と署名を備えた(量子)デジタル署名スキームです。
  論文  参考訳（メタデータ） (2023-11-01T20:54:50Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  ターゲットの折り畳みは、公開可能な削除(PVD)を可能にすることを示す。 我々は、弱い暗号的仮定から公開可能な削除を支援する様々なプリミティブを得るために、このフレームワークを構築している。
  論文  参考訳（メタデータ） (2023-03-15T15:00:20Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。 我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。 補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
  論文  参考訳（メタデータ） (2020-09-29T08:41:53Z)

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

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