Score:1

Hash functions with constant number of 1's

cn flag

In the following paper: https://eprint.iacr.org/2018/056.pdf, the random oracle is defined as follows: $ H: *\xrightarrow{} \{ \mathbf{v} | \mathbf{v} \in R_{q,[1]}, || \mathbf{v}||_{1}=\omega\}$

Where $R_{q,[1]}$ stands for those elements that belong to the ring $R_{q}=Z_{q}/<x^n+1>$ and have coefficients between [-1,1].

Are these random oracles secure? If so, which hash function could output a constant number of 1's without comprimissing the security?

kelalaka avatar
in flag
I don't think that $||v||_1$ is cointing $1$s. It is rather $p-norm$ where $p$ is one.
Score:1
ru flag

If they behave like random oracles, then they offer security commensurate with the size of the image space which is $2^\omega\binom n\omega$ (note that there are $\omega$ non-zero entries which can each be plus or minus one). Thus if the security is compromised by finding a collision in $H$ this should require $O(2^{\omega/2}\sqrt{\binom n\omega})$ evaluations of $H$ to find. For any given security level, it is possible to find appropriate values of $n$ and $\omega$ for which the required work is greater than the security level.

The easiest way to practically construct such an $H$ is to adapt a regular $h$-bit hash function that is believed to behave like a random oracle. Use this to generate a uniform value between 0 and $V:=2^\omega\binom n\omega$ (e.g. by treating the hash output as a $h$-bit integer; if this value is less than $2^h\mod V$, append a 1 to the input and iterate, else reduce the value modulo $V$). Now split the value $v$ into two values $c:=v/2^\omega$ and $b:=v\mod {2^\omega}$ (note that $b$ and $c$ will be independent and uniformly distributed modulo $2^\omega$ and $\binom n\omega$ respectively). Now use $c$ and the method of this answer to choose a set of $\omega$ coefficients that will be non-zero and use the bits of $b$ to select between the coefficients plus and minus 1.

poncho avatar
my flag
Actually, an easier (if not as efficient) way to implement such an Oracle is to take the sequence $0, 1, 2, ..., n-1$, shuffle them using Fisher-Yates (using a good RNG seeded by a cryptographic hash of the string), and then take the resulting sequence, and convert any value $< \omega$ into a '1' bit and any value $\ge \omega$ into a 0 bit...
Daniel S avatar
ru flag
@poncho Easier still would be to use a XOF to generate uniform random values from $[0,n)$ until $\omega$ distinct values have been produced. The combinatorist in me still leans towards the precision of the combinatorial number system.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.