Determining Affine and Extended Affine Equivalence of Boolean Functions with SAT [July 3, 2020]


by Luis Moraes and Rakesh Verma presented by Luis Moraes for the 11th Pragmatics of SAT International workshop (

Many cryptographically desirable properties of Boolean functions are preserved by affine and extended affine equivalence. Thus, being able to determine equivalence between Boolean functions efficiently is useful in cryptography. We present an encoding of affine and extended affine equivalence into SAT. We experiment with different encodings and demonstrate how implicit constraints affect performance. In addition, we draw parallels between known algorithms and these encodings.


Added by :
Daniel Le Berre

Updated on :
July 4, 2020, 11:55 a.m.

Duration :

Number of view :
3 (Show details views)

Type :

Main language :