Efficient Ranking, Order Statistics, and Sorting under CKKS

on YouTube ↗16m

" summary

Presents an algorithmic redesign for ranking, order-statistics, and sorting under CKKS that replaces swap-based methods with a SIMD re-encoding so one comparison reveals all pairwise relations, achieving a comparison depth of 2 and costing only O(log N) homomorphic rotations. Reports concrete timings: rank 128 elements in 5.76s, argmin/argmax in 12.83s, sort 128 elements in 78.64s. Fits in one ciphertext up to sqrt(slots); multi-ciphertext mode scales with parallel cores.

AI-written summary · about

" chapters (9)

1. 0:00Homomorphic encryption and CKKS
2. 1:59CKKS operations and comparison
3. 4:06Plaintext limits under CKKS
4. 5:51Reduce comparison depth
5. 6:54Encrypted matrices in CKKS
6. 8:19Ranking algorithm implementation
7. 11:56Vector size limits in CKKS
8. 13:23Performance comparison
9. 14:26Real-world use cases

" related talks

• 01h 06mAlgorithms for the k-List ProblemsElena Kirshanova · Lattices: Geometry, Algorithms and Hardness 2020
• 52mFaster, Smaller, Weaker, DarkerBenedikt Bunz · Proofs, Consensus, and Decentralizing Society Reunion 2020
• 57mAlgorithms for Lattice Problems, in PracticeElena Kirshanova, Pierre-Alain Fouque · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 08mCryptography from Ideal LatticesDamien Stehlé · The Mathematics of Modern Cryptography
• 20mBenchmarking RISC-V Post-QuantumMarkku-Juhani O. Saarinen · RISC-V Summit North America 2023
• 52mAn LLL Algorithm for Module LatticesAlice Pellet-Mary · Lattices: Geometry, Algorithms and Hardness 2020
• 57mEssentially Optimal Interactive Certificates in Linear AlgebraErich Kaltofen · Geometric Complexity Theory 2014
• 41mReducibility and Statistical-Computational Gaps from Secret LeakageGuy Bresler · Computational Phase Transitions (Simons Institute, 2020)