Using a fixed point instead of a floating point to implement the Falcon electronic signature

Abstract

The article examines the efficiency of using fixed-point arithmetic in cryptographic algorithms, particularly for key generation and digital signature formation. A modification of the key generation algorithm is proposed, allowing the use of a unified scale for all stages of cryptographic operations. The proposed approach simplifies the implementation of algorithms while maintaining high performance and eliminates the need for different data representation formats. A universal library was developed to support operations with arbitrary scales, enabling key operations such as multiplication, division, root extraction, and exponentiation. Special attention was given to the implementation of multiplication and division, which are the most resource-intensive operations. Multiplication is implemented using the Karatsuba algorithm, while division is based on bitwise long division. For operations involving secret keys, the requirement for time-independent execution was addressed to ensure cryptographic resistance. Complex multiplication was identified as the most resource-intensive operation due to its multi-step calculations, including multiple multiplication and division steps. Experimental studies on the performance of the algorithms were conducted on random data sets with overflow prevention and minimization of random factors influencing execution time. The results showed that the minimum execution time values for fixed-point arithmetic outperform the corresponding values for emulated floating-point mode. However, the average and maximum execution times for fixed-point arithmetic are inferior to those of floating-point emulation in most cases, which is attributed to an increase in reduce_error-type errors. These errors significantly impact key generation, as they are detected at the final stage of the operation, requiring its re-execution. The obtained results demonstrate the potential of using fixed-point arithmetic in cryptographic algorithms with optimal scale selection. This approach enhances computational efficiency and ensures time-independent execution of operations, which is critical for working with secret data. The presented findings can be utilized for further improvement of cryptographic algorithms and their implementation in resource-constrained environments.