論文の概要: Black-Box Crypto is Useless for Pseudorandom Codes
- arxiv url: http://arxiv.org/abs/2506.01854v1
- Date: Mon, 02 Jun 2025 16:41:08 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-05 04:22:50.774994
- Title: Black-Box Crypto is Useless for Pseudorandom Codes
- Title（参考訳）: 偽造コードのブラックボックス暗号は役に立たない
- Authors: Sanjam Garg, Sam Gunn, Mingyuan Wang,
- Abstract要約: 擬似乱数符号(英: pseudorandom code)は、任意の数の符号化が任意の計算上の有界敵に対してランダムに現れるという性質を持つ鍵付き誤り訂正スキームである。
ランダムエラーの一定率を許容するコードの疑似ランダム性は、ほぼすべての汎用暗号プリミティブに対するブラックボックスの削減に基づいてはならないことを示す。
- 参考スコア（独自算出の注目度）: 10.791880225915257
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A pseudorandom code is a keyed error-correction scheme with the property that any polynomial number of encodings appear random to any computationally bounded adversary. We show that the pseudorandomness of any code tolerating a constant rate of random errors cannot be based on black-box reductions to almost any generic cryptographic primitive: for instance, anything that can be built from random oracles, generic multilinear groups, and virtual black-box obfuscation. Our result is optimal, as Ghentiyala and Guruswami (2024) observed that pseudorandom codes tolerating any sub-constant rate of random errors exist using a black-box reduction from one-way functions. The key technical ingredient in our proof is the hypercontractivity theorem for Boolean functions, which we use to prove our impossibility in the random oracle model. It turns out that this easily extends to an impossibility in the presence of ``crypto oracles,'' a notion recently introduced -- and shown to be capable of implementing all the primitives mentioned above -- by Lin, Mook, and Wichs (EUROCRYPT 2025).
- Abstract（参考訳）: 擬似乱数符号(英: pseudorandom code)は、任意の多項式数のエンコーディングが任意の計算上の有界敵に対してランダムに現れるという性質を持つ鍵付き誤り訂正スキームである。
ランダムエラーの一定率を許容するコードの擬似ランダム性は、ほとんどすべての一般的な暗号プリミティブに対するブラックボックスの削減(例えば、ランダムオラクル、汎用マルチ線形グループ、仮想ブラックボックスの難読化)に基づかないことを示す。
Ghentiyala と Guruswami (2024) は、ランダムな誤りを許容する疑似ランダム符号が、一方通行関数からのブラックボックス還元を用いて存在することを観察した。
証明の鍵となる技術的要素はブール関数の超収縮定理であり、これはランダムオラクルモデルにおける不合理性を証明するために用いられる。
これは、Lin, Mook, Wichs (EUROCRYPT 2025) が最近導入した概念である 'crypto oracles' の存在下で、簡単には不可能であることが判明した。
関連論文リスト
- Ideal Pseudorandom Codes [8.382679821011134]
擬似乱数符号は誤り訂正符号であり、効率のよい敵が一様ランダムな文字列から符号化を区別できない性質を持つ。
その後、いくつかの擬似乱数符号の構成が提案されているが、これらは以前に見られたコードワードに依存するエラーチャネルに対して堅牢なものではない。
単一ビットメッセージに対して適応的にロバストな擬似乱数符号を用いて、CCAセキュアな擬似乱数符号を構築することができることを示す。
論文 参考訳（メタデータ） (2024-11-08T20:22:14Z) - (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
微分可能性(Indifferentiability)は、理想的なオブジェクトのセキュリティを分析するための暗号パラダイムである。
その強さにもかかわらず、前処理攻撃に対するセキュリティを提供する無差別性は知られていない。
本稿では、構成可能であるだけでなく、任意の事前計算を考慮に入れた微分可能性の強化を提案する。
論文 参考訳（メタデータ） (2024-10-22T00:41:47Z) - Correcting Subverted Random Oracles [55.4766447972367]
簡単な構成は、少数の入力で元のものと矛盾する「反転」ランダムオラクルを、ランダム関数から微分不可能な対象に変換することができることを証明している。
この結果から, 暗号プリミティブの設計者は, 通常のクリプトグラフィ設定で, ランダムなオラクルを信頼できるブラックボックスとして使用することができる。
論文 参考訳（メタデータ） (2024-04-15T04:01:50Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Pseudorandom Error-Correcting Codes [0.716879432974126]
暗号置換や削除エラーに対して堅牢な擬似乱数符号を構築します。
ランダムな置換と削除の出力に対する検出不能な透かし方式を提案する。
第2の応用はステガノグラフィーで、秘密のメッセージが無実のコンテンツに隠されている。
論文 参考訳（メタデータ） (2024-02-14T18:17:45Z) - A Non-monotonic Self-terminating Language Model [62.93465126911921]
本稿では,不完全復号アルゴリズムによる非終端列の問題に焦点をあてる。
まず、グリーディ探索、トップ$kのサンプリング、核サンプリングを含む不完全確率復号アルゴリズムを定義する。
次に,単調な終端確率の制約を緩和する非単調な自己終端言語モデルを提案する。
論文 参考訳（メタデータ） (2022-10-03T00:28:44Z) - Cryptography from Pseudorandom Quantum States [6.164147034988822]
片道関数は擬似ランダム状態の存在を暗示するが、Kretschmer (TQC'20) は最近、一方通行関数が存在しないが擬似ランダム状態が存在するという相対的なオラクルを構築した。
疑似ランダム状態における興味深い暗号タスクの基盤となる可能性について検討する。
a)の結果として、疑似ランダム状態は不正にセキュアなマルチパーティプロトコルを構築するのに十分である。
論文 参考訳（メタデータ） (2021-12-18T22:53:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。