Scalable and privacy-preserving rectangular matrix multiplication with FHE by divide-and-conquer approach

Abstract

Treball de fi de Grau en Enginyeria Informàtica

Directora: Zaira Pindado Tost

Data privacy and security are crucial in today’s world. While encryption secures data at rest and in transit, fully homomorphic encryption (FHE) offers a solution for secure processing by enabling direct computation on encrypted data. However, FHE’s practical application is limited by significant computational overhead, especially in fundamental operations like matrix multiplication. The CKKS scheme, designed for approximate arithmetic, faces challenges with matrix multiplication due to data packing constraints and the need for expensive homomorphic rotations. This dissertation addresses the efficient homomorphic multiplication of rectangular matrices within ciphertexts. It proposes and implements a divideand-conquer strategy, contrasting with the zero-padding approach. The research benchmarks this implementation across various dimensions, offering a framework for improved homomorphic rectangular matrix multiplication.

La privadesa i la seguretat de les dades s´on crucials en el m´ on actual. El xifratge totalment homom` orfic (FHE) permet realitzar c`alculs directament sobre dades xifrades. No obstant aix` o, l’aplicaci´o pr`actica de FHE es veu limitada per una sobrec`arrega computacional significativa, especialment en operacions fonamentals com la multiplicaci´ o de matrius L’esquema CKKS, dissenyat per a l’aritm`etica aproximada, s’enfronta a desafiaments amb la multiplicaci´ o de matrius a causa de les restriccions d’empaquetament de dades i la necessitat de costoses rotacions homom`orfiques. Aquesta tesi aborda la multiplicaci´ o homom`orfica eficient de matrius rectangulars dins de CKKS. Proposa i implementa una estrat`egia de “divide and conquer”, contrastant-la amb l’enfocament de farciment amb zeros. La investigaci´ o avalua aquesta implementaci´ o en diverses dimensions, oferint un marc per a una millora en la multiplicaci´ o homom` orfica de matrius rectangulars.