Аннотация: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.