1. Economically Optimal Variable Tag Length Authentication 2017 Authentication FinancialCryptography
    Reihaneh Safavi-Naini, Viliam Lisy, Yvo Desmedt
    [View PDF on fc17.ifca.ai]
    [Show BibTex Citation]

    author = {Reihaneh Safavi{-}Naini and
    Viliam Lis{\'{y}} and
    Yvo Desmedt},
    editor = {Aggelos Kiayias},
    title = {Economically Optimal Variable Tag Length Message Authentication},
    booktitle = {Financial Cryptography and Data Security - 21st International Conference,
    {FC} 2017, Sliema, Malta, April 3-7, 2017, Revised Selected Papers},
    series = {Lecture Notes in Computer Science},
    volume = {10322},
    pages = {204--223},
    publisher = {Springer},
    year = {2017},
    url = {https://doi.org/10.1007/978-3-319-70972-7\_11},
    doi = {10.1007/978-3-319-70972-7\_11},
    timestamp = {Tue, 14 May 2019 10:00:38 +0200},
    biburl = {https://dblp.org/rec/bib/conf/fc/Safavi-NainiLD17},
    bibsource = {dblp computer science bibliography, https://dblp.org}

Cryptographic authentication protects messages against forgeries. In real life, messages carry information of different value and the gain of the adversary in a successful forgery and the corresponding cost of the system designers, depend on the “meaning” of the message. This is easy to see by comparing the successful forgery of a $1,000 transaction with the forgery of a $1 one. Cryptographic protocols require computation and increase communication cost of the system, and an economically optimal system must optimize these costs such that message protection be commensurate to their values. This is especially important for resource limited devices that rely on battery power. A MAC (Message Authentication Code) provides protection by appending a cryptographic tag to the message. For secure MACs, the tag length is the main determinant of the security level: longer tags provide higher protection and at the same time increase the communication cost of the system. Our goal is to find the economically optimal tag lengths when messages carry information of different values.

We propose a novel approach to model the cost and benefit of information authentication as a two-party extensive-form game, show how to find a Nash equilibrium for the game, and determine the optimal tag lengths for messages. We prove that computing an optimal solution for the game is NP-complete, and then show how to find an optimal solution using single Mixed Integer Linear Program (MILP). We apply the approach to the protection of messages in an industrial control system using realistic messages, and give our analysis with numerical results obtained using off-the-shelf IBM CPLEX solver.