I would like to know what is the proper way of fitting the hash digest to the prime in which the encryption scheme operates. regardless if the bits of the hash digest is larger or smaller than the prime.

I've read that the Cramer-Shoup uses a universal one-way hash function, but didn't state what it is. Wikipedia says its just a property, and with that I plan on using SHA256. My simulator uses smaller bits for presentation purposes and the larger bits digest of SHA256, I have a problem on how to fit it in. I've read in some forums to use mod on in, is this the proper way ?

  • $\begingroup$ In the section, a simple implementation, it proposes to use SHA-1. But proposes to use a new hash to solve this issue. Note that SHA256, SHA-1 is not universal, GHASH and Poly1305 is. In either way, use XOF. $\endgroup$
    – kelalaka
    Nov 10, 2019 at 8:29
  • $\begingroup$ Well, MGF1 is the method that PKCS#1 uses, does that fit your need? It has security proofs for both signing and encryption (although those have been attacked and had to be amended, at least for RSA / OAEP). $\endgroup$
    – Maarten Bodewes
    Nov 10, 2019 at 14:18
  • $\begingroup$ And generally we don't allow smaller hash values to be used, because that would impede the security / collision resistance of a hash. However, you could define a hash algorithm that uses smaller output than the original. For instance, you can use SHA-224 which is just SHA-256 with different initial constants and a smaller output size. Similarly you could define SHA-160 or lower - but it would be only 80 bit collision resistant. (Using a XOF would be better if you want both large and small output sizes, I suppose, but that requires SHA-3) $\endgroup$
    – Maarten Bodewes
    Nov 10, 2019 at 14:28
  • 1
    $\begingroup$ @kelalaka FYI, UOWHF does not mean a universal hash family; it's an older name for target-collision-resistant. $\endgroup$ Nov 10, 2019 at 17:38
  • 2
    $\begingroup$ Maarten Bodewes, cramer-shoup uses the hash digest as an exponent for one computation. Squeamish Ossifrage, i'm new to this course, and doing this for a school project :). Thank you for the answers $\endgroup$ Nov 11, 2019 at 5:19

1 Answer 1


A universal one-way hash function (or UOWHF), also known as a target-collision-resistant (or TCR) hash function, is a randomized hash function $H_r(m)$ with the following security: If an adversary commits to a message $m$, then upon being challenged with a random $r$, the adversary cannot find a distinct message $m' \ne m$ such that $H_r(m) = H_r(m')$. (More details, background, history, and references on UOWHF/TCR, particularly in signature applications.)

Any collision-resistant hash function is obviously also TCR, but TCR is a much weaker security property—much all major ‘cryptographic hash functions’ like SHA-256 including broken ones like MD5 are generally conjectured to exhibit TCR in prefix-hash form $H(r \mathbin\| m)$ and in HMAC form $\operatorname{HMAC-\!}H_r(m)$, but in the off chance that they don't (the Merkle–Damgård construction does not necessarily preserve TCR), there's a generic construction called RMX from Halevi and Krawczyk's research program on randomized signatures, which was standardized by NIST in SP 800-106. If you like more modern flavors, you could use keyed BLAKE2 or KMAC128 too, since TCR—and the slightly stronger eTCR—was an explicit design goal for SHA-3.

If you want a smaller digest, just truncate the hash function; if you want a larger digest, the easiest way is to use an XOF like the SHA-3 function SHAKE128 or like BLAKE2x. You could also use SHA-256 in ‘CTR mode’, yielding $H(r \mathbin\| m \mathbin\| 0) \mathbin\| H(r \mathbin\| m \mathbin\| 1) \mathbin\| H(r \mathbin\| m \mathbin\| 2) \mathbin\| \dotsb$, provided you make sure to pad it unambiguously, or use a standard (if somewhat more complicated) construction like HKDF-SHA256 or MGF1 of PKCS#1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.