Combinational circuit, encryption circuit, method for constructing the same and program

A combinational circuit including a plurality of selectors, the combinational circuit comprising:

• a 2n:1 selector that replaces a predetermined number n of stages of 2:1 selectors on the output side in 2:1 selectors connected to each other to form a number of stages, the number being equal to or less than a number of bits of a primary input, on a condition that, at least in the n stages of 2:1 selectors, no 2:1 selector is shared among groups of 2:1 selectors for generating a plurality of output bits;
• and
• 2:1 selectors remaining after the replacement with said 2n:1 selector,
• wherein said 2n:1selector comprises:
• a generator circuit for generating a select signal for determining which is selected among from 2n inputs;
• and
• a selection circuit for selecting one of the 2n inputs based on the select signal generated in said generator circuit.

An encryption circuit including an S-Box, wherein

• a combinational circuit equivalent to said S-Box comprises:
• a number of independent selector groups for each generating an output bit separately, the number corresponding to number of the output bits;
• and
• a driver for supplying a primary input to each of said selector groups, and
• each of said selector groups comprises a plurality of selectors connected to each other to form a number of stages, the number of stages being equal to or less than number of bits of said primary input, and
• a select signal for said selectors in each stage is driven by one said primary input.

An encryption circuit including an S-Box, wherein a combinational circuit equivalent to said S-Box comprises:

• a 2n:1 selector that replaces a predetermined number n of stages of 2:1 selectors on the output side in 2:1 selectors connected to each other to form a number of stages, the number being equal to or less than number of bits of a primary input, on a condition that, at least in the n stages of 2:1 selectors, no 2:1 selector is shared among groups of 2:1 selectors for generating a plurality off output bits;
• and
• 2:1 selectors remaining after the replacement with said 2n:1 selector, and
• said 2n:1 selector comprises:
• a generator circuit for generating a select signal for determining which is selected among from 2n inputs;
• and
• a selection circuit for selecting one of the 2n inputs based on the select signal generated in said generator circuit.

A method for constructing a combinational circuit using RO-BDD (Reduced Ordered Binary Decision Diagrams), the method comprising the steps of:

• creating a number of RO-BDDs that share no node therebetween and have different sequences of variables, the number corresponding to number of output bits;
• replacing each node in each of said RO-BDDS with a selector;
• and
• providing a driver chain for generating a control signal for each of said selectors and connecting said selectors and the driver chains to each other by associating the stages of said selectors based on said RO-BDD with the driver chains.

A method for constructing a combinational circuit using RO-BDD (Reduced Ordered Binary Decision Diagrams), the method comprising the steps of:

• creating an RO-BDD having a complete tree structure with number of nodes in a predetermined number n of stages on the output side corresponding to number of output bits;
• replacing said n stages of nodes in said RO-BDD with a 2n:1 selector comprising a generator circuit for generating a select signal for determining which is selected among from 2n inputs and a selection circuit for selecting one of the 2n inputs based on the select signal;
• and
• replacing the other nodes with 2:1 selectors.

A program for controlling a computer to logically synthesize a circuit structure of a combinational circuit, wherein the program causes said computer to execute the processings of:

• reading from a memory a logical formula or truth table of the combinational circuit to be processed and splitting the logical formula or truth table for each output bit to generate logical formulas or truth tables each for 1-bit output;
• determining, for each of said logical formula or truth table for 1-bit output, a sequence of variables of an RO-BDD (Reduced Ordered Binary Decision Diagrams) while avoiding overlap with other logical formula or truth table, constructing a shared-RO-BDD for the logical formula or truth table according to the sequence of variables and mapping each node in the shared-RO-BDD to a 2:1 selector;
• providing a driver chain for generating a control signal for each of said 2:1 selectors and connecting the driver chain to the control signal of said RO-BDD;
• and
• storing in said memory the logical formula or truth table for the combinational circuit for which selectors have been mapped and the driver chains have been set.

A recording medium having a program for controlling a computer to logically synthesize a circuit structure of a combinational circuit recorded therein in a computer-readable manner, wherein said program causes said computer to execute the steps of:

• reading from a memory a logical formula or truth table of the combinational circuit to be processed and splitting the logical formula or truth table for each output bit to generate logical formulas or truth tables each for 1-bit output;
• determining, for each of said logical formula or truth table for 1-bit output, a sequence of variables of an RO-BDD (Reduced Ordered Binary Decision Diagrams) while avoiding overlap with other logical formula or truth table, constructing a shared-RO-BDD for the logical formula or truth table according to the sequence of variables and mapping each node in the shared-RO-BDD to a 2:1 selector;
• providing a driver chain for generating a control signal for each of said 2:1 selectors and connecting the driver chain to the control signal of said RO-BDD;
• and
• storing in said memory the logical formula or truth table for the combinational circuit for which selectors have been mapped and the driver chains have been set.

A method comprising:

• constructing an encryption circuit including an S-Box, such that a combinational circuit equivalent to said S-Box comprises:
• a number of independent selector groups for each generating an output bit separately, the number corresponding to number of the output bits;
• and
• a driver for supplying a primary input to each of said selector groups, and
• each of said selector groups comprises a plurality of selectors connected to each other to form a number of stages, the number of stages being equal to or less than number of bits of said primary input, and
• a select signal for said selectors in each stage is driven by one said primary input.