Wang Zuxi (Name: Jin Jiu)

Ant Group development engineer is responsible for ant Kubernetes cluster container delivery, focusing on cluster delivery capability, delivery performance and delivery of Trace and other related fields

This article can be read at **** 5 **** minutes

— Data does not go out of the domain, available and invisible

01 back view

With the rapid development of big data and artificial intelligence, privacy data leakage and abuse happen from time to time, and privacy security has been paid more and more attention.

The country will implement the Password Law in 2020 and the Personal Information Protection Law in 2021, with higher requirements for personal privacy data and data security encryption.

Therefore, privacy computing has also been constantly mentioned and concerned, due to its excellent data protection role, making ** “data is not out of the domain, available invisible” **, limited the use of data scenarios, to prevent data leakage, and caused the industry’s hot.

Privacy computing refers to a set of technologies that realize data sharing and computing on the premise of protecting the data itself from disclosure. The value of shared data, rather than the source data itself, makes the data available and invisible.

  • Privacy computing for individual users, help to ensure the security of personal information;

  • For enterprises, privacy computing is a critical path to fulfill data protection obligations in the process of data collaboration.

  • For the government, private computing is an important support for maximizing the value of data.

Privacy computing is currently being tested in finance, medical care, telecommunications, government affairs and other fields, such as:

  • Banks and financial institutions

On the premise of not disclosing the original data of all parties, the distributed model training can effectively reduce the risks of credit and fraud.

  • medical institution

Joint modeling and data analysis can be carried out without sharing raw data, and data users can use the results of modeling operations to effectively promote the efficient utilization of data in the healthcare industry without violating the privacy of users.

The related technologies of privacy computing include multi-party secure computing (MPC), trusted Execution Environment (TEE), federated learning (FL), homomorphic encryption (HE), differential privacy (DP), zero-knowledge proof (ZKP), block chain (BC) and so on.

Each of these technologies has its advantages and disadvantages, and private computing products or platforms are built by these technologies.

Homomorphic encryption is obviously related to cryptography. Currently, the open source projects of homomorphic encryption algorithms have their own strengths, and users are more complicated to use. BabaSSL, as the basic cryptographic library, should provide a set of simple, easy to use and efficient homomorphic encryption algorithm implementation and interface, so that the upper application is more convenient and simple to use homomorphic encryption algorithm.

In addition, with the rise of privacy computing technology, Ant Group launched out-of-the-box privacy computing infrastructure combined with hardware and software, one-stop solution, that is, trusted native all-in-one machine.

As the core basic software password library in ant trusted native all-in-one machine, BabaSSL integrates the cryptography capabilities required by homomorphic encryption and other privacy computing, bringing more convenient and efficient use experience for users of trusted native all-in-one machine.

02 Homomorphic encryption

Homomorphic Encryption (HE) refers to Encryption algorithms that meet the properties of ciphertext homomorphism operation, which can be divided into additive homomorphism and multiplicative homomorphism by property:

  • Additive homomorphic

  • Multiplicative homomorphic

After homomorphic encryption, ciphertext data is obtained. After homomorphic addition or multiplication of ciphertext data, ciphertext results are obtained. After homomorphic decryption of ciphertext results, calculation results of direct addition or multiplication of original data can be obtained.

The diagram below:

According to the number of operations to meet the addition and multiplication are divided into: homomorphic encryption and semi-homomorphic encryption.

– Homomorphic encryption

(Fully Homomorphic Encryption, FHE)

1. Supports any addition and multiplication operations

2. Difficult to implement and poor performance (too large key, low operation efficiency, too large ciphertext)

3. Mainstream algorithms: Gentry, BFV, BGV, CKKS

4. Interfaces to be implemented

  • Semihomomorphic encryption

Partially Homomorphic Encryption, PHE

1. Supports only one operation of addition or multiplication, or supports a limited number of addition and multiplication operations at the same time

2. Simple principle, easy to implement, good performance

3. Mainstream algorithms: RSA, ElGamal, Paillier

4. Interfaces to be implemented:

(1) KeyGen() : Key generation algorithm used to generate the Public Key PK (Public Key), private Key SK (Secret Key), and some Public parameters PP (Public Parameter) of encrypted data.

(2)Encrypt () :Encryption algorithm: uses PK to encrypt user Data and obtain Ciphertext CT (Ciphertext).

(3)Decrypt () :Decryption algorithm, using SK to decrypt ciphertext CT data PT (Plaintext).

(4)The Add () :Ciphertext homomorphic addition, input two CT homomorphic addition operation.

(5)Sub () :Ciphertext homomorphic subtraction, input two CT homomorphic subtraction calculation.

(6)ScalaMul () or the Mul (): Ciphertext homomorphic scalar multiplication, input a CT and a scalar PT, calculate the scalar multiplication result of CT.

 

EC – ElGamal principle

ElGamal encryption algorithm is an asymmetric encryption algorithm based on Diffie-Hellman key exchange. Ec-elgamal is a kind of ECC, which is the implementation of porting ElGamal to elliptic curve. The main calculation includes: elliptic curve point addition, point subtraction, dot product, modular inverse and discrete logarithm.

Here is the principle of ec-Elgamal’s algorithm:

– Public parameters

1.G: Base point of elliptic curve

2.SK: indicates the private key.SK =d

(D is a random number between 0 and order Q of an elliptic curve)

3.PK: public key, PK=dG

Encryption –

1. Plaintext M and random number r

2. Calculate ciphertext C:

(3) The value range of plaintext M is the modulo space of modulo Order (G), but in practice M should be limited to a small number (such as 32 bits), otherwise the elliptic curve Discrete logarithm problem (ECDLP) cannot be solved.

 

– the decryption

1. Calculate rPK:

2. Calculate mG: \

3. Calculate the ECDLP of mG and obtain the plaintext M.

– Ciphertext addition and subtraction

1. Two ciphertexts:

2. Ciphertext plus:

Point addition is made to the two ECC points of the two ciphertexts respectively, which is a total of two points. The formula is as follows:

3. Ciphertext minus:

The two ECC points of the two ciphertexts are subtracted separately, so there are two point subtractions in total, and the formula is as follows:

– Ciphertext scalar multiplication

1. The cipher

2. Take the dot product of the two ECC points of the ciphertext respectively with 𝑚_2, which is a total of two dot products, and the formula is as follows:

3. The above formula is consistent with the homomorphic encryption result of plaintext M2M1:

Where r = m2r1

03 Algorithm Implementation

The interface definition

  • Object dependent interface

1. Context object: EC_ELGAMAL_CTX, which is used to store the public and private keys and other information for internal use. It is the first parameter of other interfaces of EC-Elgamal algorithm.

The interfaces are as follows:

// Create an EC_ELGAMAL_CTX object. The key is the EC_KEY object of the ECC public or private keyCopy the code

2. Decrypt table object

EC_ELGAMAL_DECRYPT_TABLE, which holds the internal information of the decrypted table. The discrete logarithm problem of elliptic curve (ECDLP) can be solved only by the method of burst force cracking, which is relatively slow, usually using baby-step, giant-step, BSGS algorithm. The general idea is to calculate all possible plaintext results in advance and save them in the hash table. The result can be obtained by a small amount of operations and hash table lookup next time, which greatly improves the decryption efficiency of ECDLP. However, the initialization of the decryption table may be slow, and the implementation of the decryption table is related to the decryption speed. After considering can open the implementation of the interface to the upper application, so here first defined a decryption table object and the default implementation.

The interfaces are as follows:

// Create EC_ELGAMAL_DECRYPT_TABLE object // When decrypt_negative is 1, the decryption table can decrypt negative numbers, and the possible negative numbers are computed and inserted into the hash during initial decryption. EC_ELGAMAL_DECRYPT_TABLE *EC_ELGAMAL_DECRYPT_TABLE_new(EC_ELGAMAL_CTX *ctx, int32_t decrypt_negative); // release the EC_ELGAMAL_DECRYPT_TABLE object void EC_ELGAMAL_DECRYPT_TABLE_free(EC_ELGAMAL_DECRYPT_TABLE *table); // Set the EC_ELGAMAL_DECRYPT_TABLE object to the context object. Void EC_ELGAMAL_CTX_set_decrypt_table(EC_ELGAMAL_CTX * CTX, EC_ELGAMAL_DECRYPT_TABLE *table);Copy the code

3. Ciphertext object:

EC_ELGAMAL_CIPHERTEXT: this object is used to store encrypted ciphertext information (two points), encryption/decryption and.

The interfaces are as follows:

EC_ELGAMAL_CIPHERTEXT *EC_ELGAMAL_CIPHERTEXT_new(EC_ELGAMAL_CTX * CTX); // Free the EC_ELGAMAL_CIPHERTEXT object void EC_ELGAMAL_CIPHERTEXT_free(EC_ELGAMAL_CIPHERTEXT *ciphertext);Copy the code

4. Encrypt/decrypt interfaces

// Encrypt, encrypt the plaintext, The result is saved to the pointer r of the EC_ELGAMAL_CIPHERTEXT object int EC_ELGAMAL_encrypt(EC_ELGAMAL_CTX * CTX, EC_ELGAMAL_CIPHERTEXT *r, int32_t plaintext); // Decrypt the ciphertext. The result is saved in int32_t pointer R int EC_ELGAMAL_decrypt(EC_ELGAMAL_CTX * CTX, INT32_t *r, EC_ELGAMAL_CIPHERTEXT *ciphertext);Copy the code

5. Ciphertext plus/minus/scalar multiplication operation interface

// ciphertext, r = c1 + c2 int EC_ELGAMAL_add(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r, EC_ELGAMAL_CIPHERTEXT *c1, EC_ELGAMAL_CIPHERTEXT *c2); // Ciphertext minus, r = c1 - c2 int EC_ELGAMAL_sub(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r, EC_ELGAMAL_CIPHERTEXT *c1, EC_ELGAMAL_CIPHERTEXT *c2); // Scalar ciphertext multiplication, r = m * c int EC_ELGAMAL_mul(EC_ELGAMAL_CTX *ctx, EC_ELGAMAL_CIPHERTEXT *r, EC_ELGAMAL_CIPHERTEXT *c, int32_t m);Copy the code

6. Encoding/decoding interface

Homomorphic encryption involves the participation of multiple parties and may require network transmission. Therefore, the ciphertext object EC_ELGAMAL_CIPHERTEXT can be encoded before being transmitted to the other party. The other party also needs to decode and obtain the EC_ELGAMAL_CIPHERTEXT object before calling other interfaces for calculation.

The interfaces are as follows:

// Encode the ciphertext and save it in the out pointer. The memory of the OUT pointer should be allocated in advance. // If out is NULL, the size of memory required for encoding is returned; Compressed indicates whether to use compressed encoding, 1 indicates compressed encoding (the encoding result is small), Size_t EC_ELGAMAL_CIPHERTEXT_encode(EC_ELGAMAL_CTX * CTX, unsigned char *out, size_t size, EC_ELGAMAL_CIPHERTEXT *ciphertext, int compressed); / / decoding, Int EC_ELGAMAL_CIPHERTEXT_decode(EC_ELGAMAL_CTX * CTX, EC_ELGAMAL_CIPHERTEXT *r, unsigned char *in, size_t size);Copy the code

The core to realize

BabaSSL is a derivative of OpenSSL and internally supports many implementations of elliptic curve algorithms.

For example, has supported international (prime256V1, SECP384R1, etc.) and state secret (SM2) most elliptic curve, naturally realized the elliptic curve point operation, public and private key generation and other basic algorithms, Therefore, the core realization of EC-ElGAMal algorithm in BabaSSL is mainly the realization of EC-Elgamal principle and the realization of ECDLP solution algorithm.

Because the code is too long, view the code laborious move GitHub:

Github.com/BabaSSL/Bab…

Specific use methods and cases, you can click to view.