Skip to Content


Jointly Owned Invention Available for Non-Exclusive, Royalty-Free Licensing for Advanced Encryption Standard S-box Applications

Document Details

Information about this document as published in the Federal Register.

Published Document

This document has been published in the Federal Register. Use the PDF linked in the document sidebar for the official electronic format.

Start Preamble


National Institute of Standards and Technology, Commerce.


Notice of jointly owned invention available for non-exclusive, royalty-free licensing for Advanced Encryption Standard S-box applications.


The invention listed below is jointly owned by the U.S. Government, as represented by the Department of Commerce, and the University of Southern Denmark. The Department of Commerce's interest in the invention is available for non-exclusive, royalty-free licensing in the Field of Use of Advanced Encryption Standard S-box applications, in accordance with 35 U.S.C. 207 and 37 CFR part 404 to achieve expeditious commercialization of results of federally funded research and development.

Start Further Info


Technical and licensing information on this invention may be obtained by writing to: National Institute of Standards and Technology, Office of Technology Partnerships, Building 820, Room 213, Gaithersburg, MD 20899. Information is also available via telephone: 301-975-3084, fax 301-975-3482, or e- mail: Any request for information should include the NIST Docket number or Patent number and title for the invention as indicated below. The invention available for licensing is:

[Patent Number Application No. 12/367,660 filed February 9, 2009]


Title: A New Technique for Combinational Circuit Optimization and a New Circuit for the S-Box of AES.

Abstract: A method of simplifying a combinational circuit establishes an initial combinational circuit operable to calculate a set of target signals. A quantity of multiplication operations performed in a first portion of the initial combinational circuit is reduced to create a first, simplified combinational circuit. The first portion includes only multiplication operations and addition operations. A quantity of addition operations performed in a second portion of the first, simplified combinational circuit is reduced to create a second, simplified combinational circuit. The second portion includes only addition operations. Also, the second, simplified combinational circuit is operable to calculate the target signals using fewer operations than the initial combinational circuit.

A computer-implemented method of simplifying a plurality of formulas establishes a plurality of formulas. The formulas include only addition operations, and the formulas correspond to a portion of a combinational circuit including only addition operations. A basis set including a plurality of input signals is defined. Using a computer, a distance vector is determined that includes one value for each of the plurality of formulas, the one value corresponding to a number of addition operations necessary to calculate a corresponding formula using signals from the basis set. Using the computer, two basis vectors are determined whose sum, when added to the distance vector, reduces at least one value in the distance vector, and the sum is added to the basis set. The steps of determining two basis vectors whose sum, when added to the basis set, reduces at least one value in the distance vector, and adding the sum to the basis set may be selectively repeated until the basis set includes sums corresponding to each of the plurality of formulas.

A combinational circuit for a Substitution-Box for the Advanced Encryption Standard having a total of 115 Boolean gates comprises a first, input portion, a second portion coupled to the first, input portion, and a third, output portion coupled to the second portion. The first, input portion has 23 XOR gates. The second portion has 30 XOR gate and 32 AND gates, and computes the non-linear component of inversion in GF(256). Also, in the second portion 11 of the 30 XOR gates and 5 of the 32 AND gates are operable to perform inversion in GF(16). The third, output portion has 26 XOR gates and 4 XNOR gates.

Start Signature

Dated: June 18, 2009.

Patrick Gallagher,

Deputy Director.

End Signature End Further Info End Preamble

[FR Doc. E9-14734 Filed 6-22-09; 8:45 am]