論文の概要: 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からの事前構成よりも,準ポリノミクス的にのみ安全な衝突耐性ハッシュ関数を実現する。
関連論文リスト
- Pseudorandom Permutations from Random Reversible Circuits [1.9567015559455132]
固定された最寄りのアーキテクチャにおいて,各層が$approx n/3$のランダムゲートからなる深さ$n cdot tildeO(k2)$のランダム回路がほぼ$k$の独立な置換をもたらすことを示す。
また、擬似乱数関数からの擬似乱数置換のLuby-Rack-off構成は可逆回路で実装可能であることを示す。
論文 参考訳(メタデータ) (2024-04-23T00:50:57Z) - 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 [55.2480439325792]
スポンジハッシュ(Spnge hashing)は、現在の国際ハッシュ関数標準SHA-3の基盤となる暗号ハッシュアルゴリズムの新たなクラスである。
ウンルーが提唱した「二重側ゼロ探索」予想を証明する。
また、ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要であることも示している。
論文 参考訳(メタデータ) (2024-03-07T18:46:58Z) - Bit-flipping Decoder Failure Rate Estimation for (v,w)-regular Codes [84.0257274213152]
並列ビットフリップデコーダのDFRを高精度に推定する手法を提案する。
本研究は,本症候群のモデル化およびシミュレーションによる重み比較,第1イテレーション終了時の誤りビット分布の誤検出,復号化復号化率(DFR)について検証した。
論文 参考訳(メタデータ) (2024-01-30T11:40:24Z) - 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) - A Quantum Approach for Reducing Communications in Classical
Cryptographic Primitives [2.3465488122819123]
我々は、おそらく驚くべきことに、より弱い仮定の下で量子技術でこの問題を解決することが可能であることを示した。
我々の研究は、量子暗号が新しいタイプの問題で古典的暗号より優れているという興味深いメッセージを伝える。
論文 参考訳(メタデータ) (2023-10-08T16:07:46Z) - Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the
Cryptanalysis of pSIDH [5.398058794903461]
自己同型環問題(英語版)(IsERP)は、超特異曲線の間の同型写像の余領域の自己同型環を計算することを要求する。
次数が奇数で、多くの素因子が$O(loglog p)=$である等質性に対して、IsERPを解くための新しい量子時間アルゴリズムを導入する。
論文 参考訳(メタデータ) (2023-05-31T14:30:32Z) - Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
ターゲットの折り畳みは、公開可能な削除(PVD)を可能にすることを示す。
我々は、弱い暗号的仮定から公開可能な削除を支援する様々なプリミティブを得るために、このフレームワークを構築している。
論文 参考訳(メタデータ) (2023-03-15T15:00:20Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳(メタデータ) (2022-06-07T18:00:01Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。