I have two frames f1 and f2 that are each composed of several elements noted e. Note that, an element can fall into one of those two categories: an identifier or a counter.

What I want is to find a property that verifies indistinguishability of elements between frames. For instance, given the element e as an identifier, if f1.e==f2.e the property is not verified while it is verified if f1.e!=f2.e.

For now, I only suppose that such a property includes probabilities and can be obtained via:

  1. semantically secure block cipher for identifier elements;
  2. PRNG for counter elements.
  • $\begingroup$ What's a 'frame'? Sounds specific. I.e. is this a maths or computer science question? $\endgroup$ – Paul Uszak Jul 26 at 11:34
  • $\begingroup$ @PaulUszak : A frame is a sequence of bytes. For instance, the hexadecimal representation of a frame can be 0x1242338455667798f1eeaa.... The question can be seen as a math question applied to computer science :). $\endgroup$ – Guillaume Jul 29 at 9:26

You could use Format Preserving Encryption for either one of the elements. FPE will create a keyed permuation for a specific domain (presuming that this domain can be practically converted to a number representation). That way your identifier can just be a sequential number.

You could see a block cipher as an FPE for a specific domain with $2^n$ elements, where $n$ is the block size in bits. If you can define your domain to have that many elements (even unused ones) then yes, you could use a block cipher. This could be an issue if you cannot handle a relatively large output size (you cannot store $2^{32}$ bits or more, for instance).

You can also create a random nonce, but due to the birthday problem, you will have to generate a pretty large value to avoid collisions in the element itself (and, of course, the encrypted element as well).

  • $\begingroup$ I'm sorry but I don't see how can I translate elements of your answer into a formal/mathematical definition including probabilities ? $\endgroup$ – Guillaume Jul 26 at 8:55
  • $\begingroup$ Probabilities of what exactly? $\endgroup$ – Maarten Bodewes Jul 26 at 8:59
  • $\begingroup$ For instance, the probability of the field e of f2 not to be the same as e of f1. The point is that I don't know how to formalize it with mathematical formulas... $\endgroup$ – Guillaume Jul 26 at 10:21
  • $\begingroup$ If the input is unique then the output is also unique for format preserving encryption. So $e \neq e' \to E(e) \neq E(e')$. The probability is zero as it is a permutation. You can only get collisions when using the same input or when using a different key. $\endgroup$ – Maarten Bodewes Jul 26 at 12:14

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.