1
$\begingroup$

Let we have a finite (small compared to 2256) set $T$ of 257-bit numbers.

Need a function $f: T \to 2^{256}$ such that it's almost of zero probability that $f(n)=f(m)$ for two different numbers $n,m\in T$.

Computation of $f^{-1}$ must be constant (at worst logarithmic) on the size of $T$.

Computation of $f$ must also be easy (not exponential, ideally constant time).

The function $f$ should "extend" easily when we add one new element to $T$.

How? Is this possible at all?

I need this to map two (in the future three) different kinds of crytocurrency token IDs into a set of tokens IDs.

Update: I realized I need to be able to do this even if 257 is replaced by 512 in the question. Well to be able to pack not 512 but just 256+160 = 316 numbers would be enough. It can be done by storing every new element of 𝑇 (it's initially empty) into the storage mapping its consecutive number $f(T)$ to the element of 𝑇, but I'd prefer to do it without any persistent storage (that is not storing anything between invocations of $f$ and when adding a new element to $T$).

$\endgroup$
4
  • $\begingroup$ I realized I need to be able to do this even if 257 is replaced by 512 in the question. Well to be able to pack not 512 but just 256+160 = 316 numbers would be enough. It can be done by storing every new element of $T$ (it's initially empty) into the storage mapping its consecutive number to the element of $T$, but I'd prefer to do it without any persistent storage! $\endgroup$
    – porton
    Dec 25 '20 at 12:16
  • $\begingroup$ Any function from $\{0,1\}^{512}\to\{0,1\}^{256}$ that's easy to compute in both directions for all inputs $t$ in arbitrary subset $T$ of $\{0,1\}^{512}$ will need about $256\,|T|$ bits of storage. $\endgroup$
    – fgrieu
    Dec 25 '20 at 12:20
  • $\begingroup$ @fgrieu Can I see a proof? $\endgroup$
    – porton
    Dec 25 '20 at 12:21
  • $\begingroup$ Entropy argument: we can store set $T$ as the definition of function $f$ and the set $f(T)$. That gives a minimum size for the definition of $f$. We can approach that minimum with an explicit construction. $\endgroup$
    – fgrieu
    Dec 25 '20 at 13:35

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.