Stronger simpler cryptographic hash functions using new math assumptions
Simple Extremely Lossy Functions from Small-Exponent Hashing
Cryptography and Security
Summary
Creating secure cryptographic functions often relies on complicated methods and certain math assumptions that work mostly in specific settings. This paper introduces a new kind of hash function that is simpler and stronger, based on different mathematical problems than usual. The authors use assumptions about the difficulty of certain exponent problems in modular arithmetic rather than relying on traditional ones that only work well for elliptic curves. This new approach could make some cryptographic designs more diverse and efficient.
What this means in practice
- •For cryptographic system designers: Design cryptographic schemes requiring random oracle properties with simpler, more efficient hash functions based on different hardness assumptions from modular arithmetic.
- •For blockchain developers: Implement hash functions resistant to certain attacks using alternative assumptions beyond elliptic curve discrete logarithm, potentially enhancing blockchain security.
A theory result. No direct application yet.
Authors
Damiano Abram, Agni Datta, Archisman Dutta, Lawrence Roy
Abstract
Extremely Lossy Functions (ELFs) are a standard model primitive that captures many useful properties of random oracles (Zhandry, Crypto 2016). While there are many variations of ELFs with additional properties, every construction (excluding obfuscation) has followed essentially the same template of bootstrapping from a sequence of ELFs secure only against fixed-size adversaries, and every construction was based on only the exponential hardness of DDH (or $k$-Lin), an assumption that is only reasonable over elliptic curves. We introduce and construct Extremely Lossy Trapdoor Hashing (ELTDH), a stronger notion that implies all known variations of ELFs. Our construction achieves ELTDH in one go, without bootstrapping from schemes secure for only fixed-size adversaries, which makes it simpler and more efficient than existing ELFs. We assume exponential security of the small-exponent discrete logarithm, together with polynomial security of decisional composite residuosity (DCR). Exponential security is only required in the size of the secret exponent, not the size of the group, so the assumption plausibly holds for multiplication modulo $N^2$ (and for many other cryptographic groups), despite the subexponential-time discrete logarithm attacks from index calculus. Our results diversify the assumptions underlying ELFs, while also giving a simpler construction.