Secure Change-Point Detection for Time Series under Homomorphic Encryption

Federico Mazzone (Paper author · University of Twente), Giorgio Micali (Paper author · University of Twente), Massimiliano Pronesti (Paper author · IBM Research Europe)

Privacy Enhancing Technologies Symposium (PETS) 2026 · Day 2 · Beaver

Overview

This talk, presented by Federico Mazzone, delves into the critical challenge of performing change point detection (CPD) on time series data in a privacy-preserving manner. The research addresses a common scenario where data owners, due to resource constraints or legal mandates, must outsource computationally intensive data analysis to third-party servers. In such settings, safeguarding the privacy of sensitive time series data—which can range from medical records like EEGs and heartbeats to cybersecurity logs for network anomaly detection—becomes paramount.

Watch on YouTube · Slides

Visual summary for Secure Change-Point Detection for Time Series under Homomorphic Encryption by Federico Mazzone, Giorgio Micali, Massimiliano Pronesti
Visual summary for Secure Change-Point Detection for Time Series under Homomorphic Encryption by Federico Mazzone, Giorgio Micali, Massimiliano Pronesti

Key moments

  1. 0:00 Introduction and quick summary of secure CPD with FHE
  2. 2:00 Defining change point detection and outsourced privacy setting
  3. 4:20 Three types of change points and algorithm overview
  4. 6:00 FHE challenges: comparisons, absolute value, argmax optimization
  5. 7:30 Scalability results: 1 million points in 3 minutes
  6. 8:50 FHE vs. Differential Privacy: accuracy comparison
  7. 9:50 Paper details, contact, and PhD student recruitment

Secure Change-Point Detection for Time Series under Homomorphic Encryption

Speakers: Federico Mazzone (Paper author, University of Twente); Giorgio Micali (Paper author, University of Twente); Massimiliano Pronesti (Paper author, IBM Research Europe)

Conference: PETS

YouTube: https://www.youtube.com/watch?v=qtBjVL4QLIs

Overview

This talk, presented by Federico Mazzone, delves into the critical challenge of performing change point detection (CPD) on time series data in a privacy-preserving manner. The research addresses a common scenario where data owners, due to resource constraints or legal mandates, must outsource computationally intensive data analysis to third-party servers. In such settings, safeguarding the privacy of sensitive time series data—which can range from medical records like EEGs and heartbeats to cybersecurity logs for network anomaly detection—becomes paramount.

The core contribution of this work lies in its innovative application of Fully Homomorphic Encryption (FHE), specifically the CKKS (Cheon-Kim-Kim-Song) scheme, to enable secure outsourced CPD. The speakers highlight the notorious computational bottleneck associated with FHE operations and present a significant breakthrough: processing time series with up to 1 million timestamps within approximately 3 minutes on a moderately sized cluster. This achievement not only pushes the boundaries of practical FHE applications but also offers a robust alternative to other privacy-enhancing technologies like differential privacy, particularly when high analytical accuracy is non-negotiable.

Background

▶ Watch: Introduction and quick summary of secure CPD with FHE (0:00)

Time series data, characterized as a one-dimensional stream of values sampled over time, is ubiquitous across numerous domains. Its analysis, particularly the identification of change points, is crucial for detecting anomalies, shifts in behavior, or structural transformations within the data. A change point signifies a moment when the underlying statistical distribution generating the time series data shifts, for example, a sudden alteration in the mean, variance, or frequency of the observed values. In medical contexts, this could indicate a patient's health deterioration; in cybersecurity, it might signal a network intrusion or a denial-of-service attack.

The challenge arises when organizations need to perform CPD on sensitive time series but lack the local computational resources or are bound by stringent privacy regulations (e.g., GDPR, HIPAA) that prevent direct processing of plaintext data by external services. This necessitates a secure outsourced computation model, where a data owner sends their data to a computing server for analysis without revealing the raw information. While various Privacy-Enhancing Technologies (PETs) exist, Homomorphic Encryption (HE) stands out for its ability to enable computation on encrypted data directly, without decryption. The chosen FHE scheme, CKKS, is particularly well-suited for approximate computations on real numbers, making it a strong candidate for statistical analyses like CPD. However, the inherent computational overhead of FHE has historically limited its practical applicability to large datasets, posing a significant barrier to its widespread adoption in real-world scenarios. This research directly confronts this limitation, aiming to make secure, accurate CPD feasible at scale.

Key Findings

▶ Watch: Three types of change points and algorithm overview (4:20)

The research presented by Mazzone and his co-authors yields several significant findings that advance the practical utility of FHE for time series analysis:

Firstly, the most impactful achievement is the substantial reduction in computation time for FHE-based CPD. The system is capable of processing time series containing up to 1 million timestamps within approximately 3 minutes for frequency shift detection, and even faster (under 2.5 minutes) for mean and variance shifts, utilizing a "relatively decent size cluster." This performance marks a critical step towards overcoming the long-standing computational bottleneck associated with FHE, making it viable for large-scale, real-world data analysis.

Secondly, the proposed FHE-friendly CPD algorithm demonstrates remarkable accuracy. For synthetic datasets, the FHE-encrypted computation achieves results perfectly identical to its plaintext baseline. While a slight relative error was observed for real-world datasets, this error was comparable to the inherent error of the plaintext baseline when measured against human-identified ground truth, indicating that the FHE approximation introduces negligible additional inaccuracy. This finding underscores the method's reliability for critical applications where precision is paramount.

Thirdly, the work rigorously evaluates the performance of FHE against alternative PETs, specifically Differential Privacy (DP), in the context of outsourced computation, focusing on Local Differential Privacy (LDP). The results clearly show that LDP incurs a "quite heavy" accuracy loss, particularly for privacy parameters epsilon below 10, irrespective of the time series size. In contrast, the FHE-based approach maintains high accuracy, establishing it as a superior choice for scenarios where data utility cannot be significantly sacrificed for privacy.

Finally, the research successfully adapts an existing CPD algorithm to be compatible with FHE, addressing three distinct types of change points: shifts in mean, variance, and frequency of the time series distribution. This comprehensive coverage expands the applicability of secure CPD to a broader range of analytical tasks.

Technical Deep Dive

▶ Watch: FHE challenges: comparisons, absolute value, argmax optimization (6:00)

The core of this work lies in making an established CPD algorithm amenable to Fully Homomorphic Encryption (FHE), specifically using the CKKS scheme. The challenge was to transform operations traditionally considered computationally expensive or incompatible with FHE into efficient, encrypted equivalents.

The CPD algorithm is structured in three main steps:

  1. Time Series Splitting: The initial step involves dividing the input time series, of length n, into smaller chunks. The optimal split size, as theoretically proven, is approximately sqrt(n). This reduces the complexity of subsequent computations by operating on smaller, more manageable blocks. For example, a time series with 1 million points would be split into approximately 1000 chunks.
  1. Summary Statistic Computation: For each of these sqrt(n) chunks, a summary statistic is computed. The nature of this statistic depends on the type of change point being detected:
  • Mean Change: The summary statistic is simply the mean of the values within each block. This involves basic arithmetic operations (summation and division), which are relatively straightforward under FHE.
  • Variance Change: The summary statistic is the variance of the values within each block. This requires calculating squared differences from the mean, also manageable with FHE arithmetic.
  • Frequency Change: This is the most technically involved. It requires counting specific patterns of triplets within each block. Specifically, the algorithm looks for "up and down" or "down and up" sequences. For instance, if x_i < x_{i+1} > x_{i+2} (up and down) or x_i > x_{i+1} < x_{i+2} (down and up). Counting these patterns necessitates comparison operations under FHE. Comparisons (e.g., a < b) are inherently non-polynomial and thus challenging for FHE, which primarily supports polynomial operations. The authors leveraged "previous results on how to perform ranking computation" to approximate these comparisons efficiently within the encrypted domain.
  1. Cumulative Sum Statistic (CUSUM) Application: Once the sqrt(n) summary statistics are computed, they form a new, shorter time series. On this summarized series, a mean change point detection algorithm is applied, specifically using the Cumulative Sum (CUSUM) statistic. The CUSUM method is a well-known technique for detecting shifts in the mean of a sequence. However, its application typically involves operations such as absolute value (|x|) and argmax (finding the index of the maximum value). Like comparisons, these functions are non-polynomial and present significant hurdles for FHE.

The critical innovation in this research lies in optimizing these FHE-unfriendly computations. The authors achieved this by "fully exploiting the SIMD (Single Instruction, Multiple Data) capabilities of CKKS." CKKS, by design, allows for packing multiple plaintext values into a single ciphertext slot (a technique known as "slot packing" or batching). This enables the same homomorphic operation to be applied simultaneously to all packed values, dramatically increasing throughput. By carefully structuring the algorithm to maximize parallelization via SIMD, the researchers managed to make the non-polynomial approximations for comparisons, absolute values, and argmax functions computationally feasible within practical timeframes. This strategic use of CKKS's inherent parallel processing power was instrumental in achieving the reported performance metrics for large time series.

Demo / Proof of Concept

▶ Watch: FHE vs. Differential Privacy: accuracy comparison (8:50)

While the presentation did not feature a live, interactive demonstration, the research provides robust empirical evidence through scalability and accuracy analyses that serve as a comprehensive proof of concept for the proposed FHE-based secure change point detection system.

The scalability analysis clearly illustrates the method's efficiency. The most computationally intensive task, frequency shift analysis (due to the complex triplet comparisons under FHE), processes time series with 1 million timestamps in approximately 3 minutes. For mean and variance shift detections, the processing times are even lower, falling between 2 and 2.5 minutes for the same data size. This performance was achieved on a "relatively decent size cluster," indicating the practicality of deploying such a system. The speaker noted that the processing time scales "quite nicely," demonstrating the algorithm's capability to handle large datasets effectively.

Regarding accuracy, the system achieves a remarkable fidelity. When tested with synthetic data, the FHE-encrypted computations yield results perfectly identical to those obtained from plaintext processing. This confirms that the approximations used for non-polynomial functions (like comparisons, absolute values, and argmax) are sufficiently precise. For real-world datasets, a "slight relative error" was observed compared to the plaintext baseline. Crucially, the plaintext baseline itself exhibited a similar "slight relative error" when compared against human-identified ground truth, suggesting that the FHE approach introduces minimal, if any, additional inaccuracy beyond what is inherent in the plaintext algorithm itself.

Furthermore, the research included a comparative analysis against Local Differential Privacy (LDP), a competing PET for outsourced computation. This comparison demonstrated a significant advantage for the FHE approach in terms of data utility. LDP was shown to incur "quite heavy" accuracy loss, particularly when the privacy parameter epsilon was set below 10, regardless of the time series size. This highlights a key trade-off: while LDP offers strong privacy guarantees, it often comes at the cost of reduced data utility, making it less suitable for applications requiring high analytical precision. The FHE-based solution, by contrast, maintains high accuracy while providing robust privacy. These empirical results collectively establish the viability and superiority of the FHE approach for secure, accurate, and scalable change point detection on sensitive time series data.

Defensive Implications

▶ Watch: Paper details, contact, and PhD student recruitment (9:50)

The work presented by Mazzone and his colleagues offers profound implications for cybersecurity defenders and organizations handling sensitive time series data across various sectors, including healthcare, finance, and critical infrastructure.

Firstly, this research enables organizations to confidently outsource computationally intensive time series analysis to cloud providers or third-party computing services without compromising data privacy. This is a game-changer for entities constrained by limited local resources or stringent regulatory requirements (e.g., GDPR, HIPAA) that traditionally prevent such outsourcing. Defenders can now leverage the scalability and cost-effectiveness of cloud infrastructure for tasks like network anomaly detection, fraud detection, or patient health monitoring, while ensuring the raw, sensitive data remains encrypted throughout the computation.

Secondly, the demonstrated high accuracy of the FHE-based CPD algorithm, especially when compared to methods like Differential Privacy, means that defenders do not have to significantly sacrifice analytical precision for privacy. In cybersecurity, for instance, accurate detection of subtle changes in network traffic patterns is crucial for identifying advanced persistent threats (APTs) or zero-day exploits. The ability to perform such precise analysis on encrypted data ensures that critical security insights are not diluted by privacy-preserving noise.

Defenders should consider integrating Homomorphic Encryption libraries and services into their data processing pipelines. This involves understanding the CKKS scheme and its capabilities for approximate real-number computations. While the initial setup for FHE, including key generation and data encoding, requires careful implementation, the long-term benefits in terms of privacy and data utility are substantial.

Furthermore, this work underscores the importance of a holistic security strategy that includes secure key management for the FHE encryption keys. The integrity and confidentiality of these keys are paramount, as their compromise would undermine the entire privacy-preserving framework. Organizations should implement robust key generation, storage, and access control mechanisms, potentially leveraging hardware security modules (HSMs).

Finally, this research highlights the growing maturity of FHE as a practical privacy-enhancing technology. Security architects and data privacy officers should stay abreast of advancements in FHE, exploring how it can be applied to other sensitive analytical tasks beyond change point detection. By adopting FHE-enabled solutions, defenders can proactively address privacy concerns while continuing to extract valuable intelligence from their ever-growing volumes of time series data.

Key Takeaways

  • Practical FHE for Large-Scale Analysis: The research demonstrates that FHE-based change point detection is now practical for time series with up to 1 million timestamps, completing computations within 3 minutes on a cluster.
  • Superior Accuracy over Differential Privacy: The FHE approach maintains perfect accuracy relative to plaintext for synthetic data and exhibits minimal error for real-world data, significantly outperforming Local Differential Privacy, which incurs substantial accuracy loss (especially for epsilon < 10).
  • Enables Secure Outsourced Computation: Organizations can now perform sensitive time series analysis (e.g., medical, cybersecurity) on third-party servers without exposing raw data, addressing privacy and compliance challenges.
  • Leverages CKKS SIMD Capabilities: The performance breakthrough was achieved by fully exploiting the SIMD (Single Instruction, Multiple Data) features of the CKKS scheme to parallelize FHE-unfriendly operations like comparisons, absolute values, and argmax.
  • Comprehensive Change Point Detection: The solution effectively identifies three critical types of structural changes in time series: shifts in mean, variance, and frequency.
  • FHE-Friendly Algorithm Adaptation: The work successfully adapted an existing CPD algorithm, including the Cumulative Sum (CUSUM) statistic, to be compatible and efficient under homomorphic encryption, addressing inherent challenges with non-polynomial functions.

About the Speaker(s)

Federico Mazzone is a paper author and was the presenter for this talk. At the time of the presentation, he was affiliated with the University of Oldenburg, although the paper metadata also lists the University of Twente. His research focuses on advancing the practical application of homomorphic encryption, particularly in making complex data analysis tasks like change point detection feasible in privacy-preserving outsourced computation settings.

Giorgio Micali is a co-author of the paper, affiliated with the University of Twente.

Massimiliano Pronesti is also a co-author of the paper, affiliated with IBM Research Europe. Their collaborative work underscores a multi-institutional effort to push the boundaries of privacy-enhancing technologies.

Reviews

Dr. Zero (Offensive Security Researcher) — SOLID

Taking FHE out of the ivory tower and making it chew through a million timestamps in three minutes is a real engineering flex. They bypassed the non-polynomial bottlenecks in CKKS by actually utilizing SIMD slot packing instead of just complaining about the math. It's a strong paper that proves homomorphic encryption is finally approaching operational viability for offline telemetry analysis.

Heather Calloway (CISO) — SOLID

Fully Homomorphic Encryption (FHE) has historically been an academic science project that melts enterprise compute budgets. This research proves it is finally approaching operational viability for analyzing massive, highly sensitive datasets. If you are a CISO restricted by data residency or privacy laws from outsourcing analytics, this changes the timeline on when you can safely utilize third-party compute.

→ Top-rated talks at Privacy Enhancing Technologies Symposium (PETS) 2026

All talks from Privacy Enhancing Technologies Symposium (PETS) 2026