Geodesic
IQRA: Incremental Quadratic Re-keying friendly Authentication scheme
Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 3, pp. 5-35 
L. R. Akhmetzyanova; E. K. Alekseev; A. A. Babueva; L. O. Nikiforova; S. V. Smyshlyaev. IQRA: Incremental Quadratic Re-keying friendly Authentication scheme. Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 3, pp. 5-35. http://geodesic.mathdoc.fr/item/MVK_2022_13_3_a0/
@article{MVK_2022_13_3_a0,
     author = {L. R. Akhmetzyanova and E. K. Alekseev and A. A. Babueva and L. O. Nikiforova and S. V. Smyshlyaev},
     title = {IQRA: {Incremental} {Quadratic} {Re-keying} friendly {Authentication} scheme},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {5--35},
     year = {2022},
     volume = {13},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2022_13_3_a0/}
}
TY  - JOUR
AU  - L. R. Akhmetzyanova
AU  - E. K. Alekseev
AU  - A. A. Babueva
AU  - L. O. Nikiforova
AU  - S. V. Smyshlyaev
TI  - IQRA: Incremental Quadratic Re-keying friendly Authentication scheme
JO  - Matematičeskie voprosy kriptografii
PY  - 2022
SP  - 5
EP  - 35
VL  - 13
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MVK_2022_13_3_a0/
LA  - en
ID  - MVK_2022_13_3_a0
ER  - 
%0 Journal Article
%A L. R. Akhmetzyanova
%A E. K. Alekseev
%A A. A. Babueva
%A L. O. Nikiforova
%A S. V. Smyshlyaev
%T IQRA: Incremental Quadratic Re-keying friendly Authentication scheme
%J Matematičeskie voprosy kriptografii
%D 2022
%P 5-35
%V 13
%N 3
%U http://geodesic.mathdoc.fr/item/MVK_2022_13_3_a0/
%G en
%F MVK_2022_13_3_a0

Voir la notice de l'article provenant de la source Math-Net.Ru

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.

[1] Akhmetzyanova L., Alekseev E., Oshkin I., Smyshlyaev S., Sonina L., “On the properties of the CTR encryption mode of the Magma and Kuznyechik block ciphers with re-keying method based on CryptoPro Key Meshing”, Matematicheskie voprosy kriptografii, 8:2 (2017), 39–50 | DOI | MR

[2] Akhmetzyanova L., Alekseev E., Oshkin I., Smyshlyaev S., “On Internal Re-keying”, Int. Conf. Research Security Standard., Lect. Notes Comput. Sci., 12529, 2020, 23–45 | DOI

[3] Akhmetzyanova L., Alekseev E., Sedov G., Smyshlyaeva E., Smyshlyaev S., “Practical significance of security bounds for standardized internally re-keyed block cipher modes”, Matematicheskie voprosy kriptografii, 10:2 (2019), 31–46 | DOI | MR

[4] Alekseev E., Akhmetzyanova L., Zubkov A., Karpunin G., Smyshlyaev S., “On one approach to formalizing cryptographic analysis tasks”, Matem. Vopr. Kriptogr., 2021 (to appear) (in Russian)

[5] Arte V., Bellare M., Khati L., “Incremental cryptography revisited: PRFs, nonces and modular design”, INDOCRYPT 2020, Lect. Notes Comput. Sci., 12578, 2020, 576–598 | DOI | MR

[6] Atighehchi K., Muntean T., “Towards fully incremental cryptographic schemes”, Proc. 8th ACM SIGSAC Symp. Inf., Computer and Commun. Security, ACM, 2013, 505–510

[7] Atighehchi K., Space-efficient, byte-wise incremental and perfectly private encryption schemes, Cryptology ePrint Archive, Report 2014/104, 2014

[8] Bellare M., Canetti R., Krawczyk H., “Pseudorandom functions revisited: The cascade construction and its concrete security”, Proc. 37th Conf. Found. Computer Sci., IEEE, 1996, 514–523 | DOI | MR

[9] Bellare M., Canetti R., Krawczyk H., “Keying hash functions for message authentication”, CRYPTO 96, Lect. Notes Comput. Sci., 1109, 1996, 1–15 | DOI | MR

[10] Bellare M., Desai A., Jokipii E., Rogaway P., “A concrete security treatment of symmetric encryption: Analysis of DES modes of operation”, Proc. 38th Annu. Symp. Found. Computer Sci., FOCS'97, IEEE, 1997, 394–403 | DOI

[11] Bellare M., Namprempre C., “Authenticated encryption: Relations among notions and analysis of the generic composition paradigm”, ASIACRYPT 2000, Lect. Notes Comput. Sci., 1976, 2000, 531–545 | DOI | MR

[12] Bellare M., Goldreich O., Goldwasser S., “Incremental cryptography: The case of hashing and signing”, CRYPTO'94, Lect. Notes Comput. Sci., 839, 1994, 216–233 | DOI

[13] Bellare M., Goldreich O., Goldwasser S., “Incremental cryptography and application to virus protection”, Proc. 27th Annu. ACM Symp. Theory Computing, ACM, 1995, 45–56

[14] Bellare M., Guérin R., Rogaway P., “XOR MACs: New methods for message authentication using finite pseudorandom functions”, CRYPTO'95, Lect. Notes Comput. Sci., 963, 1995, 15–28 | DOI | MR

[15] Bellare M., Micciancio D., “A new paradigm for collision-free hashing: Incrementality at reduced cost”, EUROCRYPT'97, Lect. Notes Comput. Sci., 1233, 1997, 163–192 | DOI | MR

[16] Bellare M., Rogaway P., Univ. California at Davis, 2005, 283 pp.

[17] Bellare M., Rogaway P., “The security of triple encryption and a framework for code-based game-playing proofs”, EUROCRYPT 2006, Lect. Notes Comput. Sci., 4004, 2006, 409–426 | DOI | MR

[18] Bernstein D., Stronger security bounds for permutations, , 2005 cr.yp.to/papers.html#poly1305

[19] Bernstein D., “Stronger security bounds for Wegman–Carter–Shoup authenticators”, EUROCRYPT 2005, Lect. Notes Comput. Sci., 3494, 2005, 164–180 | DOI | MR

[20] Black J., Rogaway P., “A block-cipher mode of operation for parallelizable message authentication”, EUROCRYPT 2002, Lect. Notes Comput. Sci., 2332, 2002, 384–397 | DOI | MR

[21] Buonanno E., Katz J., Yung M., “Incremental unforgeable encryption.”, FSE 2001, Lect. Notes Comput. Sci., 2355, 2002, 109–124 | DOI

[22] Itani W., Kayssi A., Chehab A., “Energy-efficient incremental integrity for securing storage in mobile cloud computing”, 2010 Int. Conf. Energy Aware Computing, IEEE, 2010, 1–2

[23] Khati L., Full disk encryption and beyond, Diss., Ecole Norm. Supér. de Paris, 2019, 182 pp.

[24] Khati L., Vergnaud D., “Analysis and improvement of an authentication scheme in incremental cryptography”, SAC 2019, Lect. Notes Comput. Sci., 11349, 2019, 50–70 | DOI | MR

[25] Fischlin M., “Incremental cryptography and memory checkers”, EUROCRYPT'97, Lect. Notes Comput. Sci., 1233, ed. Walter Fumy, 1997, 293–408 | MR

[26] Fischlin M., “Lower bounds for the signature size of incremental schemes”, 38th Annu. Symp. Found. Computer Sci., IEEE, 1997, 438–447 | DOI

[27] Bok-Min G., Siddiqi M. U., Hean-Teik C., “Incremental hash function based on pair chaining modular arithmetic combining”, INDOCRYPT 2001, Lect. Notes Comput. Sci., 2247, 2001, 50–61 | DOI | MR

[28] Hart J. K., Martinez K., Environmental sensor networks: A revolution in the Earth system science?, Earth-Science Reviews, 2006, 177–191 | DOI

[29] Iwata T., Minematsu K., Peyrin T., Seurin Y., “ZMAC: A fast tweakable block cipher mode for highly secure message authentication”, CRYPTO 2017, Lect. Notes Comput. Sci., 10401, 2017, 34–65 | DOI | MR

[30] Krawczyk H., “Cryptographic extraction and key derivation: The HKDF scheme”, CRYPTO 2010, Lect. Notes Comput. Sci., 6223, 2010, 631–648 | DOI | MR

[31] Mihajloska H., Gligoroski D., Samardjiska S., “Reviving the idea of incremental cryptography for the zettabyte era use case: Incremental hash functions based on SHA-3”, Int. Workshop Open Problems Network Security, 2015, 97–111

[32] Mironov I., Pandey O., Reingold O., Segev G., “Incremental deterministic public-key encryption”, EUROCRYPT 2012, Lect. Notes Comput. Sci., 7237, 2012, 628–644 | DOI | MR

[33] Micciancio D., “Oblivious data structures: Applications to cryptography”, 29th Annu. ACM Symp. Theory Computing, ACM, 1997, 456–464 | MR

[34] McGrew D.A., Viega J., “The security and performance of the Galois/counter mode (GCM) of operation”, INDOCRYPT 2004, Lect. Notes Comput. Sci., 3348, 2004, 343–355 | DOI | MR

[35] Peyrin T., Seurin Y., “Counter-in-tweak: Authenticated encryption modes for tweakable block ciphers”, CRYPTO 2016, Lect. Notes Comput. Sci., 9814, 2016, 33–63 | DOI | MR

[36] Sasaki Y., Yasuda K., “A new mode of operation for incremental authenticated encryption with associated data”, SAC 2015, Lect. Notes Comput. Sci., 9566, 2016, 397–416 | DOI | MR

[37] Smyshlyaev S., Re-keying Mechanisms for Symmetric Keys, RFC 8645, 2019 https://www.rfc-editor.org/info/rfc8645

[38] Standaert F.-X., “Introduction to side-channel attacks”, Secure Integrated Circuits and Systems, Springer, 2010, 27–42 | DOI