Re: commuting?/non-group cipher?

From: bmm (bmm6o_at_hotmail.com)
Date: 10/29/04 

Date: Thu, 28 Oct 2004 22:36:44 -0700

"Peter Fairbrother" <zenadsl6186@zen.co.uk> wrote in message
news:BDA7514D.70457%zenadsl6186@zen.co.uk...
> For future reference, can I rewrite the property as:
>
> Given a set S and a binary operation *;
>
> the property that for all a, b in S there exists a c in S such that, for
all
> d in S, c*d = a*(b*d)

Here, you're not asking explicitly for associativity or closure, but some
combination of them. This doesn't seem the same to me. Even if they are
the same, this seems more complicated (a,b,c,d instead of a,b,c).

> > Because commuting is already taken. It implies that order doesn't
> > matter (ab=ba).
>
> I thought that was "commutative", rather than "commuting".

Different forms of the word have slightly different usages ("the operation
is commutative", "the elements commute") but all have to do with operations
or elements such that a*b=b*a.

> > I would call it closure - that the set of encryption
> > operations is closed under composition.
>
> Isn't "closure" already taken - to mean: for all a and b in S, a*b is in
S?
>
> The property is different.

I don't see it. But first things first. You originally talked about:
>E(k3)[P] = E(k1)[E(k2)[P]]
Just to be explicit, you mean this for all P, right? If so, I would just
write it as something like E(k3) = E(k1)[E(k2)] to make it clearer that we
are saying the permutations are equal.

The set S are all of the permutations described by E(k), where the operation
is composition. Let a = E(k1) and b = E(k2). Then a*b = E(k1) * E(k2), ie
the permutation defined by P -> E(k1)[E(k2)[P]]. The question is about
whether this is E(k3) for some k3. This is closure.

> A set and binary operation with the property will have closure; but
closure
> doesn't imply the property - for instance many [1] ciphers have closure,
but
> do not have the property.

Can you be more explicit about how this isn't the same as closure?

> [1] (all?) I'll reply seperately to the other part of your post ('cos it's
> very complicated!! for my poor little brain, and also seems to relate to
> John M's post).

Brian

Relevant Pages

  • Re: A function that returns a function that adds x to its argument
    ... denoted below by explicit "magic" -- one might write something like ... is something that those languages usually call a "closure". ... in each "new_adder"-created adder, and when one calls the functions ... Reading email is like searching for food in the garbage, ...
    (comp.lang.c)
  • Re: Looking for a surjection or R^2
    ... guide us towards a completely explicit function ... of p is a diffeomorphism onto either the upper or the lower half-plane; ... closure of the "bottom" 2-cell, that is, the one that contains the ... up to what *may* be your more exacting standards, ...
    (sci.math)
  • Re: Using apply with a closure with unbound variables
    ... Since the body of that closure is outside the LET, it cannot access the local binding. ... You'd need to declare X special in the LET and the closure for them to find each other (most implementations will do this automatically for the closure, because they can see that there's no surrounding binding of the free variable, but you still have to make it explicit for the LET). ...
    (comp.lang.lisp)