Geodesic
IQRA: Incremental Quadratic Re-keying friendly Authentication scheme
Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 3, pp. 5-35 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@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
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/

[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