Optimal SAT solver synthesis of quantum circuits representing cryptographic nonlinear functions

Adam Stanisław Jagielski


In this article we present a procedure that allows
to synthesize optimal circuit representing any reversible function
within reasonable size limits. The procedure allows to choose
either theNCTor theMCTgate set and specify any number of
ancillary qubits to be used in the circuit. We will explore efficacy
of this procedure by synthesizing various sources of nonlinearity
used in contemporary symmetric ciphers and draw conclusions
about properties of those transformations in quantum setting. In
particular we will try to synthesize optimal circuit representing
ASCON cipher SBOX which recently won NIST competition for
Lightweight Cryptography standard.

Full Text:



R. Wille and R. Drechsler, Towards a Design Flow for Reversible Logic.

Dordrecht: Springer Netherlands, 2010.

C. Sinz, “Towards an Optimal CNF Encoding of Boolean Cardinality

Constraints,” in Principles and Practice of Constraint Programming - CP

, D. Hutchison, T. Kanade, J. Kittler, J. M. Kleinberg, F. Mattern,

J. C. Mitchell, M. Naor, O. Nierstrasz, C. Pandu Rangan, B. Steffen,

M. Sudan, D. Terzopoulos, D. Tygar, M. Y. Vardi, G. Weikum, and P. van

Beek, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005, vol.

, pp. 827–831.

D. Miller, D. Maslov, and G. Dueck, “A transformation based algorithm

for reversible logic synthesis,” in Proceedings - Design Automation

Conference, Jul. 2003, pp. 318–323.

J. Daemen, S. Hoffert, M. Peeters, G. Van Assche, and R. Van Keer,

“Xoodyak, a lightweight cryptographic scheme,” IACR Transactions on

Symmetric Cryptology, pp. 60–87, Jun. 2020.

T. Beyne, C. Yu Long, C. Dobraunig, and b. Mennink,

“Elephant v2,” https://csrc.nist.gov/CSRC/media/Projects/lightweight-



S. Banik, A. Chakraborti, T. Iwata, K. Minematsu, M. Nandi,

T. Peyrin, Y. Sasaki, S. Meng Sim, and Y. Todo, “Gift-cofb

v1.1,” https://csrc.nist.gov/CSRC/media/Projects/lightweight-



Z. Bao, A. Chakraborti, N. Datta, J. Guo, M. Nandi, T. Peyrin,

and K. Yasuda, “Photon-beetle authenticated encryption and

hash family,” https://csrc.nist.gov/CSRC/media/Projects/lightweight-



R. C.-W. Phan, “Mini advanced encryption standard (mini-aes): A

testbed for cryptanalysis students,” Cryptologia, vol. 26, no. 4, pp. 283–

, Oct. 2002.

V. Rijmen and P. S. L. M. Barreto, “The whirlpool hashing function,”

W. Hongjun, “The hash function jh,”

https://www3.ntu.edu.sg/home/wuhj/research/jh/jh round3.pdf, 2011.

C. Dobraunig, M. Eichlseder, F. Mendel, and

M. Schl ̈affer, “Ascon v1.2 submission to nist,”




G. Bertoni, J. Daemen, M. Peeters, and G. Van Assche, “Keccak

specifications,” http://keccak.noekeon.org/


  • There are currently no refbacks.

International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933