TY - GEN
T1 - Random oracles and non-uniformity
AU - Coretti, Sandro
AU - Dodis, Yevgeniy
AU - Guo, Siyao
AU - Steinberger, John
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2018.
PY - 2018
Y1 - 2018
N2 - We revisit security proofs for various cryptographic primitives in the auxiliary-input random-oracle model (AI-ROM), in which an attacker A can compute arbitrary S bits of leakage about the random oracle O before attacking the system and then use additional T oracle queries to O during the attack. This model has natural applications in settings where traditional random-oracle proofs are not useful: (a) security against non-uniform attackers; (b) security against preprocessing. We obtain a number of new results about the AI-ROM: Unruh (CRYPTO’07) introduced the pre-sampling technique, which generically reduces security proofs in the AI-ROM to a much simpler P-bit-fixing random-oracle model (BF-ROM), where the attacker can arbitrarily fix the values of O on some P coordinates, but then the remaining coordinates are chosen at random. Unruh’s security loss for this transformation is √ST/P. We improve this loss to the optimal value O(ST/P), obtaining nearly tight bounds for a variety of indistinguishability applications in the AI-ROM. While the basic pre-sampling technique cannot give tight bounds for unpredictability applications, we introduce a novel “multiplicative version” of pre-sampling, which allows to dramatically reduce the size of P of the pre-sampled set to P = O(ST) and yields nearly tight security bounds for a variety of unpredictability applications in the AI-ROM. Qualitatively, it validates Unruh’s “polynomial pre-sampling conjecture”-disproved in general by Dodis et al. (EUROCRYPT’17)-for the special case of unpredictability applications. Using our techniques, we reprove nearly all AI-ROM bounds obtained by Dodis et al. (using a much more laborious compression technique), but we also apply it to many settings where the compression technique is either inapplicable (e.g., computational reductions) or appears intractable (e.g., Merkle-Damgård hashing). We show that for any salted Merkle-Damgård hash function with m-bit output there exists a collision-finding circuit of size Θ(2m/3) (taking salt as the input), which is significantly below the 2m/2 birthday security conjectured against uniform attackers. We build two compilers to generically extend the security of applications proven in the traditional ROM to the AI-ROM. One compiler simply prepends a public salt to the random oracle, showing that salting generically provably defeats preprocessing.Overall, our results make it much easier to get concrete security bounds in the AI-ROM. These bounds in turn give concrete conjectures about the security of these applications (in the standard model) against nonuniform attackers.
AB - We revisit security proofs for various cryptographic primitives in the auxiliary-input random-oracle model (AI-ROM), in which an attacker A can compute arbitrary S bits of leakage about the random oracle O before attacking the system and then use additional T oracle queries to O during the attack. This model has natural applications in settings where traditional random-oracle proofs are not useful: (a) security against non-uniform attackers; (b) security against preprocessing. We obtain a number of new results about the AI-ROM: Unruh (CRYPTO’07) introduced the pre-sampling technique, which generically reduces security proofs in the AI-ROM to a much simpler P-bit-fixing random-oracle model (BF-ROM), where the attacker can arbitrarily fix the values of O on some P coordinates, but then the remaining coordinates are chosen at random. Unruh’s security loss for this transformation is √ST/P. We improve this loss to the optimal value O(ST/P), obtaining nearly tight bounds for a variety of indistinguishability applications in the AI-ROM. While the basic pre-sampling technique cannot give tight bounds for unpredictability applications, we introduce a novel “multiplicative version” of pre-sampling, which allows to dramatically reduce the size of P of the pre-sampled set to P = O(ST) and yields nearly tight security bounds for a variety of unpredictability applications in the AI-ROM. Qualitatively, it validates Unruh’s “polynomial pre-sampling conjecture”-disproved in general by Dodis et al. (EUROCRYPT’17)-for the special case of unpredictability applications. Using our techniques, we reprove nearly all AI-ROM bounds obtained by Dodis et al. (using a much more laborious compression technique), but we also apply it to many settings where the compression technique is either inapplicable (e.g., computational reductions) or appears intractable (e.g., Merkle-Damgård hashing). We show that for any salted Merkle-Damgård hash function with m-bit output there exists a collision-finding circuit of size Θ(2m/3) (taking salt as the input), which is significantly below the 2m/2 birthday security conjectured against uniform attackers. We build two compilers to generically extend the security of applications proven in the traditional ROM to the AI-ROM. One compiler simply prepends a public salt to the random oracle, showing that salting generically provably defeats preprocessing.Overall, our results make it much easier to get concrete security bounds in the AI-ROM. These bounds in turn give concrete conjectures about the security of these applications (in the standard model) against nonuniform attackers.
UR - http://www.scopus.com/inward/record.url?scp=85045879999&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045879999&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-78381-9_9
DO - 10.1007/978-3-319-78381-9_9
M3 - Conference contribution
AN - SCOPUS:85045879999
SN - 9783319783802
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 227
EP - 258
BT - Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018 Proceedings
A2 - Nielsen, Jesper Buus
A2 - Rijmen, Vincent
PB - Springer Verlag
T2 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018
Y2 - 29 April 2018 through 3 May 2018
ER -