README
¶
References
- Minimax Approximation of Sign Function by Composite Polynomial for Homomorphic Comparison (https://ieeexplore.ieee.org/abstract/document/9517029)
Documentation
¶
Overview ¶
Package minimax implements a homomorphic minimax circuit for the CKKS scheme.
Index ¶
- Variables
- func GenMinimaxCompositePolynomial(prec uint, logalpha, logerr int, deg []int, f func(*big.Float) *big.Float) (coeffs [][]*big.Float)
- func GenMinimaxCompositePolynomialForSign(prec uint, logalpha, logerr int, deg []int)
- func PrettyPrintCoefficients(decimals int, coeffs []*big.Float, odd, even, first bool)
- type Evaluator
- type Polynomial
Constants ¶
This section is empty.
Variables ¶
var CoeffsSignX2Cheby = []string{"0", "1.125", "0", "-0.125"}
CoeffsSignX2Cheby (from https://eprint.iacr.org/2019/1234.pdf) are the coefficients of 1.5*x - 0.5*x^3 in Chebyshev basis. Evaluating this polynomial on values already close to -1, or 1 ~doubles the number of of correct digits. For example, if x = -0.9993209 then p(x) = -0.999999308 This polynomial can be composed after the minimax composite polynomial to double the output precision (up to the scheme precision) each time it is evaluated.
var CoeffsSignX4Cheby = []string{"0", "1.1962890625", "0", "-0.2392578125", "0", "0.0478515625", "0", "-0.0048828125"}
CoeffsSignX4Cheby (from https://eprint.iacr.org/2019/1234.pdf) are the coefficients of 35/16 * x - 35/16 * x^3 + 21/16 * x^5 - 5/16 * x^7 in Chebyshev basis. Evaluating this polynomial on values already close to -1, or 1 ~quadruples the number of of correct digits. For example, if x = -0.9993209 then p(x) = -0.9999999999990705 This polynomial can be composed after the minimax composite polynomial to quadruple the output precision (up to the scheme precision) each time it is evaluated.
Functions ¶
func GenMinimaxCompositePolynomial ¶
func GenMinimaxCompositePolynomial(prec uint, logalpha, logerr int, deg []int, f func(*big.Float) *big.Float) (coeffs [][]*big.Float)
GenMinimaxCompositePolynomial generates the minimax composite polynomial P(x) = pk(x) o pk-1(x) o ... o p1(x) o p0(x) for the provided function in the interval in their interval [min-err, -2^{-alpha}] U [2^{-alpha}, max+err] where alpha is the desired distinguishing precision between two values and err an upperbound on the scheme error.
The user must provide the following inputs:
- prec: the bit precision of the big.Float values used by the algorithm to compute the polynomials. This will impact the speed of the algorithm. A too low precision can prevent convergence or induce a slope zero during the zero finding. A sign that the precision is too low is when the iteration continue without the error getting smaller.
- logalpha: log2(alpha)
- logerr: log2(err), the upperbound on the scheme precision. Usually this value should be smaller or equal to logalpha. Correctly setting this value is mandatory for correctness, because if x is outside of the interval (i.e. smaller than -1-e or greater than 1+e), then the values will explode during the evaluation. Note that it is not required to apply change of interval [-1, 1] -> [-1-e, 1+e] because the function to evaluate is the sign (i.e. it will evaluate to the same value).
- deg: the degree of each polynomial, ordered as follow [deg(p0(x)), deg(p1(x)), ..., deg(pk(x))]. It is highly recommended that deg(p0) <= deg(p1) <= ... <= deg(pk) for optimal approximation.
The polynomials are returned in the Chebyshev basis and pre-scaled for the interval [-1, 1] (no further scaling is required on the ciphertext).
Be aware that finding the minimax polynomials can take a while (in the order of minutes for high precision when using large degree polynomials).
The function will print information about each step of the computation in real time so that it can be monitored.
The underlying algorithm use the multi-interval Remez algorithm of https://eprint.iacr.org/2020/834.pdf.
func GenMinimaxCompositePolynomialForSign ¶
GenMinimaxCompositePolynomialForSign generates the minimax composite polynomial P(x) = pk(x) o pk-1(x) o ... o p1(x) o p0(x) of the sign function in their interval [min-err, -2^{-alpha}] U [2^{-alpha}, max+err] where alpha is the desired distinguishing precision between two values and err an upperbound on the scheme error.
The sign function is defined as: -1 if -1 <= x < 0, 0 if x = 0, 1 if 0 < x <= 1.
See GenMinimaxCompositePolynomial for information about how to instantiate and parameterize each input value of the algorithm.
Types ¶
type Evaluator ¶
type Evaluator struct {
*ckks.Evaluator
PolyEval *polynomial.Evaluator
BtsEval bootstrapping.Bootstrapper
Parameters ckks.Parameters
}
Evaluator is an evaluator used to evaluate composite polynomials on ciphertexts. All fields of this struct are publics, enabling custom instantiations.
func NewEvaluator ¶
func NewEvaluator(params ckks.Parameters, eval *ckks.Evaluator, btsEval bootstrapping.Bootstrapper) *Evaluator
NewEvaluator instantiates a new Evaluator. This method is allocation free.
func (Evaluator) Evaluate ¶
func (eval Evaluator) Evaluate(ct *rlwe.Ciphertext, mcp Polynomial) (res *rlwe.Ciphertext, err error)
Evaluate evaluates the provided MinimaxCompositePolynomial on the input ciphertext.
type Polynomial ¶
type Polynomial []bignum.Polynomial
Polynomial is a struct storing P(x) = pk(x) o pk-1(x) o ... o p1(x) o p0(x).
func NewPolynomial ¶
func NewPolynomial(coeffsStr [][]string) Polynomial
NewPolynomial creates a new Polynomial from a list of coefficients. Coefficients are expected to be given in the Chebyshev basis.
func (Polynomial) Evaluate ¶
func (mcp Polynomial) Evaluate(x interface{}) (y *bignum.Complex)
func (Polynomial) MaxDepth ¶
func (mcp Polynomial) MaxDepth() (depth int)
Source Files