How to implement hash functions $H1 \colon \{0,1\}^* \to \mathbb{Z}_p^$ and $H2 \colon \mathbb{Z}_p^ \to \{0,1\}^k$?

shxxlas

1/19/24, 11:25 AM

I would like to implement a hash function $H1 \colon \{0,1\}^* \to \mathbb{Z}_p^*$ such that $p$ is a prime number and second fonction $H2 \colon \mathbb{Z}_p^* \to \{0,1\}^k$ where $k$ is a security parameter

what is the best way to implement them with SHA 256 or another hash function?

117

0 + 6

implementation

poncho

1/19/24, 2:03 PM

Unless $p$ is small (e.g. limited to $2^{60}$ or so), H2 is effectively unimplementable, as it would require an impractical amount of memory to store the result

shxxlas

1/19/24, 2:47 PM

@poncho I didn't understand you

poncho

1/19/24, 2:51 PM

$\{ 0, 1 \}^k$ means a string of $k$ bits; if $k > 2^{64}$ then that string is >2 exabytes long. Did you mean perhaps $(0, k)$ instead?

shxxlas

1/19/24, 3:00 PM

Sorry there are no constraints on k

fgrieu

1/19/24, 3:07 PM

Hint: first, construct from SHA-256 a family of hashes $H_{(C,k)}:\{0,1\}^*\to\{0,1\}^k$ parameterized by $C$ (for $k\le256$, HMAC-SHA-256 with key C and output truncated to $k$ bits will do; above, vary the constant $C$). Then build $H_2$ as $H_{(C_2,k)}$ for some arbitrary $C_2$. And build $H_1$ as$$H_1(M)=\left(H_{(C_1,\lceil\log_2(k)+\lambda\rceil)}(M)\bmod(p-1)\right)+1$$

fgrieu

1/23/24, 7:58 PM

Comments are not for extended discussion; this conversation has been [moved to chat](https://chat.stackexchange.com/rooms/142284/discussion-on-question-by-shxxlas-how-to-implement-hash-functions-h1-colon-0).

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How to implement hash functions $H1 \colon \{0,1\}^* \to \mathbb{Z}_p^*$ and $H2 \colon \mathbb{Z}_p^* \to \{0,1\}^k$?

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.