bitcoin-dev

Lamport scheme (not signature) to economize on L1

Lamport scheme (not signature) to economize on L1

Original Postby Nagaev Boris

Posted on: December 20, 2023 21:33 UTC

In the realm of cryptographic hash functions, there is a well-acknowledged consensus that the digest size should ideally be double that of the key size used in symmetric encryption.

This recommendation stems from the consideration of security against collision attacks, which is significantly relevant due to the implications of the birthday paradox. Specifically, for a hash function with a 128-bit digest size, an adversary would need to perform approximately 2^64 hash calculations to successfully find a collision.

The idea of reducing the block space utilization by 26% has its merits; however, it comes at the cost of weakened security when considering a reduction to 12-byte hashes. The latter would require only 2^48 calculations to find a collision, which is considerably less secure and thus not an advisable tradeoff.

Further analysis on the feasibility of 12-byte hashes includes their vulnerability to rainbow table attacks, especially by well-resourced organizations such as state-level actors. For illustration, if one assumes a rainbow table with a chain length of 1024^3 (one billion), the required storage size would amount to 900 exabytes. While this figure appears daunting given current technological constraints, it's important to acknowledge that advancements in hash function optimization, memory technology, and storage affordability could potentially make such an attack more feasible in the future.

It is crucial to remain cognizant of these evolving factors as they underline the importance of maintaining robust security standards for cryptographic practices.