Public-key cryptography is essential for realizing a secure digital society. The award recipients proposed fundamental algorithms for implementing public-key cryptography using the residue number system (RNS), which is more suitable for parallel processing than ordinary binary representation. Their main contribution was to open a door to the new field of research called the “implementation of public-key cryptography using RNS”, by introducing an approximation in the process of RNS operation and thus invented efficient but accurate algorithms for modular reduction and comparison in RNS.

RNS is a method for representing an integer x as an n-tuple of residues, x mod m_i, where m_i is the i-th element of the RNS base set (Fig. 1(a)). Since no carry-propagation occurs between adjacent blocks, addition, subtraction, and multiplication can be divided into n independent additions, subtractions, and multiplications respectively, in regard to each modulus. If n arithmetic units are available, the processing speeds increases n times. Despite this merit, RNS had the shortcoming that it was not possible to efficiently compute division (or modular reduction) and comparison since the magnitude evaluation of an integer was difficult in RNS. Therefore, no practical applications of RNS existed before 2000.

The award recipients realized that if division and comparison algorithms were invented, RNS could be a promising candidate for the implementation of public-key cryptography that was constructed with huge integers, typically of several hundred to several thousand bits. For instance, if 32-bit moduli are chosen, a 1024-bit integer operation can be implemented for 32 layers in parallel. To overcome this difficulty, the recipients proposed a method to evaluate an integer x by a relative value of x/M, instead of the actual value of x and to obtain the approximate binary sequence of x/M, where M is a product of the base elements and represents the range of x.

(1) Efficient modular reduction algorithm

An RNS variant of a modular reduction that computes x modulo p includes an evaluation of x/M computed by Eq. (1) in Fig.1(b). Conventionally, the evaluation required a multiplier and a large circuit size that tends to be an obstacle against practical use. The award recipients optimized Eq. (1) to reduce the evaluation process to a new problem that evaluates the approximate integer part of the argument for the function Fr. The latter problem is carried out by summing a few most significant bits of each argument as shown in Eq. (2). This requires a single adder, the size of which is less than 1/10 of the conventional circuit. This algorithm was applied to the implementation of an RSA cryptosystem to develop an LSI. The recipients finally proposed an improved algorithm that achieved the minimum number of modular multiplications [1-4].

(2) Efficient comparison algorithm

A comparison of two integers is equivalent to determining the sign of the difference between the two numbers. Let us define the sign-bit of an integer x by the first bit from the decimal point of x/M. In this case, we can use the above approximation of Eq. (2) to compute the sign-bit efficiently. In most cases, the sign is determined during the evaluation of the first word of x/M. Since it is quite rare that more accuracy is required, this algorithm realizes the least resource consuming sign-detection (Table. 1). This algorithm requires the smallest memory size and realizes asymptotically optimum computational complexity, and thus solving an open issue since the beginning of engineering applications of RNS [5].

(3) Development of a new field of research

It is not rare that RNS is superior to binary concerning concurrency, processing speed, and lower power consumption. RNS is promising since it has good affinity to ASIC, FPGA, and GPU, the market of which is growing significantly [8]. The recipients’ work [1] is cited by 45% of the papers on RNS, the number of which drastically increased after the publication of the paper. Survey papers [6-8] and textbooks [9-10] cited the work as one of the most important works on RNS. The award recipients’ proposals are scalable with respect to base size n and can be adapted easily to future situations that need a larger key-size. The award recipients’ proposals are also used as a countermeasure to side-channel attacks, and were recently applied to the latest lattice-base cryptography and homomorphic cryptography [6-8].

The recipients have made significant pioneering contributions by establishing a new field of research, the implementation of cryptography using RNS. Their outstanding accomplishments are worthy of the IEICE Achievement Award.

References

1. Kawamura, S. et al.: “Cox-rower architecture for fast parallel Montgomery multiplication,” In: EUROCRYPT2000, LNCS1807, Springer (May, 2000).
2. Nozaki, H., et al.: “Implementation of RSA algorithm based on RNS Montgomery multiplication.” In: CHES 2001, LNCS2162, Springer (Sep. 2001).
3. Nozaki, H., et al.: “RNS Montgomery multiplication algorithm for duplicate processing of base transformations”, IEICE Trans. Fundamentals, Vol.E86-A, No.1, (Jan. 2003).
4. Kawamura, S., et al.: “RNS Montgomery reduction algorithms using quadratic residuosity,” Journal of Cryptographic Engineering, Vol.9, Issue 4, Springer (Nov. 2019).
5. Kawamura, S., et al.: “Efficient algorithms for sign detection in RNS using approximate reciprocals,” To appear in IEICE Trans. Vol.E104-A, No.1, (Jan. 2021)
6. D. Schoinianakis: “Residue arithmetic systems in cryptography: a survey on modern security applications,” Journal of Cryptographic Engineering, Springer, 25 (June, 2020). DOI: https://doi.org/10.1007/s13389-020-00231-w
7. J.-C. Bajard, et al.: “Montgomery reduction within the context of residue number system arithmetic”, Journal of Cryptographic Engineering, Vol.8, Issue 3, pp.189-200, Springer (Sept. 2018).
8. L. Sousa, et al.: “Combining residue arithmetic to design efficient cryptographic circuits and systems,” IEEE Circuit and Systems Magazine, Vol.16, Issue 4, pp.6-32 (Nov. 2016).
9. P.　V.　Ananda Mohan: “Residue number systems, theory and applications,” In Sect. 10.3 RNS Montgomery Multiplication and Exponentiation, pp.287-295, Springer (2016).
10. A. S. Molahosseini, et al. (Eds): “Embedded systems design with special arithmetic and number systems,” In Chapter 2 and Chapter 12, Springer, (2017).