Integer Secret Sharing Using CRT

Abstract

In this work, we revisit Yao’s [Yao82] celebrated 1982 question concerning the collaborative computation of integer functions by a set of n parties, each initially possessing only their respective inputs. The challenge is to compute an integer function without revealing individual inputs. Previous solutions typically assume f is represented by an arithmetic circuit over a finite field, limiting applicability to integer-based functions as originally proposed by Yao. Adapting F to simulate integer computations introduces practical issues: the need for known input bounds and the limitations of finite field arithmetic compared to integers. In an ongoing MPC computation, the input can be provided in any round and the input size might depend on unpredictable factors. Hence, the size of the field might be impossible to predict or must be chosen unreasonably big to simulate an integer computation of a function f. In this thesis, we introduce a novel non-linear integer secret-sharing scheme tailored specifically for integer secrets. Unlike traditional approaches, which often rely on finite fields, our scheme operates directly over integers, leveraging the Chinese Remainder Theorem to design a ramp secret-sharing scheme. This approach combines the efficiency of modular arithmetic with the inherent security properties of secret sharing. The ramp scheme enables efficient reconstruction of secrets while providing statistical privacy guarantees, ensuring robust protection of sensitive information.