article

Logic Minimization Techniques with Applications to Cryptology

Authors:

Philip Matthews,

René PeraltaAuthors Info & Claims

Journal of Cryptology, Volume 26, Issue 2

Pages 280 - 312

https://doi.org/10.1007/s00145-012-9124-7

Published: 01 April 2013 Publication History

Abstract

A new technique for combinational logic optimization is described. The technique is a two-step process. In the first step, the nonlinearity of a circuit--as measured by the number of nonlinear gates it contains--is reduced. The second step reduces the number of gates in the linear components of the already reduced circuit. The technique can be applied to arbitrary combinational logic problems, and often yields improvements even after optimization by standard methods has been performed. In this paper we show the results of our technique when applied to the S-box of the Advanced Encryption Standard (FIPS in Advanced Encryption Standard (AES), National Institute of Standards and Technology, 2001 ).

We also show that, in the second step, one is faced with an NP-hard problem, the Shortest Linear Program (SLP) problem, which is to minimize the number of linear operations necessary to compute a set of linear forms. In addition to showing that SLP is NP-hard, we show that a special case of the corresponding decision problem is Max SNP-complete, implying limits to its approximability.

Previous algorithms for minimizing the number of gates in linear components produced cancellation-free straight-line programs, i.e., programs in which there is no cancellation of variables in GF(2). We show that such algorithms have approximation ratios of at least 3/2 and therefore cannot be expected to yield optimal solutions to nontrivial inputs. The straight-line programs produced by our techniques are not always cancellation-free. We have experimentally verified that, for randomly chosen linear transformations, they are significantly smaller than the circuits produced by previous algorithms.

References

[1]

S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and the hardness of approximation problems. J. Assoc. Comput. Mach. 45 , 501-555 (1998).

Digital Library

[2]

P. Austrin, S. Khot, M. Safra, Inapproximability of vertex cover and independent set in bounded degree graphs, in IEEE Conference on Computational Complexity (IEEE Computer Society, Los Alamitos, 2009), pp. 74-80.

[3]

D.J. Bernstein, Optimizing linear maps modulo 2, in Workshop Record of SPEED-CC: Software Performance Enhancement for Encryption and Decryption and Cryptographic Compilers . http://cr.yp.to/papers.html#linearmod2

[4]

L. Blum, M. Shub, S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull. Am. Math. Soc. 21 , 1-46 (1989).

[5]

J. Boyar, R. Peralta, Tight bounds for the multiplicative complexity of symmetric functions. Theor. Comput. Sci. 396 (1-3), 223-246 (2008).

Digital Library

[6]

J. Boyar, R. Peralta, Patent application number 61089998 filed with the U.S. Patent and Trademark Office. A new technique for combinational circuit optimization and a new circuit for the S-Box for AES, 2009.

[7]

J. Boyar, R. Peralta, A new combinational logic minimization technique with applications to cryptology, in 9th International Symposium on Experimental Algorithms, SEA 2010 . Lecture Notes in Computer Science, vol. 6049 (Springer, Berlin, 2010), pp. 178-189.

[8]

J. Boyar, R. Peralta, A depth-16 circuit for the AES S-box. Cryptology ePrint archive, report 2011/332, 2011. http://eprint.iacr.org/

[9]

J. Boyar, R. Peralta, D. Pochuev, On the multiplicative complexity of Boolean functions over the basis (¿ ¿ 1). Theor. Comput. Sci. 235 , 43-57 (2000).

[10]

J. Boyar, P. Matthews, R. Peralta, On the shortest linear straight-line program for computing linear forms, in 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008 . Lecture Notes in Computer Science, vol. 5162 (Springer, Berlin, 2008), pp. 168-179.

[11]

P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic Complexity Theory (Springer, Berlin, 1997), Chap. 13.

[12]

D. Canright, A very compact Rijndael S-box. Technical report NPS-MA-05-001, Naval Postgraduate School, 2005.

[13]

D. Canright, A very compact Rijndael S-box, in 7th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2005 . Lecture Notes in Computer Science, vol. 3659 (Springer, Berlin, 2005), pp. 441-455.

Digital Library

[14]

A.E.F. Clementi, L. Trevisan, Improved non-approximability results for vertex cover with density constraints, in Computing and Combinatorics (1996), pp. 333-342.

[15]

J.W. Cooley, J.W. Tukey, An algorithm for the machine calculation of complex Fourier series. Math. Comput. 19 , 297-301 (1965).

[16]

N. Courtois, D. Hulme, T. Mourouzis, Solving circuit optimisation problems in cryptography and cryptanalysis. IACR Cryptology ePrint Archive , 2011:475, 2011.

[17]

FIPS, Advanced Encryption Standard (AES) (National Institute of Standards and Technology, Gaithersburg, 2001).

[18]

C. Fuhs, P. Schneider-Kamp, Synthesizing shortest linear straight-line programs over GF(2) using SAT, in 13th International Conference on Theory and Applications of Satisfiability Testing . Lecture Notes in Computer Science, vol. 6175 (Springer, Berlin, 2010), pp. 71-84.

[19]

C. Fuhs, P. Schneider-Kamp, Optimizing the AES S-Box using SAT, in Proceedings of the 8th International Workshop on the Implementation of Logics (2010).

[20]

J. Håstad, Tensor rank is NP-Complete. J. Algorithms 11 (4), 644-654 (1990).

Digital Library

[21]

Y. Huang, D. Evans, J. Katz, L. Malka, Faster secure two-party computation using garbled circuits, in Proceedings of the 20th USENIX Security Symposium , San Francisco, CA, August 2011.

Digital Library

[22]

T. Itoh, S. Tsujii, A fast algorithm for computing multiplicative inverses in GF(2 ^m) using normal bases. Inf. Comput. 78 (3), 171-177 (1988).

Digital Library

[23]

E. Käsper, P. Schwabe, Faster and timing-attack resistant AES-GCM, in 11th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2009 . Lecture Notes in Computer Science, vol. 5747 (Springer, Berlin, 2009), pp. 1-17.

[24]

S. Khot, On the power of unique 2-prover 1-round games, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, STOC '02 , New York, NY, USA (ACM, New York, 2002), pp. 767- 775.

[25]

V. Kolesnikov, T. Schneider, Improved garbled circuit: free XOR gates and applications, in Proceedings of Automata, Languages and Programming, 35th International Colloquium, ICALP 2008 . Lecture Notes in Computer Science, vol. 5126 (Springer, Berlin, 2008), pp. 486-498.

[26]

O.B. Lupanov, A method of circuit synthesis. Izv. Vys¿. U¿ebn. Zaved., Radiofiz. 1 , 120-140 (1958).

[27]

E. Mastrovito, VLSI architectures for computation in Galois fields. Ph.D. thesis, Linköping University, Dept. Electr. Eng., Sweden, 1991.

[28]

S. Morioka, A. Satoh, An optimized S-Box circuit architecture for low power AES design, in Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2002 . Lecture Notes in Computer Science, vol. 2523 (Springer, Berlin, 2003), pp. 172-186.

[29]

Y. Nogami, K. Nekado, T. Toyota, N. Hongo, Y. Morikawa, Mixed bases for efficient inversion in f (((2 ²) ²) ²) and conversion matrices of subbytes of AES, in 12th International Workshop on Cryptographic Hardware and Embedded Systems, CHES 2010 . Lecture Notes in Computer Science, vol. 6225 (Springer, Berlin, 2010), pp. 234-247.

[30]

C. Paar, Some remarks on efficient inversion in finite fields, in 1995 IEEE International Symposium on Information Theory , Whistler, BC, Canada (1995), p. 58.

[31]

C. Paar, Optimized arithmetic for Reed-Solomon encoders, in IEEE International Symposium on Information Theory (1997), p. 250.

[32]

C. Papadimitriou, M. Yannakakis, Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43 , 425-440 (1991).

[33]

A. Satoh, S. Morioka, K. Takano, S. Munetoh, A compact Rijndael hardware architecture with S-Box optimization, in Advances in Cryptology--Proceedings of ASIACRYPT 01 . Lecture Notes in Computer Science, vol. 2248 (Springer, Berlin, 2001), pp. 239-254.

[34]

J.E. Savage, An algorithm for the computation of linear forms. SICOMP 3 (2), 150-158 (1974).

[35]

C. Shannon, The synthesis of two-terminal switching circuits. Bell Syst. Tech. J. 28 , 59-98 (1949).

[36]

L.G. Valiant, Completeness classes in algebra, in Proceedings of the 11th Annual ACM Symposium on the Theory of Computing (1979), pp. 249-261.

Digital Library

[37]

R. Williams, Matrix-vector multiplication in sub-quadratic time (some preprocessing required), in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (2007), pp. 995-1001.

[38]

S. Winograd, On the number of multiplications necessary to compute certain functions. Commun. Pure Appl. Math. 23 , 165-179 (1970).

[39]

J. Wolkerstorfer, E. Oswald, M. Lamberger, An ASIC implementation of AES SBoxes, in Topics in Cryptology--CT-RSA 2002 . Lecture Notes in Computer Science, vol. 2271 (Springer, Berlin, 2002), pp. 67-78.

Cited By

Dumas JPernet CSedoglavic A(2024)Strassen's algorithm is not optimally accurateProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669697(254-263)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669697
Bernstein DChou T(2024)CryptAttackTester: high-assurance attack analysisAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68391-6_5(141-182)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68391-6_5
Zhao ZLiu QFan YWang M(2024)Construction of Lightweight Low-Latency Involutory MDS MatricesApplied Cryptography and Network Security Workshops10.1007/978-3-031-61489-7_8(119-140)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-61489-7_8
Show More Cited By

Logic Minimization Techniques with Applications to Cryptology
1. Theory of computation

Recommendations

A new combinational logic minimization technique with applications to cryptology
SEA'10: Proceedings of the 9th international conference on Experimental Algorithms

A new technique for combinational logic optimization is described. The technique is a two-step process. In the first step, the non-linearity of a circuit – as measured by the number of non-linear gates it contains – is reduced. The second step reduces ...
Quantum Circuit Implementations of AES with Fewer Qubits
Advances in Cryptology – ASIACRYPT 2020
Abstract
We propose some quantum circuit implementations of AES with the following improvements. Firstly, we propose some quantum circuits of the AES S-box and S-box $^{- 1}$ , which require fewer qubits than prior work. Secondly, we reduce the number of qubits in ... $^{}$
Upper bound of the length of truncated impossible differentials for AES

On the provable security of a block cipher against impossible differential cryptanalysis, the maximal length of impossible differentials is an essential aspect. Most previous work on finding impossible differentials for AES, omits the non-linear ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Cryptology

Journal of Cryptology Volume 26, Issue 2

April 2013

183 pages

ISSN:0933-2790

Issue’s Table of Contents

Copyright © Copyright © 2013 International Association for Cryptologic Research.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dumas JPernet CSedoglavic A(2024)Strassen's algorithm is not optimally accurateProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669697(254-263)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669697
Bernstein DChou T(2024)CryptAttackTester: high-assurance attack analysisAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68391-6_5(141-182)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68391-6_5
Zhao ZLiu QFan YWang M(2024)Construction of Lightweight Low-Latency Involutory MDS MatricesApplied Cryptography and Network Security Workshops10.1007/978-3-031-61489-7_8(119-140)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1007/978-3-031-61489-7_8
Wang RSun DWong R(2023)Symbolic Minimization on Relational DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.322282735:9(9307-9318)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3222827
Swann RStine J(2023)Evaluation of a Modular Approach to AES Hardware Architecture and OptimizationJournal of Signal Processing Systems10.1007/s11265-022-01832-w95:7(797-813)Online publication date: 28-Feb-2023
https://dl.acm.org/doi/10.1007/s11265-022-01832-w
Liu QZhao ZWang M(2023)Improved Heuristics for Low-Latency Implementations of Linear LayersTopics in Cryptology – CT-RSA 202310.1007/978-3-031-30872-7_20(524-550)Online publication date: 24-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-30872-7_20
Häner TSoeken M(2022)Lowering the T-depth of Quantum Circuits via Logic Network OptimizationACM Transactions on Quantum Computing10.1145/35013343:2(1-15)Online publication date: 4-Mar-2022
https://dl.acm.org/doi/10.1145/3501334
Soeken MMykhailova MOshana R(2022)Automatic oracle generation in microsoft's quantum development kit using QIR and LLVM passesProceedings of the 59th ACM/IEEE Design Automation Conference10.1145/3489517.3530626(1363-1366)Online publication date: 10-Jul-2022
https://dl.acm.org/doi/10.1145/3489517.3530626
Liu HLi YChen YWang C(2022)A Don’t-Care-Based Approach to Reducing the Multiplicative Complexity in Logic NetworksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.314744441:11(4821-4825)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1109/TCAD.2022.3147444
Xu RXiang ZLin DZhang SHe DZeng X(2022)High-throughput block cipher implementations with SIMDJournal of Information Security and Applications10.1016/j.jisa.2022.10333370:COnline publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1016/j.jisa.2022.103333
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents