Sandwich Construction for Keyed Sponges: Independence between Capacity and Construction Queries

In this study, the authors study the pseudo-random function (PRF) security of keyed sponges. ‘Capacity’ is a parameter of a keyed sponge that usually defines a dominant term in the PRF-security bound. The previous works have improved the capacity term in the PRF-security bound of the ‘prefix’ keyed sponge, where a secret key is prepended to an input message, and then the resultant value is inputted into the sponge function. A tight bound for the capacity term was given by Naito and Yasuda (FSE 2016): ( q Q + q 2 ) / 2 c for the capacity c, the number of construction queries q and the number of primitive queries Q. Thus, the following question naturally arises: Can they construct a keyed sponge with beyond the ( q 2 + q Q ) / 2 c -bound security? In this study, they consider the ‘sandwich’ keyed sponge, where a secret key is both prepended and appended to an input message, and then the resultant value is inputted into the sponge function. They prove that the capacity term becomes r Q / 2 c for the rate r, which is usually r ≪ q and r ≪ Q . That is, the dependence between the capacity and construction queries can be removed by the sandwich construction.