Quartz 5

A Logic Synthesis Toolbox for Reducing the Multiplicative Complexity in Logic Networks

Properties1
tagspaper, fhe/circuit

5 min read

A Logic Synthesis Toolbox for Reducing the Multiplicative Complexity in Logic Networks

@inproceedings{testa2020logic,
  title={A logic synthesis toolbox for reducing the multiplicative complexity in logic networks},
  author={Testa, Eleonora and Soeken, Mathias and Riener, Heinz and Amaru, Luca and De Micheli, Giovanni},
  booktitle={2020 Design, Automation \& Test in Europe Conference \& Exhibition (DATE)},
  pages={568--573},
  year={2020},
  organization={IEEE},
  url={https://eprint.iacr.org/2020/706.pdf}
}

Abstract

XAG のANDゲートの数は、論理ネットワークの
multiplicative compexity
と呼ばれ, FHEで重要

また、ANDゲートの数は、論理回路の脆弱性を評価する上でも重要です。

しかし、これまでのところ、論理ネットワークの乗法的複雑さを軽減するための完全な論理合成フローはありません

本論文では、暗号用の論理合成ツールボックスを提案します。

再置換、リファクタリング、書き換えという強力な変換で構成され、特に
XAG
の乗法的な複雑さを最小化するように設計されています

正規化幾何平均値
は0.82となりました。

Introduction

以前は論理合成は
CMOS回路
の最適化にフォーカスされていた

最近は暗号用の回路合成に使われている

なぜなら, 暗号回路は AND, XOR, NOTゲートからなる
XAG
なので

ANDゲートの数を最小化するのは2つの理由

multiplicative complexity
: ANDゲートの数

回路の
degree of vulnerability
に相関するから

algebraic attacks
に対する耐性

Zero knowledge
protocols,
MPC
,
FHE
などの高度な暗号プロトコルで重要な役割

e.g.
MPC-in-the-head
に基づく耐量子ゼロ知識署名のサイズは
ブロック暗号
の
multiplicative_complexity
に依存

e.g.
XOR technique
を用いた Yao の
garbled circuits
の計算

量子回路においても, 量子ビット数や量子演算の数を減らすことに
Reducing_the_Multiplicative_Complexity_in_Logic_Networks_for_Cryptography_and_Security_Applications
は暗号向けの回路書き換えアルゴリズム

他方で, 回路合成用ツールも色々あるが, ANDゲートの数を最小化は出来ない

本研究では6入力の小さなサブネットワークを書き換えに焦点をあてた
Reducing the Multiplicative Complexity in Logic Networks for Cryptography and Security Applications
を克服

XAG
で関数を表現, 書き換え -> リファクタリング -> 再置換をANDゲート最小化の為に行う

EPFL Benchmark
, FHEアプリケーションの回路について比較

32bit multiplier のANDゲートの数を59%削減

Background

XAGs and Multiplicative Complexity

fig1: どちらも
multiplicative complexity
は1

点線は反転していることを表す(

) と等価ので置き換えられる

Rewriting Algorithm for Cryptography Applications

グラフ書き換えアルゴリズムは幅広い用途(e.g. ノード数, レベル数の最適化)で使用可能

サブネットワークは事前計算可能

Reducing the Multiplicative Complexity in Logic Networks for Cryptography and Security Applications
では
DAG-Aware AIG rewriting
の一般化

cut enumeration
をコストの調整を計算に?

affine functions classification
: 6-input XAGを最適化に

multiplicative complexity
は
affine operations
で不変

最適な
XAG
は知られている

それぞれの
affine class
は最大6-inputs まで(詳しくは 5 を参照

Logic Synthesis Toolkit for Cryptography and security

再置換とリファクタリングを紹介

Resubstitution

あるノード

の機能をすでにある別ノードで代替する
よりコンパクトなら置き換える
0-resubstitution: 新しいノードを追加しない

1-resubstitution: 1つ


ノードを追加したとき, もし改善が

なら

はノード

の
Maximum Fanout Free Cone
のノード数

プール回路のアフィン変換https://www.rocq.inria.fr/secret/Anne.Canteaut/poly.pdf
の1.4.3みる

Graph View

Backlinks