Square Table Lookup Multiparty Computation Protocol
Zhongqi Wang, Keita Fuse, Takashi Nishide · 2022
A secure interval test protocol is a powerful and useful tool to check whether a shared secret value is within a particular interval without revealing any information about the secret value, and therefore it has important applications in secure multi-party computation, machine learning, privacy-preserving location services, and many other areas. The secure inerval test protocol can be used as a building block in larger or more complex systems. A secure table lookup protocol based on the secure interval test can be used to implement approximate calculations of certain functions. In this work, we propose a square table lookup protocol based on the secure interval test protocol, which improves the efficiency in a certain setting compared to the state-of-the-art secure table lookup protocol proposed by Morita el al. (CANS'19). We reduce the computational complexity of the table lookup protocol from$O(N)$to$O(\sqrt{N})$where$N$is the number of elements in the lookup table by changing the dimension of the lookup table from a one-dimensional array to a two-dimensional array, arranging it as a square matrix, and redesigning the procedure of secure table lookup protocol.