CKKS Scheme

Unlike other FHE schemes that perform exact computations, CKKS is optimized for approximate arithmetic. It allows for small, controlled errors in computation, which is acceptable for many real-world applications like machine learning and statistical analysis. This trade-off enables:

• Massive performance gains over exact arithmetic schemes.
• Native support for real and complex numbers.
• Practical applications in data science where perfect precision is not required.

CKKS encodes real numbers into ciphertexts using a fixed-point representation within polynomial rings. This is achieved by scaling the numbers by a large factor before encryption and managing the scale during operations. Key mechanisms include:

• Rescaling: Automatically reduces the scale after multiplication to prevent overflow, analogous to adjusting the decimal point.
• Modulus Switching: A technique intertwined with rescaling to manage the noise growth inherent in homomorphic operations.

CKKS packs thousands of numbers into a single ciphertext, enabling SIMD (Single Instruction, Multiple Data) operations. This allows a single homomorphic operation (addition, multiplication) to be performed on all encoded values simultaneously.

• Massive parallelism: Drastically improves throughput for vector and matrix operations.
• Efficient data processing: Essential for scaling privacy-preserving computations on large datasets.
• Managed via rotations and other slot manipulation operations.

While early implementations were somewhat homomorphic, modern CKKS includes a bootstrapping procedure. This operation refreshes a ciphertext, reducing accumulated noise and allowing for an unlimited number of sequential operations (fully homomorphic encryption).

• Computationally expensive: Bootstrapping is the most costly operation in FHE.
• Enables complex circuits: Makes long, iterative computations (like deep neural network inference) feasible.

CKKS achieves its performance through carefully managed trade-offs within the Ring Learning With Errors (RLWE) problem framework.

• Security: Based on the presumed hardness of RLWE, a well-studied lattice problem.
• Error Tolerance: The allowance for approximation is the key differentiator from BGV or BFV schemes.
• Parameter Selection: Security level, precision, and capacity for computation depth are tuned via polynomial degree and ciphertext modulus.

CKKS is the leading scheme for privacy-enhancing technologies (PETs) in data analytics and AI due to its native handling of approximate numbers.

• Private Machine Learning: Secure training and inference on encrypted data.
• Privacy-Preserving Analytics: Statistical analysis on sensitive datasets (e.g., healthcare, finance).
• Secure Outsourced Computation: Processing data in untrusted cloud environments without decryption.

CKKS is ideal for processing streams of encrypted numerical data from devices. Applications include:

• Smart grid analysis where power consumption data from homes is aggregated and analyzed in encrypted form.
• Private environmental monitoring where sensor readings (temperature, air quality) are processed without revealing location-specific data.
• Secure industrial IoT for predictive maintenance analytics on encrypted machinery sensor data.

CKKS is distinct from other Fully Homomorphic Encryption (FHE) schemes:

• BFV/BGV: Optimized for exact integer arithmetic. CKKS is for approximate arithmetic on real/complex numbers.
• TFHE: Specialized for fast Boolean circuit evaluation (AND, OR, NOT). CKKS excels at arithmetic circuits (addition, multiplication).
• Trade-off: CKKS provides efficiency and native support for decimals but introduces controlled, bounded noise in computations.

While powerful, CKKS has specific constraints:

• Approximate Results: Outputs are close approximations, not exact, due to noise management and rescaling operations.
• Computational Overhead: Operations are significantly slower than on plaintext, though batching thousands of numbers into a single ciphertext improves throughput.
• Parameter Selection: Choosing the right polynomial degree and ciphertext modulus is critical for balancing security, precision, and performance.

CKKS is distinguished from other Fully Homomorphic Encryption (FHE) schemes like BFV and BGV.

• CKKS: Optimized for approximate arithmetic on real/complex numbers. Ideal for analytics and ML.
• BFV/BGV: Perform exact integer arithmetic. Better for applications requiring precise counts or financial transactions.
• TFHE: Specializes in fast Boolean circuit evaluation (AND, OR, NOT gates).

Using CKKS involves navigating key performance trade-offs:

• Ciphertext Size: Encrypted data is significantly larger than plaintext, impacting bandwidth and storage.
• Computational Overhead: Operations are orders of magnitude slower than on plaintext, requiring careful parameter selection (polynomial degree, modulus size).
• Noise Management: Each operation adds "noise" to the ciphertext; bootstrapping is a costly operation required to reset noise and enable unlimited computations.

Unlike FHE schemes like BFV or BGV that guarantee exact computation, CKKS is designed for approximate arithmetic. This means it intentionally allows a small, bounded error in the plaintext result to achieve greater efficiency and support for real numbers. The security model must account for this inherent noise, which is distinct from the cryptographic noise added for security. The scheme's security is based on the Ring Learning With Errors (RLWE) problem, but the plaintext error must be managed to prevent it from corrupting the meaningful result.

The concrete security of a CKKS implementation is determined by parameter selection, primarily the polynomial degree (N) and the ciphertext modulus (q). These parameters define the lattice dimension and complexity for an attacker. Choosing parameters involves a trade-off:

• Higher security: Larger N and q, resulting in slower operations and larger ciphertexts.
• Lower security: Smaller parameters, faster operations, but vulnerable to lattice reduction attacks. Parameters must be chosen to meet a target security level (e.g., 128-bit security), which estimates the computational cost for an adversary to break the encryption.

Each homomorphic operation, especially multiplication, increases the noise in the ciphertext. CKKS uses bootstrapping to reduce this noise and enable unlimited computations, but it is a costly operation. The multiplicative depth of a circuit (the maximum number of sequential multiplications) is a critical limitation before bootstrapping is required. Without careful management, noise can overflow, corrupting the encrypted data. This necessitates precise noise budgeting during application design, influencing the choice of algorithms and parameter sets.

CKKS encodes real or complex numbers into a polynomial plaintext slot with a defined scaling factor. This process inherently introduces encoding error. Subsequent operations cause:

• Scaling factor management: Required after multiplications to control plaintext growth, which can consume ciphertext modulus and reduce capacity.
• Precision loss: The cumulative effect of approximate arithmetic and rescaling. The final decrypted result is an approximation of the true computation, with precision decreasing as multiplicative depth increases. This is a fundamental limitation for applications requiring exact results.

CKKS natively supports addition, multiplication, and rotation on encrypted vectors. However, it cannot efficiently perform non-arithmetic operations:

• Comparisons (<, >, =)
• Division
• Branching (if/else logic)
• Non-polynomial functions (e.g., sigmoid, ReLU) These must be approximated using high-degree polynomials (e.g., via Taylor series or Chebyshev approximation), which drastically increases computational cost, multiplicative depth, and noise. This limits the complexity of algorithms that can be practically implemented.

Homomorphic Encryption is a cryptographic method that allows computations to be performed directly on encrypted data without first decrypting it. The result of the computation, when decrypted, matches the result of the same operations performed on the plaintext.

• Core Property: Enables privacy-preserving data analysis in untrusted environments like the cloud.
• Types: Includes Somewhat Homomorphic Encryption (SHE), Fully Homomorphic Encryption (FHE), and Leveled Homomorphic Encryption (LHE).
• Use Case: CKKS is a specific scheme designed for efficient approximate arithmetic on real or complex numbers.

Approximate Arithmetic refers to computations that tolerate a small, controlled amount of numerical error, which is the key innovation of the CKKS scheme. Unlike other FHE schemes that require exact integer arithmetic, CKKS is optimized for real-world data.

• Trade-off: Sacrifices perfect precision for massive gains in performance and practicality.
• Applications: Ideal for machine learning, statistical analysis, and financial modeling where results are interpreted within an error margin (e.g., 2^-40).
• Mechanism: Encodes numbers as polynomials with noise, where the noise is managed as part of the approximation error.

Learning With Errors (LWE) is a foundational hard problem in lattice-based cryptography that provides security for many homomorphic encryption schemes, including CKKS. Ring-LWE is its more efficient ring-based variant.

• Security Basis: Assumes it is computationally infeasible to distinguish between random linear equations and equations with a small amount of additive noise.
• Efficiency: Ring-LWE operates over polynomial rings, enabling Single Instruction, Multiple Data (SIMD) operations, which CKKS uses to pack thousands of numbers into a single ciphertext for parallel computation.
• Post-Quantum: LWE problems are considered resistant to attacks from quantum computers.

Bootstrapping is a critical procedure in Fully Homomorphic Encryption that refreshes a ciphertext, reducing accumulated noise from previous operations to allow for unlimited computations.

• Noise Growth: Each homomorphic operation increases the "noise" in a ciphertext; too much noise renders decryption impossible.
• Function: Bootstrapping homomorphically decrypts and re-encrypts the ciphertext, resetting the noise level. It is computationally expensive.
• CKKS Context: CKKS can operate in a Leveled HE mode for deep, predefined computation circuits without bootstrapping, or use bootstrapping for theoretically infinite computations.

Ciphertext Packing, or Single Instruction, Multiple Data (SIMD) batching, is a technique that encodes multiple data values into a single ciphertext polynomial, allowing parallel homomorphic operations on all values at once.

• Massive Throughput: A single CKKS ciphertext can contain thousands of slots, each holding a separate number. An operation (addition, multiplication) applies to all slots simultaneously.
• Key Efficiency Driver: This batching is what makes CKKS practical for large-scale data processing, amortizing the high computational cost over many data points.
• Use Case: Essential for performing vector and matrix operations efficiently on encrypted data.

Privacy-Preserving Machine Learning is a primary application domain for the CKKS scheme, enabling model training and inference on encrypted data without exposing the raw inputs or the model parameters.

• Data Privacy: Sensitive data (e.g., medical records, financial data) remains encrypted during the entire ML pipeline.
• Model Privacy: The proprietary ML model can also be encrypted, protecting intellectual property.
• CKKS Role: Its support for approximate arithmetic and SIMD operations makes it uniquely suited for the linear algebra operations (matrix multiplications, activation functions) at the heart of neural networks.