Towards practical GGM-based PRF from (Module-)Learning-with-Rounding

Chitchanok Chuengsatiansup; Damien Stehle

Paper 2021/446

Towards practical GGM-based PRF from (Module-)Learning-with-Rounding

Chitchanok Chuengsatiansup and Damien Stehle

Abstract

We investigate the efficiency of a (module-)LWR-based PRF built using the GGM design. Our construction enjoys the security proof of the GGM construction and the (module-)LWR hardness assumption which is believed to be post-quantum secure. We propose GGM-based PRFs from PRGs with larger ratio of output to input. This reduces the number of PRG invocations which improves the PRF performance and reduces the security loss in the GGM security reduction. Our construction bridges the gap between practical and provably secure PRFs. We demonstrate the efficiency of our construction by providing parameters achieving at least 128-bit post-quantum security and optimized implementations utilizing AVX2 vector instructions. Our PRF requires, on average, only 39.4 cycles per output byte.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. SAC 2019
Keywords: pseudorandom function (module-)learning-with-rounding post-quantum security efficient implementation Karatsuba multiplication
Contact author(s): chitchanok chuengsatiansup @ ens-lyon org
History: 2021-04-08: received
Short URL: https://ia.cr/2021/446
License: CC BY

BibTeX

@misc{cryptoeprint:2021/446,
      author = {Chitchanok Chuengsatiansup and Damien Stehle},
      title = {Towards practical GGM-based PRF from (Module-)Learning-with-Rounding},
      howpublished = {Cryptology ePrint Archive, Paper 2021/446},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/446}},
      url = {https://eprint.iacr.org/2021/446}
}