im not familiar with the terminology of computer-science which makes it pretty difficult to search for the problem I have.

I'm looking for a function that generates a sequence of bits (B) of a given length (i.e. 1024 bit) from a chosen bit-sequence (A) (i.e. 32 bit).

This function needs to have the following properties:

  1. The relation A->B has to be unique
  2. A slight change of A (i.e. 1 bit) results in a slight change of B (~1024bit/32bit = ~32)

While searching I came across hash-algorithms but they achive kind of the oppisite I want to do. They shorten a sequence and a small change of the first one results in a big change of the other one.

Do you know of such a function or do I have to come up with something myself?

Example (with fewer bits):

Let bit-sequence A be given as 0b0101 (integer-representation: 5). Let function F map A to B so that B = 0b1001 0010 0101 0111 (example). Here, B can be split into 4 4-bit integers (9, 2, 5, 7).

Changing 1 bit of A from 0b0101 (5) to 0b0100 (4) results in 4 changed bits of B so that the resulting bits are 0b1011 0000 0101 0110 (integer: 11, 0, 5, 6).

The 4 integers contained in B will be used in further computations and I'm looking for function F.

  • 1
    $\begingroup$ How about repeating A 32 times? $\endgroup$ – Yuval Filmus Feb 24 '18 at 13:25
  • $\begingroup$ This is probably the easiest solution to my constrains. Sadly it doesnt completely fit my problem. Is there a function with a more "randomized" outcome? $\endgroup$ – Freakwave Feb 24 '18 at 14:09
  • $\begingroup$ Can you explain why it doesn't fit your problem? Otherwise it is hard to guess what will fit your problem. $\endgroup$ – Yuval Filmus Feb 24 '18 at 14:52
  • 1
    $\begingroup$ If that doesn't meet your needs, there must be some requirement you have that it violates. Please use this opportunity to identify what that requirement is, then edit the question to include that requirement in the question. We want questions to stand on their own, so people don't need to read the comments to understand what you are asking, and we need to know all of the requirements from the start, so this doesn't devolve into a guessing game. $\endgroup$ – D.W. Feb 24 '18 at 16:29
  • 1
    $\begingroup$ I'm afraid the example you added to the question doesn't help address my comment at all. It doesn't provide me any greater clarity what your requirements are -- i still have the same feedback. $\endgroup$ – D.W. Feb 25 '18 at 16:36

Let $\pi$ be a random permutation on $\{1,\ldots,1024\}$, and let $K$ be a random bit string of length 1024 bits. The following mapping seems to satisfy your needs (with probability close to 1): $$ A \mapsto \pi(A^{32} \oplus K). $$ In particular, changing $b$ bits of $A$ will result in changing $32b$ bits of the result.

If you are OK with changing more than 32 bits, then you can take a random sparse affine function, that is the function whose $i$th bit is an XOR of a small number of bits of $A$ chosen at random, XORed with a random bit.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.