In this paper, we prove that the odd-even transposition sort is size-optimal and depth-optimal among stable standard sorting networks. While the best known lower bound on the size of stable sorting networks with n inputs is Ω( n log n ), the odd-even transposition sort uses Θ( n 2 ) comparators, leaving an asymptotic gap. Our result provides a partial resolution of this gap by establishing optimality within stable standard sorting networks, a restricted class of stable sorting networks in which all comparators have a consistent orientation. This result follows from a structural characterization of this class, showing that such networks can be reduced to primitive sorting networks up to the removal of redundant comparisons. The proof is elementary and relies on the 0–1 principle.

Torus fully homomorphic encryption (TFHE) is a promising solution for secure computation, offering low computational cost and simple setup requirements. A key feature of TFHE is programmable bootstrap (PBS), which enables efficient homomorphic evaluation of arbitrary functions over small domains. However, the domain size of PBS is constrained by the word size limitation of TFHE, an unavoidable restriction to ensure data security. This limitation raises scalability challenges for extending homomorphic function evaluation to larger domains. Existing approaches attempt to overcome this limitation but suffer from high computational costs. The vertical packing technique (Chillotti et al., 2020) supports function evaluations beyond the word size limitation but depends on circuit bootstrap, a computationally expensive primitive. The tree-based method (Guimarães et al., 2021) avoids using circuit bootstrap but introduces significant computational overhead, requiring O(2W) PBS calls for a W-bit domain.

Abstract Card-based cryptography allows us to securely compute arbitrary functions using a deck of physical cards. Its performance is mainly measured by the number of used cards and shuffles, and there is a line of work that aims to reduce either of them. One seminal work is the card-based garbled circuit technique by Shinagawa and Nuida (Discret Appl Math 289:248–261, 2021, https://doi.org/10.1016/j.dam.2020.10.013 ), which allows the construction of a card-based protocol for any Boolean function with a single shuffle. Their construction requires $$2n + 24g$$ 2 n + 24 g cards for an n-input Boolean function that is represented by g logical gates. In this paper, we reduce the number of cards to $$2n + 8g$$ 2 n + 8 g for arbitrary functions while keeping it working with only one shuffle. In addition, we propose two types of extensions to support numerical encoding and multi-input gates. In the extended scheme, the free-ADD technique, obtained by generalizing the free-XOR technique by Manabe and Shinagawa (Deng J, Kolesnikov V, Schwarzmann AA (eds) CANS 2023, LNCS, vol 14342. Springer, Singapore, pp 232–248, 2023, https://doi.org/10.1007/978-981-99-7563-1-11 ), is available. The free-ADD technique allows our scheme to evaluate any n-input symmetric Boolean function using $$2n^2+6n+2$$ 2 n 2 + 6 n + 2 cards.

We introduce Oblivious Parallel Stateful Computation (OPSC), a form of secure multi-party computation (MPC) tailored for stateful machine computation models emphasizing parallel execution across multiple data. OPSC enables parties to compute multiple results simultaneously in a parallel fashion, leveraging all data from current states and auxiliary inputs dynamically entered at that point. With its parallel and dynamic nature, OPSC holds promise for privacy-preserving applications in intricate decision-making scenarios involving multiple agents, such as traffic analyses, individual consumer behavior economics, and epidemiological simulations.

Decision tree evaluation is extensively used in machine learning to construct accurate classification models. Often in the cloud-assisted communication paradigm cloud servers execute remote evaluations of classification models using clients' data. In this setting, the need for private decision tree evaluation (PDTE) has emerged to guarantee no leakage of information for the client's input nor the service provider's trained model i.e., decision tree. In this paper, we propose a private decision tree evaluation protocol based on the three-party replicated secret sharing (RSS) scheme. This enables us to securely classify inputs without any leakage of the provided input or the trained decision tree model. Our protocol only requires constant rounds of communication among servers, which is useful in a network with longer delays.Ma et al. (NDSS 2021) presented a lightweight PDTE protocol with sublinear communication cost with linear round complexity in the size of the input data. This protocol works well in the low latency network such as LAN while its total execution time is unfavourably increased in the WAN setting. In contrast, Tsuchida et al. (ProvSec 2020) constructed a constant round PDTE protocol at the cost of communication complexity, which works well in the WAN setting. Although their construction still requires 25 rounds, it showed a possible direction on how to make constant round PDTE protocols. Ji et al. (IEEE Transactions on Dependable and Secure Computing) presented a simplified PDTE with constant rounds using the function secret sharing (FSS) at the cost of communication complexity. Our proposed protocol only requires five rounds among the employed three servers executing secret sharing schemes, which is comparable to previously proposed protocols that are based on garbled circuits and homomorphic encryption. To further demonstrate the efficiency of our protocol, we evaluated it using real-world classification datasets. The evaluation results indicate that our protocol provides better concrete performance in the WAN setting that has a large network delay.

In this paper, we propose memory- and round-efficient protocols for securely evaluating arithmetic primitives. We focus on secure two-party computation over the ring ℤ2k that achieves security against semi-honest adversaries and works in the pre-processing model. Our protocols rely on the unit vectorization technique introduced by Boyle et al. (TCC 2019). The unit vectorization technique provides online-optimal protocols for several fundamental operations in the pre-processing model. However, a relatively large memory cost for correlated randomness is required, which might become an obstacle in a large-scale application. In order to achieve both memory and communication efficiency, we propose a size reduction method that uses unit vectorization only for short-length inputs, and based on this, construct two-round protocols for equality test, detecting the most significant non-zero bit, detecting wrap-around, and less-than comparison. In addition, as applications of these results, we provide practically efficient protocols for integer division, integer square root, integer logarithm, and modular exponentiation.

Parallel computation is an important aspect of multi-party computation, not only in terms of improving efficiency, but also in terms of providing privacy for computation involving conditional branching based on private data. While applying multi-party computation in parallel over several sets of input data is straightforward if the partitioning of the input data into sets is publicly known, the problem becomes much more challenging when this partitioning is private. This setting is relevant to broad class of secure computations, in particular to secure graph and database analysis in which the underlying data (graph or database) is private. In this paper, we consider a general class of functions which can be expressed via the iterative evaluation of a binary associative operation, and propose efficient protocols for evaluating such functions in parallel over privately partitioned input data. Our protocols are optimal in terms of the required number of evaluations of the underlying binary operation (i.e.\ N-1 evaluations for total input size N), while simultaneously achieving a round complexity which is only logarithmic in the total size of the input data (i.e.\ O(łog N)).

In this paper we propose efficient two-party protocols for obliviously applying a (possibly random) linear group action to a data set. Our protocols capture various applications such as oblivious shuffles, circular shifts, matrix multiplications, to name just a few. A notable feature enjoyed by our protocols, is that they admit a round-optimal (more precisely, one-round) online computation phase, once an input-independent off-line computation phase has been completed. Our oblivious shuffle is the first to achieve a round-optimal online phase. The most efficient instantiations of our protocols are obtained in the so-called client-aided client-server setting, where the offline phase is run by a semi-honest input party (client) who will then distribute the generated correlated randomness to the computing parties (servers). When comparing the total running time to the previous best two-party oblivious shuffle protocol by Chase et al. (Asiacrypt 2020), our shuffle protocol in this client-aided setting is up to 105 times and 152 times faster, in the LAN and WAN setting, respectively. We additionally show how the Chase et al. protocol (which is a standard two-party protocol) can be modified to leverage the advantages of the client-aided setting, but show that, even doing so, our scheme is still two times faster in the online phase and 1.34 times faster in total on average.