CryptoDB
On the Security of Split-and-Lookup-Based ZK-Friendly Primitives
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Arithmetization-Oriented hash functions are optimized for their verification to be efficiently implemented within various proof systems, but they are often too slow when evaluated on a regular machine. To solve this problem for some specific protocols, some recent proposals introduced a new type of operations: the Split- And-Lookup. The idea in this case is to “split” prime field elements into smaller integers, e.g. by simply considering their binary representations, and then applying a permutation on each such integer before rebuilding a field element from them. Such operations are fast to evaluate, and of a very high degree in the field, which hopefully implies a high resistance against algebraic attacks.In this paper, we investigate the security offered by such components using two distinct approaches. First, we provide a detailed analysis of the cryptographic properties of the Split-And-Lookup construction. In particular, we present technique to efficiently compute its Fourier coefficients and linear approximation probabilities, and use them to show linear approximations of the S-boxes of Skyscraper, Monolith, Tip5, and Reinforced Concrete with surprisingly high probabilities. We also present our own S-boxes that could be used as a drop-in replacement for those of Monolith and Tip5, and would provide enhanced security and performances in some contexts. Finally, we turn our attention to the primitives themselves, and present a freestart partial preimage attack on a version of Tip5 reduced to four out of five rounds, where the attacker is allowed to control only one word in the initialization vector. This can be turned into a collision attack against a four-round version of Tip5 with a capacity reduced to 320 bits out of 384, though it should still provide the same security level as the original hash function. Despite the high degree of the Split-And- Lookup construction, we use an algebraic attack that essentially goes “around” these components.While these results do not directly threaten the security of full-round primitives, they further the understanding of the cryptographic properties of these new operations, and of the actual impact they have on the security against various attacks. |
BibTeX
@article{tosc-2025-35841,
title={On the Security of Split-and-Lookup-Based ZK-Friendly Primitives},
journal={IACR Transactions on Symmetric Cryptology},
publisher={Ruhr-Universität Bochum},
volume={2025},
pages={87-123},
url={https://tosc.iacr.org/index.php/ToSC/article/view/12245},
doi={10.46586/tosc.v2025.i2.87-123},
author={Antoine Bak and Léo Perrin},
year=2025
}