How to map output of SHA to $\mathbb{F}_q^n$

Shweta Aggrawal

6/6/23, 8:54 AM

I have an arbitrary string. I want to know how to implement a hash function $H: \{0,1\}^* \to \mathbb F_q^n$ which takes arbitrary strings to an element of $\mathbb{F}_q^n$. Here $\mathbb{F}_q$ denotes the finite field of order $q$.

Edit: $q=256$

Edit 2: $\mathbb F_q^n$ simply means $n$ dimensional vector space over $\mathbb{F}_q$. If $x \in \mathbb F_q^n$, it means $x$ has the following form

$$x=(x_1,x_2,\ldots,x_n), \mbox{ with } x_i \in \mathbb{F}_q$$

0 + 0

hash

post-quantum-cryptography

meshcollider

6/6/23, 9:31 AM

Relevant: https://crypto.stackexchange.com/questions/88002/how-to-map-output-of-hash-algorithm-to-a-finite-field

kelalaka

6/6/23, 10:47 AM

It is not clear about $q=?$. Another one https://crypto.stackexchange.com/q/87012/18298 and another https://crypto.stackexchange.com/q/86375/18298

fgrieu

6/6/23, 6:02 PM

[Revised for Edit2] Hint: What is [$\mathbb F_q$](https://en.wikipedia.org/wiki/Finite_field)? How many elements are there in $\mathbb F_q$? Thus in [${\mathbb F_q}^n$](https://en.wikipedia.org/wiki/Cartesian_product#n-ary_Cartesian_power)? How do you write $\mathbb F_q$ as $\mathbb F_{p^k}$? Thus how many bits do you need to represent an element of $\mathbb F_q$? Of ${\mathbb F_q}^n$? How do you get these bits with a hash of the SHA family?

Shweta Aggrawal

6/7/23, 7:34 AM

@fgrieu Thank you for your hints. I will think about it and let you know as soon as possible. Thanks again for showing the right direction.

Elon Musk

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

EN: How to map output of SHA to $\mathbb{F}_q^n$

TH: วิธีแมปเอาต์พุตของ SHA กับ $\mathbb{F}_q^n$

RO: Cum să mapați rezultatul SHA la $\mathbb{F}_q^n$

RU: Как сопоставить вывод SHA с $\mathbb{F}_q^n$

VI: Cách ánh xạ đầu ra của SHA thành $\mathbb{F}_q^n$

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.