Homomorphic Cryptography Protocols for Measurement Information Collection

3.1. Lattice and Ring

The following prerequisite mainly refers to the description in the survey paper [LWE]. To create a lattice, usually we can denote dots in 2D and 3D dimension. And every two and more dots can be seen as a vector. New vectors formed by a set of existing combination of vectors is called a lattice. the set of vectors which define the denoted lattice is called the "basis" of a lattice. There are a couple of long-standing hard problems when propcessing with the lattice such as shortest vector problem, closest vector problem. And the most well-known hard problem for the cryptography is called Learning with errors (LWE). Originally LWE is from the machine learning field, in a Learning with Errors (LWE) system we take a square array A^→. We can take a secret vector s^→ and calculate a value vector b^→ with following formula (the text below related to arrays, vectors, etc. are depicted with " ^→ ".).¶

• b^→ = s^→ • A^→ + e^→¶

where b^→, s^→, and e^→ are vectors and A^→ is an array. The value e^→ is a small vector of error. In general, s^→ cannot be recovered from just A^→ and b^→. therefore LWE has the same features like Diffie-Hellman [DIFFIE]¶

Moreover, to reduce the size, a common way is to replace the matrix operations with polynomial functions. Instead of array operations, b^→ = s^→ •A^→ + e^→ can turn the array and vectors into a polynomial. For example, a vector: <a1, a2, a3> can map to a polynomial a₁^2 * x^2 + a₂ * x + a₃. Therefore, the equation b^→ = s^→ • A^→ + e^→ can be all represented in polynomial functions in the same way and it can be used in the same protocol as with the standard LWE where s^→ is still the private key and bs^→ is the public key, but now they can transfer to be represented in polynomials instead of vectors and matrices. The multiplication is a standard polynomial multiply that is reduced modulo a polynomial (usually x^n + 1). This is a "ring " and therefore it is named Ring Learning with Errors (RLWE). It is worth noting the RLWE is not the same math problem of LWE, since it is mapped into polynomial fieled. It is a different hard problem.¶

3.2. Document Organization

The remainder of this document is organized as follows:¶

• Section 3 introduces the proposed homomorphic cryptography protocol.¶

• Section 3.2 introduces the detail architecture of the proposed protocols.¶

• Section 4 describes the recommended algorithm for the homomorphic cryptography protocol.¶

• Section 5 describes conditions of usage including how to combined with other protocols in PPM WG such as DAP¶

• Section 6-7 describes the analysis of performance and security characteristics¶

4.1. Overview

The overall system architecture is shown in Figure 1.¶

                      Computation
+------------------+    function     +------------------+
|                  |        f        |                  |
|    Plaintext m   |  ------------>  | Plaintext Result |
|                  |       (1)       |      f(m)        |
+------------------+                 +------------------+
         |                                     ^
         |  Homomorphic                        | Homomorphic
         |  Enc                                | Dec
         |                                     |
         |                  (2)                |
         v             Homomorphic             |
+------------------+    computing    +------------------+
|                  |    circuit      |                  |
|    Ciphertext    |       C_f       |Ciphertext Result |
|   c = E_pk(m)    |  ------------>  | c^ = E_pk(f(m))  |
|                  |                 |                  |
+------------------+                 +------------------+
     Figure 1: Overview of the Homomorphic Protocol

As a overview, the basic procedures with or without the homomorphic protocol are as follows. Without the homomorphic protocol, The server uses mode (1) to obtain the plaintext and computation functions (e.g., statistical functions include addition and multiplication) to obtain the plaintext results of computation. In this case, the client needs to allow the original data to be exposed to the server for calculation purposes, which may contain privacy information. In the case of homomorphic cryptography protocol, the server performs the privacy computation in mode (2). First, the client (or a proxy) performs homomorphic encryption E_pk(m) on plaintext, and generate homomorphic ciphertext c. Then, an aggregator gathers the ciphertext and compute the result c^ of the ciphertext through the homomorphic computing circuit C_f and transferred to the server. After that, the server obtains the plaintext calculation result through homomorphic decryption with corresponding key. The client does not need to expose the plaintext data to the aggregator and server. The server only obtains the final result and does not need to know the data of each client.¶

4.2. System Architecture

The main participants in the protocol are as follows:¶

• Server (collector): An entity that obtains computation results and needs to obtain computation results for a task (such as statistics collection, visit views, bug reports, etc.).¶

• Client (data owner): An entity that sends data to be collected. The data may contain privacy information and must be provided privacy preserving during its data being used.¶

• Aggregator: An entity aggregates data of multiple clients for privacy computation and provides the ciphertext result to the server. In some cases, it can be a network function in the server.¶

The overall interaction functions of participants are defined as follows:¶

• HE.Keygen: Generates associated keys, usually generated by a trusted third party or related key management function for the client.¶

• HE.Enc: The encryption execute entity (for example, the client) uses the homomorphic encryption key to generate the ciphertext c.¶

• HE.Dec: The decryption execute entity (for example, the collector server) uses the homomorphic decryption key to generate the plaintext result f(m).¶

• HE.Eval: The execute entity (for example, the aggregator) use multiple input ciphertexts and corresponding key to generate ciphertext computation results as the output. It includes addition HE.Eval.Add, and multiplication HE.Eval.Mul.¶

In the following sections, the asymmetric cryptography use cases are used as examples. The detailed process of homomorphic cryptography protocols and interaction protocols between participants is in the session 3.2.1 to 3.2.5.¶

                                                         +-------------------+
                         +----------------------+   +--->|pk: encryption key |
                         |   Trust 3rd party    |   |    +-------------------+
 +------------------+    | +-----------------+  |   |    +-------------------+
 |Security Parameter|----->|  Homeomorphic   |------|--->|sk: decryption key |
 +------------------+    | |  Key Generator  |  |   |    +-------------------+
                         | +-----------------+  |   |    +-------------------+
                         +----------------------+   +--->|evk: evaluation key|
                                                         +-------------------+
                     Figure 2: the process of HE.Keygen

                             +------------------------+
                             |         Client         |
                             |  +-----------------+   |
  +------------------+       |  |  Encryption Key |   |         +--------------------+
  |      Input       | ----->|  |  K_enc          |   |---------> Output Ciphertext  |
  |       m          |       |  +-----------------+   |         |      c             |
  +------------------+       |  +-----------------+   |         +--------------------+
                             |  |   Plaintext m   |   |
                             |  +-----------------+   |
                             +------------------------+

                    Figure 3: The procedure of Client Encryption

                           +------------------------+
                           |         Server         |
                           |  +-----------------+   |
+------------------+       |  |  Deccryption Key|   |         +--------------------+
|       Input      | ----->|  |  K_dec          |   |---------> Output Plaintext   |
|       c_f        |       |  +-----------------+   |         |      m             |
+------------------+       |  +-----------------+   |         +--------------------+
                           |  |  Ciphertext     |   |
                           |  |   Result c_f    |   |
                           |  +-----------------+   |
                           +------------------------+

                  Figure 4: The procedure of Server Decryption

                           +------------------------+
                           |       Aggregator       |
                           |  +-----------------+   |
+------------------+       |  |  Evaluation Key |   |         +--------------------+
|        Input     | ----->|  |  K_eval         |   |---------> Ciphertext Result  |
|   c_1,....,c_l   |       |  +-----------------+   |         |      c_f           |
+------------------+       |  +-----------------+   |         +--------------------+
                           |  |  Ciphertext     |   |
                           |  | c_1,....,c_l    |   |
                           |  +-----------------+   |
                           +------------------------+

     Figure 5: The procedure of aggregator homomorphic evaluation

4.3. Fully Homomorphic Encryption (FHE)

According to the definition of homomorphic cryptography, the ciphertext computation result after the decryption is equivalent to the plaintext direct computation result. Many encryption algorithms can satisfy the definition of homomorphic encryption (HE). However, only some algorithms satisfy fully homomorphic encryption (FHE) features. In generally, single HE algorithms only satisfy one of the operations such as addition or multiplication. A classic example is that RSA algorithm satisfies only multiplicative homomorphism, namely HE.Eval.mul_evk, which leads to limited practicability for the single HE. Because both multiplication and addition are basic operators for computation f.¶

At present, the common FHE algorithm is basically based on the lattice construction, which is based on the Learning with Errors (LWE) or Learning with Errors over Ring (RLWE) problem in lattice cryptography. It has been widely used in lattice cryptography since then. A classical fully homomorphic encryption construction is defined as follows:¶

            Unknown      Unknown     Unknown
  Known      sk           Message     Noise        Known
+--------+                 +--+         +--+         +--+
|        |     +--+        |  |         |  |         |  |
|        |     |  |        |  |         |  |         |  |
|        |     |  |        |  |         |  |         |  |
|        |     |  |        |  |         |  |         |  |
|   A    | *   |s |   +    |m |    +    |e |   =     |b |
|        |     |  |        |  |         |  |         |  |
|        |     |  |        |  |         |  |         |  |
|        |     +--+        |  |         |  |         |  |
|        |                 |  |         |  |         |  |
+--------+                 +--+         +--+         +--+
    Figure 6:  Fully Homomorphic Encryption and Noise

The ciphertext is denoted as c = (a, b^→), where b^→ = [ A^→ * s^→ + m^→ + e^→ ]_q. The random vector s^→ is used as the sk, the positive integer n stands for the dimension of the vector. q stands for the modulus of the ciphertext, and m^→ stands for the plaintext. A ∈ Z_q ^ ( N × n ) stands for a uniformly distributed random matrix, where the set estimates ( -q / 2 , q / 2 ] ∩ Z, and N > n. Noise e ∈ Chi ^ N. The noise distribution is usually Gaussian discrete.¶

4.4. Noise Control and Evaluation Key

Most existing fully homomorphic encryption algorithms usually add a random noise "e" during the encryption and the decryption. Therefore, the values of plaintext and ciphertext can only be approximately equal. Generally, it is acceptable. However, conducting the homomorphic computation on ciphertext may cause these noises to increase. When a homomorphic computation is performed with multiple ciphertexts, the noise contained in ciphertexts will be also expanded. In particular, multiplication causes a dramatic increase of the noise. When the total noise value is under the control, the decryption algorithm can restore the ciphertext back to the plaintext. But, if f contains too complex operators, once the noise range exceeds the critical value, the original plaintext cannot be recovered, resulting in homomorphic decryption failure.¶

A feasible solution was proposed in Gentry's paper [GENTRY] in 2009, called the "Bootstrapping". the Bootstrapping is a processing for ciphertext to reduce the noise. After Bootstrapping, c = (a, b^→) can be "refreshed" into a new ciphertext with lower noise. A key, named as a Bootstrapping key (BSK), needs to be used in the process. In addition to bootstrapping, there is also other types of homomorphic evaluation keys, such as key switching keys (KSK). They are all designed to reduce the expansion of noise in the process of calculation and achieves multi-layer operators. Therefore, evaluation key is needed in some operators to control noise, such as the multiplication of multiple ciphertexts.¶

6.1. Discuss the Combination with DAP

The proposed homomorphic protocol can reuse the architecture of Distributed Aggregation Protocol (DAP). The homomorphic protocols also meet the security requirement of DAP. i.e., the robustness and privacy. A malicious client cannot interfere with the reports of other clients (i.e., robustness) and the aggregator cannot acknowledge each report of each client and only know the final result (i.e., privacy). In the homomorphic cryptography protocols, neither the aggregator nor the collector (i.e., the server) can read the customer's data. To achieve this, the aggregator needs to do most of the statistics computation task and only transmits the ciphertext results to the collector server.¶

For comparison, there are pros of homomorphic protocols that DAPs cannot support at present. First, the homomorphic protocol does not require on-line computation. In most cases, the client only needs to report once using homomorphic encryption while other DAP algorithms may require multiple interactions between the clients and aggregators. Second, an aggregator performs homomorphic evaluation (i.e., computation) without requiring on-line joint validation with other aggregators. the asynchronous collection and evaluation can be supported. Third, the existing DAP protocol requires at least two aggregators for aggregation. While homomorphic protocols require minimal one aggregator.¶

But the homomorphic protocol also has limitations. First, homomorphic algorithms may need to be configured on the client side, resulting in complex algorithms. Second, depending on the content of the statistics, it may not be possible to implement multiple statistics in one round of reporting at same time, which makes the protocol unable to efficiently perform some statistics, such as building histograms, compared to other DAP algorithm e.g., Poplar1 [POPLAR]¶

10.1. Normative Reference

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

10.2. Informative References

[DIFFIE]

Diffie, W., "Diffie-Hellman Key Exchange", 1976, <https://app.ptuk.edu.ps/PTUK-stuff/UploadsMaterial/Material_151723_12140527_Section10.pdf>.

[draft-irtf-cfrg-vdaf-12]

Barnes, R., Cook, D., Patton, C., and P. Schoppmann, "Verifiable Distributed Aggregation Functions", Work in Progress, Internet-Draft, draft-irtf-cfrg-vdaf-12, 4 October 2024, <https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vdaf-12>.

[GENTRY]

Gentry, C., "Fully homomorphic encryption using ideal lattices", Proceedings of the forty-first annual ACM symposium on Theory of computing , 2009, <https://dl.acm.org/doi/abs/10.1145/1536414.1536440>.

[I-D.ietf-ppm-dap]

Geoghegan, T., Patton, C., Pitman, B., Rescorla, E., and C. A. Wood, "Distributed Aggregation Protocol for Privacy Preserving Measurement", Work in Progress, Internet-Draft, draft-ietf-ppm-dap-12, 10 October 2024, <https://datatracker.ietf.org/doc/html/draft-ietf-ppm-dap-12>.

[LWE]

Regev, O., "The Learning with Errors Problem", <https://cims.nyu.edu/~regev/papers/lwesurvey.pdf>.

[POPLAR]

Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., and Y. Ishai, "Lightweight Techniques for Private Heavy Hitters", IEEE S&P 2021 , 2021, <https://ia.cr/2021/017>.