One-Pass Oblivious Bootstrap for Serial Mediation Inside Secure Enclaves

Serial mediation analysis asks whether a cause $X$ affects an outcome $Y$ through an ordered chain of intermediate variables. For example, it asks whether vision impairment worsens sleep, sleep worsens psychological health, and psychological health in turn lowers cognition. The data behind such chains are sensitive individual records: health surveys, psychiatric scales, genomic covariates. A natural place to analyze them on shared cloud hardware is a secure enclave, a hardware-isolated region of memory that the host operating system cannot read. Enclaves have two well-documented weaknesses. Their protected memory is small, and exceeding it causes sharp slowdowns. The host can also still watch which memory pages are touched, and that access pattern can reveal data. The standard statistical practice of drawing 5,000 to 10,000 bootstrap resamples to get a confidence interval for the chained indirect effect is badly suited to both weaknesses. Each resample reads records at random indices, which leaks through the access pattern, and holding many resamples at once exhausts protected memory.

Our claim is that this collision largely disappears once the problem is restated, and that doing so exposes a sharper question than "port the statistics tool into an enclave." Serial mediation with linear links depends on the data only through one joint cross-product matrix (the sum over records of each row's outer product with itself). A bootstrap replicate can be produced by giving every record a random count drawn inside the enclave (a Poisson bootstrap) rather than by fetching resampled indices. Combining the two, all $B$ replicates can be accumulated during a fixed sequential scan of the encrypted data. That scan touches memory in exactly the same order whatever the data contain, so no oblivious shuffle is needed. The open problems that remain are of a different kind. The first is a memory-versus-passes trade-off, because the $B$ replicate accumulators, not the data, are what outgrow the enclave. The second is statistical: whether Poisson-weighted percentile intervals for the product $a_1 d_{21} b_2$ keep the coverage that practitioners rely on multinomial resampling for. The third is whether a cheaper one-pass Monte Carlo interval would do just as well.

What exists and what is missing

On the enclave side, the performance problem is established. SecureCloud reports a slowdown of nearly 18x when a routing database grew from within the 128 MB protected-memory limit to 200 MB. PRESAGE packs genomic records compactly so that lookups run about 120x faster than homomorphic encryption. Both papers motivate the proposal, but neither does statistical estimation. Two lines of work avoid paging by touching only what is needed: HardIDX pulls index nodes on demand, and Kato et al. chunk trajectory data. We borrow their streaming stance. MAGE plans page movement offline for computations whose access pattern is known in advance, and gets within 15% of an in-memory run for garbled circuits and homomorphic encryption. Its authors suggest enclaves as future work. We reuse its planning idea in a much simpler form, because our access pattern is a fixed sequence of scans.

On leakage, Ding et al. fit counting, histogram and heavy-hitter analytics into enclave memory with oblivious sketches, but stop at descriptive statistics. Sasy et al. show that non-oblivious sampling inside an enclave breaks privacy amplification: privacy loss on DP-MNIST rises from 0.82 under oblivious Poisson sampling to 9.39 under naive shuffling. They build oblivious minibatch samplers for training. Oblivious Stash Shuffle permutes $N$ items obliviously with $O(\sqrt N)$ private memory, for example 100 million items with 3,000 buckets and a 117,000-item stash. These two papers supply the strongest competing design: an oblivious multinomial bootstrap assembled from oblivious sampling or shuffling. We argue that design is unnecessary for linear path models. Enclave decision-support systems (Marangone et al., Enabling decision support over confidential data) address integrity of high-level queries, not memory or inference.

On the statistics side, the applied literature fixes the target. Studies such as Yu et al. on 10,884 Health and Retirement Study (HRS) respondents, Wang et al. and Zheng et al. all fit the recursive system $M_1 \sim X$, $M_2 \sim X + M_1$, $Y \sim X + M_1 + M_2$ with covariates, and judge the sequential effect $a_1 d_{21} b_2$ by bootstrap percentile intervals, as the PROCESS "Model 6" macro does. CauSciBench is a reminder that getting the estimator right is itself nontrivial: automated pipelines reach only 45.8% method correctness on real studies. That result constrains the proposal to match established practice rather than invent new estimators.

Core Claim

Let $z_i = (1, C_i, X_i, M_{1i}, M_{2i}, Y_i)$ be record $i$'s row, with $P$ covariates $C_i$. Each of the three regressions uses a sub-block of the single matrix $G = \sum_i z_i z_i^\top$, which has dimension $(P+4)\times(P+4)$. Any linear path estimate, including $a_1 d_{21} b_2$ with or without covariates, is therefore a deterministic function of $G$. A Poisson bootstrap replicate $b$ replaces $G$ with

$$G^{(b)} = \sum_{i=1}^{N} w_i^{(b)} z_i z_i^\top, \qquad w_i^{(b)} \sim \text{Poisson}(1),$$

where the weights $w_i^{(b)}$ come from a pseudorandom generator keyed inside the enclave and are never stored. Records are read in a fixed order and every replicate is updated for every record, including when a weight is zero. The page and cache-line trace is then a function of $N$, $P$ and $B$ alone. Arithmetic is done in fixed point or with subnormal handling disabled so that timing does not depend on values. The binding resource becomes the $B(P+4)(P+5)/2$ stored accumulator entries. With $B = 5{,}000$ and $P = 20$ this is about 13 MB in double precision, which fits easily. With $P = 100$ it is about 230 MB, which does not fit a 128 MB budget. Genomic principal components, rich clinical covariates or site indicators push $P$ into this range. The enclave then holds $B_k$ replicates at a time and rescans the encrypted data $\lceil B/B_k \rceil$ times. Because the whole schedule is known in advance, choosing $B_k$ against the measured scan cost and memory budget is a small offline plan in the spirit of MAGE, not a demand-paging problem.

Research Program

The work has three parts. The first is systems work. We will implement the streaming accumulator in an SGX enclave, with records encrypted in untrusted memory and decrypted one block at a time. We will add the pass planner, and a leakage harness that records the host-visible page-fault and access trace. Oblivious code sometimes leaks through overlooked branches, so we will not rely on the design argument: we will check empirically that traces for pairs of datasets with identical shape but different values are bit-identical.

The second part is statistical. The Poisson bootstrap is asymptotically equivalent to multinomial resampling, but serial mediation practice relies on bootstrap intervals precisely in the regime where asymptotics are weak. That regime is products of three coefficients near zero, where the product's distribution is most skewed, at moderate $N$. We will measure coverage and interval-endpoint agreement directly. We will also extend to the bias-corrected percentile interval PROCESS reports. That extension needs the full-sample estimate, which a separate pass or the same pass provides.

The third part is a boundary case. When $Y$ is binary, logistic links break sufficiency. We will test a one-step linearized bootstrap: the full-sample fit takes a few oblivious passes of iteratively reweighted least squares, and one Newton step per replicate adds one more pass. We will report where its coverage fails rather than assume it holds.

Baselines

The naive reference point is the standard workflow run unmodified inside the enclave. The same serial-mediation code (a PROCESS-Model-6-equivalent implementation with multinomial resampling) runs under the enclave's default demand paging with an identical memory budget and $B$. This shows what practitioners would get today. We expect a paging collapse of the kind SecureCloud reports, nearly 18x past the 128 MB limit, along with an index-dependent access trace. Beating it means lower wall-clock time and a data-independent trace. Its intervals should be identical in distribution to ours, and that is the point of comparison.

The accuracy reference is the same multinomial bootstrap run in plaintext outside any enclave, with $B = 10{,}000$ and the same covariates. Its intervals serve as ground truth for endpoint agreement. It is not a security competitor.

The strongest existing secure method is an oblivious multinomial bootstrap assembled from prior primitives. Each replicate draws its resample obliviously, using the sampling routines of Sasy et al. or a permutation from Oblivious Stash Shuffle, and then streams the resample into the same regression code. It runs on the same hardware, data, memory budget and $B$, with its bucket and stash parameters tuned to the budget. No reported result was found on Lacuna for an oblivious bootstrap of mediation or regression coefficients. The nearest reported figures are Sasy et al.'s privacy loss of 0.82 versus 9.39 on DP-MNIST and the Stash Shuffle's configuration for 100 million items with failure probability $2^{-81.9}$, neither of which is a bootstrap runtime. Beating this baseline means matching its interval quality with at least an order of magnitude less time. That gap is expected, because it pays for $B$ oblivious shuffles where we pay for $\lceil B/B_k\rceil$ linear scans, and because it has no nonzero abort probability.

The strongest cheap statistical competitor is a Monte Carlo interval computed from a single pass. It estimates the path coefficients and their covariance, using both classical and heteroscedasticity-robust sandwich forms (the latter takes a second pass for residual-weighted cross-products). It then simulates $a_1 d_{21} b_2$ from the implied joint normal. A delta-method (Sobel-style) interval is included as the normal-theory reference.

Two ablations isolate the key ingredients. The first keeps Poisson weighting but reads records at data-dependent positions, for example by skipping zero-weight records. This shows that obliviousness comes from the fixed scan, and quantifies what skipping would save. The second replaces the single joint matrix $G$ with separate per-equation accumulators and replaces the planned batch schedule with demand paging of the accumulators. This isolates the memory contribution of the nesting and of the plan.

Why not just…?

Why not just use a newer enclave with more protected memory and let paging handle the rest? For small studies this is a fair answer on speed, and we will say so. At HRS scale with few covariates, even the naive baseline may fit. It does not answer leakage. Resampling by index produces a data-dependent trace however large the memory, and Sasy et al. show such traces undo the guarantees analysts assume. We will sweep the memory budget in the experiments so that the speed benefit is reported as a function of budget and $P$, not asserted.

Why not just use homomorphic encryption or multi-party computation and avoid trusting hardware? Those systems remove the hardware trust assumption, which is a real advantage. The file's evidence is that they are far slower and expand memory: PRESAGE was about 120x faster than homomorphic encryption, and MAGE cites a 128x data expansion for garbled circuits. Five thousand encrypted weighted regressions would multiply that cost. We treat this as a different trust model and do not benchmark it head to head.

Why not just adapt existing oblivious sampling or shuffling to draw bootstrap resamples? This is the obvious design, and it is secure. It is the strongest secure baseline above. Its cost scales with the number of replicates times an oblivious shuffle, and it inherits stash-overflow aborts. Our argument is that for linear links the resample never needs to be materialized. The head-to-head runtime and coverage comparison settles whether that argument survives contact with real hardware.

Why not just skip the bootstrap and use a normal-theory or Monte Carlo interval from one pass? The Sobel test is known to be poorly calibrated for products of coefficients, which is why the applied studies above use bootstrap intervals. The Monte Carlo interval is a genuine threat, though. It needs one or two passes and trivial memory, and it may match bootstrap coverage in many settings. We will test it under heteroscedastic, skewed-error and small-$N$ conditions. If its sandwich variant matches bootstrap coverage everywhere we test, we will report that as the main practical finding: enclave-based serial mediation should use Monte Carlo intervals, and our bootstrap engine would be needed only where Monte Carlo fails.

Proposed Experiments

The simulation study generates serial-mediation data with known $a_1, d_{21}, b_2$ spanning null, small and moderate sequential effects. We vary $N$ from 200 to $10^6$, $P$ from 5 to 200, and error distributions from homoscedastic Gaussian to heteroscedastic and skewed. The primary metrics are interval coverage of $a_1 d_{21} b_2$ at nominal 95%, interval width, endpoint difference from the plaintext multinomial bootstrap, wall-clock time, protected-memory page faults and number of passes.

The real-data check reconstructs the vision-impairment chain of Yu et al. on HRS. The authors report a total effect of $\beta = -0.986$ on 10,884 respondents, with the sequential path carrying 6.6% of it. Our variable construction will only approximate theirs, so these figures serve as a sanity check. The binding comparison is against our own plaintext bootstrap on identical variables. We then enlarge $P$ with additional covariates to cross the memory budget. A CHARLS-based chain, following the cohort used in the stroke mediation study, provides a second population.

The decisive checks are four. The access traces must be identical across value-perturbed datasets. The Poisson intervals must be within Monte Carlo error of plaintext multinomial intervals in coverage, especially for near-null products at $N$ in the low hundreds. The planned multi-pass schedule must stay within a small constant of an unconstrained-memory run as $P$ crosses the budget, while the demand-paging ablation collapses. Finally, the Monte Carlo sandwich interval either does or does not match bootstrap coverage in the hard regimes, and that result determines whether the bootstrap engine is the recommended tool or only a fallback.