1
$\begingroup$

Does there exist a cryptographically secure hash function (or keyed PRF) that can take, as a parameter, the number of 'hot bits' in the output? And if so, what is the name? The goal here is to produce a cryptographically-secure pseudorandom bitmask with a fixed number of bits in the mask.

E.g. $\text{some_magic_hash}(x; 12)$ should produce a bitstring with exactly 12 positive bits.

$\endgroup$
3
  • $\begingroup$ Use any prf to generate a random tape. Use the random tape to sample $i$ distinct indices. Set those bits to $1$. $\endgroup$
    – Maeher
    Nov 28 '20 at 18:34
  • $\begingroup$ This sounds sensible, but since there are chances of colliding with an already-hot bit, would require a slightly different construction, looping until all the bits are set to 1. Intuitively this sounds secure. Has this construction already been proposed in literature, and if so, is there a name assigned to it? $\endgroup$
    – lynn
    Nov 28 '20 at 19:07
  • 2
    $\begingroup$ I don't think it's something anyone has ever needed. The security proof should be straightforward. It's a pretty generic construction for a PRF with any efficiently samplable codomain. Just run the sampler using a random tape generated from a regular prf (stretched with a prg if necessary). $\endgroup$
    – Maeher
    Nov 28 '20 at 19:21
2
$\begingroup$

I will answer the question for PRFs, I don't know whether it's possible to securely hash into the respective set.

So, what is it we are actually trying to achieve here? We want to create a family of pseudorandom functions with the co-domain of all bit-strings of a certain length $\ell$ of Hamming weight $w$. I.e., the set $$Y_{\ell,w}=\bigl\{y\in \{0,1\} \mid \mathsf{hw}(x) = w\bigr\}.$$

I will actually answer a more general question.

Theorem. Let $Y$ be a set and let $\mathcal{S}$ be an efficient (i.e. PPT) algorithm that samples uniformly from $Y$. We denote by $y := \mathcal{S}(r)$ the output of $\mathcal{S}$ when sampling with random coins $r$. There exists a family of pseudorandom functions with co-domain $Y$, if a regular family of pseudorandom functions (i.e. with co-domain $\{0,1\}^n$ exists.

Proof. Let $p$ be a polynomial that bounds the runtime of $\mathcal{S}$. Let $F : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^{p(n)}$ be a family of PRFs.¹ We construct a family of PRFs $G \{0,1\}^n \times \{0,1\}^n \to Y$ as $G(x) := \mathcal{S}(F(x))$.

We can show that $G$ is a PRF using a trivial reduction to the security of $F$. Let $A$ be an arbitrary PPT distinguisher for $G$. We construct a distinguisher $B$ for $F$ as follows. Upon input the security parameter $1^n$ and given access to an oracle, $B$ invokes $A(1^n)$. Whenever $A$ queries its oracle with input $x$, $B$ forwards $x$ to its own oracle, receiving $y$ as a response and returns $\mathcal{S}(y)$ to $A$. Eventually $A$ will outputs bit $b$, which $B$ will also output.

If $B$ has access to an oracle implementing a truly random function $f$, then its responses to $A$ are by definition of $\mathcal{S}$ uniformly distributed and thus, $B$ is perfectly simulating a random function $g : \{0,1\}^n \to Y$ in this case. If, on the other hand, $B$ has access to an oracle implementing $F(k,\cdot)$, then it's perfectly simulating $G(k,\cdot)$.

Thus, $B$ distinguishes $F$ from a random function with the same advantage as $A$ distinguishes $G$ from a random function. Since $F$ is a PRF, the advantage of $A$ must thus be negligible and $G$ is therefore also a PRF. $\tag*{$\square$}$

What remains to show, is that $Y_{\ell,w}$ can be uniformly sampled in strict polynomial time. Sadly, this is not the case.² The straightforward way of sampling uniformly from $Y_{\ell,w}$, is to sample $w$ unique indices $i_1,\dots,i_w \in \{0,\dots,\ell-1\}$ and returning the bitstring representing $$\sum_{j=1}^w 2^{i_j}$$ in big-endian.

The issue with this strategy is that it involves successively sampling uniform integers between $0$ and $\ell-j$ for $j = 1,\dots,w+1$. That's however not possible in strict polynomial time using binary random coins, unless $\ell-j$ is a power of $2$. We can however do two things:

  1. We can sample uniformly in expected polynomial time using rejection sampling. However, this means our reduction above now no longer runs in strict polynomial time, so we would need to deal with that, which gets ugly very quickly.
  2. We can sample arbitrarily close to uniform in strict polynomial time. This works by sampling an integer $I$ between $0$ and $2^a \gg \ell$ and setting $i=I \bmod \ell$. In this case, even in the uniform case, $\mathsf{S}$ does not sample uniformly. However, it samples statistically arbitrarily close to uniform, which allows the above proof to still go through.

¹ Note that PRFs with co-domain $\{0,1\}^n$ and $\{0,1\}^{p(n)}$ are existentially equivalent for any polynomial $p$. ² I have no proof for this right now, but I would be very surpised if there exists some strategy to do this.

$\endgroup$
1
  • $\begingroup$ I need to review this further when I have the time, but I appreciate this! It seems like this answers my question! It's been awhile since I've gotten too deep into cryptography. One of the difficult issues with analyzing this has been the unbounded recursion (/while loop) used to construct it, which I think equivalent to that non-strict-polynomial time you mention... I'll update this page if I find anything new! :) (Btw, sorry for the late response to this!) $\endgroup$
    – lynn
    Dec 4 '20 at 0:34

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.