# Applications of Group Ciphers

I've been reading a paper [1], and I've ran across something called a "Group Cipher", which is similar to homomorphic encryption, with an important difference.

In homomorphic encryption we have an encryption operation $E_k: P \rightarrow C$, where $P$ is the set of plain texts and $C$ is the set of cipher texts. We also have an efficient group operation on $C$ that induces a homomorphism to the group operation on $P$.

The difference with Group Ciphers is that the group operation on $C$ is composition of encryption $E$, and it induces a homomorphism on the group operation of the set of keys $K$. That means, if we denote an encryption of a plain text $X$ as ${X}_i$, then we would have that ${ { X }_i }_j = { X }_{i \circ j}$.

In the paper they use it to do something like asymmetric encryption, but using symmetric encryption. They do need a semi-trusted third party.

For example, Alice's key is $i$, Bob's key is $j$. Ted has the key $i^{-1} \circ j$.

Alice will encryption something : ${X}_i$. Send it to Ted, who will then encrypt it again : ${ {X}_i }_{i^{-1} \circ j}$ , which will yield ${X}_j$, then Ted send it to Alice again. After that Alice sends it to Bob. Bob can then decrypt it.

What happened here is that Alice can send to Bob, without knowing bob's (symmetric) key. And Bob can decrypt without knowing Alice's (symmetric) key. Just like asymmetric encryption. But using symmetric encryption instead (and a semi-trusted third party).

They also prove that the Pohlig-Hellman cipher has this property.

The question is:

1- Does Group Ciphers have any other applications in the literature (with references) ?

2- What are the drawbacks of this scheme compared to asymmetric encryption (other than the required semi-trusted third party) ?

(I was not sure of which tag to use for this question.)

1 S. M. Bellovin and W. R. Cheskwick (2004). "Privacy-Enhanced Searches Using Encrypted Bloom Filters". Draft.

-
It is also commonly called as "Commutative encryption schemes". –  M. Alaggan Sep 5 '11 at 18:41

What they are calling a "group cipher" is much more commonly referred to as proxy re-encryption. Proxy re-encryption is typically asymmetric but I don't think there is anything prohibiting it being symmetric. It has many applications (see this list) but most of these applications are using the asymmetric variants. I myself cannot point to another application of symmetric proxy re-encryption.

One drawback is that it is almost as expensive as an asymmetric scheme, so there is little reason to prefer it with today's computational abilities.

Another is that it requires a small multi-party computation between the three parties so that the third party learns the ratio key without Alice or Bob learning it, or the third party learning anything other than it. This MPC requires secure channels, which for all scenarios where at least one pair of parties haven't exchanged keys in-person, this means using asymmetric cryptography to setup the channels.

-

One thing I would like to add: a "Group Cipher" comes fairly close to the properties you need from a public key cipher. In particular, if the group is abelian (or has an abelian subgroup for which the group cipher is still secure), then you can use it to do public key encryption directly.

Because of this, it seems unlikely that a "Group Cipher" will be computationally cheaper than real public key encryption.

Details on how one can convert a Abelian Group Cipher into a Public Key Encryption Cipher:

The global parameters are:

• $X$ – Well known plaintext for the cipher

The private key is:

• $i$ – A random key

The public key is:

• $X_i$ – The key applied to the well known plaintext

To encrypt a message, you pick a random key $j$, and send: $$X_j, E( \text{Message}, \text{Hash}( (X_i)\vphantom{X}_j ))$$ where $\text{Hash}$ is a random oracle translating the ciphertext into a symmetric key and $E$ is your favorite symmetric cipher.

To decrypt this message, the receiver with the private key computes: $$\text{Hash}( (X_j)\vphantom{X}_i ) = \text{Hash}( (X_i)\vphantom{X}_j )$$ and uses that to decrypt the message.

This works because of the group cipher properties (and that the group is Abelian):

$$(X_i)\vphantom{X}_j = X_{i \circ j} = X_{j \circ i} = (X_j)\vphantom{X}_i$$

The group for the Pohlig–Hellman cipher is Abelian; the result of this transform gives you a variant of ElGamal.

-

Group encryption has been used for Mental Poker protocols, as a commutative encryption primitive. See SRA protocol.

I've extensively used symmetric commutative group encryption in my graduate thesis under the name CGC (Commutative Group Cipher), because the term "Group encryption" is generally associated with Group Signatures, which is a completely different thing.

-

Obviously, you may use a group cipher as a replacement of traditional ciphers to avoid side-channel leakage, using the homomorphic property to randomise the key (with two calls to the encryption function instead of just one). One can easily extend this to k-th order leakage by secret-sharing the key.

-
This is a very interesting application, thank you! –  M. Alaggan Aug 14 '11 at 23:55