論文の概要: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
- arxiv url: http://arxiv.org/abs/2401.03703v1
- Date: Mon, 8 Jan 2024 07:14:54 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-09 17:25:06.111393
- Title: On Lattices, Learning with Errors, Random Linear Codes, and Cryptography
- Title（参考訳）: 格子、誤りを伴う学習、ランダム線形符号および暗号について
- Authors: Oded Regev
- Abstract要約: 主な結果は、GapSVPやSIVPのような最悪の格子問題から、ある学習問題への還元である。
本稿では,学習問題の難易度に基づく(古典的な)公開鍵暗号システムを提案する。
- 参考スコア（独自算出の注目度）: 0.27195102129094995
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Our main result is a reduction from worst-case lattice problems such as
GapSVP and SIVP to a certain learning problem. This learning problem is a
natural extension of the `learning from parity with error' problem to higher
moduli. It can also be viewed as the problem of decoding from a random linear
code. This, we believe, gives a strong indication that these problems are hard.
Our reduction, however, is quantum. Hence, an efficient solution to the
learning problem implies a quantum algorithm for GapSVP and SIVP. A main open
question is whether this reduction can be made classical (i.e., non-quantum).
We also present a (classical) public-key cryptosystem whose security is based
on the hardness of the learning problem. By the main result, its security is
also based on the worst-case quantum hardness of GapSVP and SIVP. The new
cryptosystem is much more efficient than previous lattice-based cryptosystems:
the public key is of size $\tilde{O}(n^2)$ and encrypting a message increases
its size by a factor of $\tilde{O}(n)$ (in previous cryptosystems these values
are $\tilde{O}(n^4)$ and $\tilde{O}(n^2)$, respectively). In fact, under the
assumption that all parties share a random bit string of length
$\tilde{O}(n^2)$, the size of the public key can be reduced to $\tilde{O}(n)$.
- Abstract（参考訳）: 主な結果は、gapsvpやsivpといった最悪の場合の格子問題から特定の学習問題への削減です。
この学習問題は‘パリティからエラーへの学習’問題をより高いモジュライに自然な拡張である。
これはまた、ランダムな線形コードから復号する問題と見なすこともできる。
これは、これらの問題が難しいという強い兆候だ、とわれわれは信じている。
しかし、我々の減少は量子的だ。
したがって、学習問題の効率的な解はgapsvpとsivpの量子アルゴリズムを意味する。
主な疑問は、この還元が古典的(すなわち非量子的)にできるかどうかである。
また,学習問題の難易度に基づくセキュリティを備えた(古典的な)公開鍵暗号システムを提案する。
その結果、そのセキュリティは、GapSVPとSIVPの最悪の量子硬度にも基づいている。
公開鍵は$\tilde{O}(n^2)$で、メッセージの暗号化は$\tilde{O}(n)$(以前の暗号システムでは$\tilde{O}(n^4)$と$\tilde{O}(n^2)$)でそのサイズを増大させる。
実際、すべての当事者が長さ$\tilde{O}(n^2)$のランダムビット列を共有するという仮定の下で、公開鍵のサイズは$\tilde{O}(n)$に縮めることができる。
関連論文リスト
- On encoded quantum gate generation by iterative Lyapunov-based methods [0.0]
本稿では,量子ゲート生成の符号化問題について述べる。
emphReference Input Generation Algorithm (RIGA) はこの研究で一般化されている。
論文 参考訳（メタデータ） (2024-09-02T10:41:15Z) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳（メタデータ） (2024-06-18T08:54:04Z) - A Quantum Approach for Reducing Communications in Classical
Cryptographic Primitives [2.3465488122819123]
我々は、おそらく驚くべきことに、より弱い仮定の下で量子技術でこの問題を解決することが可能であることを示した。
我々の研究は、量子暗号が新しいタイプの問題で古典的暗号より優れているという興味深いメッセージを伝える。
論文 参考訳（メタデータ） (2023-10-08T16:07:46Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Revocable Cryptography from Learning with Errors [61.470151825577034]
我々は、量子力学の非閉鎖原理に基づいて、キー呼び出し機能を備えた暗号スキームを設計する。
我々は、シークレットキーが量子状態として表現されるスキームを、シークレットキーが一度ユーザから取り消されたら、それらが以前と同じ機能を実行する能力を持たないことを保証して検討する。
論文 参考訳（メタデータ） (2023-02-28T18:58:11Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
ブロックサイズ$n$に対して$p$が小さい$q = pm$の場合、時間内の問題を解く量子アルゴリズムが存在することを示す。
一方、古典的アルゴリズムはこの問題をはるかに小さな逆因子に対してのみ効率的に解くことができる。
論文 参考訳（メタデータ） (2022-10-20T19:35:50Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Efficient Quantum Public-Key Encryption From Learning With Errors [1.8021287677546958]
我々の主な成果は、外挿二面コセット問題(EDCP)に基づく量子公開鍵暗号方式である。
公開鍵数に制限がある場合、提案方式は情報理論的に安全である。
論文 参考訳（メタデータ） (2021-05-26T18:48:26Z) - Lattice sieving via quantum random walks [0.0]
格子ベースの暗号は、量子後暗号の主要な提案の一つである。
最短ベクトル問題(SVP)は、格子ベースの暗号の暗号解析において最も重要な問題である。
我々は、$d$が格子次元であるような20.2570 d + o(d)$のランニング時間を持つアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-12T11:59:30Z) - Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU
Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。
正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文 参考訳（メタデータ） (2020-06-22T17:53:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。