Cryptology and Complexity Theory

The efficiency of cryptographic systems and protocols has been the focus of our recent work in cryptology. Many cryptographic protocols involve proving predicates about a string X that is available in committed form only, i.e., the bits of X are individually encrypted using a bit-commitment scheme satisfying standard cryptographic properties. A discreet proof is a non-interactive cryptographic proof of an arbitrary predicate F on X. For example, X could be a commitment to a bidding price in a sealed-bid auction. A predicate of interest in this scenario might include F(X) = X>100, meaning that the offer is more than 100. A discreet proof reveals no information about X other than what is inferable from the value (true or false) of F(X). The predicate F is defined by a verification circuit C containing AND, NOT, and XOR gates only. The length of these discreet proofs is linear in the number of AND gates in C and is unaffected by the number of NOT or XOR gates. This discovery led to a study of the multiplicative complexity of Boolean functions, i.e., the minimum number of binary AND gates required to construct a circuit representing the function, when only exclusive-or, conjunction and negation gates may be used.

This study of multiplicative complexity is being extended to general techniques for reducing the gate complexity of cryptographic functions, including AES.

Much of this work is joint with René Peralta, from the National Institute for Standards and Technology (NIST) in USA.

Joan Boyar

To give you the best possible experience, this site uses cookies Read more about cookies

Accept cookies