Theorem 6.3 — Full lattice recovery from short-shell samples
OpenZLIPPadding.Padding.Supplement.short_shell_recoveryAssume and integer . Given a rational input basis of and independent exact uniform samples from , one uniform randomized oracle program solves full ZLIP for every . The same program and uniform polynomial bounds work for every automorphism-invariant shell law with :
Time and samples are polynomial in , with polynomial witnesses fixed before all inputs, laws, and error parameters. Returned bases are verified exactly; unsuccessful executions report failure. The representation gives exact integer coordinates relative to the supplied basis and no hidden factors, profiles, or shell classifier. This companion theorem brings the earlier moment, counting and classification results together without altering the padding goal.
Differences from the source:
- encoding: uniform or invariant short-shell sampling with polynomial recovery → one finite coordinate-output program with uniform polynomial witnesses and dyadic failure-budget input; reason: this retains both law classes, every real error target and the full lattice-basis conclusion
import Definitions.Def_ZLIPPadding_Padding_Supplement_Reductions
namespace ZLIPPadding.Padding.Supplement open scoped BigOperators ENNReal theorem short_shell_recovery : ShellRecovery := by sorry end ZLIPPadding.Padding.Supplement