Monoids and cryptography

Anthony Widjaja To pointed to an monograph by Straubing on his weblog. I thought I'd briefly mention another Straubing article I liked, which touches on a cryptographic problem. Well, kind of.



The article is

When Can One Finite Monoid Simulate Another?
http://www.cs.bc.edu/~straubin/papers/lincoln.ps

A "monoid" is an object like a mathematical group, except we do not require the existence of inverses. That is, we have a set S and an operation * such that for any pair of elements a,b in S, the element a*b is also in S. We also require the existence of an identity element e such that for all c in S, e*c = c (if we don't require an identity, we call the object a semigroup). The main question of the article is the following: what if you are given the ability to compute operations in one monoid M_1 = (S_1,*_1), but you actually want to compute operations in a different monoid M_2 = (S_2,*_2) ? In what cases is there a clever way to use the computational ability you have in M_1 to "simulate" computation in the monoid M_2 ? As it turns out, this question has several different answers, depending on just what you might mean by "simulate." The article goes through these possible answers and gives an overview of what is known. Along the way it develops connections between "math" questions about semigroups and "complexity theory" questions about circuit class separations.

This connects to cryptography through homomorphic encryption. As it turns out, several known cryptosystems have special homomorphic properties. For example, RSA is multiplicatively homomorphic. Recall that the encryption of a message M in RSA is E(M) := M^e mod n, where e is the public exponent and n is the public modulus. By the laws of exponents, M1^e * M2^e = (M1*M2)^e, so we have E(M1) * E(M2) = E(M1 * M2). Several other examples exist, as well as many examples of protocols that take advantage of such properties. See this manuscript for just a partial list of protocols that benefit from homomorphic properties of a cryptosystem:

Additive Conditional Disclosure of Secrets And Applications
S. Laur and H. Lipmaa
http://eprint.iacr.org/2005/378.pdf

One of the major open questions in cryptography is the existence of an "algebraically homomorphic" cryptosystem. This means a cryptosystem that is
homomorphic with respect to a ring or field. For example, while we can obtain multiplications of encryptions in RSA, we don't know how to add encryptions in the same way. If had a cryptosystem that could do both, then we could do some amazing things. We don't know much about what such a beast would look like, or even if it is possible. The main result in this area of which I am aware is the following

Algorithms for Black Box Fields and Their Application to Cryptography
D. Boneh and R. Lipton
http://crypto.stanford.edu/~dabo/abstracts/bbf.html

in which the authors show that any deterministic field-homorphic cryptosystem can be broken in subexponential time. By "broken" I mean that given an encryption E(x), there is an algorithm that can come up with x in subexponential time. From what I can tell, however, their algorithms depend essentially on being able to test whether a given string is an encryption of zero, so it's not clear whether the approach could be extended to a probabilistic/semantically secure homomorphic cryptosystem. While this is a negative result, it still leaves open the possibility that a practical algebraically homomorphic cryptosystem could be found; after all, RSA is breakable in subexponential time, too. As far as I know, though, we don't have one.

What we do have, however, are a number of group-homomorphic cryptosystems (again, RSA is an example). We also have at least two examples of which I am aware that are homomorphic with respect to an algebraic structure that is not a group. First is the Sander, Young, and Yung cryptosystem

Non-Interactive Crypto-Computing for NC^1
T. Sander, A. Young, M. Yung
http://portal.acm.org/citation.cfm?id=796534

and the second is the Boneh, Goh, and Nissim cryptosystem

Evaluating 2-DNF Formulas on Ciphertexts
D. Boneh, E-J. Goh, K. Nissim
http://crypto.stanford.edu/~dabo/abstracts/2dnf.html

OK, so this is the cryptography question. We have some examples of cryptosystems that give us "host" algebraic structures to play with, mostly groups. We have a target algebraic structure in which we would _like_ to do encrypted computations. I mentioned the field-homomorphic cryptosystem as a particularly important target, but I wouldn't be surprised if we can view some of the protocols that currently benefit from homomorphic encryptions as giving rise to algebraic objects of their own. For a fixed host and target, can we simulate the target object given the host object provided by the homomorphic cryptosystem? Here by "simulation" I really mean some kind of black-box reduction that only makes use of the homomorphic properties of the host cryptosystem. This is a generalization of the questions Straubing considers, since his article only talks about monoids. A positive answer extends the kind of cryptographic protocols we can construct.

Can we show no such simulation is possible? One of the other things Straubing's article does is survey the conditions known under which we can show that one monoid cannot be simulated by another. What kind of reductions, if any, do such results rule out? Between which cryptosystems and which other algebraic objects? While it isn't completely clear what such results would mean (in particular, there might be an especially clever reduction that looks at some structure of the cryptosystem not captured by the host algebraic object), we could at least obtain some evidence that such-and-such target object cannot be constructed from any known homomorphic cryptosystem.