Encrypting with LWE
The simplest way of encrypting plaintexts into ciphertexts in Concrete is via LWE encryption.
LWE stands for Learning With Errors and refers to a computational problem conjectured to be hard to solve. With LWE, every computation is performed in a modular integer ring such as where is the modulus (typically 64).
For simplicity, we use "LWE" and "LWE ciphertext" interchangeably.
Choosing strong security parameters
An LWE is composed of a vector of integers called a mask and an integer called a body. The size of the mask vector is called the dimension. To achieve a strong level of security, we need to add random gaussian noise to the body. The combination of the mask's dimension and standard deviation of the noise distribution is what we call the LWE security parameters.
Choosing wrong security parameters can lead to weak security, slow computations or insufficient precision to carry the computations.
Parameters are stored in a LWEParams
struct that takes the dimension and standard deviation as parameters. Concrete also comes with predefined sets of parameters for 80 or 128 bits of security. These parameters were secure as of September 15th 2020, and estimated using the LWE estimator.
We can see above that for a given security level, the larger the dimension is, the smaller the noise standard deviation has to be. A larger dimension will lead to more computation and larger ciphertexts, while a larger standard deviation will lead to more noisy ciphertexts and less precise messages. Hence, there is a tradeoff between performance and precision, which is inherent to any FHE program.
A good rule of thumb is to pick secure parameters with the largest possible noise that supports your program's desired precision. By not provisioning unnecessary precision, you can use a smaller mask dimension and thus get better runtime performance.
Generating an LWE secret key
Once appropriate security parameters have been chosen, we can generate a secret key that will be used to encrypt and decrypt ciphertexts. Concrete currently only implements symmetric uniformly random binary secret keys. Future versions will offer support for public-key cryptography and other key generation methods.
Creating a secret key in Concrete is as easy as using the new
function from the LWESecretKey
struct, and passing it the chosen security parameters:
Secret keys can be saved into json files with the save
method, and recovered using the load
method:
Encrypting messages
Encrypting messages can be done by either:
using the
LWE
struct's factory methodencrypt
, which takes a plaintext and a secret key as a parameter.using the
LWE
struct's factory methodencode_encrypt
, which takes a message, an encoder and a secret key. This method will encode the messages before encrypting them.
The following code shows how to create an LWE by encoding and encrypting in one step:
In FHE, it is often necessary to manipulate a vector of encrypted values, rather than a single value. Concrete has a convenience struct to simplify working with vectors of LWEs called VectorLWE
, which has the same methods as the LWE struct, but taking a vector of message as input:
Decrypting ciphertexts
Decryption turns a ciphertext into a plaintext and decodes it to yield the final message. The same secret key that was used for encryption must be used for decryption. The decrypt_decode
method exists both for LWE and VectorLWE ciphertexts:
The decrypt_decode
method performs two separate operations:
the decryption, which decrypts the ciphertext using the secret key
the decoding, which removes the noise and decodes the result back to the domain of the original message.
Putting everything together
Here is a complete example using a vector of messages:
Last updated