<inline-formula><tex-math id="M1">\begin{document}$\textsf{DWCDM+}$\end{document}</tex-math></inline-formula>: A BBB secure nonce based MAC

Nilanjan Datta; Avijit Dutta; Mridul Nandi; Kan Yasuda

doi:10.3934/amc.2019042

Previous Article
The secure link prediction problem
AMC Home
This Issue
Next Article
Revisiting design principles of Salsa and ChaCha

November 2019, 13(4): 705-732. doi: 10.3934/amc.2019042

$\textsf{DWCDM+}$: A BBB secure nonce based MAC

Nilanjan Datta ^1,, , Avijit Dutta ^1, , Mridul Nandi ^1, and Kan Yasuda ^2,

1.	Indian Statistical Institute, Kolkata, India
2.	NTT Secure Platform Laboratories, NTT Corporation, Japan

^* Corresponding author

Received November 2018 Revised January 2019 Published June 2019

Fund Project: This is an extended version of the article accepted in IACR-CRYPTO 2018. Section 3, section 4 and section 5 contains the substantial changes from our article accepted in IACR-CRYPTO 2018. Mridul Nandi is supported by R.C.Bose Centre for Cryptology and Security.

In CRYPTO 2016, Cogliati and Seurin have proposed a nonce-based MAC called Encrypted Wegman-Carter with Davies-Meyer (

$\textsf{EWCDM}$

), from an

$n$

-bit block cipher

$\textsf{E}$

and an

$n$

-bit almost xor universal hash function

$\textsf{H}$

$\textsf{E}_{K_2}\bigl(\textsf{E}_{K_1}(N)\oplus N\oplus \textsf{H}_{K_h}(M)\bigr),$

for a nonce

$N$

and a message

$M$

that provides roughly

$2n/3$

-bit MAC security. However, obtaining the similar security using a single block cipher key was posed as an open research problem. In this paper, we present Decrypted Wegman-Carter with Davies-Meyer (

$\textsf{DWCDM+}$

) construction based on a single block cipher key that provides

$2n/3$

-bit MAC security from an

$n$

-bit block cipher

$\textsf{E}$

and an

$n$

-bit

$k$

-regular (

$\forall k \leq n$

), almost xor universal hash function

$\textsf{H}$

$ \textsf{E}^{-1}_{K}\bigl(\textsf{E}_{K}(N)\oplus N \oplus \textsf{H}_{K_h}(M)\bigr). $

$\textsf{DWCDM+}$

is structurally very similar to its predecessor

$\textsf{EWCDM}$

except that the facts that (i) the number of block cipher keys reduced from

$2$

$1$

and (ⅱ) the outer encryption call is replaced by a decryption one. To make the construction truely single-keyed, here we derive the hash key

$K_h$

as the block cipher output of a fixed string

$0^{n-2} \| 10$

as long as the hash key is of

$n$

bits. We show that if the nonce space is restricted to

$(n-1)$

bits,

$\textsf{DWCDM+}$

is secured roughly up to

$2^{2n/3}$

MAC queries (

$2^{n/2}$

MAC queries) and

$2^n$

verification queries against nonce respecting (nonce misuse resp.) adversaries.

Keywords: $\textsf{EWCDM}$, $\textsf{DWCDM+}$, mirror theory, extended mirror theory, H-coefficient.

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation: Nilanjan Datta, Avijit Dutta, Mridul Nandi, Kan Yasuda. $\textsf{DWCDM+}$: A BBB secure nonce based MAC. Advances in Mathematics of Communications, 2019, 13 (4) : 705-732. doi: 10.3934/amc.2019042

References:

[1]	M. Bellare and R. Impagliazzo, A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion, preprint, ePrint: 1999/024.ps.
[2]	M. Bellare, O. Goldreich and A. Mityagin, The power of verification queries in message authentication and authenticated encryption, preprint, ePrint: 2004/309.ps.
[3]	S. Chen and J. Steinberger, Tight Security Bounds for Key-Alternating Ciphers, in Advances in Cryptology - EUROCRYPT 2014, Academic Press, 8441 (2014), 327–350.
[4]	S. Chen, R. Lampe, J, Lee, Ya. Seurin and J. Steinberger, Minimizing the two-round even-Mansour cipher, in Advances in Cryptology - CRYPTO 2014, Academic Press, 8616 (2014), 39–56. doi: 10.1007/978-3-662-44371-2_3.
[5]	B. Cogliati and Y. Seurin, Analysis of the single-permutation encrypted Davies-Meyer construction, Des. Codes Cryptography, 86 (2018), 2703-2723. doi: 10.1007/s10623-018-0470-9.
[6]	B. Cogliati and Y. Seurin, EWCDM: An efficient, beyond-birthday secure, nonce-misuse resistant MAC, in Advances in Cryptology - CRYPTO 2016, Academic Press, 9814 (2016), 121–149. doi: 10.1007/978-3-662-53018-4_5.
[7]	W. Dai, V. T. Hoang and S. Tessaro, Information-theoretic indistinguishability via the chi-squared method, in Advances in Cryptology - CRYPTO 2017, Academic Press, 10403 (2017), 497–523.
[8]	N. Datta, A. Dutta, M. Nandi and K. Yasuda, Encrypt or decrypt? To make a single-key beyond birthday secure nonce-based MAC, in Advances in Cryptology - CRYPTO 2018, Academic Press, 10991 (2018), 631–661.
[9]	N. Datta, A. Dutta, M. Nandi, G. Paul and L. Zhang, Single key variant of PMAC_plus, IACR Trans. Symmetric Cryptol., 2017 (2017), 268–305.
[10]	N. Datta, A. Dutta, M. Nandi and G. Paul, Double-block hash-then-sum: A paradigm for constructing BBB secure PRF, IACR Trans. Symmetric Cryptol., 2018 (2018), 36–92.
[11]	A. Dutta, A. Jha and M. Nandi, Tight security analysis of ehtm MAC, IACR Trans. Symmetric Cryptol., 2017 (2017), 130–150.
[12]	B. Gilles, On computationally secure authentication tags requiring short secret shared keys, in Advances in Cryptology - CRYPTO '82, Academic Press, (1983), 79–86. doi: 10.1007/978-1-4757-0602-4_7.
[13]	O. Goldreich, S. Goldwasser and S. Micali, On the cryptographic applications of random functions, in Advances in Cryptology - CRYPTO '84, Academic Press, 196 (1984), 276–288. doi: 10.1007/3-540-39568-7_22.
[14]	P. Jacques, The "Coefficients H" technique, in Selected Areas in Cry. ptography, Academic Press, 5381 (2008), 328–345. doi: 10.1007/978-3-642-04159-4_21.
[15]	P. Jacques, Introduction to mirror theory: Analysis of systems of linear equalities and linear non equalities for cryptography, preprint, https://eprint.iacr.org/2010/287.pdf.
[16]	P. Jacques, Mirror theory and cryptography, Appl. Algebra Engrg. Commun. Comput., 28 (2017), 321-338. doi: 10.1007/s00200-017-0326-y.
[17]	S. Lucks, The sum of PRPs is a secure PRF, in Advances in Cryptology - EUROCRYPT 2000(Bruges), Academic Press, 1807 (2000), 470–484. doi: 10.1007/3-540-45539-6_34.
[18]	B. Mennink and S. Neves, Encrypted davies-meyer and its dual: Towards optimal security using mirror theory, in Advances in cryptology - CRYPTO 2017, Academic Press, 10403 (2017), 556–583.
[19]	B. Mihir, K. Ted and R. Phillip, Luby-Rackoff backwards: Increasing security by making block ciphers non-invertible, in Advances in Cryptology - EUROCRYPT '98, Academic Press, 1403 (1998), 266–280. doi: 10.1007/BFb0054132.
[20]	K. Minematsu and T. Iwata, Building blockcipher from tweakable blockcipher: Extending FSE 2009 proposal, in Cryptography and Coding, Academic Press, 7089 (2011), 391–412. doi: 10.1007/978-3-642-25516-8_24.
[21]	Y. Naito, Blockcipher-based MACs: Beyond the birthday bound without message length, in ASIACRYPT 2017, Academic Press, 10626 (2017), 446–470.
[22]	J. Patarin, A proof of security in O(2n) for the Benes scheme, in Progress in Cryptology - AFRICACRYPY 2008, Academic Press, 5023 (2008), 209–220. doi: 10.1007/978-3-540-68164-9_14.
[23]	J. Patarin, Security in O(2ⁿ) for the xor of two random permutations - proof with the standard H technique, preprint, https://eprint.iacr.org/2013/368.pdf.
[24]	B. Srimanta and N. Mridul, Revisiting variable output length xor pseudorandom function, IACR Trans. Symmetric Cryptol., 2018 (2018), 314–335.
[25]	I. Tetsu, M. Bart and V. Damian, CENC is Optimally Secure, preprint, https://eprint.iacr.org/2016/1087.pdf.
[26]	I. Tetsu, New blockcipher modes of operation with beyond the birthday bound security, in Fast Software Encryption, Academic Press, 4047 (2006), 310–327. doi: 10.1007/11799313_20.
[27]	S. Victor, On fast and provably secure message authentication based on universal hashing, in Advances in Cryptology - CRYPTO '96, Academic Press, 1109 (1996), 313–328. doi: 10.1007/3-540-68697-5_24.
[28]	K. Yasuda, A new variant of PMAC: Beyond the birthday bound, in Advances in Cryptology - CRYPTO 2011, Academic Press, 6841 (2011), 596–609. doi: 10.1007/978-3-642-22792-9_34.
[29]	L. Zhang, W. L. Wu, H. Sui and P. Wang, 3kf9: Enhancing 3GPP-MAC beyond the birthday bound, in Advances in Cryptology - ASIACRYPT 2012, Academic Press, 7658 (2012), 296–312. doi: 10.1007/978-3-642-34961-4_19.

show all references

References:

[1]	M. Bellare and R. Impagliazzo, A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion, preprint, ePrint: 1999/024.ps.
[2]	M. Bellare, O. Goldreich and A. Mityagin, The power of verification queries in message authentication and authenticated encryption, preprint, ePrint: 2004/309.ps.
[3]	S. Chen and J. Steinberger, Tight Security Bounds for Key-Alternating Ciphers, in Advances in Cryptology - EUROCRYPT 2014, Academic Press, 8441 (2014), 327–350.
[4]	S. Chen, R. Lampe, J, Lee, Ya. Seurin and J. Steinberger, Minimizing the two-round even-Mansour cipher, in Advances in Cryptology - CRYPTO 2014, Academic Press, 8616 (2014), 39–56. doi: 10.1007/978-3-662-44371-2_3.
[5]	B. Cogliati and Y. Seurin, Analysis of the single-permutation encrypted Davies-Meyer construction, Des. Codes Cryptography, 86 (2018), 2703-2723. doi: 10.1007/s10623-018-0470-9.
[6]	B. Cogliati and Y. Seurin, EWCDM: An efficient, beyond-birthday secure, nonce-misuse resistant MAC, in Advances in Cryptology - CRYPTO 2016, Academic Press, 9814 (2016), 121–149. doi: 10.1007/978-3-662-53018-4_5.
[7]	W. Dai, V. T. Hoang and S. Tessaro, Information-theoretic indistinguishability via the chi-squared method, in Advances in Cryptology - CRYPTO 2017, Academic Press, 10403 (2017), 497–523.
[8]	N. Datta, A. Dutta, M. Nandi and K. Yasuda, Encrypt or decrypt? To make a single-key beyond birthday secure nonce-based MAC, in Advances in Cryptology - CRYPTO 2018, Academic Press, 10991 (2018), 631–661.
[9]	N. Datta, A. Dutta, M. Nandi, G. Paul and L. Zhang, Single key variant of PMAC_plus, IACR Trans. Symmetric Cryptol., 2017 (2017), 268–305.
[10]	N. Datta, A. Dutta, M. Nandi and G. Paul, Double-block hash-then-sum: A paradigm for constructing BBB secure PRF, IACR Trans. Symmetric Cryptol., 2018 (2018), 36–92.
[11]	A. Dutta, A. Jha and M. Nandi, Tight security analysis of ehtm MAC, IACR Trans. Symmetric Cryptol., 2017 (2017), 130–150.
[12]	B. Gilles, On computationally secure authentication tags requiring short secret shared keys, in Advances in Cryptology - CRYPTO '82, Academic Press, (1983), 79–86. doi: 10.1007/978-1-4757-0602-4_7.
[13]	O. Goldreich, S. Goldwasser and S. Micali, On the cryptographic applications of random functions, in Advances in Cryptology - CRYPTO '84, Academic Press, 196 (1984), 276–288. doi: 10.1007/3-540-39568-7_22.
[14]	P. Jacques, The "Coefficients H" technique, in Selected Areas in Cry. ptography, Academic Press, 5381 (2008), 328–345. doi: 10.1007/978-3-642-04159-4_21.
[15]	P. Jacques, Introduction to mirror theory: Analysis of systems of linear equalities and linear non equalities for cryptography, preprint, https://eprint.iacr.org/2010/287.pdf.
[16]	P. Jacques, Mirror theory and cryptography, Appl. Algebra Engrg. Commun. Comput., 28 (2017), 321-338. doi: 10.1007/s00200-017-0326-y.
[17]	S. Lucks, The sum of PRPs is a secure PRF, in Advances in Cryptology - EUROCRYPT 2000(Bruges), Academic Press, 1807 (2000), 470–484. doi: 10.1007/3-540-45539-6_34.
[18]	B. Mennink and S. Neves, Encrypted davies-meyer and its dual: Towards optimal security using mirror theory, in Advances in cryptology - CRYPTO 2017, Academic Press, 10403 (2017), 556–583.
[19]	B. Mihir, K. Ted and R. Phillip, Luby-Rackoff backwards: Increasing security by making block ciphers non-invertible, in Advances in Cryptology - EUROCRYPT '98, Academic Press, 1403 (1998), 266–280. doi: 10.1007/BFb0054132.
[20]	K. Minematsu and T. Iwata, Building blockcipher from tweakable blockcipher: Extending FSE 2009 proposal, in Cryptography and Coding, Academic Press, 7089 (2011), 391–412. doi: 10.1007/978-3-642-25516-8_24.
[21]	Y. Naito, Blockcipher-based MACs: Beyond the birthday bound without message length, in ASIACRYPT 2017, Academic Press, 10626 (2017), 446–470.
[22]	J. Patarin, A proof of security in O(2n) for the Benes scheme, in Progress in Cryptology - AFRICACRYPY 2008, Academic Press, 5023 (2008), 209–220. doi: 10.1007/978-3-540-68164-9_14.
[23]	J. Patarin, Security in O(2ⁿ) for the xor of two random permutations - proof with the standard H technique, preprint, https://eprint.iacr.org/2013/368.pdf.
[24]	B. Srimanta and N. Mridul, Revisiting variable output length xor pseudorandom function, IACR Trans. Symmetric Cryptol., 2018 (2018), 314–335.
[25]	I. Tetsu, M. Bart and V. Damian, CENC is Optimally Secure, preprint, https://eprint.iacr.org/2016/1087.pdf.
[26]	I. Tetsu, New blockcipher modes of operation with beyond the birthday bound security, in Fast Software Encryption, Academic Press, 4047 (2006), 310–327. doi: 10.1007/11799313_20.
[27]	S. Victor, On fast and provably secure message authentication based on universal hashing, in Advances in Cryptology - CRYPTO '96, Academic Press, 1109 (1996), 313–328. doi: 10.1007/3-540-68697-5_24.
[28]	K. Yasuda, A new variant of PMAC: Beyond the birthday bound, in Advances in Cryptology - CRYPTO 2011, Academic Press, 6841 (2011), 596–609. doi: 10.1007/978-3-642-22792-9_34.
[29]	L. Zhang, W. L. Wu, H. Sui and P. Wang, 3kf9: Enhancing 3GPP-MAC beyond the birthday bound, in Advances in Cryptology - ASIACRYPT 2012, Academic Press, 7658 (2012), 296–312. doi: 10.1007/978-3-642-34961-4_19.

Figure 4.1. $\textsf{DWCDM+}$ construction with an n-bit block cipher E_K and n-bit keyed hash function H_L where L = E_K(0ⁿ⁻²║10).

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.2. Birthday bound MAC attack against $\textsf{DWCDM+}$ if full nonce space is used.

Figure Options

Download full-size image

Download as PowerPoint slide

[1]	Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $ k $-error linear complexity for $ p^n $-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018
[2]	Pak Tung Ho. Prescribing $ Q $-curvature on $ S^n $ in the presence of symmetry. Communications on Pure and Applied Analysis, 2020, 19 (2) : 715-722. doi: 10.3934/cpaa.2020033
[3]	Dean Crnković, Nina Mostarac, Bernardo G. Rodrigues, Leo Storme. $ s $-PD-sets for codes from projective planes $ \mathrm{PG}(2,2^h) $, $ 5 \leq h\leq 9 $. Advances in Mathematics of Communications, 2021, 15 (3) : 423-440. doi: 10.3934/amc.2020075
[4]	Harbir Antil, Mahamadi Warma. Optimal control of the coefficient for the regional fractional $p$-Laplace equation: Approximation and convergence. Mathematical Control and Related Fields, 2019, 9 (1) : 1-38. doi: 10.3934/mcrf.2019001
[5]	Ildoo Kim. An $L_p$-Lipschitz theory for parabolic equations with time measurable pseudo-differential operators. Communications on Pure and Applied Analysis, 2018, 17 (6) : 2751-2771. doi: 10.3934/cpaa.2018130
[6]	Beom-Seok Han, Kyeong-Hun Kim, Daehan Park. A weighted Sobolev space theory for the diffusion-wave equations with time-fractional derivatives on $ C^{1} $ domains. Discrete and Continuous Dynamical Systems, 2021, 41 (7) : 3415-3445. doi: 10.3934/dcds.2021002
[7]	Melvin Faierman. Fredholm theory for an elliptic differential operator defined on $ \mathbb{R}^n $ and acting on generalized Sobolev spaces. Communications on Pure and Applied Analysis, 2020, 19 (3) : 1463-1483. doi: 10.3934/cpaa.2020074
[8]	Florin Diacu, Shuqiang Zhu. Almost all 3-body relative equilibria on $ \mathbb S^2 $ and $ \mathbb H^2 $ are inclined. Discrete and Continuous Dynamical Systems - S, 2020, 13 (4) : 1131-1143. doi: 10.3934/dcdss.2020067
[9]	Rong Zhang. Nonexistence of Positive Solutions for high-order Hardy-H$ \acute{e} $non Systems on $ \mathbb{R}^{n} $. Communications on Pure and Applied Analysis, , () : -. doi: 10.3934/cpaa.2022078
[10]	Jennifer D. Key, Bernardo G. Rodrigues. Binary codes from $ m $-ary $ n $-cubes $ Q^m_n $. Advances in Mathematics of Communications, 2021, 15 (3) : 507-524. doi: 10.3934/amc.2020079
[11]	Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2020133
[12]	Umberto De Maio, Peter I. Kogut, Gabriella Zecca. On optimal $ L^1 $-control in coefficients for quasi-linear Dirichlet boundary value problems with $ BMO $-anisotropic $ p $-Laplacian. Mathematical Control and Related Fields, 2020, 10 (4) : 827-854. doi: 10.3934/mcrf.2020021
[13]	Rakesh Nandi, Sujit Kumar Samanta, Chesoong Kim. Analysis of $ D $-$ BMAP/G/1 $ queueing system under $ N $-policy and its cost optimization. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3603-3631. doi: 10.3934/jimo.2020135
[14]	Lin Du, Yun Zhang. $\mathcal{H}_∞$ filtering for switched nonlinear systems: A state projection method. Journal of Industrial and Management Optimization, 2018, 14 (1) : 19-33. doi: 10.3934/jimo.2017035
[15]	Shengbing Deng. Construction solutions for Neumann problem with Hénon term in $ \mathbb{R}^2 $. Discrete and Continuous Dynamical Systems, 2019, 39 (4) : 2233-2253. doi: 10.3934/dcds.2019094
[16]	Lakehal Belarbi. Ricci solitons of the $ \mathbb{H}^{2} \times \mathbb{R} $ Lie group. Electronic Research Archive, 2020, 28 (1) : 157-163. doi: 10.3934/era.2020010
[17]	Chaoqian Li, Yajun Liu, Yaotang Li. Note on $ Z $-eigenvalue inclusion theorems for tensors. Journal of Industrial and Management Optimization, 2021, 17 (2) : 687-693. doi: 10.3934/jimo.2019129
[18]	Eun-Kyung Cho, Cunsheng Ding, Jong Yoon Hyun. A spectral characterisation of $ t $-designs and its applications. Advances in Mathematics of Communications, 2019, 13 (3) : 477-503. doi: 10.3934/amc.2019030
[19]	Sugata Gangopadhyay, Goutam Paul, Nishant Sinha, Pantelimon Stǎnicǎ. Generalized nonlinearity of $ S$-boxes. Advances in Mathematics of Communications, 2018, 12 (1) : 115-122. doi: 10.3934/amc.2018007
[20]	Jiahao Qiu, Jianjie Zhao. Maximal factors of order $ d $ of dynamical cubespaces. Discrete and Continuous Dynamical Systems, 2021, 41 (2) : 601-620. doi: 10.3934/dcds.2020278

2020 Impact Factor: 0.935

Tools

Metrics

Tools

Article outline

Figures and Tables

2020 Impact Factor: 0.935

Tools

Figures and Tables

2020 Impact Factor: 0.935

American Institute of Mathematical Sciences

$\textsf{DWCDM+}$: A BBB secure nonce based MAC

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

$\textsf{DWCDM+}$: A BBB secure nonce based MAC

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors