論文の概要: Multiple Subset Problem as an encryption scheme for communication
- arxiv url: http://arxiv.org/abs/2401.09221v2
- Date: Mon, 22 Jan 2024 18:45:37 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-25 12:27:42.421312
- Title: Multiple Subset Problem as an encryption scheme for communication
- Title（参考訳）: 通信用暗号化方式としての多重サブセット問題
- Authors: Yair Zadok, Nadav Voloch, Noa Voloch-Bloch, Maor Meir Hajaj,
- Abstract要約: 部分集合和問題(SSP)は、与えられた集合から整数のサブセットを見つけ、その和は指定された整数に等しいと定義することができる。
本稿では,MSSPに基づく暗号化方式を提案し,その新しい利用法と実装について述べる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Using well-known mathematical problems for encryption is a widely used technique because they are computationally hard and provide security against potential attacks on the encryption method. The subset sum problem (SSP) can be defined as finding a subset of integers from a given set, whose sum is equal to a specified integer. The classic SSP has various variants, one of which is the multiple-subset problem (MSSP). In the MSSP, the goal is to select items from a given set and distribute them among multiple bins, en-suring that the capacity of each bin is not exceeded while maximizing the total weight of the selected items. This approach addresses a related problem with a different perspective. Here a related different kind of problem is approached: given a set of sets A={A1, A2..., An}, find an integer s for which every subset of the given sets is summed up to, if such an integer exists. The problem is NP-complete when considering it as a variant of SSP. However, there exists an algorithm that is relatively efficient for known pri-vate keys. This algorithm is based on dispensing non-relevant values of the potential sums. In this paper we present the encryption scheme based on MSSP and present its novel usage and implementation in communication.
- Abstract（参考訳）: 暗号化によく知られた数学的問題を用いることは、計算的に困難であり、暗号化手法に対する潜在的な攻撃に対するセキュリティを提供するため、広く使われているテクニックである。
部分集合和問題(SSP)は、与えられた集合から整数のサブセットを見つけ、その和は指定された整数に等しいと定義することができる。
古典的なSSPには様々なバリエーションがあり、そのうちの1つはマルチサブセット問題(MSSP)である。
MSSPでは、選択したアイテムの総重量を最大化しながら、各ビンの容量が超えていないことを保証して、所定のセットからアイテムを選択し、複数のビンに分散させることが目的である。
このアプローチは、異なる視点で関連する問題に対処する。
ここで、関連する異なる種類の問題にアプローチする: 集合 A={A1, A2 の集合が与えられる。
., An} は、与えられた集合のすべての部分集合が、そのような整数が存在するならば、合計される整数 s を見つける。
問題は SSP の変種として考えるとき NP 完全である。
しかし、既知のpri-vateキーに対して比較的効率的なアルゴリズムが存在する。
このアルゴリズムは、ポテンシャル和の非関連値を排除することに基づいている。
本稿では,MSSPに基づく暗号化方式を提案する。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization [55.81991984375959]
本研究では、以下の簡単な観察を通して、個別化されたプライバシ会計を解析する新しい手法を提案する。
我々は、分解可能な部分モジュラーおよびセットアルゴリズム被覆を含む、プライベート最適化問題に対するいくつかの改良されたアルゴリズムを得る。
論文 参考訳（メタデータ） (2024-05-28T19:02:30Z) - Accelerated quantum search using partial oracles and Grover's algorithm [0.0]
グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成される結果集合から解を抽出するためにも用いられる。
マッチング条件の各ビットに個別のオラクルを関連付け、独立にテスト可能な複数の部分的なオラクル関数を得るという考え方を探求する。
アルゴリズムは最も単純な検索シナリオに対して検証され、入力されたインデックスビットは置換演算を用いてスクランブルされる。
論文 参考訳（メタデータ） (2024-03-19T11:32:02Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - A generalization of Bernstein-Vazirani algorithm with multiple secret
keys and a probabilistic oracle [0.0]
問題は、量子オラクルを使って複数の秘密鍵の集合から1つ以上の秘密鍵を見つけることである。
提案した量子アルゴリズムは(a)確率オラクルへの単一のクエリを用いて任意のキー(確実に)を取得することができる。
古典的なアルゴリズムでは、秘密鍵の1ビットも確実に見つけることができません。
論文 参考訳（メタデータ） (2023-01-21T19:34:57Z) - Longest Common Substring in Longest Common Subsequence's Solution
Service: A Novel Hyper-Heuristic [0.0]
最も長い共通部分列(Longest Common Subsequence、LCS)は、すべての文字列に共通であり、最も長い2つの性質を持つ文字列の集合の列を見つける問題である。
本稿では,その類似性に基づいて文字列の集合を分類する新しい基準を用いて,最も長い共通部分列問題の解法を提案する。
論文 参考訳（メタデータ） (2022-12-03T07:52:57Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR [10.391533135772699]
a average-case variant of a $k$-SUM conjecture(英語版)は、$r$乱数のリストで 0 に等しい数を見つけることは $rlceil k/2 rceil$ time よりもはるかに少ない。
リストがより多くの数を持ち、多くの解が存在する高密度なパラメータ体系では、その中の1つを見つける複雑さは、ワーグナーの$k$-treeアルゴリズムによって著しく改善される。
論文 参考訳（メタデータ） (2021-10-31T13:03:36Z) - Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。
複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。
ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文 参考訳（メタデータ） (2021-06-14T13:01:46Z) - Efficient Quantum Public-Key Encryption From Learning With Errors [1.8021287677546958]
我々の主な成果は、外挿二面コセット問題(EDCP)に基づく量子公開鍵暗号方式である。
公開鍵数に制限がある場合、提案方式は情報理論的に安全である。
論文 参考訳（メタデータ） (2021-05-26T18:48:26Z) - Towards Meta-Algorithm Selection [78.13985819417974]
インスタンス固有のアルゴリズム選択(AS)は、固定された候補集合からのアルゴリズムの自動選択を扱う。
メタアルゴリズムの選択は、いくつかのケースで有益であることを示す。
論文 参考訳（メタデータ） (2020-11-17T17:27:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。