# How to best mix two arbitrary/random n-bit words? [closed]

Given two arbitrary/random $n$-bit words, how could one best mix them to get one $n$-bit word for general crypto usages?

I suppose that one should have an adequate measure of goodness of the mix before being able to answer that question. So I would like to first ask: If $z=f(x,y) \bmod 2**n$ is the result of the mixing $x$ and $y$, how does one assess the goodness of $f$ in our context?

I am currently thinking of the following: Let a bit of $x$ be flipped to become $x_1$, compute $z_{1}=f(x_{1},y)$ and then $c=z\oplus z_{1}$. $bc=bitcount(c)$ gives then the avalanche for that bit. Thus a good $f$ should provide a statistically good (high) mean value (over all the $n$ bits) of $bc$ as well as a good standard deviation. Would this be an acceptable measure or are there better measures in practice?

Of course I should also appreciate very much being able to know immediately the answer to my proper question as stated at the very beginning. Thanks very much beforehand.

• Arbitrary or random? The two are not the same... but if you have two uniform random variables, combining them via any bijective operation produces an equally uniform variable (that could range from a simple XOR to running a cascade of five block ciphers on the variable - the result is the same). So I'm not too sure what you mean, could you clarify? Mar 11 '14 at 19:50
• I am most interested in the case of pseudo-random, i.e. x and y are from some good crypto processing. Mar 11 '14 at 21:31

Given two arbitrary/random $n$-bit words, how could one best mix them to get one $n$-bit word for general crypto usages?

There's no such thing as "general crypto usage". Whenever we combine two different values in crypto, we have specific properties in mind, depending on why we are combining them, and in what context. For example, if we combine them as a part of a larger cipher operation, then we need to examine what properties the larger cipher will assume on the combination function. The "correct" combiner will have those properties. Since we have different properties in mind in various places, then different combiners will be "best" at various times.

I am currently thinking of the following: Let a bit of $x$ be flipped to become $x_1$, compute $z_{1}=f(x_{1},y)$ and then $c=z\oplus{z_{1}}$. $bc=bitcount(c)$ gives then the avalanche for that bit. Thus a good $f$ should provide a statistically good (high) mean value (over all the $n$ bits) of $bc$ as well as a good standard deviation. Would this be an acceptable measure or are there better measures in practice?

Depending on the properties we need, that might be the Right Thing, or it might be hideously inappropriate.

• ok. Let's say one has in some crypto processing obtained x and y and then need to combine them into z for going further, how should one do that optimally? Mar 11 '14 at 21:35
• @Mok-KongShen: define "optimally". Mar 11 '14 at 21:42
• Let's consider the following case: Suppose one encrypts 2 natural language texts (there are estimates of some 1 bit pro character, if I don't err) with a certain block cipher to obtain 2 sequences of blocks. Now one desires to combine these sequences into one sequence with the goal that the resulting sequnce is hopefully better in the sense of entropy. (If I don't err, measuring entropy is difficult, but it seems nonetheless not incorrect to expect/demand that the resulting sequence should have higher entropy.) Mar 11 '14 at 22:39
• @Mok-KongShen: well, natural language texts are quite compressible, it should be quite possible to compress both texts into half their size. Once you've done that, concatinate the two compressed halves together; this result has all the entropy of the original texts, and hence is an optimal solution (to the very specific problem you stated). Mar 12 '14 at 18:51
• I am merely using an example to answer your question of defining "optimally". That is, the notion of "better" exists in the present context. My problem as such is evidently indepent of what one could best do with that specific potential application. Mar 12 '14 at 19:02

If you are designing a cryptographic protocol and need to combine contributions from two different sources, the standard way is to use a cryptographic hash function to combine the two values. Basically, use $H(x,y)$, where here you use a standard way of forming a tuple of two values (if $x$ or $y$ are known to have a fixed length that's always the same, you can just concatenate them to get $x||y$, otherwise you use something like $\textrm{len}(x)||x||y$).

In the random oracle model, this has excellent properties. For instance, if $x$ and $y$ are chosen independently and one of them has large entropy, then $H(x,y)$ will have large entropy. If $x$ and $y$ are chosen independently and one of them is uniform over a $n$-bit space, where $n$ is sufficiently large, then $H(x,y)$ will be pseudorandom (indistinguishable from random). And so on.

The main requirement is that $x,y$ be chosen independently; if the choice of $y$ is allowed to depend upon the choice of $x$, you have problems -- in fact, you will have problems in any scheme. One way to ensure independent is to require both parties to commit to their values. For instance, Alice sends Bob a commitment to $x$; Bob sends Alice a commitment to $y$; then when Alice has received a commitment from Bob, she opens her commitment to reveal $x$ to Bob, and symmetrically for Bob. This ensures independence of the values $x,y$.

Some protocols use the combiner $x \oplus y$. This also has some good properties, but is more fragile. In particular, if $x,y$ are not independent, the failure mode is a lot worse than with $H(x,y)$. For instance, if Bob can choose $y=x$, then the combiner $x\oplus y$ gives zero, whereas the combiner $H(x,y)$ might still give a decently random value if Alice chose her value $x$ randomly. Therefore, in most real-world settings, $H(x,y)$ is better than $x \oplus y$, because it is more robust.

Of course some purists may complain about use of the random oracle model, but in practice, the random oracle model is quite reasonable. Failures due to the random oracle model are probably a lot less likely than failures due to other real-world issues that tend to be ignored by purists. So for most settings, $H(x,y)$ is likely to be fine.

• What I would prefer to have is not to use, if possible, a rather complex computation like a crypto-secure hash function but some more simple computations in practice, of the genre of xor you mentioned. For it is not extremely high crypto security that is demanded in the cases I have in mind but, roughly speaking, certain comparatively good security that could be obtained with some not too expensive computing expenses. Mar 14 '14 at 15:58
• @Mok-KongShen, it would have been better if you had listed those requirements in the question. This is related to why poncho told you your question was too broad/ill-defined. Generally speaking, we tend not to like chameleon questions where someone asks a broad question without listing the requirements, then when they get an answer that answers the question-as-stated, they respond by saying "oh, that wasn't really what I was looking for, I actually had this extra requirement/goal/criterion I didn't tell you about". You can avoid that by asking narrower questions that include all the criteria.
– D.W.
Mar 14 '14 at 21:00
• The specific application that interests me currently would certainly be deemed too mundane from a theoretical point of view. In a certain encryption processing I am considering there are two n-bit words, x and y, one on the plaintext side and one on the ciphertext side (but neither is directly plaintext or ciphertext). I like to combine them into z and sum the z's of all preceding blocks into a value s and use that to chain the blocks. It's my thinking that, if z is "somehow" optimal in capturing the randomness of x any y, then the chaining would also be fine. Would that satisfy your query? Mar 14 '14 at 21:40