Quantification of Adversarial Resources. We will consider information-theoretic adversaries that have two oracle inter- K faces: a construction oracle, KDf or IXIFRO, and a primitive oracle f . For K the construction queries, it can make initialization queries or duplexing queries. Note that, when querying IXIFRO, every query has a path Path associated to it. To unify notation, we also associate a Path to each query (initialization or duplexing) to KDf . This Path is defined the straightforward way: it simply con- sists of the concatenation of Encode(δ), iv of the most recent initialization call and all σ-values that have been queried after the last initialization but before the current query. Using this formalization, every initialization or duplexing call K that the adversary makes to KDf or IXIFRO can be properly captured by a tuple (Path, Z, σ), || ∈ ∈ where, intuitively, Path is all data that is used to generate response Z Zr , and σ Zb is the input string (slightly abusing notation; σ = σ if flag = false and σ = σ + (Z 0c) if flag = true). Following Xxxxxxxx et al. [2], we specify adversarial resources that impose limits on the transcripts that any adversary can obtain. The basic resource met- rics are quantitative: they specify the number of queries an adversary is allowed to make for each type. – N : the number of primitive queries. It corresponds to computations requiring no access to the (keyed) construction. It is usually called the time or offline complexity. In practical use cases, N is only limited by the computing power and time available to the adversary. – M : the number of construction queries. It corresponds to the amount of data processed by the (keyed) construction. It is usually called the data or online complexity. In many practical use cases, M is limited. We remark that identical calls are counted only once. In other words, N only counts the number of primitive queries, and M only counts the number of unique tuples (Path, σ). It is possible to perform an analysis solely based on these metrics, but in order to more accurately cover practical settings that were not covered before (such as the multi-key setting or the nonce-respecting setting), and to eliminate the multiplicity (a metric used in all earlier results in this direction), we define a number of additional metrics. – q: the total number of different initialization tuples (Encode(δ), iv). Para- meter q corresponds to the number of times an adversary can start a fresh initialization of KD or IXIF. – qiv: iv multipli...
