publication . Conference object . 2020

An asymptotically faster version of FV supported on HPR

Jean-Claude Bajard; Julien Eynard; Paulo A.F. Martins; Leonel Sousa; Vincent Zucca;
Open Access
  • Published: 07 Jun 2020
  • Publisher: IEEE
  • Country: France
Abstract
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 di...
Persistent Identifiers
Subjects
ACM Computing Classification System: Hardware_ARITHMETICANDLOGICSTRUCTURES
free text keywords: Residue Number System, Fan-Vercauteren scheme, Homomorphic Encryption, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Discrete mathematics, Binary logarithm, Radix, Mathematics, Residue number system, Multiplication, Asymptotic complexity, Encryption, business.industry, business, Rounding, Homomorphic encryption
Funded by
EC| FutureTPM
Project
FutureTPM
Future Proofing the Connected World: A Quantum-Resistant Trusted Platform Module
  • Funder: European Commission (EC)
  • Project Code: 779391
  • Funding stream: H2020 | RIA
Communities
COVID-19

[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.

[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

[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.

[11] T. Pöppelmann and T. Güneysu, “Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware,” in Progress in Cryptology - LATINCRYPT 2012, A. Hevia and G. Neven, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 139-158. [OpenAIRE]

[12] M. R. Albrecht, R. Player, and S. Scott, “On the concrete hardness of Learning with Errors.” Journal of Mathematical Cryptology, vol. 9, pp. 169-203, October 2015.

[13] J. Bos, K. Lauter, J. Loftus, and M. Naehrig, “Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme,” in Cryptography and Coding, ser. Lecture Notes in Computer Science, M. Stam, Ed. Springer Berlin Heidelberg, 2013, vol. 8308, pp. 45-64. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-45239-0_4 m0]t + vmult + q([m]t r0 + [m0]t r + [OpenAIRE]

Abstract
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 di...
Persistent Identifiers
Subjects
ACM Computing Classification System: Hardware_ARITHMETICANDLOGICSTRUCTURES
free text keywords: Residue Number System, Fan-Vercauteren scheme, Homomorphic Encryption, [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, Discrete mathematics, Binary logarithm, Radix, Mathematics, Residue number system, Multiplication, Asymptotic complexity, Encryption, business.industry, business, Rounding, Homomorphic encryption
Funded by
EC| FutureTPM
Project
FutureTPM
Future Proofing the Connected World: A Quantum-Resistant Trusted Platform Module
  • Funder: European Commission (EC)
  • Project Code: 779391
  • Funding stream: H2020 | RIA
Communities
COVID-19

[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.

[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

[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.

[11] T. Pöppelmann and T. Güneysu, “Towards Efficient Arithmetic for Lattice-Based Cryptography on Reconfigurable Hardware,” in Progress in Cryptology - LATINCRYPT 2012, A. Hevia and G. Neven, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012, pp. 139-158. [OpenAIRE]

[12] M. R. Albrecht, R. Player, and S. Scott, “On the concrete hardness of Learning with Errors.” Journal of Mathematical Cryptology, vol. 9, pp. 169-203, October 2015.

[13] J. Bos, K. Lauter, J. Loftus, and M. Naehrig, “Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme,” in Cryptography and Coding, ser. Lecture Notes in Computer Science, M. Stam, Ed. Springer Berlin Heidelberg, 2013, vol. 8308, pp. 45-64. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-45239-0_4 m0]t + vmult + q([m]t r0 + [m0]t r + [OpenAIRE]

Any information missing or wrong?Report an Issue