Problem: I have a small sized domain, say s-bit. It's clear that the probability for an adversary to guess an element is $ \frac{1}{2^s}$. I need to make the probability negligible. However, I need to use a public encoding (or mapping) techniques, so anybody can map its elements from an small sized domain to a big one.

Question: What techniques can I use?

Please note that encoded data is going to be computed, so public key encryption naively may not work, as different participants have different keys. Thus I'm wondering if there is any generic encoding technique that does not require any secret keys.

  • 2
    $\begingroup$ If the technique is public, what stops the adversary from running it herself?Typically the answer to that is a secret key, but you don't want to use secret keys. So, maybe there is no solution? $\endgroup$ – mikeazo Apr 24 '15 at 19:24
  • 1
    $\begingroup$ Anything wrong with simply: each user $j$ secretly chooses a 256-bit random secret key $K_j$, then computes the 256-bit $\operatorname{HMAC-SHA-256}(K_j,x)$ where $x$ is a $s$-bit element of the small domain? $\;$ Perhaps that does not match the "public encoding" requirement, even though the method is public? $\endgroup$ – fgrieu Apr 24 '15 at 19:30
  • 1
    $\begingroup$ @fgrieu the problem is that I need a deterministic function, so the output of the function should be the same for two identical elements drawn from small domain. $\endgroup$ – user13676 Apr 24 '15 at 19:36
  • $\begingroup$ With the requirements as I understand them, and the addition that the encoding/mapping is a deterministic function (in addition to public), there is no solution, for precisely the reason given in mikeazo's comment. $\endgroup$ – fgrieu Apr 24 '15 at 20:06
  • $\begingroup$ @fgrieu Consider I have encrypted an element drawn from small domain as $v=Enc_{pk}(r \cdot e)$, where $Enc$ is Paillier encryption and $r$ is a random value, $r \stackrel{R}\leftarrow \mathbb{F}_p$, and $p$ is a prime number smaller than Paillier moduli $N$. My problem is to reduce the chance of adversary to eliminate $e$ from $v$, when it has access to $v$. You may say use a tag (or MAC) but the value $v$ is going to be randomized and then combined with some other value; therefore, we cannot keep the tag consistent with the these changes. $\endgroup$ – user13676 Apr 25 '15 at 12: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.