- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper proposes a threshold CKKS-based secure transformer inference framework for multi-user setting. While one can straightforwardly achieve multi-user setting via threshold CKKS, the distributed setup for ternary/sparse secret keys remains a core bottleneck. This paper’s solution is to employ two, non-colluding auxiliary servers and run a generic two-party computation protocol (GMW in the paper) to evaluate the Boolean circuit corresponding to ternary key sampling. After then, both parties lift the Boolean key shares to an RNS domain where CKKS ciphertexts live in. To achieve multi-user inference, they extend interleaved batching through a careful packing of ciphertexts with designated payload placements per party. The authors provided an implementation of their framework on anonymous GitHub/supplementary material and presented benchmark results on various numbers of parties.
Critical strengths
- The MPC-based sparse ternary key sampling looks interesting—though I did not fully verify the novelty of the method—and could be reused for other privacy-preserving computation tasks.
Critical weaknesses
-
I think the paper’s contribution lies beyond the scope of ICLR. From my understanding, the key contribution of the paper is about efficiently incorporating the SSE technique to threshold CKKS during collaborative key setup phase. No techniques specialized for “transformer” architecture were introduced, unlike other STI papers that has published/presented in ML venues. This paper’s contribution can be stated even without introducing the STI scenario, and I personally think this paper should have been submitted to security or applied cryptography venues.
-
The paper introduces somewhat strong assumption to solve the distributed key generation problem: Two non-colluding servers for key generation. However, the authors did not justify why such a setting is reasonable in practice. This gives me the impression that the authors sidestep the problem by introducing a strong assumption rather than addressing it directly. Of course, I don’t deny the GMW-based key generation is one of the possible approaches. But the rationale for adopting this approach should be more carefully treated and justified as it deviates the problem setting. After all, this approach makes the comparison with Min et al. (Table 5) unfair in terms of the underlying assumption.
Questions for authors
-
I think the core technical parts of the paper are the distributed dense/sparse secret generation (Section 4.1, 4.2) but I could not assess how novel they are due to the lack of detailed comparison on sampling methods from prior works, e.g., Min et al. Could you compare your method with Min et al.’s idea, and if possible, could you discuss about what happens if you adapt Min et al.’s approach to your GMW-based framework?
-
After reading Table 4, I have doubts about the practicality of the proposed protocol. For matrix multiplication, nearly rotation keys (e.g., Galois keys in the paper) should be prepared, i.e., at least tens or more keys should be prepared for computational efficiency of the algorithm (e.g., well-known Halevi-Shoup's algorithm with BSGS optimziation). However, even for a single rotation key, Table 4 says that the communication cost for this takes nearly 2.5GB. Hence, if we wish to multiply two matrices, which is a moderate size in typical ML applications, at least 46 rotation keys should be generated, eventually yielding GB of communication during setup. I don't think such an amount of communication is practical. Could you comment on this overhead, or any mitigations to circumvent this issue?
-
I’m not fully convinced the claimed efficiency gain reported in Table 8 is reasonable. In my opinion, there would be a trade-off between the number of tokens handled by a single ciphertext and the number of users involved. Hence, such a gain would disappear when the user’s input is long enough; so, in this case it is necessary to use all the available slots of a single ciphertext. Could you comment on how the efficiency gain observed in Table 8 is affected in such cases?
8 comments
Response to Reviewer VegE (Q1)
Q1: Our approach differs from Min et al.'s Distributed Key Generation for Efficient Threshold-CKKS in four main aspects.
1. System and security assumptions. Min et al. consider a multiparty threshold-CKKS setting that tolerates the corruption of up to participants. Their construction first establishes a temporary multiparty threshold-CKKS instance to support subsequent homomorphic secret generation. In contrast, our framework introduces two non-colluding auxiliary servers for setup and a separate inference server for multi-user secure Transformer inference (STI). The auxiliary servers construct the shared cryptographic infrastructure and subsequently distribute secret shares to the users, separating key construction from distributed key ownership.
2. Cryptographic primitives. Min et al. rely on CKKS-based homomorphic evaluation to generate secret keys, whereas our construction employs secure multiparty computation (MPC) over Boolean shares. This distinction allows our framework to perform secret sampling and selection directly in the Boolean domain, avoiding the homomorphic evaluation and bootstrapping required by CKKS-based secret generation.
3. Key-generation overhead and inference support. In the fully distributed construction of Min et al., participants contribute to the initial threshold-CKKS setup, introducing communication and noise contributions that depend on the number of participants. For independently sampled noise terms of equal variance, the aggregate noise standard deviation grows proportionally to . In contrast, the main key-generation communication in our framework occurs between two auxiliary servers, making this component independent of the number of users and limiting the corresponding noise contributions to two parties. Beyond distributed key generation, our framework provides user-input packing, multi-user ciphertext processing, and synchronized threshold decryption to support practical multi-user STI.
4. Secret-generation mechanisms. The two approaches employ fundamentally different procedures for generating dense and sparse secrets.
Dense-secret generation. Min et al. employ a temporary threshold-CKKS instance and use small-integer bootstrapping (SI-BTS) and bit extraction to obtain encrypted random values modulo 3, from which ternary dense-secret coefficients are generated. In contrast, our framework uses Boolean rejection sampling: each coefficient is sampled from two random bits, the combination is rejected, and the remaining combinations are mapped to , yielding the target ternary distribution.
Sparse-secret generation. Min et al. use SI-BTS and bit extraction to generate encrypted random bits, followed by OneHotVecGen to construct random one-hot vectors. They then compute prefix sums of these vectors, eliminate duplicate positions, and use Hamming-weight detection and an Integer Indicator Function to select a vector reaching the prescribed weight. After sign assignment, ShGen converts the resulting sparse secret into additive shares held by the participants.
In contrast, our framework directly samples candidate position encodings under Boolean MPC and applies collision filtering to obtain distinct positions. These positions are then expanded into one-hot vectors to construct a fixed-weight ternary sparse secret. By performing collision detection before one-hot expansion, our approach avoids constructing and deduplicating prefix sums of encrypted one-hot vectors.
Importantly, directly transferring Min et al.'s sparse-secret generation algorithm to a GMW-based MPC framework would require redesigning and reanalyzing its underlying operations, particularly the Integer Indicator Function, OneHotVecGen, and the prefix-sum selection procedure. Their efficiency and security properties rely on CKKS homomorphic evaluation and SIMD processing and therefore do not directly carry over to Boolean MPC.
Overall, while both approaches aim to generate distributed CKKS secrets with prescribed distributions, they differ in their security assumptions, cryptographic primitives, sampling algorithms, and scalability characteristics. Moreover, our secret construction forms part of an integrated framework specifically designed for multi-user secure Transformer inference.
We will add a subsection to Appendix A.2 to briefly clarify the differences between our approach and that of Min et al.
Response to Reviewer VegE (Q2; Q3)
Q2: A practical cryptographic infrastructure indeed requires multiple Galois keys. Under our configuration with , the multi-user STI pipeline provisions 31 Galois keys, comprising rotation keys for steps and one complex-conjugation key. Other rotation steps can be realized by composing these supported rotations.
As specified in Algorithm 7, the communication cost reported in Table 4 consists of three components: the transmission of the common random polynomial from auxiliary server to , and the exchange of their respective key-generation shares and . Since these values are represented in RNS form, with , 40 RNS limbs, and 64-bit storage per coefficient, each RNS polynomial occupies
Our configuration uses 39 limbs in and one auxiliary limb in , resulting in 39 gadget-decomposition components. Each component requires a separate set of , , and , yielding a total communication cost of MiB (2,453.67 MB) per key.
This overhead can be reduced in two ways. First, as supported by Algorithm 7, generating the common random polynomial from a public seed eliminates its full transmission, reducing the communication cost per key to approximately 1,635.78 MB. Second, when the required multiplicative depth is lower, hybrid key-switching decomposition [1] can reduce the number of decomposition components by using a larger auxiliary modulus . This provides a tradeoff between key-generation communication and the modulus requirements of key switching, subject to the overall security and depth constraints.
[1] Han, Kyoohyung, and Dohyeong Ki. "Better bootstrapping for approximate homomorphic encryption." In Cryptographers’ Track at the RSA Conference, pp. 364-390. Cham: Springer International Publishing, 2020.
We will include these discussions on Galois-key generation in the appendix.
Q3: We acknowledge the reviewer's concern. As stated in Section 6.5, “The gain comes from sharing otherwise underutilized packing capacity across independent users, rather than accelerating the HE operators or enlarging the packing capacity.” This limitation stems from the finite number of SIMD slots available in CKKS ciphertexts. For example, with , each ciphertext provides 32,768 slots. When a user's input reaches 32,767 tokens, the request occupies the entire packing capacity, including the reserved output slot, leaving no additional slots for other users. Consequently, the multi-user efficiency gains reported in Table 8 disappear in this case. To further illustrate this limitation, the following table presents theoretical efficiency estimates for varying input sequence lengths and numbers of users under .
Table: Theoretical multi-user speedup under varying input sequence lengths ().
| Input tokens | |||
|---|---|---|---|
| 127 | |||
| 1023 | |||
| 2047 | |||
| 4095 | |||
| 8191 | |||
| 16383 | |||
| 32767 |
The table above presents theoretical upper bounds on multi-user speedup under varying input sequence lengths, assuming ideal slot utilization and negligible batching overhead. With , each CKKS ciphertext provides 32,768 SIMD slots. As the input sequence length increases, fewer independent requests can share the same packing capacity, gradually reducing the achievable multi-user speedup. For 16 users, the ideal speedup remains for input lengths up to 2,047 tokens, decreases to at 4,095 tokens, and eventually reaches at 32,767 tokens. These estimates illustrate the inherent packing-capacity limitation of our framework rather than an improvement in the underlying HE operators.
Response to Reviewer VegE (W1; W2)
We thank the reviewer for these constructive comments and insightful questions. We address each concern below.
W1: We sincerely thank the reviewer for recognizing our multiparty threshold CKKS construction, and we agree that this construction has broader applicability. However, as discussed in the Introduction, our work focuses on efficient secure Transformer inference (STI) in multi-user settings, for which establishing a multi-user cryptographic infrastructure is essential. Beyond this cryptographic construction, we develop a multi-user STI framework incorporating user-input packing and synchronized threshold decryption, both of which directly support multi-user STI. Furthermore, our inference framework builds upon the interleaved batching (IB) technique introduced in MOAI, which is specifically designed to exploit the computational characteristics of Transformer architectures. Thus, our framework inherently leverages Transformer-specific properties through IB, even though these optimizations are not explicitly introduced as new architectural techniques. We therefore believe that our contributions are well aligned with the scope of ICLR.
W2: Introducing two non-colluding auxiliary servers represents a deliberate tradeoff between security and practicality. As stated in the Introduction, “Our key insight is to decouple distributed ownership of the common cryptographic infrastructure from its expensive construction.” The primary benefit is to decouple the communication-intensive secret and key generation procedures from the number of participants. By performing these procedures through communication between two auxiliary servers, our approach substantially reduces communication overhead and limits noise accumulation during key generation.
This design choice is particularly important for distributed key generation. For example, Min et al.'s approach requires all participants to contribute secret shares and noise during CKKS secret and key generation. As the reviewer noted in Q2, generating even a single key incurs substantial communication overhead under our two-server setting. In contrast, the communication cost of Min et al.'s approach scales with the number of participants, reaching approximately 40 GB per key for 16 participants.
Regarding noise accumulation, as shown in Algorithms 5–7, our construction introduces approximately twice the noise contribution of a conventional single-party construction, whereas the number of noise contributions in Min et al.'s approach increases with the number of participants. Thus, the two-server design provides a practical means of controlling both communication overhead and key-generation noise while preserving distributed key ownership.