Please pardon my rather crude description of this problem, I am not very adept at mathematical notation and language, but I will do my best to describe it in a way as to be understandable.

I have one number, lets call it $K$. I need to be able to modify $K$ based on other numbers, but in a certain way, that can later yield me some information as to how $K$ was modified.

One could imagine a function like $f(K, R) = K_m$. When a new number is obtained by such modification, it might get modified again, iteratively, a number of times. It could look something like this: $f(f(f(k, R_1), R_1), R_1)$. Apologies for the ugly notation, but it should get the point across.

Is it possible to construct the function $f(K, R)$, such that after having applied a number of such modifications to the initial $K$, I will be able to test whether a specific value of $R$ was used at any point in the succession of iterations? I do not need to be able to recover the complete list of $R$ values from the final $K_m$, in fact this must not be the case. Only the ability to pick any conceivable value of $R$ and test whether it was in fact used in any of the iterations is needed.

One simple way that I can imagine doing this that comes close is choosing the $R$ values to be powers of two, and letting $f(K, R)$ perform a binary OR on $K$. I have two objections to this approach. The first being that this would actually yield a final value of $K_m$ that would be directly translatable into a list of all the $R$ values used, which is not desirable. The second being that it isn't very efficient, since we need $n$ bits of information, to discern $n$ different $R$ values. I keep thinking that there must be a smarter and more efficient way to do this, but I can't figure out how to do it!

If it is possible to construct such a function, what defines the limits of such a system? How would the values of the $R$s have to be arranged? Would a particular initial value of $K$ be needed? What defines how many iterations can be made before collisions become inevitable, or highly likely?

I have tried formulating this more concisely thanks to the help of Giovanni Resta

  • You are free to choose $K$
  • You are free to choose a set $R$ of $n$ possible values, say {$R_1, R_2, ..., R_n$}
  • You are free to select a function $f$

  • Someone calculates a series of values $K_1 = f(K, r_1)$, $K_2 = f(K_1, r_2)$ and so on up to $K_m = f(K_m-1, r_m)$, where the $r_i$'s are from the set $R$, but we don't know which ones, or how many iterations were used, $m$

  • Thus, we only know $K$, $K_m$, $R$ and $f$

Now, given the above

  • Taking an arbitrary element from $R$, we want to be able to decide whether it has been used to compute $K_m$

  • It is a goal to make $n$ as large as possible while keeping $K_m$ small (in terms of bits needed to encode $K_m$)

  • One must not be able to trivially recover all the elements from $R$ that was used to compute $K_m$, one should need to test for each element to know whether it was used in the computation.

Is it possible to select $K$, $R$ and $f$ so that this is possible?

  • $\begingroup$ Thanks Lovsovs for the formatting! $\endgroup$ – Mark Qvist Feb 13 '16 at 10:16
  • $\begingroup$ I'm not sure to understand all the details. So please, correct me, or improve question. You are free to choose $K$. You are free to choose a set $R$ of $n$ possible values, say $\{R_1, R_2,..,R_n\}$. You are free to select a function $f$ and then somebody computes a serie of values $K_1 = f(K,r_1)$, $K_2=f(K_1,r_2)$, and so on up to $K_m = f(K_{m-1},r_m)$, where the $r_i$'s are from $R$, but you don't know which ones. And you want to select $K$, the set $R$ and $f$ so that you can decide, knowing $K$, $K_m$, $R$ and $f$ if a specific element of $R$ has been used to compute $K_m$. $\endgroup$ – Giovanni Resta Feb 13 '16 at 11:27
  • $\begingroup$ Thank you Giovanni. With the help of your comment I have updated the question to be more concise. Your interpretation is correct, and I have furthermore specified the goal of making $n$ as large as possible, while keeping the number of bits needed to encode $Km$ small, which was not entirely clear from the original question. $\endgroup$ – Mark Qvist Feb 13 '16 at 16:49

Your Answer

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

Browse other questions tagged or ask your own question.