컨텐츠 시작
학술대회/행사
초록검색
| 제출번호(No.) | 0173 |
|---|---|
| 분류(Section) | Contributed Talk |
| 분과(Session) | (CR) Cryptography (CR) |
| 발표시간(Time) | 19th-A-10:00 -- 10:20 |
| 영문제목 (Title(Eng.)) |
Fast and accurate homomorphic softmax evaluation |
| 저자(Author(s)) |
Wonhee Cho1, Guillaume Hanrot2, Taeseong Kim1, Minje Park2, Damien Stehlé2 Seoul National University1, CryptoLab Inc.2 |
| 초록본문(Abstract) | In the present paper, we propose a Homomorphic Encryption algorithm for the SoftMax function. The current, even recent solutions remain restricted, especially in large dimensions, while important applications such as Large Language Models (LLM) require computing SoftMax over large dimensional vectors. Our algorithm has strong scalability properties in terms of range and dimension while maintaining very good numerical accuracy. In terms of depth of the computation, our algorithm achieves an improvement from $O(\log^2 n)$ to $O(\log n)$ for a fixed range, where $n$ is the SoftMax dimension. Our algorithm is especially adapted to the situation where we must compute many SoftMax at the same time; for instance, in the LLM situation, the asymptotic amortized complexity per ciphertext is then $O(1 + m/N)$ for $N$ the homomorphic ring degree (thus almost constant in practice), compared to growing as $\log n$ for the state-of-the-art algorithm. The main ingredient of our algorithms is a normalize-and-square strategy, which manages to interlace the (numerically unstable) exponential computation over a large range and (very expensive) normalization, decomposing both in stabler and cheaper smaller steps. We have implemented our algorithms using the HEaaN implementation of the CKKS HE system. Our experiments demonstrate good accuracy (around 16-bit precision in the worst case, around 20 on average) and support the linear behavior in the dimension. The many-ciphertexts version allows us to compute 8192 SoftMax of dimension 256 in 486s (single-thread CPU), corresponding to an amortized 0.06s per SoftMax call. Finally, we demonstrate the scalability of our algorithm by computing one SoftMax in dimension 32768 with decent accuracy over $[-256, 0]$, in 351s. |
| 분류기호 (MSC number(s)) |
94A60 |
| 키워드(Keyword(s)) | Fully homomorphic encryption, CKKS scheme, softmax, polynomial approximation |
| 강연 형태 (Language of Session (Talk)) |
Korean |