1 Introduction
2 Related work
2.1 HE-based applications
2.2 Relation with our previous work
2.3 HE and TEE related work
3 Preliminaries
3.1 Homomorphic encryption preliminaries
3.1.1 CKKS scheme
3.1.2 HE-based algorithm design: challenges and limitations
3.2 TEE overview
4 Manufacturing compliance scenario
4.1 Notation
4.2 Manufacturing scenario
4.3 Point cloud to mesh distance computation
Steps | Algorithm step for function d(P, T) | Type of plaintext operation | HE algorithm |
---|---|---|---|
Step 1 | Compute vector \(\hat{n}=\frac{n}{||n||}\) normal to plane \(\pi (T)\), containing T | Real number additions, multiplications, division, square root | All operations HE performed by the server Scale to avoid division and square root Compute scale value |
Step 2 | Compute the projection of P to plane \(\pi (T)\), using \(\hat{n}\) | Real number additions, multiplications | All operations HE performed by the server |
Step 3 | Compute the projection region \({\textit{Reg}}\) of plane \(\pi (T)\) using \(\hat{n}\) | Real number additions, multiplications, comparison | Operations performed by a Trusted Party |
Step 4 | Depending on region \({\textit{Reg}}\) perform Euclidean distance computations to compute d | AlReal number additions, multiplications, division, square root, “If” branching | All operations HE performed by the server Scale to avoid division and square root Compute scale value Branching (with and without leakage) |
Step 5 | Return d | Return d | Return d’ and scale value The client computes \(d=d'\)/scale |
-
when H is inside the triangle T, we compute d(P, T) as the usual Euclidean norm \({{\textit{dist}}}(P, H)\),
-
when H is not inside the triangle T, we compute d(P, T) as \({{\textit{dist}}}(P, K)\), where K is the closest point to H which is inside T.
5 Compliance check secure outsourcing
5.1 HE-based architecture
5.2 Design and setup phase
6 Communication and computation improvements
6.1 Plaintext packing strategy
-
If \(1\le \nu _1\le \frac{n}{9}\), then \(\nu _2\) CWP groups are used and \(\lceil \frac{\nu _1}{\frac{n}{9}}\rceil \) PWP groups. The total cost is \(\nu _2\cdot 12+ \lceil \frac{\nu _1}{\frac{n}{9}}\rceil \cdot 4\) plaintexts (ciphertexts).
-
If \(\nu _1 =0\), then \(\nu _2\) CWP groups are used and storage cost is \(\nu _2\cdot 12\) plaintexts (ciphertexts).
-
If \(\nu _1 >\frac{n}{9}\), then \(\nu _2+1\) CWP groups are used and the storage cost is \((\nu _2+1)\cdot 12\) plaintexts (ciphertexts).
6.2 Security/performance trade-off
Test ID | HE version | HE parameter (pol. degree) | Accuracy required |
---|---|---|---|
1 | CWP | \(n = 32{,}768\) | \(10^{-5}\) |
2 | PWP | \(n = 32{,}768\) | \(10^{-5}\) |
3 | CWP | \(n = 16{,}384\) | \(10^{-5}\) |
Test ID | Number of computations | % of errors | Mean value error | Mean value accepted results |
---|---|---|---|---|
1 | 12,426,456 | 0.00007 | \(3.21 \times 10^{-5}\) | \(2.17 \times 10^{-12}\) |
2 | 12,426,456 | 0.53915 | \(2.00 \times 10^{-4}\) | \(2.99 \times 10^{-8 }\) |
3 | 12,426,456 | 0.15894 | \(3.42 \times 10^{-3}\) | \(3.08 \times 10^{-7 }\) |
7 Experiments and evaluation
7.1 Description of the tests
7.2 Test results
7.2.1 Accuracy
7.2.2 Time performances
7.2.3 Memory resources
Test ID 1 | Test ID 2 | Test ID 3 | |
---|---|---|---|
First comparison | 26 | 8 | 9 |
Second comparison | 34 | 29 | 12 |
Third comparison | 87 | 76 | 31 |
Input pairs | 1820 | 3640 | 5460 | 7280 | 8192 | 9100 | 10,920 | 16,384 | 24,000 |
---|---|---|---|---|---|---|---|---|---|
CWP \((n = 16{,}384)\) | 12 | 12 | 12 | 12 | 12 | 24 | 24 | 24 | 36 |
CWP \((n = 32{,}768)\) | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 12 | 24 |
PWP \((n = 32{,}768)\) | 4 | 8 | 12 | 16 | 20 | 20 | 24 | 40 | 56 |