We propose a secure multi-party computation (MPC) protocol that constructs a secret-shared decision tree for a given secret-shared dataset. The previous MPC-based decision tree training protocol (Abspoel et al. 2021) requires $O(2^hmn log n)$ comparisons, being exponential in the tree height $h$ and with $n$ and $m$ being the number of rows and that of attributes in the dataset, respectively. The cause of the exponential number of comparisons in $h$ is that the decision tree training algorithm is based on the divide-and-conquer paradigm, where rows are padded after each split in order to hide the number of rows in the dataset. We resolve this issue via secure data structure that enables us to compute an aggregate value for every group while hiding the grouping information. By using this data structure, we can train a decision tree without padding to rows while hiding the size of the intermediate data. We specifically describes a decision tree training protocol that requires only $O(hmn log n)$ comparisons when the input attributes are continuous and the output attribute is binary. Note that the order is now linear in the tree height $h$. To demonstrate the practicality of our protocol, we implement it in an MPC framework based on a three-party secret sharing scheme. Our implementation results show that our protocol trains a decision tree with a height of 4 in 404 seconds for a dataset of $2^{20}$ rows and 11 attributes.

We present a three-party sorting protocol secure against passive and active adversaries in the honest majority setting. The protocol can be easily combined with other secure protocols which work on shared data, and thus enable different data analysis tasks, such as private set intersection of shared data, deduplication, and the identification of heavy hitters. The new protocol computes a stable sort. It is based on radix sort and is asymptotically better than previous secure sorting protocols. It improves on previous radix sort protocols by not having to shuffle the entire length of the items after each comparison step.

Machine Learning (ML) algorithms, especially deep neural networks (DNN), have proven themselves to be extremely useful tools for data analysis, and are increasingly being deployed in systems operating on sensitive data, such as recommendation systems, banking fraud detection, and healthcare systems. This underscores the need for privacy-preserving ML (PPML) systems, and has inspired a line of research into how such systems can be constructed efficiently. However, most prior works on PPML achieve efficiency by requiring advanced ML algorithms to be simplified or substituted with approximated variants that are “MPC-friendly” before multi-party computation (MPC) techniques are applied to obtain a PPML systems. A drawback of this approach is that it requires careful fine-tuning of the combined ML and MPC algorithms, and might lead to less efficient algorithms or inferior quality ML (such as lower prediction accuracy). This is an issue for secure training of DNNs in particular, as this involves several arithmetic algorithms that are thought to be “MPCunfriendly”, namely, integer division, exponentiation, inversion, and square root extraction. In this work, we take a structurally different approach and propose a framework that allows efficient and secure evaluation of full-fledged state-of-the-art ML algorithms via secure multi-party computation. Specifically, we propose secure and efficient protocols for the above seemingly MPC-unfriendly computations (but which are essential to DNN). Our protocols are three-party protocols in the honest-majority setting, and we propose both passively secure and actively secure with abort variants. A notable feature of our protocols is that they simultaneously provide high accuracy and efficiency. This framework enables us to efficiently and securely compute modern ML algorithms such as Adam (Adaptive moment estimation) and the softmax function “as is”, without resorting to approximations. As a result, we obtain secure DNN training that outperforms state-of-the-art threeparty systems; our full training is up to 6.7 times faster than just the online phase of FALCON (Wagh et al. at PETS’21) and up to 4.2 times faster than Dalskov et al. (USENIX’21) on the standard benchmark network for secure training of DNNs. The potential advantage of our approach is even greater when considering more complex realistic networks. To demonstrate this, we perform measurements on real-world DNNs, AlexNet and VGG16, which are large networks containing millions of parameters. The performance of our framework for these networks is up to a factor of 26 ∼ 33 faster for AlexNet and 48 ∼ 51 faster for VGG16 to achieve an accuracy of 60% and 70%, respectively, when compared to FALCON. Even compared to CRYPTGPU (Tan et al. IEEE S&P’21), which is optimized for and runs on powerful GPUs, our framework achieves a factor of 2.1 and 4.1 faster performance, respectively, on these networks.

Stateful packrat parsing is an algorithm for parsing syntaxes that have context-sensitive features. It is a well-known knowledge among researchers that the running time of stateful packrat parsing is linear for real-world grammars, as demonstrated in existing studies. However, we have found the cases in real-world grammars and tools that lead its running time to become exponential.

Secret sharing (SS) has been extensively studied as both a means of secure data storage and a fundamental building block for multiparty computation (MPC). For these purposes, code‐efficiency and MPC‐suitability are required for SS but they are incomparable. Recently, a computational SS and a conversion protocol were proposed. The computational SS is code‐efficient and the conversion protocol converts shares of the computational (code‐efficient) SS into those of an MPC‐suitable SS, and it can be applied to reduce the amount of data storage while maintaining extendibility to MPC. However, this protocol is one‐way: one cannot convert the share of MPC output value. In addition, it is only passively secure. The authors propose three protocols and a new computational SS. The first protocol is the inverse of the existing protocol, that is, it converts an MPC‐suitable SS to the existing SS. The other two protocols are actively secure conversion protocols that convert shares between the new SS and an MPC‐suitable SS. The new computational SS is code‐efficient when the number of parties is small, so these two protocols are for converting between the code‐efficient SS and an MPC‐suitable SS. These two conversion protocols are actively secure in the honest majority.

Building optimal virtual networks across multiple domains is an essential technology for offering flexible network services. However, existing research is founded on an unrealistic assumption: providers will share their private information including resource costs. Providers, as well known, never actually do that so as to remain competitive. Secure multi-party computation, a computational technique based on cryptography, can be used to secure optimization, but it is too time consuming. This paper presents a novel method that can optimize virtual networks built over multiple domains efficiently without revealing any private information. Our method employs secure multi-party computation only for masking sensitive values; it can optimize virtual networks under limited information without applying any time-consuming techniques. It is solidly based on the theory of optimality and is assured of finding reasonably optimal solutions. Experiments show that our method is fast and optimal in practice, even though it conceals private information; it finds near optimal solutions in just a few minutes for large virtual networks with tens of nodes. This is the first work that can be implemented in practice for building optimal virtual networks across multiple domains.

Building optimal virtual networks across multiple domains is an essential technology to offer flexible network services. However, existing research is founded on an unrealistic assumption; providers will share their private information including resource costs. Providers, as is well known, never actually do that to remain competitive. Technically, secure multiparty computation, which is a computational technique based on the cryptography, can be used to secure optimization, but it is too time-consuming. This paper presents a novel method to optimize virtual networks built over multiple domains, with great efficiency but without revealing any private information. Our method employs secure multi-party computation but only for masking sensitive values; it can optimize virtual networks under limited information without any time-consuming technique. It is solidly based on the theory of optimality, and is assured of finding reasonably optimal solutions. Experiments show that our method is fast and optimal in practice even concealing private information; it finds nearly optimal solutions in just a few minutes for large virtual networks with tens of nodes. This is the first work that can be implemented in practice for building optimal virtual networks across multiple domains.