Practical Provably-Secure Authenticated Encryption Schemes Using Lattice-based Pseudorandom Function SPRING

Document Type : Article

Authors

1 Data and Network Security Lab (DNSL), Department of Computer Engineering, Sharif University of Technology, Tehran, Iran

2 Hardware Security and Trust (HST) Lab, Department of Computer Engineering, Sharif University of Technology, Tehran, Iran

Abstract

Lattice-based cryptography has received significant attention from security practitioners in the past decade. It exhibits attractive properties, including being a major post-quantum cryptography candidate, enjoying worst-case to average-case security reductions, and being supported by efficient implementations. In this paper, we propose three practical lattice-based authenticated encryption (AE) schemes. These schemes are provably secure assuming hardness of basic lattice problems. The proposed schemes have remarkable motivations
and advantages over widely-used AEs as follows. These schemes are alternatives to current conventional and post-quantum AE schemes in the post-quantum era. Moreover, composing the proposed AEs with a lattice-based asymmetric key distribution scheme results to a hybrid encryption which depends only on one (type of) security assumption. The implementation of such hybrid encryption can make use of specific optimizations regarding, e.g., code size in software, and gate equivalent or FPGA area usage in hardware. That is because the symmetric and asymmetric algorithms have some common primitive computations. To evaluate the performance of the proposed AEs, we implement them on current Intel CPUs and benchmark them to encrypt messages of various sizes. The most efficient proposed scheme is only 12% slower than AES-256-GCM for 40-byte messages on Sandy Bridge, and 34% faster for 1500-byte messages.

Keywords

Main Subjects

References

References
1. Bernstein, D.J. \Introduction to post-quantum cryptography",
Post-Quantum Cryptography, Springer
Berlin Heidelberg, pp. 1-14 (2009).
2. Peikert, C. \A decade of lattice cryptography", Technical
Report 939, ePrint IACR (2015).
3. Shor, P.W. \Algorithms for quantum computation:
Discrete logarithms and factoring", Foundations of
Computer Science, 35th Annual Symposium on, IEEE,
pp. 124-134 (1994).
4. Proos, J. and Zalka, C. \Shor's discrete logarithm
quantum algorithm for elliptic curves", Quantum Info.
Comput., 3(4), pp. 317-344 (2003).
5. Lindner, R. and Peikert, C. \Better Key Sizes (and
Attacks) for LWE-Based Encryption", Topics in Cryptology
- CT-RSA 2011, LNCS, 6558, Springer, pp.
319-339 (2011).
A. Boorghany et al./Scientia Iranica, Transactions D: Computer Science & ... 25 (2018) 3442{3460 3459
6. Micciancio, D. and Peikert, C. \Trapdoors for lattices:
Simpler, tighter, faster, smaller", EUROCRYPT 2012,
LNCS, 7237, Springer, pp. 700-718 (2012).
7. Ducas, L., Durmus, A., Lepoint, T., and Lyubashevsky,
V. \Lattice signatures and bimodal gaussians",
CRYPTO 2013, LNCS, 8042, Springer, pp.
40-56 (2013).
8. Gottert, N., Feller, T., Schneider, M., Buchmann, J.,
and Huss, S. \On the design of hardware building
blocks for modern lattice-based encryption schemes",
Cryptographic Hardware and Embedded Systems -
CHES, 2012, LNCS, 7428, Springer, pp. 512-529
(2012).
9. Oder, T., Poppelmann, T., and Guneysu, T. \Beyond
ECDSA and RSA: lattice-based digital signatures on
constrained devices", 51st Annual Design Automation
Conference, USA DAC'14, ACM, pp. 110:1-110:6
(2014).
10. Boorghany, A. and Jalili, R. \Implementation and
comparison of lattice-based identi cation protocols on
smart cards and microcontrollers", Technical Report
078, ePrint IACR (2014).
11. Boorghany, A., Bayat Sarmadi, S., and Jalili, R.
\On constrained implementation of lattice-based cryptographic
primitives and schemes on smart cards",
ACM Transactions on Embedded Computing Systems
(TECS), 14(3), ACM, pp. 42:1-42:25 (2014).
12. Azarderakhsh, R., Liu, Z., Seo, H., and Kim, H.
\NEON PQCryto: Fast and Parallel Ring-LWE Encryption
on ARM NEON Architecture", Technical
Report 1081, ePrint IACR (2015).
13. CAESAR: Competition for Authenticated Encryption:
Security, Applicability, and Robustness. http://
competitions.cr.yp.to/caesar-call.html (2013).
14. McGrew, D. and Ho man, P., Cryptographic Algorithm
Implementation Requirements and Usage Guidance
for Encapsulating Security Payload (ESP) and
Authentication Header (AH), RFC 7321, IETF (2014).
15. McGrew, D.A. and Viega, J. \The security and Performance
of the galois/counter mode (GCM) of operation",
INDOCRYPT 2004, LNCS, 3348, Springer, pp.
343-355 (2005).
16. Whiting, D., Ferguson, N., and Housley, R. \Counter
with CBC-MAC (CCM)", RFC 3610, IETF (2003).
17. Namprempre, C., Rogaway, P., and Shrimpton, T.
\Reconsidering generic composition", EUROCRYPT
2014, LNCS, 8441, Springer Berlin Heidelberg, pp.
257-274 (2014).
18. Kurosawa, K. and Iwata, T. \TMAC: two-key CBC
MAC", Topics in Cryptology { CT-RSA 2003, LNCS,
2612, Springer Berlin Heidelberg, pp. 33-49 (2003).
19. Iwata, T. and Kurosawa, K. \OMAC: One-Key
CBC MAC", Fast Software Encryption, LNCS, 2887,
Springer Berlin Heidelberg, pp. 129-153 (2003).
20. Black, J. and Rogaway, P. \A block-cipher mode of
operation for parallelizable message authentication",
EUROCRYPT 2002, LNCS, 2332, Springer Berlin
Heidelberg, pp. 384-397 (2002).
21. Jutla, C.S. \Encryption modes with almost free message
integrity", EUROCRYPT 2001, LNCS, 2045,
Springer Berlin Heidelberg, pp. 529-544 (2001).
22. Rogaway, P., Bellare, M., and Black, J. \OCB: A
blockcipher mode of operation for ecient authenticated
encryption", ACM Trans. Inf. Syst. Secur., 6(3),
ACM, pp. 365-403 (2003).
23. Rogaway, P. \Ecient instantiations of tweakable
blockciphers and re nements to modes OCB and
PMAC", ASIACRYPT 2004, LNCS, 3329, Springer,
pp. 16-31 (2004).
24. Krovetz, T. and Rogaway, P. \The software performance
of authenticated-encryption modes", Fast
Software Encryption, LNCS, 6733, Springer, pp. 306-
327 (2011).
25. Minematsu, K. \Parallelizable rate-1 authenticated
encryption from pseudorandom functions", EUROCRYPT
2014, LNCS, 8441, Springer Berlin Heidelberg,
pp. 275-292 (2014).
26. Banerjee, A., Peikert, C., and Rosen, A. \Pseudorandom
functions and lattices", EUROCRYPT 2012,
LNCS, 7237, Springer, pp. 719-737 (2012).
27. Banerjee, A., Brenner, H., Leurent, G., Peikert, C.,
and Rosen, A. \SPRING: fast pseudorandom functions
from rounded ring products", Fast Software Encryption,
LNCS, 8540, Springer Berlin Heidelberg, pp. 38-
57 (2014).
28. Bellare, M. and Rogaway, P. \Entity authentication
and key distribution", CRYPTO 1993, pp. 232-249.
Springer (1993).
29. Bellare, M., Kilian, J., and Rogaway, P. \The security
of cipher block chaining", CRYPTO 1994, Springer-
Verlag, pp. 341-358 (1994).
30. Bellare, M., Guerin, R., and Rogaway, P. \XOR
MACs: New methods for message authentication using
nite pseudorandom functions", CRYPTO 1995,
Springer Berlin Heidelberg, pp. 15-28 (1995).
31. Grover, L.K. \A fast quantum mechanical algorithm
for database search", Twenty-Eighth Annual ACM
Symposium on Theory of Computing, USA STOC '96,
New York, NY, ACM, pp. 212-219 (1996).
32. Kaplan, M., Leurent, G., Leverrier, A., and Naya-
Plasencia, M. \Breaking symmetric cryptosystems using
quantum period nding", CRYPTO 2016, LNCS,
9815, Springer Berlin Heidelberg, pp. 207-237 (2016).
33. Kuwakado, H. and Morii, M. \Security on the
quantum-type even-mansour cipher", International
Symposium on Information Theory and Its Applications
(ISITA), pp. 312-316 (2012).
34. Peikert, C. \Lattice cryptography for the internet",
Post-Quantum Cryptography, LNCS, 8772, Springer
International Publishing, pp. 197-219 (2014).
35. Lyubashevsky, V., Peikert, C., and Regev, O. \On
ideal lattices and learning with errors over rings", J.
ACM, 60(6), pp. 43:1-43:35 (2013).
3460 A. Boorghany et al./Scientia Iranica, Transactions D: Computer Science & ... 25 (2018) 3442{3460
36. Black, J. and Rogaway, P. \CBC MACs for arbitrarylength
messages: The three-key constructions", Journal
of Cryptology, 18(2), pp. 111-131 (2005).
37. Luby, M. and Racko , C. \How to construct pseudorandom
permutations from pseudorandom functions",
SIAM J. Comput., 17(2), pp. 373-386 (1988).
38. Gligor, V.D. and Donescu, P. \Fast encryption and
authentication: XCBC encryption and XECB authentication
modes", Fast Software Encryption, LNCS,
2355, Springer Berlin Heidelberg, pp. 92-108 (2001).
39. Rogaway, P. \Authenticated-encryption with associated-
data", 9th ACM Conference on Computer and
Communications Security, USA CCS'02, New York,
NY, ACM, pp. 98-107 (2002).
40. Rogaway, P. and Shrimpton, T. \A provable-security
treatment of the key-wrap problem", EUROCRYPT
2006, LNCS, 4004, Springer Berlin Heidelberg, pp.
373-390 (2006).
41. Bellare, M., Kilian, J., and Rogaway, P. \The security
of the cipher block chaining message authentication
code", Journal of Computer and System Sciences,
61(3), pp. 362-399 (2000).
42. Iwata, T. and Kurosawa, K. \Stronger security bounds
for OMAC, TMAC, and XCBC", INDOCRYPT 2003,
LNCS, 2904, Springer Berlin Heidelberg, pp. 402-415
(2003).
43. Bellare, M. and Namprempre, C. \Authenticated encryption:
Relations among notions and analysis of the
generic composition paradigm", Journal of Cryptology,
21(4), pp. 469-491 (2008).
44. Bellare, M., Desai, A., Jokipii, E., and Rogaway, P. \A
concrete security treatment of symmetric encryption",
38th Annual Symposium on Foundations of Computer
Science, pp. 394-403 (1997).
45. Wegman, M.N. and Carter, J.L. \New hash functions
and their use in authentication and set equality",
Journal of Computer and System Sciences, 22(3), pp.
265-279 (1981).
46. Damgard, I., Pedersen, T.B., and Salvail, L. \A
quantum cipher with near optimal key-recycling",
CRYPTO 2005, Springer Berlin Heidelberg, pp. 494-
510 (2005).
47. Shoup, V. \Sequences of games: A tool for taming
complexity in security proofs", Technical Report 332,
ePrint IACR (2004).
48. Bellare, M. and Rogaway, P. \The security of triple
encryption and a framework for code-based gameplaying
proofs", EUROCRYPT 2006, LNCS, 4004,
Springer Berlin Heidelberg, pp. 409-426 (2006).

Scientia Iranica
Volume 25, Issue 6
Transactions on Computer Science & Engineering and Electrical Engineering (D)
November and December 2018
Pages 3442-3460

Files

Share

How to cite

Statistics