|
|||
|
IMADA - Department of Mathematics and Computer Science |
|
Cryptographic primitives such as encryption, digital signatures, and hashing are implemented as electronic circuits for a wide class of applications. A variety of metrics are relevant to designing "good" circuits. In particular, minimizing size and maximizing speed closely translates into the combinatorial problem of designing circuits with few gates and short depth. Solving this design problem, even approximately, is beyond current algorithmic and computational capabilities. For example, it is not known how many gates are necessary to implement the Advanced Encryption Standard (AES). For a function to be secure (one-way) it must be the case that any circuit that implements it is sufficiently complex. In particular, a function is insecure if it can be implemented by a circuit containing very few binary multiplication (i.e. AND) gates. This security metric, namely the number of AND gates necessary and sufficient to implement a function, is called multiplicative complexity. When it comes to comparing between two cryptographic functions we should, all other things being equal, prefer the one with higher multiplicative complexity. Unfortunately, there is no known practical algorithm to determine multiplicative complexity (even for predicates on as few as eight bits). This talk is a progress report on our research on circuit complexity. (This is joint work with Joan Boyar.) Host: Joan Boyar SDU HOME | IMADA HOME | Previous Page Last modified: Wed May 2 16:00:16 CEST 2007 Joan Boyar (joan@imada.sdu.dk) |