Prev: Is encrypting twice much more secure?
Next: Basics of encrypting
From: wizzi fig on 14 Jan 2010 17:15
On Jan 14, 4:38 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> ... then apply certain techniques of yours to 'create' a polynomial
> H(x), or is there a method without having to examine these values?

Of course there is such a method. I described it. H(x) is formed
from P and P's inverse. P is given, and as long as you can compute
the lengths of the cycles of P, you can compute P's inverse, and so
you can compute H.

> Anyway, if you ever succeed in doing that, then you will find that your
> H(x) satisfies the criteria I quoted from [4]. So why don't you simply
> apply that criteria in the first place to choose your polynomials for
> use in your applications?

Frankly I just thought it was relevant mathematically. The technique
I mentioned applies more generally than [4]. It will work when the
modulus is not a power of 2, for example. It will work when P is not
a polynomial (in which case the result won't be a polynomial). If I
recall correctly, some of Anashin's work deals with non-polynomial
permutations as well.

Moreover, you ought to be curious and ask yourself whether you would
really be gaining anything by using a generator with a polynomial of
degree more than 1. What I have really shown above is that using P in
counter mode is equivalent to using some other polynomial, H,
iteratively (i.e. analogous to CBC mode with no plaintext). Given a P
which has low degree can lead to an H with high degree. And clearly
the reverse is also true-- if you create an iterative PRNG using a
polynomial of high degree, how do you know there doesn't exist some
low degree polynomial which your adversary can apply in counter mode
to break your generator (these last comments are related to the idea
of your post in October about trying to keep an adversary from
figuring out your PRNG by observing its output). Or if the idea is
that a high-degree polynomial would give a more random sequence, would
you really consider it more random if the nth value is related to n by
a low-degree polynomial.

I think you would do well to work through the example I posted, so
that you understand it.

Bob H (via a send-only email address)

From: Mok-Kong Shen on 14 Jan 2010 17:58
wizzi fig wrote:
> Mok-Kong Shen wrote:
>> ... then apply certain techniques of yours to 'create' a polynomial
>> H(x), or is there a method without having to examine these values?
>
> Of course there is such a method. I described it. H(x) is formed
> from P and P's inverse. P is given, and as long as you can compute
> the lengths of the cycles of P, you can compute P's inverse, and so
> you can compute H.
>
>> Anyway, if you ever succeed in doing that, then you will find that your
>> H(x) satisfies the criteria I quoted from [4]. So why don't you simply
>> apply that criteria in the first place to choose your polynomials for
>> use in your applications?
>
> Frankly I just thought it was relevant mathematically. The technique
> I mentioned applies more generally than [4]. It will work when the
> modulus is not a power of 2, for example. It will work when P is not
> a polynomial (in which case the result won't be a polynomial). If I
> recall correctly, some of Anashin's work deals with non-polynomial
> permutations as well.
>
> Moreover, you ought to be curious and ask yourself whether you would
> really be gaining anything by using a generator with a polynomial of
> degree more than 1. What I have really shown above is that using P in
> counter mode is equivalent to using some other polynomial, H,
> iteratively (i.e. analogous to CBC mode with no plaintext). Given a P
> which has low degree can lead to an H with high degree. And clearly
> the reverse is also true-- if you create an iterative PRNG using a
> polynomial of high degree, how do you know there doesn't exist some
> low degree polynomial which your adversary can apply in counter mode
> to break your generator (these last comments are related to the idea
> of your post in October about trying to keep an adversary from
> figuring out your PRNG by observing its output). Or if the idea is
> that a high-degree polynomial would give a more random sequence, would
> you really consider it more random if the nth value is related to n by
> a low-degree polynomial.
>
> I think you would do well to work through the example I posted, so
> that you understand it.

I am not aware of Anashin's work on non-polynomial permuations. If you
have references, I should be very grateful to know them.

If you can derive from an (entirely) "arbitrary" P(x) a H(x) that
generates cycle free permutation, then you can certainly also generate
a H(x) without P(x). Am I right? That means, you can give a criteria
that a general H(x) has to satisfy for producing cycle free
permutations for modulus not a power of 2. If yes, could you formally
state that criteria, for that would be very valuable in my view?

I have no knowledge on the randomness comparsion between linear and
higher degree polynomials. It seems to be intuitively clear that even
for a fixed degree, different values of coefficients could produce
sequences of widely different nature. On the other hand, a higher order
polynimial allows one to specify more numerical values as coefficients.
So, if these are considered as a key, it means one can specify a longer
key. However, if P(x) is used to xor plaintext, then with known
plaintext the coefficients of the polynomial can certainly be
determined just as easily as in the linear case. Sophisticated analysis
needs only some lower order bits from the keystream, if I don't err. It
could be that in combination with other suitable techniques the use of
an higher order polynomial could be advantageous, but that's a mere
speculation of mine and I don't have any solid knowledge on that. If
you happen to have founded informations in that respect , I should like
very much to know.

M. K. Shen
From: me13013 on 14 Jan 2010 18:20
On Jan 14, 5:58 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> I am not aware of Anashin's work on non-polynomial permuations. If you
> have references, I should be very grateful to know them.

I will look for them. I'm pretty sure that whatever I found was the
result of something posted in this newsgroup, but it was probably 5 to
10 years ago.

> If you can derive from an (entirely) "arbitrary" P(x) a H(x) that
> generates cycle free permutation, then you can certainly also generate
> a H(x) without P(x). Am I right?

No, that's not right, beyond the trivial case of just listing H's
input/output table.

> That means, you can give a criteria that a general H(x) has to satisfy
> for producing cycle free permutations for modulus not a power of 2.

I don't think you mean a general H(x). I think you mean a polynomial H
(x). I don't know such criteria, but that was my original motivation
for exploring the compositional method that I posted in this thread.

I still think if you worked through my earlier example you would gain
some insight.

Bob H
From: me13013 on 14 Jan 2010 18:41
On Jan 14, 6:20 pm, me13013 <me13...(a)gmail.com> wrote:
> On Jan 14, 5:58 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> > I am not aware of Anashin's work on non-polynomial permuations. If you
> > have references, I should be very grateful to know them.
>
> I will look for them.  I'm pretty sure that whatever I found was the
> result of something posted in this newsgroup, but it was probably 5 to
> 10 years ago.

The document I have is V. Anashin, "Uniformly distrbuted sequences of
p-adic integers, II". Note the "II". Apparently it is a follow up to
your reference [3]. Originally in Russian, translated to English in
Discrete Math. Appl. vol. 12 (2002), no. 6, pp. 527–590. English
version available at http://arxiv.org/abs/math/0209407 . In my copy
of it, there is a monstrous-looking function at the bottom of page 3,
involving logical AND, OR, XOR, division, and exponentiation with the
exponent being a function of x. The claim is made that using this
function in a certain way produces a complete cycle. Possibly this is
just a red herring and the monster is identical to a function with a
simpler description.

I still think if you worked through my earlier example it would do you
know harm.

Bob H
From: Mok-Kong Shen on 14 Jan 2010 18:46
me13013 wrote:
> Mok-Kong Shen wrote:
>> I am not aware of Anashin's work on non-polynomial permuations. If you
>> have references, I should be very grateful to know them.
>
> I will look for them. I'm pretty sure that whatever I found was the
> result of something posted in this newsgroup, but it was probably 5 to
> 10 years ago.

I mentioned that in Feb. 1998 the reference [3] was known in
discussions. You could find it with groups.google.com. To my knowledge
that's the very first occurrence of references to his work in posts of
our group.

>> If you can derive from an (entirely) "arbitrary" P(x) a H(x) that
>> generates cycle free permutation, then you can certainly also generate
>> a H(x) without P(x). Am I right?
>
> No, that's not right, beyond the trivial case of just listing H's
> input/output table.

Couldn't you somehow "abstract" from the techniques that you apply in
practice to derive H(x) from a given P(x) to arrive at a formal
criteria? Alternatively, an computer implementable algorithm to
automatically generate H(x) from P(x) would also be valuable. BTW,
for modulus not a power of 2, one needs also a method to get a P(x)
to start with, right?

>> That means, you can give a criteria that a general H(x) has to satisfy
>> for producing cycle free permutations for modulus not a power of 2.
>
> I don't think you mean a general H(x). I think you mean a polynomial H
> (x). I don't know such criteria, but that was my original motivation
> for exploring the compositional method that I posted in this thread.

O.k., but even a special more or less large class of H(x) for modulus
not a power of 2 could be interesing.

> I still think if you worked through my earlier example you would gain
> some insight.

I certainly never exclude that attractive possibility, though with my
layman's knowledge, I doubt I would be able to go very far. (I don't
understand anything of the proof of the criteria quoted from [4],
for example.)

M. K. Shen
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: Is encrypting twice much more secure?
Next: Basics of encrypting