You have already added 0 works in your ORCID record related to the merged Research product.
You have already added 0 works in your ORCID record related to the merged Research product.
An asymptotically faster version of FV supported on HPR
An asymptotically faster version of FV supported on HPR
Due to the Covid-19 crisis all around the world in 2020, the face-to-face meeting has been canceled. However, the paper selection process was completed. The accepted papers have been included in the ARITH-2020 proceedings and will soon be published on IEEE Xplore. They are also posted in the Programme section of this web site: http://arith2020.arithsymposium.org/; International audience; State-of-the-art implementations of homomorphic encryption exploit the Fan and Vercauteren (FV) scheme and the Residue Number System (RNS). While the RNS breaks down large integer arithmetic into smaller independent channels, its non-positional nature makes operations such as division and rounding hard to implement, and makes the representation of small values inefficient. In this work, we propose the application of the Hybrid Position-Residues Number System representation to the FV scheme. This is a positional representation of large radix where the digits are represented in RNS. It inherits the benefits from RNS and allows to accelerate the critical division and rounding operations while also making the representation of smaller values more compact. This directly benefits the decryp-tion and the homomorphic multiplication procedures, reducing their asymptotic complexity, in dimension n, from O(n 2 log n) to O(n log n) and from O(n 3 log n) to O(n 3), respectively and has resulted in noticeable speedups when experimentally compared to related art RNS implementations.
ACM Computing Classification System: Hardware_ARITHMETICANDLOGICSTRUCTURES
Microsoft Academic Graph classification: Homomorphic encryption Mathematics Radix Multiplication Dimension (graph theory) Residue number system Rounding Discrete mathematics Binary logarithm Division (mathematics)
arXiv: Computer Science::Hardware Architecture
Fan-Vercauteren scheme, Residue Number System, Homomorphic Encryption, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic
Fan-Vercauteren scheme, Residue Number System, Homomorphic Encryption, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic
ACM Computing Classification System: Hardware_ARITHMETICANDLOGICSTRUCTURES
Microsoft Academic Graph classification: Homomorphic encryption Mathematics Radix Multiplication Dimension (graph theory) Residue number system Rounding Discrete mathematics Binary logarithm Division (mathematics)
arXiv: Computer Science::Hardware Architecture
1312
[1] C. Gentry, “A fully homomorphic encryption scheme,” Ph.D. dissertation, Stanford, CA, USA, 2009, aAI3382729.
[2] J. Fan and F. Vercauteren, “Somewhat Practical Fully Homomorphic Encryption,” Cryptology ePrint Archive, Report 2012/144, 2012, http: //eprint.iacr.org/.
[3] L. Sousa, S. Antao, and P. Martins, “Combining residue arithmetic to design efficient cryptographic circuits and systems,” IEEE Circuits and Systems Magazine, vol. 16, no. 4, pp. 6-32, Fourthquarter 2016.
[4] J.-C. Bajard, J. Eynard, M. A. Hasan, and V. Zucca, “A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes,” in Selected Areas in Cryptography - SAC 2016, R. Avanzi and H. Heys, Eds. Cham: Springer International Publishing, 2017, pp. 423-442. [OpenAIRE]
[5] S. Halevi, Y. Polyakov, and V. Shoup, “An Improved RNS Variant of the BFV Homomorphic Encryption Scheme,” in Topics in Cryptology - CT-RSA 2019, M. Matsui, Ed. Cham: Springer International Publishing, 2019, pp. 83-105. [OpenAIRE]
[6] K. Bigou and A. Tisserand, “Hybrid Position-Residues Number System,” in ARITH: 23rd Symposium on Computer Arithmetic, J. Hormigo, S. Oberman, and N. Revol, Eds. Santa Clara, CA, United States: IEEE, Jul. 2016. [Online]. Available: https://hal.inria.fr/hal-01314232 [OpenAIRE]
[7] C. Aguilar-Melchor, J. Barrier, S. Guelton, A. Guinet, M.-O. Killijian, and T. Lepoint, Topics in Cryptology - CT-RSA 2016: The Cryptographers' Track at the RSA Conference 2016, San Francisco, CA, USA, February 29 - March 4, 2016, Proceedings. Cham: Springer International Publishing, 2016, ch. NFLlib: NTTBased Fast Lattice Library, pp. 341-356. [Online]. Available: http://dx.doi.org/10.1007/978-3-319-29485-8_20
[8] A. P. Shenoy and R. Kumaresan, “Fast Base Extension Using a Redundant Modulus in RNS,” IEEE Trans. Comput., vol. 38, no. 2, pp. 292-297, Feb. 1989. [Online]. Available: http://dx.doi.org/10.1109/12. 16508 [OpenAIRE]
[9] A. Qaisar Ahmad Al Badawi, Y. Polyakov, K. M. M. Aung, B. Veeravalli, and K. Rohloff, “Implementation and Performance Evaluation of RNS Variants of the BFV Homomorphic Encryption Scheme,” IEEE Transactions on Emerging Topics in Computing, pp. 1-1, 2019.
[10] J.-C. Bajard, J. Eynard, P. Martins, L. Sousa, and V. Zucca, “Note on the noise growth of the RNS variants of the BFV scheme,” Cryptology ePrint Archive, Report 2019/1266, 2019, https://eprint.iacr.org/2019/1266.
- 1
- 2
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Popularity provided by BIP!
- Fundação para a Ciência e a Tecnologia, I.P. (FCT)
- UIDB/50021/2020
- 6817 - DCRRNI ID
- Fundação para a Ciência e a Tecnologia, I.P. (FCT)
- SFRH/BD/103791/2014
- OE
Due to the Covid-19 crisis all around the world in 2020, the face-to-face meeting has been canceled. However, the paper selection process was completed. The accepted papers have been included in the ARITH-2020 proceedings and will soon be published on IEEE Xplore. They are also posted in the Programme section of this web site: http://arith2020.arithsymposium.org/; International audience; State-of-the-art implementations of homomorphic encryption exploit the Fan and Vercauteren (FV) scheme and the Residue Number System (RNS). While the RNS breaks down large integer arithmetic into smaller independent channels, its non-positional nature makes operations such as division and rounding hard to implement, and makes the representation of small values inefficient. In this work, we propose the application of the Hybrid Position-Residues Number System representation to the FV scheme. This is a positional representation of large radix where the digits are represented in RNS. It inherits the benefits from RNS and allows to accelerate the critical division and rounding operations while also making the representation of smaller values more compact. This directly benefits the decryp-tion and the homomorphic multiplication procedures, reducing their asymptotic complexity, in dimension n, from O(n 2 log n) to O(n log n) and from O(n 3 log n) to O(n 3), respectively and has resulted in noticeable speedups when experimentally compared to related art RNS implementations.