Re: commuting?/non-group cipher?

From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: 10/29/04 

Date: Fri, 29 Oct 2004 18:15:08 +0100

Kristian Gjøsteen wrote:

> Peter Fairbrother <zenadsl6186@zen.co.uk> wrote:
>> I am slightly less confused now; but I still have to prove that a cipher
>> with the property is a group (not a permutation group), in terms of the set
>> S of texts and keys and the encryption operation * (or not, if it isn't).
>> Anyone got a clue for me?
>
> I don't exactly understand what you are asking for,

I don't know the right word, "semigroup" and "groupoid" are wrong, so I'll
use "sabo" for a set-and-binary-operation, with no implications of closure
or associativity, where the binary operation can be, and can only be,
applied to any two members of the set, producing an output.

We are investigating a generalised "cipher" sabo which also possesses a
particular property, and want to know whether it must be a group.

The "cipher" part means that the sabo must function as a cipher. We will
also want to investigate ciphers which are not sabos, eg where the
encryprtion and decryption operations differ, to see if a cipher with the
particular property which is not a sabo can exist.

The particular property is as in either of the definitions I have given
earlier, for this purpose they are identical.

The elements of the set, S of the sabo consists of all the possible
messages, ciphertexts and keys. The binary operation * takes any two members
of the set and produces an output, and is the encryption/decryption
operation.

We want to know whether _that sabo_ must be a group. We are not interested
in whether there is an associated permutation group unless it tells us
something about the sabo.

On first glance I thought "obviously it doesn't have to be a group"; but now
I'm not so sure.
 

> so I'll talk about
> something that may or may not be related. I hope it helps.

I hope so too, once I've worked out what you're saying! :) I'm a bit slow
just now. But thank you, and it has been helpful so far, so fingers crossed.

> Let's ignore randomized encryption, and only consider insecure things,
> so the cipher is a function f taking a key k (from a set K) and a message
> m to a ciphertext c.
>
> Second, let's assume that the set of messages (say S1) and the set of
> ciphertexts (say S2) are independent of the key k. So we really have a
> function f:K x S1 -> S2.
>
> For a fixed key k, we get a function f(k, ):S1 -> S2. It is a function
> taking messages to ciphertexts. So we can consider our cipher as a set
> of functions X = { f(k, ):S1 -> S2 }.
>
> In your notation that E(k)[P] = f(k, P), where P is in S1.
>
> It is now clear that a decryption function exists only if the cardinality
> of S2 is larger than or equal to the cardinality of S1.
>
> We may also, without loss of generality assume that f( , ) is onto S2
> (if it is not, replace S2 by the image of f( , ) in S2).
>
> Now, unless S2 is a subset of S1, we cannot compose encryption functions:
> f(k1, f(k2, )) doesn't make sense.
>
> If S1 and K are finite, every f(k, ) must be a set isomorphism of S1
> and S2, and we may as well assume S1=S2 and consider X to be a subset
> of the permutation group, and my previous post applies, and X is a
> group and is a subgroup of the group of permutations on S1.

Okay so far. You are talking about permutation groups, which aren't that
relevant, but it's still interesting
 
> If S1 isn't finite, and S2 is a subset of S1, then we may have a
> composition operation on X, and the property that f(k1, f(k2, )) = f(k3,)
> for some k3 in K could be described as "X is closed under composition".
> In this case, the cipher set X need not be a group.

I'm getting a little lost, so I'll throw out some comments in case anyone
can see from them where I have gotten lost, They won't be very relevant,
unfortunately.

For a cipher, S1 must be finite surely? You can't have an infinitely long
message, at least not in practice.

I'm not quite sure of the meaning of "composition" here. I've looked on the
'net, and in a few books, but no joy. Is "closed under composition"
different from "closure"? Does one imply the other, or are the operations
not linked?

> Now, let's switch to alternative interpretations, where S2 need not be
> a subset of S1:

Can't compose encryptions (I assume you mean do a "double encryption"); so
the property can't exist?

> Note that there is a map from the set of keys K to the cipher set
> X given by k |-> f(k, ). We may assume that this map is a bijection
> (the map is onto by definition; it induces an equivalence relation on
> K, so by replacing K with the set of equivalence classes, we have a
> bijection). This means that if we have some kind of binary operation on
> K that is closed, that operation will induce an operation on the cipher
> set X that is also closed.

got the gist of that

> Denoting the operation on K by #, we get an induced operation # on X
> given by f(k1, ) # f(k2, ) = f(k1#k2, ).

Nope. lost me there.

> If we decide to get confusing,

!!!

> we could render this as f(k1, f(k2,P)),
> or in your notation, E(k1)[E(k2)[P]] = E(k3)[P], where k3 = k1#k2.

Still completely lost ...

> This is of course an abuse of notation.

I want everyone to know, the horrible E()[ ] notation is not mine, I was
quoting!

> This works both ways, so if we have some structure on X, that induces
> a structure on K. This may or may not be a group structure.

I get the principle, I think, just not the specifics. I'll have another go
later, and thank you again anyway, I appreciate it. 

-- 
Peter Fairbrother

Relevant Pages