Skip to content

CKKS first modulus selection analysis #2754

@j2kun

Description

@j2kun

In working on supporting rolled kernels, I hit an infinite loop in generate-params-ckks. The code uses a range analysis in getExtraBitsForLevel0 to determine how many extra bits are required (above the scaling factor bit size). That range analysis loops infinitely in the presence of loops, which is expected, and I am able to manually set the first-mod-bits to avoid this and proceed.

Along the way, I was reading about how the first modulus bit size is typically set. It seems that it is typically the sum of the scaling bit size, plus the bit size of the maximum noise at level 0 (which requires a noise model), plus some number of bits to account for precision loss during CKKS rescaling (which requires bounds on the intermediate values of variables), plus a buffer of ~2 extra bits to account for tails of noise distributions.

This issue is for the task of implementing a more full-fledged analysis here. It should also support loops, with the constraint that loop iterations are mgmt-invariant (this will remove most of the problems except ensuring range analysis doesn't loop infinitely).

Metadata

Metadata

Assignees

No one assigned

    Labels

    dialect: ckksIssues related to the CKKS dialectdialect: mgmtIssues concerning the mgmt dialectnewcomer projectProject ideas for new contributors

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions