Encryption: The Holy Grail?

• Data encryption is an attractive option
• protects user's privacy
• enables free and open sharing
• mitigate legal and ethical issues



• Encryption scheme needs to allow computations directly on the encrypted data.
• Solution: Homomorphic Encryption

Key Idea of Homomorphic Encryption

Ring Learning with Errors

HEFT: Overview

HEFT: Concatenation

Homomorphic Concatenation

HEFT: Linear Projection

Linear Projection

Naive

Hybrid

SIMD

Linear Projection Comparison

Computational Complexity

Space Complexity

HEFT: Feature Normalization

$\ell_2$-Normalization of Vector

• ^$\dagger$: problematic operations for FHE

FHE-Aware Learning

• FHE is limited to specific operations on encrypted data.


• Normalization is not directly computable - need to approximate.


• Approximation is a source of error and hence a loss of matching performance


• We incorporate approximate normalization into our training of the projection matrix to recover performance

Loss Function

• $$Loss = \lambda \underbrace{\frac{\sum_M d(\mathbf{c}_i, \mathbf{c}_j)}{|M|}}_{ \color{orange}{Pull} } + (1-\lambda)\underbrace{\frac{\sum_{V}[m + d(\mathbf{c}_i, \mathbf{c}_j) - d(\mathbf{c}_i, \mathbf{c}_k)]_{+}}{|V|}}_{ \color{orange}{Push} }$$
• where $$d(\mathbf{c}_i, \mathbf{c}_j) = 1-P\underbrace{f(\mathbf{c}_i)}_{ \color{cyan}{approximation} } \cdot P\underbrace{f(\mathbf{c}_j)}_{ \color{cyan}{approximation} }$$ $f(\cdot)$ approximates the inverse norm of a vector.

Experimental Setup

Fusion Improves Performance, Reduces Dimensionality

Computational Complexity

Summary