Low-Complexity Integer Divider Architecture for Homomorphic Encryption
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908461315391488 |
|---|---|
| author | Akherati, Sajjad Cai, Jiaxuan Zhang, Xinmiao |
| author_facet | Akherati, Sajjad Cai, Jiaxuan Zhang, Xinmiao |
| contents | Homomorphic encryption (HE) allows computations to be directly carried out on ciphertexts and enables privacy-preserving cloud computing. The computations on the coefficients of the polynomials involved in HE are always followed by modular reduction, and the overall complexity of ciphertext multiplication can be reduced by utilizing the quotient. Our previous design considers the cases that the dividend is an integer multiple of the modulus and the modulus is in the format of $2^w-2^u\pm1$, where $u<w/2$. In this paper, the division is generalized for larger $u$ and dividend not an integer multiple of the modulus. An algorithm is proposed to compute the quotient and vigorous mathematical proofs are provided. Moreover, efficient hardware architecture is developed for implementing the proposed algorithm. Compared to alternative division approaches that utilize the inverse of the divisor, for $w=32$, the proposed design achieves at least 9% shorter latency and 79\% area reduction for 75% possible values of $u$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11064 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Low-Complexity Integer Divider Architecture for Homomorphic Encryption Akherati, Sajjad Cai, Jiaxuan Zhang, Xinmiao Cryptography and Security Hardware Architecture Homomorphic encryption (HE) allows computations to be directly carried out on ciphertexts and enables privacy-preserving cloud computing. The computations on the coefficients of the polynomials involved in HE are always followed by modular reduction, and the overall complexity of ciphertext multiplication can be reduced by utilizing the quotient. Our previous design considers the cases that the dividend is an integer multiple of the modulus and the modulus is in the format of $2^w-2^u\pm1$, where $u<w/2$. In this paper, the division is generalized for larger $u$ and dividend not an integer multiple of the modulus. An algorithm is proposed to compute the quotient and vigorous mathematical proofs are provided. Moreover, efficient hardware architecture is developed for implementing the proposed algorithm. Compared to alternative division approaches that utilize the inverse of the divisor, for $w=32$, the proposed design achieves at least 9% shorter latency and 79\% area reduction for 75% possible values of $u$. |
| title | Low-Complexity Integer Divider Architecture for Homomorphic Encryption |
| topic | Cryptography and Security Hardware Architecture |
| url | https://arxiv.org/abs/2401.11064 |