論文の概要: Public Key Encryption from High-Corruption Constraint Satisfaction Problems

• arxiv url: http://arxiv.org/abs/2604.10479v1
• Date: Sun, 12 Apr 2026 06:19:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-14 20:13:16.042305
• Title: Public Key Encryption from High-Corruption Constraint Satisfaction Problems
• Title（参考訳）: 高圧制約満足度問題からの公開鍵暗号
• Authors: Isaac M Hair, Amit Sahai,
• Abstract要約: 本稿では,2つの制約満足度問題(CSP)の推測的難解性に基づく,有意な準指数セキュリティを備えた公開鍵暗号方式を提案する。 我々の公開鍵暗号方式は、汚染度の高いCSPを初めて活用し、同時に準ポリノミカルよりも遥かに高いセキュリティレベルを達成する。
• 参考スコア（独自算出の注目度）: 6.201763450086127
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of which are instantiated with a corruption rate of $1 - o(1)$. First, we conjecture the hardness of a new large alphabet random predicate CSP (LARP-CSP) defined over an arbitrary but strongly expanding factor graph, where the vast majority of predicate outputs are replaced with random outputs. Second, we conjecture the hardness of the standard $k$XOR problem defined over a random factor graph, again where the vast majority of parity computations are replaced with random bits. In support of our hardness conjecture for LARP-CSPs, we give a variety of lower bounds, ruling out many natural attacks including all known attacks that exploit non-random factor graphs. Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial. At the heart of our work is a new method for planting cryptographic trapdoors based on the label extended factor graph for a CSP. Along the way to achieving our result, we give the first uniform construction of an error-correcting code that has an expanding, low density generator matrix while simultaneously allowing for efficient decoding from a $1 - o(1)$ fraction of corruptions.
• Abstract（参考訳）: 本稿では,2つの制約満足度問題 (CSP) の難易度を推定し,その2つの制約満足度問題 (CSP) を1-o(1)$の汚職率でインスタンス化することに基づく,有望な準指数セキュリティを備えた公開鍵暗号方式を提案する。 まず、任意の拡大係数グラフ上に定義された新しい大文字ランダム述語CSP(LARP-CSP)の硬さを予想する。 第二に、ランダム係数グラフ上で定義された標準$k$XOR問題の硬さを予想する。 LARP-CSPの硬さ予想を支持するため、非ランダム因子グラフを利用するすべての既知の攻撃を含む多くの自然な攻撃を除外し、様々な下界を与える。 我々の公開鍵暗号方式は、汚染度の高いCSPを初めて活用し、同時に準ポリノミカルよりもはるかに高いセキュリティレベルを達成する。 我々の研究の中心は、CSPのためのラベル拡張因子グラフに基づいて暗号トラップドアを植える新しい方法である。 結果の達成の過程で,拡張性,低密度のジェネレータ行列を持つ誤り訂正符号を一様に構築し,同時に1-o(1)$の破損率から効率的な復号を可能にする。

関連論文リスト

• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  量子コンピュータはShorのアルゴリズムを使って最新の暗号システムを破ることができる。 我々はまず、量子攻撃に対して安全とされるコードベースのスキームであるMcEliece暗号システムについて検討する。 次に,最短ベクトル問題を解くことの難しさを基礎とした格子型システムNTRUについて検討する。
  論文  参考訳（メタデータ） (2025-05-06T03:42:38Z)
• 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モデルをウォーターマークする新しい暗号プリミティブである。 本研究では,一定誤差率に対して頑健なPRCが存在するという仮定を考察する。 これは$textitunconditionally$ indistinguishable from random by $textpoly(n)$ time, $O(n1.5-varepsilon) spaceである。
  論文  参考訳（メタデータ） (2024-09-11T19:14:39Z)
• Implementation of Entropically Secure Encryption: Securing Personal Health Data [0.704590071265998]
  Entropically Secure Encryption (ESE) はOne-Time Padに短いキーで無条件のセキュリティを提供する。 バルク暗号のためのESEの実装について述べる。
  論文  参考訳（メタデータ） (2024-04-04T12:07:33Z)
• Lossy Cryptography from Code-Based Assumptions [7.880958076366762]
  高度な暗号プリミティブの拡散は、複雑性クラス$SZK$の難しい問題を暗示している。 これは、コードベースの仮定から高度なプリミティブを構築するための障壁となる。 我々は、Dense-Sparseという、複雑性クラス$BPPSZK$に該当する新しいコードベースの仮定を提案する。
  論文  参考訳（メタデータ） (2024-02-06T02:17:08Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  ターゲットの折り畳みは、公開可能な削除(PVD)を可能にすることを示す。 我々は、弱い暗号的仮定から公開可能な削除を支援する様々なプリミティブを得るために、このフレームワークを構築している。
  論文  参考訳（メタデータ） (2023-03-15T15:00:20Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  我々は、量子力学の非閉鎖原理に基づいて、キー呼び出し機能を備えた暗号スキームを設計する。 我々は、シークレットキーが量子状態として表現されるスキームを、シークレットキーが一度ユーザから取り消されたら、それらが以前と同じ機能を実行する能力を持たないことを保証して検討する。
  論文  参考訳（メタデータ） (2023-02-28T18:58:11Z)
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits [118.22458816174144]
  そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。 我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。 GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
  論文  参考訳（メタデータ） (2022-02-03T21:19:36Z)
• 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)

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

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