2019/10/05 by Justin Bloom, Bloom, Justin, Lalita Devadas +1
Computer Science · #Coding theory and cryptography #Cryptography and Data Security #Cryptography and Residue Arithmetic #Cryptography and Security (cs.CR) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1910.02340
openalex publication_date 2019/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.