Time Series Analysis of Confidentiality Degradation in Encrypted Search Systems

Suppose we require that confidentiality remain above a threshold ${\pi }^{\ast }\in (0,1)$. We define the critical time $T^{\ast }$ as

At time $T^{\ast }$, the adversary can decode more than proportion ${\pi }^{\ast }$ of queries, violating the security requirement.

To maintain the threshold, we must reinitialize the encryption before reaching $T^{\ast }$. This typically involves changing the cryptographic key (e.g., requiring password changes), which generates a new encryption function ${\mathrm{h}}^{\prime }$ and resets the adversary’s knowledge. The adversary must then restart the attack process with ${\widehat{\mathrm{g}}}^{\prime }$.

Forecasting $\{{\pi }_t\}$ enables proactive security policies: we can predict when ${\pi }_t$ will exceed ${\pi }^{\ast }$ and schedule reinitialization accordingly.

Since $\{c_t\}$ is random, the confidentiality measure $\{{\pi }_t\}$ is also random. We model it as a stochastic process $\{{\mathrm{\Pi }}_t\}$.

Given observations ${\pi }_1,\mathrm{\dots },{\pi }_T$, the $h$-step ahead forecast distribution is

The forecast mean is denoted $𝔼[{\mathrm{\Pi }}_{T+h|T}]$.

Our goal is to estimate the forecast distribution from observed data. In practice, we estimate the forecast mean ${\widehat{\pi }}_{T+h|T}$ and construct prediction intervals using the estimated forecast variance.

The simulation proceeds in two phases: query generation and attack simulation.

ARIMA models assume stationarity: constant mean, constant variance, and autocorrelation that depends only on lag. We must transform $\{{\pi }_t\}$ to approximate stationarity before fitting ARIMA models.

Figure 1 plots the training data. The series exhibits an upward trend, indicating non-stationarity in the mean.

Figure 2 shows the sample ACF and PACF. The slow decay in the ACF confirms non-stationarity.

The variance appears reasonably constant, so variance-stabilizing transformations (e.g., logarithm) are unnecessary. To remove the trend, we apply differencing: the $d$-th order differenced series is denoted ${\nabla }^d\{{\pi }_t\}$. Differencing is a flexible, non-parametric approach that adapts to complex trend patterns without assuming a specific functional form.

Figure 3 shows the differenced series $\nabla \{{\pi }_t\}$. The trend is removed, values fluctuate around zero, and variance appears constant. This suggests stationarity.

We apply the augmented Dickey-Fuller test [2] to formally test for stationarity:

## Augmented Dickey-Fuller Test
## Dickey-Fuller = -20.37, Lag order = 15, p-value = 0.01
## alternative hypothesis: stationary

The $p$-value of 0.01 provides strong evidence against the null hypothesis of non-stationarity. We conclude that $\nabla \{{\pi }_t\}$ is approximately stationary and proceed with ARIMA modeling.

Our goal is to build a parsimonious forecasting model. Following Occam’s razor, simpler models with fewer parameters are preferred: they generalize better to unseen data and avoid overfitting [1]. However, the model must be sufficiently complex to capture the data’s structure. This is the classical bias-variance tradeoff.

ARIMA$(p,d,q)$ models are parameterized by three integers: $p$ (autoregressive order), $d$ (differencing order), and $q$ (moving average order). We seek small values of $p$, $d$, and $q$ that adequately fit the data. While information criteria like AIC can guide selection, we also examine diagnostic plots.

Figure 4 shows the ACF and PACF of $\nabla \{{\pi }_t\}$.

The ACF cuts off after lag 1, and the PACF decays exponentially, suggesting an MA(1) process for $\nabla \{{\pi }_t\}$ (i.e., IMA(1,1) for $\{{\pi }_t\}$).

The extended ACF (EACF) table provides additional guidance:

## AR/MA
##   0 1 2 3 4 5 6 7 8 9 10 11 12 13
## 0 x o o o o o o x x x o  o  o  o
## 1 x x o o o o x o o o o  o  o  o
## 2 x x x o o o x o o o o  o  o  o
## 3 x x x x o o o o o o o  o  o  o
## 4 x x x x x o o o o o o  o  o  o
## 5 x x x x x x o o o o o  o  o  o
## 6 x x x x x o x o o o o  o  o  o
## 7 x x x x x x x o o o o  o  o  o

The EACF suggests candidate models ARMA$(0,1)$, ARMA$(0,2)$, and ARMA$(1,2)$ for $\nabla \{{\pi }_t\}$. We evaluate all three.

Model adequacy is assessed through residual diagnostics. A well-specified model produces residuals $\{e_t\}$ that behave like white noise:

1. 1.

   Uncorrelated: If residuals are correlated, the model has not captured all temporal structure and can be improved.

2. 2.

   Zero mean: Non-zero mean residuals indicate systematic bias in forecasts.

3. 3.

   Constant variance: Heteroscedasticity may require variance modeling.

We now use the fitted ARIMA$(1,1,2)$ model to forecast future confidentiality degradation. At time $T=5000$, we compute forecasts ${\widehat{\pi }}_{T+h|T}$ for $h=1,\mathrm{\dots },1000$.

Figure 8 shows the forecast along with 80% prediction intervals.

The held-out test data falls within the 80% prediction interval for most time points, suggesting reasonable forecast performance. However, the prediction intervals are quite wide. We hypothesize this reflects model misspecification: the purely autoregressive structure may not capture the underlying process adequately. Theoretically, ${\pi }_t$ should approach an asymptotic limit as the adversary’s knowledge saturates, but the ARIMA model does not incorporate this constraint. We explore theory-driven models in the next section.

We now incorporate domain knowledge about the confidentiality measure. Assuming the plaintext distribution and encryption function remain fixed, we expect:

1. 1.

   ${\pi }_t\in [0,1]$ (it is a proportion).

2. 2.

   ${\pi }_t$ should be monotonically increasing: observing more queries cannot decrease the adversary’s accumulated knowledge.

3. 3.

   ${\pi }_t$ should approach an asymptotic limit $c\le 1$ as the adversary’s knowledge saturates.

These properties suggest models like Gompertz growth curves or scaled CDFs. For simplicity, we approximate the trend with a logarithmic function:

While this lacks an asymptote, it provides a reasonable approximation over finite time horizons.

We model deviations from this trend as ARIMA errors:

where ${\eta }_t\sim \mathrm{ARIMA}(p,d,q)$.

Note that this formulation (regression with ARIMA errors) differs from standard regression. As Hyndman [4] notes, the regression coefficients condition on lagged responses, complicating interpretation. Nevertheless, this model can improve forecasts by capturing both the deterministic trend and stochastic dynamics.

We fit this model to the data:

## Regression with ARIMA(1,1,2) errors
##
## Coefficients:
##          ar1      ma1     ma2    xreg
##       0.8521  -1.4012  0.4355  0.0292
## s.e.  0.0234   0.0277  0.0211  0.0202
##
## sigma^2 estimated as 6.828e-06:  log likelihood=45279.87
## AIC=-90549.73   AICc=-90549.73   BIC=-90513.68

This uses ARIMA$(1,1,2)$ errors with a logarithmic trend term. (We also tested ARIMA$(2,1,2)$, which yielded tighter prediction intervals but was not substantially better.)

Figure 9 shows residual diagnostics.

The histogram is symmetric, the Q-Q plot shows non-normality, and the ACF and PACF appear acceptable. The Ljung-Box test (lag 10):

## Box-Ljung test
## data:  reg_model$residuals
## X-squared = 10.279, df = 6, p-value = 0.1134

At the 5% significance level, the model is marginally adequate ($p=0.113$). The fitted model is

where ${\eta }_t\sim \mathrm{ARIMA}(1,1,2)$ with coefficients as above and $e_t\sim \mathrm{WN}(0,{\sigma }^2)$ with $\sigma =0.0026$.

Figure 10 shows forecasts from this model along with training and test data.

The forecasts extend much further into the future and follow the gradual upward trend more faithfully than the pure ARIMA model.

For comparison, we also fit an ARIMA$(1,1,2)$ model with drift:

##           ar1           ma1           ma2         drift
##  8.472755e-01 -1.396547e+00  4.324823e-01  4.695287e-06

The drift coefficient is small but positive. Over long horizons, this accumulates to produce an upward trend (Figure 11).

However, ARIMA with drift implies linear growth, which is theoretically inappropriate: ${\pi }_t$ must remain bounded in $[0,1]$. The logarithmic regression model better respects this constraint.

The adversary learns from observing ciphers $\{c_t\}$, but not all observations are equally informative. We could model the information content of each observation explicitly.

Define the information content of observation $t$ as

measured in bits. Observations with low probability under the adversary’s model carry more information.

Lagged values of $I_t$ could be used as predictors in a dynamic regression:

Alternatively, cumulative information (empirical entropy) could serve as a covariate. This would allow the model to adapt to the informativeness of recent queries, potentially tightening prediction intervals during periods of rapid learning.

Beyond the cipher sequence, the adversary may obtain side-channel information. For example:

• •

  Timing information revealing query complexity

• •

  Access patterns indicating document relevance

• •

  External knowledge narrowing the plaintext space

Such events could be modeled as intervention variables or structural breaks. For instance, if the adversary learns that cipher $c^{\prime }$ maps to a subset $𝕎\subset 𝕏$, this constitutes an information gain equivalent to reducing the entropy of the plaintext distribution. Dynamic regression could incorporate indicator variables for such events, allowing the model to capture sudden jumps in adversary accuracy.

The pure ARIMA$(1,1,2)$ model provides reasonable short-term forecasts and has the virtue of simplicity. However, it lacks theoretical grounding: ARIMA with drift predicts unbounded growth, eventually yielding impossible values (${\pi }_t>1$).

The logarithmic regression model (${\pi }_t={\beta }_0+{\beta }_1\log t+{\eta }_t$) better reflects the expected learning dynamics. While it also lacks an asymptote (eventually predicting ${\pi }_t>1$ after approximately $1.5\times {10}^{15}$ observations), this occurs far beyond any practical time horizon. The logarithmic form approximates the saturation behavior of adversary learning reasonably well over finite horizons.

Consider a security threshold ${\pi }^{\ast }=0.44$. Using our models, we estimate the critical time $T^{\ast }$ at which confidentiality falls below this threshold. Figure 12 shows ${\widehat{T}}^{\ast }$ as a function of ${\pi }^{\ast }$.

For ${\pi }^{\ast }=0.44$, we estimate ${\widehat{T}}^{\ast }\approx 20000$, suggesting password reset should occur before 20,000 queries to maintain the threshold.

However, the 80% prediction intervals are substantially more conservative, sometimes recommending near-immediate password reset. This conservatism limits practical utility: overly frequent resets impose costs on users and administrators.

The wide prediction intervals indicate substantial forecast uncertainty. This may stem from model misspecification or from genuine stochasticity in the adversary’s learning process. As discussed in Section 8, incorporating covariates (information content of queries, side-channel events) could reduce uncertainty and improve forecast accuracy.

Alternative model formulations (Gompertz curves, logistic growth models) that explicitly impose asymptotic bounds merit investigation. Such models would better respect the theoretical constraint ${\pi }_t\in [0,1]$ and might yield more realistic long-term forecasts.

Despite these limitations, our analysis demonstrates that time series methods can provide quantitative guidance for encrypted search security policies, enabling data-driven decisions about system reinitialization timing.