Secure Montgomery Multiplication and Repeated Squares for Modular Exponentiation
This work addresses efficiency bottlenecks in cryptographic protocols for secure computation, representing an incremental improvement over existing garbling schemes.
The paper tackles the problem of efficiently computing modular exponentiation in secure multi-party computation by developing methods for Montgomery multiplication and repeated squaring in a positional base-p number system, achieving ciphertext cost evaluations for squaring operations across various large moduli.
The BMR16 circuit garbling scheme introduces gadgets that allow for ciphertext-free modular addition, while the multiplication of private inputs modulo a prime p can be done with 2(p - 1) ciphertexts as described in Malkin, Pastro, and Shelat's An algebraic approach to garbling. By using a residue number system (RNS), we can construct a circuit to handle the squaring and multiplication of inputs modulo a large N via the methods described in Hollman and Gorissen's multi-layer residue number system. We expand on the existing techniques for arithmetic modulo p to develop methods to handle arithmetic in a positional, base-p number system. We evaluate the ciphertext cost of both of these methods and compare their performance for squaring in various large moduli.