論文の概要: A New Tool to Find Lightweight (And, Xor) Implementations of Quadratic Vectorial Boolean Functions up to Dimension 9

• arxiv url: http://arxiv.org/abs/2601.08368v1
• Date: Tue, 13 Jan 2026 09:31:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-14 18:27:19.13574
• Title: A New Tool to Find Lightweight (And, Xor) Implementations of Quadratic Vectorial Boolean Functions up to Dimension 9
• Title（参考訳）: 四重項ベクトルブール関数の軽量化(およびXor)のための新しいツール -次元9まで-
• Authors: Marie Bolzer, Sébastien Duval, Marine Minier,
• Abstract要約: 暗号学では、焦点は小さな関数であり、そのため、小さな関数のための新しい専用のツールが必要である。 そこで本研究では,AND-deepth 1 で最大9ビットの二次関数を実装するための新しいツールを提案する。
• 参考スコア（独自算出の注目度）: 0.19116784879310025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of finding a minimal circuit to implement a given function is one of the oldest in electronics. It is known to be NP-hard. Still, many tools exist to find sub-optimal circuits to implement a function. In electronics, such tools are known as synthesisers. However, these synthesisers aim to implement very large functions (a whole electronic chip). In cryptography, the focus is on small functions, hence the necessity for new dedicated tools for small functions. Several tools exist to implement small functions. They differ by their algorithmic approach (some are based on Depth-First-Search as introduced by Ullrich in 2011, some are based on SAT-solvers like the tool desgined by Stoffelen in 2016, some non-generic tools use subfield decomposition) and by their optimisation criteria (some optimise for circuit size, others for circuit depth, and some for side-channel-protected implementations). However, these tools are limited to functions operating on less than 5 bits, sometimes 6 bits for quadratic functions, or to very simple functions. The limitation lies in a high computing time. We propose a new tool (The tool is provided alongside the IEEE article with CodeOcean and at https://github.com/seduval/implem-quad-sbox) to implement quadratic functions up to 9 bits within AND-depth 1, minimising the number of AND gates. This tool is more time-efficient than previous ones, allowing to explore larger implementations than others on 6 bits or less and allows to reach larger sizes, up to 9 bits.
• Abstract（参考訳）: 与えられた機能を実装するための最小限の回路を見つける問題は、エレクトロニクスで最も古いものの一つである。 NPハードであることが知られている。 それでも、関数を実装するための準最適回路を見つけるための多くのツールが存在する。 電子工学では、そのようなツールは合成器として知られている。 しかし、これらの合成装置は、非常に大きな機能(全電子チップ)を実装することを目的としている。 暗号学では、焦点は小さな関数であり、そのため、小さな関数のための新しい専用のツールが必要である。 小さな機能を実装するためのツールがいくつか存在する。 アルゴリズムのアプローチの違い(2011年にUllrichによって導入されたDepth-First-Searchに基づくものもあれば、2016年にStoffelenによって導入されたツールのようなSAT-solverをベースとするものもある)と最適化基準(回路サイズ、回路深度、サイドチャネル保護実装など)によって異なる。 しかし、これらのツールは5ビット未満の関数、時には2次関数の6ビット、あるいは非常に単純な関数に限られる。 この制限は高い計算時間にある。 我々は、and-deepth 1で最大9ビットの二次関数を実装する新しいツール(CodeOceanとhttps://github.com/seduval/implem-quad-sbox)を提案する。 このツールは以前のものよりも時間効率が良く、6ビット以下で他のものよりも大きな実装を探索でき、最大9ビットまで大きなサイズに到達できる。

関連論文リスト

• Cirbo: A New Tool for Boolean Circuit Analysis and Synthesis [31.950717571266026]
  ブール回路を操作するためのオープンソースツールを提案する。 これは、様々な頻繁に使用される回路タスクに対して、既存および新規両方の効率的なアルゴリズムを実装している。 このツールは、IWLS 2024 Programming Contestの優勝に役立ちました。
  論文  参考訳（メタデータ） (2024-12-19T15:10:31Z)
• Finding Transformer Circuits with Edge Pruning [71.12127707678961]
  自動回路発見の効率的かつスケーラブルなソリューションとしてエッジプルーニングを提案する。 本手法は,従来の手法に比べてエッジ数の半分未満のGPT-2の回路を探索する。 その効率のおかげで、Edge PruningをCodeLlama-13Bにスケールしました。
  論文  参考訳（メタデータ） (2024-06-24T16:40:54Z)
• Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
  我々は,ゼロアンシラ量子ビットを用いた準四進時間量子乗法の新しいパラダイムを導入する。 関連するキュービットは入力と出力レジスタ自身のみである。 我々のアルゴリズムは、実際的な問題の大きさよりも優れている可能性がある。
  論文  参考訳（メタデータ） (2024-03-26T18:00:03Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• SAT-based Circuit Local Improvement [77.36158507255637]
  正確な回路サイズを見つけることは、実際よく知られた最適化問題である。 与えられた回路の周りのボール内の小さな回路を検索します。 各種対称関数を用いた実験結果について報告する。
  論文  参考訳（メタデータ） (2021-02-19T16:01:50Z)
• Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function [7.140119152422295]
  一般的には、隠れ重み付きビット関数は可逆アンシラ自由回路による実装において指数関数的に困難である。 我々はサイズ$O(n6.42)$の可逆アンシラフリー回路を開発し、$n$はビット数である。 また、この関数はサイズ$O(n2)$の量子アンシラ自由回路で計算可能であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T16:30:58Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)

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

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