The advantage of truncated permutations

Shoni Gilboa, Shay Gueron

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


Constructing a Pseudo Random Function (PRF) is a fundamental problem in cryptology. Such a construction, implemented by truncating the last m bits of permutations of {0,1}n was suggested by Hall et al. (1998). They conjectured that the distinguishing advantage of an adversary with q queries, Advn,m(q), is small if q=o(2(n+m)∕2), established an upper bound on Advn,m(q) that confirms the conjecture for m<n∕7, and also declared a general lower bound Advn,m(q)=Ω(q2∕2n+m). The conjecture was essentially confirmed by Bellare and Impagliazzo (1999). Nevertheless, the problem of estimating Advn,m(q) remained open. Combining the trivial bound 1, the birthday bound, and a result of Stam (1978) leads to the upper bound [Formula presented] In this paper we show that this upper bound is tight for every 0≤m<n and any q. This, in turn, verifies that the converse to the conjecture of Hall et al. is also correct, i.e., that Advn,m(q) is negligible only for q=o(2(n+m)∕2).

שפה מקוריתאנגלית
עמודים (מ-עד)214-223
מספר עמודים10
כתב עתDiscrete Applied Mathematics
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 15 מאי 2021

הערה ביבליוגרפית

Publisher Copyright:
© 2021 Elsevier B.V.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'The advantage of truncated permutations'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי