IQRA: Incremental Quadratic Re-keying friendly Authentication scheme

The notion of incremental cryptography becomes more and more relevant in the big data world. Incremental mechanisms allow to quickly update the result of the algorithm for a modified data, rather than having to re-compute it from scratch. A significant flaw of the existing incremental schemes, specifically incremental MACs, is that they lose incremental property in case of key update. In the current paper we propose new incremental re-keying friendly MAC scheme, called IQRA, based on quadratic multivariate polynomial and PRF. We define the way how to use the IQRA scheme with re-keying mechanism based on KDF and introduce SUF-CSMA notion to analyze the security of this composition. We provide the security bound for the proposed scheme and improve it for the special case when a block cipher is used as the underlying PRF.