Stronger security bounds for Wegman-Carter-Shoup authenticators

D.J. Bernstein

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    44 Citaten (Scopus)
    1 Downloads (Pure)


    Shoup proved that various message-authentication codes of the form (n,m) ¿ h(m) + f(n) are secure against all attacks that see at most $\sqrt{1/\epsilon}$1 authenticated messages. Here m is a message; n is a nonce chosen from a public group G; f is a secret uniform random permutation of G; h is a secret random function; and e is a differential probability associated with h. Shoup’s result implies that if AES is secure then various state-of-the-art message-authentication codes of the form (n,m) ¿h(m)¿+¿AES k (n) are secure up to Ö{ 1/e}1 authenticated messages. Unfortunately, Ö{ 1/e}1 is only about 250 for some state-of-the-art systems, so Shoup’s result provides no guarantees for long-term keys. This paper proves that security of the same systems is retained up to Ö{#G}#G authenticated messages. In a typical state-of-the-art system, Ö{#G}#G is 264. The heart of the paper is a very general "one-sided" security theorem: (n,m) ¿ h(m) + f(n) is secure if there are small upper bounds on differential probabilities for h and on interpolation probabilities for f.
    Originele taal-2Engels
    TitelAdvances in Cryptology - Eurocrypt 2005 (24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings)
    RedacteurenR. Cramer
    Plaats van productieBerlin
    ISBN van geprinte versie3-540-25910-4
    StatusGepubliceerd - 2005

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743


    Duik in de onderzoeksthema's van 'Stronger security bounds for Wegman-Carter-Shoup authenticators'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit