Square Table Lookup Multiparty Computation Protocol

• Main Authors: Wang, Zhongqi, Fuse, Keita, Nishide, Takashi
• Format: Conference Proceeding
• Language: English
• Subjects: Complex systems; Computational complexity; Conferences; Machine learning; Multi-party computation; multiparty computation; Protocols; secure interval test; secure table lookup protocol; Table lookup
• ISSN: 2832-1324
• DOI: 10.1109/CANDARW57323.2022.00048

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.