Message Authentication Codes Against Related-Key Attacks Under LPN and LWE

CUI Nan; LIU Shengli

doi:10.1049/cje.2021.05.011

Volume 30 Issue 4

Jul. 2021

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2021 > 30(4): 697-703

CUI Nan and LIU Shengli, “Message Authentication Codes Against Related-Key Attacks Under LPN and LWE,” Chinese Journal of Electronics, vol. 30, no. 4, pp. 697-703, 2021, doi: 10.1049/cje.2021.05.011

Citation:

CUI Nan and LIU Shengli, “Message Authentication Codes Against Related-Key Attacks Under LPN and LWE,” Chinese Journal of Electronics, vol. 30, no. 4, pp. 697-703, 2021, doi: 10.1049/cje.2021.05.011

Citation:

PDF( 197 KB)

Message Authentication Codes Against Related-Key Attacks Under LPN and LWE

doi: 10.1049/cje.2021.05.011

CUI Nan¹,
LIU Shengli^{1,2,3
,
,}

1. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China;
2. State Key Laboratory of Cryptology, P. O. Box 5159, Beijing 100878, China;
3. Westone Cryptologic Research Center, Beijing 100070, China

Funds:

This work is supported by Guangdong Major Project of Basic and Applied Basic Research (No.2019B030302008) and the National Natural Science Foundation of China (No.61925207).

Received Date: 2018-07-02
Available Online: 2021-07-19
Publish Date: 2021-07-05

Abstract

Abstract

Message authentication code (MAC) guarantees the authenticity of messages and is one of the most important primitives in cryptography. We study related-key attacks with which the adversary is able to choose function f and observe the behavior of the MAC under the modified authenticated key f(k), and consider unforgeability of MAC under (selectively) chosen message attack with f(k). We focus on MAC schemes from the Learning parity with noise (LPN) and the Learning with errors (LWE) problem by Kiltz et al. in EUROCRYPT 2011. We first prove that the MAC schemes from LPN/ LWE can resist key-shift attacks and enlarge the key-shift function set to support a subclass of affine functions.
- Related key attack,
- Message authentication code,
- Affine functions

FullText(HTML)

References(20)

References

T. Iwata and K. Kurosawa, "Omac:One-key cbc mac", Fast Software Encryption, Lund, Sweden, pp.129-153, 2003.

M. Bellare, K. Pietrazk and P. Rogaway, "Improved security analyses for cbc macs", International Conference on Advances in Cryptology, Santa Barbara, California, USA, pp.527-545, 2005.

Y. Dodis and J.P. Steinberger, "Message authentication codes from unpredictable block ciphers", International Conference on Advances in Cryptology, Santa Barbara, CA, USA, pp.267-285, 2009.

M. Bellare, "New proofs for nmac and hmac:security without collision-resistance", International Conference on Advances in Cryptology, Santa Barbara, California, USA, pp.602-619, 2006.

M. Naor and D. Cash, "Number-theoretic constructions of efficient pseudo-random functions", J.ACM, Vol.51, No.2, pp.231-262, 2004.

M. Naor, O. Reingold and A. Rosen, "Pseudorandom functions and factoring", SIAM J.Comput., Vol.31, No.5, pp.1383-1404, 2002.

M. Bellare and D. Cash, "Pseudorandom functions and permutations provably secure against related-key attacks", International Conference on Advances in Cryptology, Santa Barbara, CA, USA, pp.666-684, 2010.

P.W. Shor, "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer", SIAM Review, Vol.41, No.2, pp.303-332, 1999.

H. Gilbert, M.J.B. Robshaw and Y. Seurin, "How to encrypt with the lpn problem", International Colloquium Automata, Languages and Programming, Reykjavik, Iceland, pp.679-690, 2008.

N.J. Hopper and M. Blum, "Secure human identification protocols", International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, pp.52-66, 2001.

J. Katz, J.S. Shin, and A.D. Smith, "Parallel and concurrent security of the HB and HB+ protocols", J. Cryptology, Vol.23, No.3, pp.402-421, 2010.

Y. Dodis, E. Kiltz, K. Pietrzak, et al., "Message authentication, revisited", International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, pp.355-374, 2012.

E. Kiltz, K. Pietrzak, D. Cash, et al., "Efficient authentication from hard learning problems", International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, pp.7-26, 2011.

D. Boneh, R.A. DeMillo, and R.J. Lipton, "On the importance of checking cryptographic protocols for faults (extended abstract)", International Conference on the Theory and Applications of Cryptographic Techniques, Konstanz, Germany, pp.37-51, 1997.

S. Han, S.L. Liu, and L. Lyu, "Super-strong RKA secure mac, PKE and SE from tag-based hash proof system", Des. Codes Cryptogr., Vol.86, No.7, pp.1411-1449, 2018.

A. Blum, M.L. Furst, M.J. Kearns, et al., "Cryptographic primitives based on hard learning problems", International Conference on Advances in Cryptology, Santa Barbara, California, USA, pp.278-291, 1993.

A. Blum, A. Kalai, and H. Wasserman, "Noise-tolerant learning, the parity problem, and the statistical query model", J.ACM, Vol.50, No.4, pp.506-519, 2003.

K. Pietrzak, "Subspace LWE", Theory of Cryptography Conference, Taormina, Sicily, Italy, pp.548-563, 2012.

D. Micciancio and O. Regev, "Worst-case to average-case reductions based on gaussian measures", Symposium on Foundations of Computer Science, Rome, Italy, pp.372-381, 2004.

C. Peikert, "Public-key cryptosystems from the worst-case shortest vector problem", Symposium on Theory of Computing, Bethesda, MD, USA, pp.333-342, 2009.

Relative Articles

Supplements(0)

Cited By

Proportional views