Efficient isochronous fixed-weight sampling with applications to NTRU
Authors
Décio Luiz Gazzoni Filho, Tomás S. R. Silva, Julio López
Décio Luiz Gazzoni Filho
Universidade Estadual de Campinas (UNICAMP), Campinas, Brazil
State University of Londrina, Londrina, Brazil
decio dot gazzoni at ic dot unicamp dot br
State University of Londrina, Londrina, Brazil
decio dot gazzoni at ic dot unicamp dot br
Tomás S. R. Silva
Universidade Estadual de Campinas (UNICAMP), Campinas, Brazil
tomas at ime dot unicamp dot br
tomas at ime dot unicamp dot br
Julio López
Universidade Estadual de Campinas (UNICAMP), Campinas, Brazil
jlopez at ic dot unicamp dot br
jlopez at ic dot unicamp dot br
Abstract
We present a solution to the open problem of designing a linear-time, unbiased and timing attack-resistant shuffling algorithm for fixed-weight sampling. Although it can be implemented without timing leakages of secret data in any architecture, we illustrate with ARMv7-M and ARMv8-A implementations; for the latter, we take advantage of architectural features such as NEON and conditional instructions, which are representative of features available on architectures targeting similar systems, such as Intel. Our proposed algorithm improves asymptotically upon the current approach based on constant-time sorting networks ($O(n)$ versus $O(n \log^2 n)$), and an implementation of the new algorithm applied to NTRU is also faster in practice, by a factor of up to $6.91\ (591\%)$ on ARMv8-A cores and $12.89\ (1189\%)$ on the Cortex-M4; it also requires fewer uniform random bits. This translates into performance improvements for NTRU encapsulation, compared to state-of-the-art implementations, of up to 50% on ARMv8-A cores and 72% on the Cortex-M4, and small improvements to key generation (up to 2.7% on ARMv8-A cores and 6.1% on the Cortex-M4), with negligible impact on code size and a slight improvement in RAM usage for the Cortex-M4.
References
[AAB+22]
Carlos Aguilar-Melchor, Nicolas Aragon, Slim Bettaieb, Loïc Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Philippe Gaborit, Edoardo Persichetti, Gilles Zémor, Jurjen Bos, Arnaud Dion, Jerome Lacan, Jean-Marc Robert, and Pascal Veron. HQC. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions. 2022.
[ABB+22]
Nicolas Aragon, Paulo Barreto, Slim Bettaieb, Loic Bidoux, Olivier Blazy, Jean-Christophe Deneuville, Phillipe Gaborit, Shay Gueron, Tim Guneysu, Carlos Aguilar-Melchor, Rafael Misoczki, Edoardo Persichetti, Nicolas Sendrier, Jean-Pierre Tillich, Gilles Zémor, Valentin Vasseur, Santosh Ghosh, and Jan Richter-Brokmann. BIKE. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions. 2022.
[ABC+22]
Martin R. Albrecht, Daniel J. Bernstein, Tung Chou, Carlos Cid, Jan Gilcher, Tanja Lange, Varun Maram, Ingo von Maurich, Rafael Misoczki, Ruben Niederhagen, Kenneth G. Paterson, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, Cen Jung Tjhai, Martin Tomlinson, and Wen Wang. Classic McEliece. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/round-4-submissions. 2022.
[Ajt96]
Miklós Ajtai. Generating Hard Instances of Lattice Problems (Extended Abstract). In 28th Annual ACM Symposium on Theory of Computing, pages 99–108. May 1996. ACM Press. DOI: 10.1145/237814.237838
[{Ame}17]
American National Standards Institute. Lattice-Based Polynomial Public Key Establishment Algorithm for the Financial Services Industry.. ASC X9.98-2010 (R2017). 2017.
[ARM]
[{ARM}15]
ARM Limited. Cortex®-A72 Software Optimization Guide. 2015.
[{ARM}23]
ARM Limited. Arm® Architecture Reference Manual for A-profile architecture. 2023.
[Bat68]
K. E. Batcher. Sorting Networks and Their Applications. In Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference, pages 307–314, New York, NY, USA. 1968. Association for Computing Machinery. DOI: 10.1145/1468075.1468121
[BBC+20]
Daniel J. Bernstein, Billy Bob Brumley, Ming-Shing Chen, Chitchanok Chuengsatiansup, Tanja Lange, Adrian Marotzke, Bo-Yuan Peng, Nicola Tuveri, Christine van Vredendaal, and Bo-Yin Yang. NTRU Prime. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
[BBHL18]
Axel Bacher, Olivier Bodini, Alexandros Hollender, and Jérémie O. Lumbroso. MergeShuffle: a very fast, parallel random permutation algorithm. In Luca Ferrari and Malvina Vamvakari, editors, Proceedings of the 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures, GASCom 2018, Athens, Greece, June 18-20, 2018, volume 2113 of CEUR Workshop Proceedings, pages 43–52, Aachen, Germany. 2018. CEUR-WS.org.
[BBHT17]
Axel Bacher, Olivier Bodini, Hsien-Kuei Hwang, and Tsung-Hsi Tsai. Generating Random Permutations by Coin Tossing: Classical Algorithms, New Analysis, and Modern Implementation. ACM Trans. Algorithms, 13(2), February 2017. DOI: 10.1145/3009909
[BCC+23]
Gustavo Banegas, Kévin Carrier, André Chailloux, Alain Couvreur, Thomas Debris-Alazard, Philippe Gaborit, Pierre Karpman, Johanna Loyer, Ruben Niederhagen, Nicolas Sendrier, Benjamin Smith, and Jean-Pierre Tillich. Wave. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures. 2023.
[BCD+16]
Joppe W. Bos, Craig Costello, Léo Ducas, Ilya Mironov, Michael Naehrig, Valeria Nikolaenko, Ananth Raghunathan, and Douglas Stebila. Frodo: Take off the Ring! Practical, Quantum-Secure Key Exchange from LWE. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016: 23rd Conference on Computer and Communications Security, pages 1006–1018. October 2016. ACM Press. DOI: 10.1145/2976749.2978425
[BCLv17]
Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, and Christine van Vredendaal. NTRU Prime: Reducing Attack Surface at Low Cost. In Carlisle Adams and Jan Camenisch, editors, SAC 2017: 24th Annual International Workshop on Selected Areas in Cryptography, volume 10719 of Lecture Notes in Computer Science, pages 235–260. August 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-72565-9_12
[BCLv19]
Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange, and Christine van Vredendaal. NTRU Prime. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-2-submissions. 2019.
[BCS13]
Daniel J. Bernstein, Tung Chou, and Peter Schwabe. McBits: Fast Constant-Time Code-Based Cryptography. In Guido Bertoni and Jean-Sébastien Coron, editors, Cryptographic Hardware and Embedded Systems – CHES 2013, volume 8086 of Lecture Notes in Computer Science, pages 250–272. August 2013. Springer, Heidelberg. DOI: 10.1007/978-3-642-40349-1_15
[Ber04]
Daniel J. Bernstein. Cache-timing attacks on AES. http://cr.yp.to/papers.html#cachetiming. 2004.
[Ber18]
Daniel J. Bernstein. Divergence bounds for random fixed-weight vectors obtained by sorting. April 2018.
[Ber19]
Daniel J. Bernstein. djbsort. https://sorting.cr.yp.to. 2019.
[CCHY24]
Han-Ting Chen, Yi-Hua Chung, Vincent Hwang, and Bo-Yin Yang. Algorithmic Views of Vectorized Polynomial Multipliers – NTRU. In Anupam Chattopadhyay, Shivam Bhasin, Stjepan Picek, and Chester Rebeiro, editors, Progress in Cryptology – INDOCRYPT 2023, pages 177–196, Cham. 2024. Springer Nature Switzerland. DOI: 10.1007/978-3-031-56235-8_9
[CDH+20]
Cong Chen, Oussama Danba, Jeffrey Hoffstein, Andreas Hulsing, Joost Rijneveld, John M. Schanck, Peter Schwabe, William Whyte, Zhenfei Zhang, Tsunekazu Saito, Takashi Yamakawa, and Keita Xagawa. NTRU. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
[CWS+24]
Boru Chen, Yingchen Wang, Pradyumna Shome, Christopher W. Fletcher, David Kohlbrenner, Riccardo Paccagnella, and Daniel Genkin. GoFetch: Breaking Constant-Time Cryptographic Implementations Using Data Memory-Dependent Prefetchers. In USENIX Security. 2024.
[Dan19]
Oussama Danba. Optimizing NTRU using AVX2. Master's thesis, Radboud University, 2019.
[dG15]
Wouter de Groot. A Performance Study of X25519 on Cortex-M3 and M4. Master's thesis, Eindhoven University of Technology, 2015.
[Dir19]
Rhonda Dirvin. Next-generation Armv8.1-M architecture: Delivering enhanced machine learning and signal processing for the smallest embedded devices. https://www.arm.com/company/news/2019/02/next-generation-armv8-1-m-architecture. 2019.
[Dur64]
Richard Durstenfeld. Algorithm 235: Random Permutation. Commun. ACM, 7(7):420, July 1964. DOI: 10.1145/364520.364540
[Fog22]
Agner Fog. The microarchitecture of Intel, AMD, and VIA CPUs. https://www.agner.org/optimize/microarchitecture.pdf. 2022.
[FY38]
R. A. Fisher and F. Yates. Statistical tables for biological, agricultural and medical research. Oliver & Boyd, Oxford, England, 3rd edition. 1938.
[GFBL24]
Décio Luiz Gazzoni Filho, Guilherme Brandão, and Julio López. Fast polynomial multiplication using matrix multiplication accelerators with applications to NTRU on Apple M1/M3 SoCs. IACR Communications in Cryptology, 1(1), 2024. DOI: 10.62056/a3txommol
[GHJ+22]
Qian Guo, Clemens Hlauschek, Thomas Johansson, Norman Lahr, Alexander Nilsson, and Robin Leander Schröder. Don't Reject This: Key-Recovery Timing Attacks Due to Rejection-Sampling in HQC and BIKE. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(3):223–263, 2022. DOI: 10.46586/tches.v2022.i3.223-263
[Gro96]
Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pages 212–219, New York, NY, USA. 1996. Association for Computing Machinery.
[GS23]
Garrett Gu and Hovav Shacham. Constant-Time Wasmtime, for Real This Time: End-to-End Verified Zero-Overhead Constant-Time Programming for the Web and Beyond. 2023.
[HPS96]
Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. NTRU: a new high speed public key cryptosystem. https://web.securityinnovation.com/hubfs/files/ntru-orig.pdf. CRYPTO '96 rump session. 1996.
[HRSS17]
Andreas Hülsing, Joost Rijneveld, John M. Schanck, and Peter Schwabe. High-Speed Key Encapsulation from NTRU. In Wieland Fischer and Naofumi Homma, editors, Cryptographic Hardware and Embedded Systems – CHES 2017, volume 10529 of Lecture Notes in Computer Science, pages 232–252. September 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-66787-4_12
[{Ins}09]
Institute of Electrical and Electronics Engineers. IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices. IEEE Std 1363.1-2008. 2009.
[{Int}23a]
Intel Corporation. Data Operand Independent Timing Instruction Set Architecture (ISA) Guidance. 2023.
[{Int}23b]
Intel Corporation. Data Operand Independent Timing Instructions. 2023.
[{Int}23c]
International Organization for Standardization. FrodoKEM: Learning With Errors Key Encapsulation Preliminary Draft Standard. 2023.
[Joh22]
Dougall Johnson. Apple M1 Microarchitecture Research. https://dougallj.github.io/applecpu/firestorm.html. 2022.
[Knu97]
Donald E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley, Boston, Third edition. 1997.
[Knu98]
Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley Longman Publishing Co., Inc., USA, 2nd edition. 1998.
[Koc96]
Paul C. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Neal Koblitz, editor, Advances in Cryptology – CRYPTO'96, volume 1109 of Lecture Notes in Computer Science, pages 104–113. August 1996. Springer, Heidelberg. DOI: 10.1007/3-540-68697-5_9
[KRSS19]
Matthias J. Kannwischer, Joost Rijneveld, Peter Schwabe, and Ko Stoffelen. pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4. Workshop Record of the Second PQC Standardization Conference. 2019.
[Lam88]
M. Lam. Software Pipelining: An Effective Scheduling Technique for VLIW Machines. SIGPLAN Not., 23(7):318–328, June 1988. DOI: 10.1145/960116.54022
[Lem19]
Daniel Lemire. Fast Random Integer Generation in an Interval. ACM Trans. Model. Comput. Simul., 29(1), January 2019. DOI: 10.1145/3230636
[MG02]
Daniele Micciancio and Shafi Goldwasser. Complexity of Lattice Problems: A Cryptographic Perspective, volume 671 of The Springer International Series in Engineering and Computer Science. The Springer International Series in Engineering and Computer Science. Springer, New York, NY, First edition. 2002. DOI: 10.1007/978-1-4615-0897-7
[{Nat}17]
National Institute of Standards and Technology. Post-Quantum Cryptography Standardization: Call for Proposals Announcement. https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization. 2017.
[NG21]
Duc Tri Nguyen and Kris Gaj. Fast NEON-Based Multiplication for Lattice-Based NIST Post-quantum Cryptography Finalists. In Jung Hee Cheon and Jean-Pierre Tillich, editors, Post-Quantum Cryptography - 12th International Workshop, PQCrypto 2021, pages 234–254. 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-81293-5_13
[Por18]
Thomas Pornin. Constant-Time Multiplication. https://www.bearssl.org/ctmul.html. 2018.
[Rao61]
C. Radhakrishna Rao. Generation of Random Permutations of Given Number of Elements Using Random Sampling Numbers. Sankhyā: The Indian Journal of Statistics, Series A (1961-2002), 23(3):305–307, 1961.
[San62]
Martin Sandelius. A Simple Randomization Procedure. Journal of the Royal Statistical Society. Series B (Methodological), 24(2):472–481, 1962.
[Sen21]
Nicolas Sendrier. Secure Sampling of Constant-Weight Words – Application to BIKE. https://eprint.iacr.org/2021/1631. Cryptology ePrint Archive, Report 2021/1631. 2021.
[Sho97]
Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput., 26(5):1484–1509, October 1997. DOI: 10.1137/S0097539795293172
[TSS+03]
Yukiyasu Tsunoo, Teruo Saito, Tomoyasu Suzaki, Maki Shigeri, and Hiroshi Miyauchi. Cryptanalysis of DES Implemented on Computers with Cache. In Colin D. Walter, Çetin Kaya Koç, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems – CHES 2003, volume 2779 of Lecture Notes in Computer Science, pages 62–76. September 2003. Springer, Heidelberg. DOI: 10.1007/978-3-540-45238-6_6
[TTMM02]
Yukiyasu Tsunoo, Etsuko Tsujihara, Kazuhiko Minematsu, and Hiroshi Miyauchi. Cryptanalysis of Block Ciphers Implemented on Computers with Cache. In Proceedings of the International Symposium on Information Theory and Its Applications, ISITA 2002, pages 803–806. 2002.
[War12]
Henry S. Warren. Hacker's Delight. Addison-Wesley Professional, 2nd edition. 2012.
PDF
History
Submitted: 2024-04-09
Accepted: 2024-06-03
Published: 2024-07-08
Accepted: 2024-06-03
Published: 2024-07-08
How to cite
Décio Luiz Gazzoni Filho, Tomás S. R. Silva, and Julio López, Efficient isochronous fixed-weight sampling with applications to NTRU. IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/a6n59qgxq.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.