How to Withstand Mobile Virus Attacks, Revisited

Parties communicate synchronously over perfectly secure point-to-point channels and broadcast, erase old state, and alternate operation with refreshment stages.

1. threat model

   Active adaptive mobile adversary

   defined

   The adversary may adaptively corrupt different parties over time, but at most the stated threshold per stage; a party corrupted during a refresh counts in both adjacent stages.

   Proactive UC model, phases, erasures, and baseline parameters · Exact proactive UC execution and security definitions
2. assumption

   Reboot and erasure assumptions

   assumed

   Corrupted parties can be rebooted to a pristine state with global computation information and secure-channel access, and honest-period randomness and erased state remain unrecoverable; selecting whom to reboot is outside the protocol.

   Problem, roadblocks, contributions, and headline bounds · Proactive UC model, phases, erasures, and baseline parameters

The protocol composes packed sharing, proactive redistribution, circuit normalization and permutation, per-layer arithmetic, and party virtualization.

1. component

   Packed proactive secret sharing

   specified and proved

   Multiple secrets occupy evaluation points of one polynomial; random masking polynomials and hyper-invertible matrices amortize refresh and checking to O(1) communication per secret.

   Problem, roadblocks, contributions, and headline bounds · Packed sharing and Block-Redistribute
2. component

   Block-Redistribute

   specified and proved

   Three phases rerandomize packed sharings, verifiably double-share state, and reconstruct current shares for rebooted parties using Berlekamp-Welch recovery.

   Packed sharing and Block-Redistribute · Redistribution and PMPC proof chain
3. component

   Layer-by-layer PMPC

   specified and proved

   Inputs are robustly shared; secrets are permuted for each homogeneous addition or multiplication layer; obsolete state is erased; all live sharings are redistributed after every layer before final reconstruction.

   Layer-by-layer PMPC protocol and complexity

The paper states UC-security and communication bounds under explicit network, erasure, circuit-width, and corruption-rate conditions.

1. claim

   Redistribution theorem

   proved conditional

   Theorem 1 states perfect UC realization of the redistribution functionality against adaptive corruption threshold n/8, assuming secure point-to-point and broadcast channels, with O(W + poly(n)) communication for W secrets.

   Packed sharing and Block-Redistribute · Redistribution and PMPC proof chain
2. claim

   Base PMPC theorem

   proved conditional

   For an n-party arithmetic circuit at least Ω(n) gates wide, Theorem 2 gives perfect proactive UC security against an active adaptive adversary corrupting fewer than n/8 parties per stage.

   Perfect and statistical proactive-security theorems · Redistribution and PMPC proof chain
3. claim

   Virtualized thresholds

   proved conditional

   Theorem 3 raises perfect security to any constant corruption fraction δ < 1/3, while the statistical variant in Theorem 12 supports δ < 1/2.

   Perfect and statistical proactive-security theorems · Party virtualization and near-optimal thresholds
4. claim

   Near-linear communication

   analytically supported

   The final virtualized construction is reported with communication O(C log² C polylog n + D poly(n) log² C), where C and D are circuit size and depth; packed share maintenance is constant amortized per secret.

   Problem, roadblocks, contributions, and headline bounds · Layer-by-layer PMPC protocol and complexity

The source supplies ideal functionalities, explicit protocols, complexity derivations, simulators for redistribution, an inductive PMPC simulation, and committee-based threshold amplification.

1. evidence

   UC proof structure

   paper proof not machine checked

   The appendices compare real and ideal executions, construct simulators, and use layer induction plus prior subprotocol security; this audit checked statement/assumption alignment but did not rederive every simulation step.

   Redistribution and PMPC proof chain

The guarantees rely on synchrony, secure channels, broadcast, erasures, reliable pristine reboot, stage-rate enforcement, and sufficiently wide arithmetic circuits.

1. limitation

   Recovery mechanism is external

   assumed

   The paper does not specify how compromise is detected, how parties are selected and securely rebooted, or how proactive PKI/secure channels and broadcast are implemented.

   Problem, roadblocks, contributions, and headline bounds · Proactive UC model, phases, erasures, and baseline parameters
2. limitation

   No implementation evaluation

   no empirical evaluation

   Evidence is theoretical; the audited version does not provide code, benchmarks, network measurements, or concrete parameter sizing.

   Layer-by-layer PMPC protocol and complexity