arXiv:2605.07160v3 Announce Type: replace Abstract: Training neural networks on sensitive data in untrusted cloud environments requires simultaneously achieving computational efficiency and rigorous privacy guarantees. Sparsification techniques, essential for scalable training of wide layers, expose input-dependent memory-access patterns that are visible and can be exploited by a host OS/hypervisor, even when computation is protected by a Trusted Execution Environment. We present TENNOR, a system that resolves this tension by co-designing the neural network training pipeline with doubly oblivious primitives, eliminating value-dependent neural network access-pattern leakage while also utilizing adaptive sparsification. TENNOR recasts sparse neuron activation as a locality-sensitive hashing (LSH) retrieval problem, reducing secure sparsification to doubly oblivious accesses over an LSH data structure. To eliminate the prohibitive storage cost of "multi-table" LSH, we introduce Multi-Probe Winner-Take-All (MP-WTA): the first multi-probe scheme for rank-based LSH, achieving a $50\times$ reduction in (hash table) memory while preserving model accuracy. We evaluate TENNOR on multi-label classification benchmarks, with output layers of up to hundreds of thousands of neurons under different batch sizes inside an Intel TDX Trusted Domain, achieving per-batch training speedups of $13\times$-$470\times$ over a Path ORAM baseline and reducing a 208-hour run to about 26 minutes.