# Approximating Functions Using Polynomials: Chebyshev Approximation in Homomorphic Encryption

--

Like it or not, we are moving to a foundation of cybersecurity which moves us away from our traditional public key methods into a world where we operate on polynomials. These methods will allow us to implement homomorphic encryption and where we can process encrypted data.

Overall, with polynomials, we convert our binary values into a polynomial, such as:

101101 -> x⁵+x³+x²+1

Our plaintext and ciphertext are then represented as polynomial values, and where we can add, substract, multiply and divide polynomials. For example,

(x³+1) + (x²) = x³+x²+1

and:

(x³+1).(x²) = x⁵+x²

So, how can we implement functions such as mathematical functions with homomorphic encryption? Well, we can use Chebyshev polynomials to approximate a mathematical function to a polynomial.

## Approximation theory

With approximation theory, we aim to determine an approximate method for a function f(x). It was Pafnuty Lvovich Chebyshev who defined a method of finding a polynomial p(x) that is approximate for f(x). Overall, a polynomial takes the form form of:

p(x)=a_n.x^n+a_{n−1}.x^{n−1}+a_1.x+a_0

and where a0…an are the coefficients of the powers, and n is the maximum power of the polynomial. Chebyshev published his work in 1853 as ‘Theorie des mecanismes, connus sous le nom de parall´elogrammes”.

His problem statement was “to determine the deviations which one has to add to get an approximated value for a function f, given by its expansion in powers of x−a, if one wants to minimise the maximum of these errors between x = a − h and x = a + h, h being an arbitrarily small quantity”

Let’s find the polynomial that finds the magnitude of x: f(x)=|x| for an interval of -1 to 1. For this, we can use:

If we try x=0.5, we get:

p(0.5) = 15/16.0.5²+3/16= 0.421875

and for x=-0.5, we get:

p(-0.5)=15/16.(-0.5)²+3/16= 0.421875

Mathematically we can prove that the maximum error will be 0.1021.

Overall, we can use a Chebyshev polynomial of degree n by T_n(x) as:

Tn(x) = cos(n arccos(x))

For n=0, we get:

T0(x) = cos(0 arccos(x)) = 1

For n=1, we get:

T1(x) = cos (1. arrcos(x)) = x

The first 11 Chebyshev polynomial are:

## Homomorphic encryption of an approximate method using Chebyshev approximation

We can implement homomorphic encryption with floating point values using CKKS. In this case we will evaluate arbitrary smooth functions for CKKS and using Chebyshev approximation. This method involves the approximation of a smooth function using polynomials. In this case, we will implement four logarithm functions log10(), log2(), loge(), and e^x.

With this, we can implement the processing of the ciphertext with:

`Ciphertext result;        if (opt==0) {         result = cc->EvalChebyshevFunction([](double x) -> double { return std::log10(x); }, ciphertext, lowerBound, upperBound, polyDegree);        std::cout <<" x    log10(x)\n----------" << std::endl;    }   else if (opt==1) {       result = cc->EvalChebyshevFunction([](double x) -> double { return std::log2(x); }, ciphertext, lowerBound, upperBound, polyDegree);     std::cout <<" x    log2(x)\n----------" << std::endl;   }   else if (opt==2) {       result = cc->EvalChebyshevFunction([](double x) -> double { return std::log(x); }, ciphertext, lowerBound, upperBound, polyDegree);       std::cout <<" x    ln(x)\n----------" << std::endl;   }      else if (opt==3) {       result = cc->EvalChebyshevFunction([](double x) -> double { return std::exp(x); }, ciphertext, lowerBound, upperBound, polyDegree);       std::cout <<" x    exp(x)\n----------" << std::endl;   } `

The full coding is [here]:

`#include <openfhe.h>using namespace lbcrypto;using namespace std;#include <iostream>#include <sstream>#include <cstdint>int main(int argc, char *argv[]) {    int maxval=10;    int opt=1;    if (argc>1) {     std::istringstream iss(argv[1]);     iss >> maxval; }    if (argc>2) {     std::istringstream iss(argv[2]);     iss >> opt; }     std::cout << "Logarithm evaluation" << std::endl;    CCParams<CryptoContextCKKSRNS> parameters;    parameters.SetSecurityLevel(HEStd_NotSet);    parameters.SetRingDim(1024);    usint scalingModSize = 50;    usint firstModSize   = 60;    parameters.SetScalingModSize(scalingModSize);    parameters.SetFirstModSize(firstModSize);    uint32_t polyDegree = 50;    uint32_t multDepth = 7; // See table    parameters.SetMultiplicativeDepth(multDepth);    CryptoContext<DCRTPoly> cc = GenCryptoContext(parameters);    cc->Enable(PKE);    cc->Enable(KEYSWITCH);    cc->Enable(LEVELEDSHE);    cc->Enable(ADVANCEDSHE); // Needed for  Chebyshev approximation.    auto keyPair = cc->KeyGen();    cc->EvalMultKeyGen(keyPair.secretKey); // Multiple keys required for Chebyshev approximations     std::vector<double> input;     for (int i=1;i<=maxval;i++) {        input.push_back(i);    }    size_t encodedLength = maxval;    Plaintext plaintext  = cc->MakeCKKSPackedPlaintext(input);    auto ciphertext      = cc->Encrypt(keyPair.publicKey, plaintext);    double lowerBound = 0;     double upperBound = maxval+1;    //Using the lambda function of log10(x)    Ciphertext<lbcrypto::DCRTPoly> result;        if (opt==0) { result = cc->EvalChebyshevFunction([](double x) -> double { return std::log10(x); }, ciphertext, lowerBound, upperBound, polyDegree);        std::cout <<" x    log10(x)\n----------" << std::endl;    }   else if (opt==1) { result = cc->EvalChebyshevFunction([](double x) -> double { return std::log2(x); }, ciphertext, lowerBound, upperBound, polyDegree);     std::cout <<" x    log2(x)\n----------" << std::endl;   }   else if (opt==2) { result = cc->EvalChebyshevFunction([](double x) -> double { return std::log(x); }, ciphertext, lowerBound, upperBound, polyDegree);       std::cout <<" x    ln(x)\n----------" << std::endl;   }      else if (opt==3) { result = cc->EvalChebyshevFunction([](double x) -> double { return std::exp(x); }, ciphertext, lowerBound, upperBound, polyDegree);       std::cout <<" x    exp(x)\n----------" << std::endl;   }    Plaintext plaintextDec;    cc->Decrypt(keyPair.secretKey, result, &plaintextDec);    plaintextDec->SetLength(maxval);    std::vector<std::complex<double>> finalResult = plaintextDec->GetCKKSPackedValue();    std::cout.precision(4);    for (int i=1;i<=maxval;i++)         std::cout << i<<  "     " <<  std::real(finalResult[i-1]) << std::endl;}/* For EvalChebyshevFunction we required a number multiplications and which are dependent on input polynomial degree. For this we use the following table:3-5  46-13  514-27  628-59  760-119  8120-247  9248-495  10496-1007  111008-2031  12 */`

A sample run is [here]:

`Logarithm evaluation x    log10(x)----------1     -0.002862     0.30243     0.47684     0.60175     0.69896     0.77857     0.84568     0.90329     0.953910     0.999811     1.04212     1.07913     1.11414     1.14615     1.17616     1.20417     1.23118     1.25519     1.27920     1.301`

If we try Python for x=5, we get [here]:

`>>> x=3>>> import math>>> y=math.log10(x)>>> print (x,y)3 0.47712125471966244`

## Conclusions

With PQC (Post Quantum Cryptography) and Homomorphic Encryption, we are generally moving towards the usage of polynomials. With these, we can thus use polynomials to represent our mathematical functions and thus integrate it with homomorphic encryption operations. There are other examples here:

--

--

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.