Welcome Guest [Log In] [Register]
Welcome to Crypto. We hope you enjoy your visit.


You're currently viewing our forum as a guest. This means you are limited to certain areas of the board and there are some features you can't use. If you join our community, you'll be able to access member-only sections, and use many member-only features such as customizing your profile, sending personal messages, and voting in polls. Registration is simple, fast, and completely free.


Join our community!


If you're already a member please log in to your account to access all of our features:

Username:   Password:
Add Reply
Optimal combination of two (pseudo-random) n-bit words
Topic Started: Mar 13 2014, 04:46 PM (219 Views)
mok-kong shen
NSA worthy
[ *  *  *  *  *  * ]
Given two (pseudo-random) n-bit words, how could one best combine them to obtain one n-bit word for crypto usages? I am presenting below an approach conceived by me, in the hope of eventually eliciting from the readers much better ideas of a solution.

Obviously an adequate measure of the goodness of combination is a prerequisite to the stated issue. Hence, if z = f(x,y) mod 2**n is the result of combining x and y, how does one assess the goodness of f() in our context? My currently thinking is: Let a bit of x be flipped to become xr, compute zr = f(xr,y) and c = z^zr. bc = bitcount(c) gives then the avalanche for that bit. Thus a good f() should provide a statistically good (large, near n/2) mean value (over all n bits) of bc as well as a good (small) standard deviation.

I have experimentally tried a number of ways to combine x and y. The best I could achieve to date is a function f(x,y) that can be described as follows:

Define g = 2*x*y + x + y.

Separate the bits of g into 4 equal parts: g0, g1, g2, g3.

Let s = g0 + g1 + g2 + g3 mod 2**(n/4)

and z0 = 2*g0 + s, z1 = 2*g1 + s, z2 = 2*g2 + s, z3 = 2*g3 + s mod 2**(n/4).

Concatenate z0, z1, z2, z3 to become z as the result of combination: z = f(x,y).

For n = 128 I obtained for 10000 pairs of x and y (from Python's built-in PRNG) a mean value of avalanche 56.7535 and a standard deviation of 1.8792. (For comparison, the corresponding values computed for g are 34.2101 and 12.2554 respectively.)

It may be remarked that the g above is such that, given g and x, one can recover y (and similarly for g and y), meaning in a certain sense that no information has been degraded, and that one has e.g. z0 = 3*g0 + (g1 + g2 + g3), meaning that in z0, which replaces g0, the old g0 has in it the same weight as those of (the foreign) g1, g2, and g3 taken together (the two weights are thus in a good balance).

The above f(x,y) has been coded as the (updated) function ncombine(x,y) in my LOTUS Version 1.1 (http: http://s13.zetaboards.com/Crypto/topic/7166985/1/)

For constructive critiques and comments I should be very grateful.



Edited by mok-kong shen, Mar 14 2014, 03:18 PM.
Offline Profile Quote Post Goto Top
 
1 user reading this topic (1 Guest and 0 Anonymous)
« Previous Topic · General · Next Topic »
Add Reply