I would like to know an algorithm hash to a finite field.

I have an $l$ bit prime number $q$. I want setup a hash function $H: \{0,1\}^* \to \mathbb F_q$ but I do not know how I can do it. I use a library for a hash with C++, this is cryptopp. I find an answer at Right way to hash elliptic curve points into finite field but I don't understand.

Does anyone help me know what to do?

  • $\begingroup$ Could you clarify that the value of $q$ is around? What is the protocol/scheme that you want to use? What is the input space? What is the required security from the hashing? etc. Without these, this question too broad to have a proper answer. $\endgroup$ – kelalaka Feb 5 at 12:59

To hash from $\{0,1\}^*$ (or other large domain) into the integers in $[0,q)$ or any set with a natural mapping¹ to that interval, pick a $b$-bit security margin, a hash $H$ at least $h=\lceil b/2+\log_2q\rceil$-bit and unrelated to others used in the cryptosystem, and define the hash of bitstring $M$ as $H(M)\bmod q$, with $H(M)$ considered an integer in $[0,2^h)$ per e.g. big-endian convention.

When $M$ is random and $H(M)$ has at least $b$-bit security against distinguishing attacks, this has at least in the order of $b$-bit security against distinguishing attacks. When $q>2^b$, this has at least in the order of $b$-bit preimage resistance. When $q>2^{2b}$, this has at least in the order of $b$-bit collision resistance.

E.g. for $q$ up to 400 bits, $\text{SHA–512}(M)\bmod q$ will do if nothing in the system uses SHA–512 (nor something built using the same constants).

If ones needs several independent such hash functions, one should use several independent $H_i$ to start with. That can be constructed from a single hash $H$, e.g. as $H(M\mathbin\|i)\bmod q$.

¹ The mapping between the destination set and $[0,q)$ must be efficiently computable in both directions. Therefore the set can be the finite field $\mathbb F_q$ when $q$ is a prime or a prime power, or the ring $\mathbb Z_q$ (aka $\mathbb Z/q\mathbb Z$). We need a different construction for an Elliptic Curve (sub)group of order $q$ if we posit it's one where the Discrete Logarithm problem is hard.

  • $\begingroup$ Although small, the mod $q$ will introduce a bias even we assume that SHA-512 is uniform random. It should be trancate. $\endgroup$ – kelalaka Feb 5 at 10:17
  • $\begingroup$ @kelalaka: truncating will yield uniform output only for $q$ a power of two, thus we can't safely truncate (in the context as stated in the question). Because I make the hash width at least $b/2+\log_2q$, it takes $O(2^b)$ hash computations to detect the bias. That's >200-bit security with SHA-512 up to 400-bit $q$, unless I goofed somewhere. I wish I had a reference for the $b/2$ rather than $b$, though. $\endgroup$ – fgrieu Feb 5 at 10:49
  • $\begingroup$ Yes, it is small, however, we can do it without it, too. I think the answer will be better with quantified examples like for $2^m$ and $\mathbb F_p^m$. The OP, unfortunately, is not clear about this, however, we can assume the ECC primes. $\endgroup$ – kelalaka Feb 5 at 11:01
  • $\begingroup$ Excuse me, can you describe more specific how to mapping digest to finite field. E.g I using SHA3-512 hash function, it output digest with 512 bit length. Then I using hex encoder to encode digest to HEX string for export to screen. My idea is convert it to Hex number, then modulo to prime number q. Is it right? If not, how to? $\endgroup$ – Nguyễn Hồng Sơn Feb 22 at 10:36
  • $\begingroup$ @NguyễnHồngSơn: yes, assuming $q<2^{\approx432}$, you can convert the output of SHA3-512 to an integer in $[0,2^{512})$, then reduce this modulo $q$. $\endgroup$ – fgrieu Feb 28 at 2:21

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.