論文の概要: Evolutionary Construction of Perfectly Balanced Boolean Functions
- arxiv url: http://arxiv.org/abs/2202.08221v1
- Date: Wed, 16 Feb 2022 18:03:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-25 16:28:51.787650
- Title: Evolutionary Construction of Perfectly Balanced Boolean Functions
- Title（参考訳）: 完全平衡ブール関数の進化的構築
- Authors: Luca Mariot, Stjepan Picek, Domagoj Jakobovic, Marko Djurasevic,
Alberto Leporati
- Abstract要約: 遺伝的プログラミング (GP) と遺伝的アルゴリズム (GA) を用いて, 特性, 完全均衡性, および優れた非線形性プロファイルを満たすブール関数を構築する。
意外なことに、重み付けされた表現を持つGAは、非常に非線形なWPB関数を見つける際に、古典的真理表表現型でGPより優れていた。
- 参考スコア（独自算出の注目度）: 7.673465837624365
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding Boolean functions suitable for cryptographic primitives is a complex
combinatorial optimization problem, since they must satisfy several properties
to resist cryptanalytic attacks, and the space is very large, which grows super
exponentially with the number of input variables. Recent research has focused
on the study of Boolean functions that satisfy properties on restricted sets of
inputs due to their importance in the development of the FLIP stream cipher. In
this paper, we consider one such property, perfect balancedness, and
investigate the use of Genetic Programming (GP) and Genetic Algorithms (GA) to
construct Boolean functions that satisfy this property along with a good
nonlinearity profile. We formulate the related optimization problem and define
two encodings for the candidate solutions, namely the truth table and the
weightwise balanced representations. Somewhat surprisingly, the results show
that GA with the weightwise balanced representation outperforms GP with the
classical truth table phenotype in finding highly nonlinear WPB functions. This
finding is in stark contrast to previous findings on the evolution of globally
balanced Boolean functions, where GP always performs best.
- Abstract（参考訳）: 暗号プリミティブに適したブール関数を見つけることは、暗号解析攻撃に抵抗するためにいくつかの特性を満たす必要があるため、複雑な組合せ最適化問題であり、空間は非常に大きく、入力変数の数に非常に指数関数的に増加する。
近年の研究では、FLIPストリーム暗号の開発における重要性から、制限された入力セット上の特性を満たすブール関数の研究に焦点が当てられている。
本稿では, 遺伝的プログラミング (GP) と遺伝的アルゴリズム (GA) を用いて, この特性を満たすブール関数を, 優れた非線形性プロファイルとともに構築する手法について検討する。
関連する最適化問題を定式化し、候補解の2つの符号化、すなわち真理表と重み付き平衡表現を定義する。
やや意外なことに、重み付き平衡表現を持つgaは、高度に非線形な wpb 関数を見つける際に、古典的な真理表 phenotype を持つgp よりも優れていることを示している。
この発見は、GPが常に最高に機能するグローバル平衡ブール関数の進化に関する以前の発見とは対照的である。
関連論文リスト
- A Discrete Particle Swarm Optimizer for the Design of Cryptographic
Boolean Functions [1.6574413179773761]
このアルゴリズムはHu, Eberhart, Shiによる置換PSOの修正版である。
PSO速度方程式のパラメータは2つのメタ最適化手法を用いて調整される。
論文 参考訳（メタデータ） (2024-01-09T14:08:42Z) - A Search for Nonlinear Balanced Boolean Functions by Leveraging
Phenotypic Properties [3.265773263570237]
非線型値の高い完全平衡ブール関数を求める問題を考察する。
このような関数は暗号や誤り訂正符号理論のような領域に広く応用されている。
そこで本研究では,その基礎となる問題の構造を利用した局所探索手法を用いて,そのような関数の探索手法を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:16:19Z) - Promises and Pitfalls of the Linearized Laplace in Bayesian Optimization [73.80101701431103]
線形化ラプラス近似(LLA)はベイズニューラルネットワークの構築に有効で効率的であることが示されている。
ベイズ最適化におけるLLAの有用性について検討し,その性能と柔軟性を強調した。
論文 参考訳（メタデータ） (2023-04-17T14:23:43Z) - Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean
Functions [8.382710169577447]
ビットストリング符号化における遺伝的演算子の非線形性を最適化する効果について検討する。
オペレータが提供できる可能性のある変更の範囲を観察することで、この情報を使用して、より効果的な遺伝子操作子の組み合わせを設計することができる。
論文 参考訳（メタデータ） (2023-02-12T10:34:01Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions [37.84234862910533]
遺伝的プログラミングは、高い非線形性を持つバランスの取れたブール関数をもたらす構造を進化させることができることを示す。
以上の結果から,GP はよく一般化される構造,すなわち,複数のテストサイズに必要な関数を見つけることができることがわかった。
興味深いことに、GPによって発見された最も単純な解は、よく知られた間接和構成の特別な場合である。
論文 参考訳（メタデータ） (2022-02-17T16:33:24Z) - Fractal Structure and Generalization Properties of Stochastic
Optimization Algorithms [71.62575565990502]
最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。
さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
論文 参考訳（メタデータ） (2021-06-09T08:05:36Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Building powerful and equivariant graph neural networks with structural
message-passing [74.93169425144755]
本稿では,2つのアイデアに基づいた,強力かつ同変なメッセージパッシングフレームワークを提案する。
まず、各ノードの周囲の局所的コンテキスト行列を学習するために、特徴に加えてノードの1ホット符号化を伝搬する。
次に,メッセージのパラメトリゼーション手法を提案する。
論文 参考訳（メタデータ） (2020-06-26T17:15:16Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。