Fast sorting networks, branchless by design
7 days ago
- #computer-science
- #algorithms
- #cryptography
- Sorting is a critical problem in computer science, with performance being a key consideration for most applications.
- Traditional sorting algorithms like Quicksort, Mergesort, and pdqsort are vulnerable to timing side-channel attacks, which can leak sensitive data.
- Sorting networks offer a solution by providing a fixed sequence of operations, making them data-oblivious and resistant to timing attacks.
- Bubble sort is an example of a simple sorting network but is inefficient for large datasets.
- Odd-even transposition sort improves upon bubble sort by introducing parallelism, though it still has O(n²) complexity.
- Bitonic sequences and Batcher's bitonic sort provide a more efficient approach with O(n log²n) complexity, making them practical for cryptographic applications.
- djbsort, developed by Daniel J. Bernstein, implements Batcher's sorting network with optimizations for speed, constant-time execution, and formal verification.
- A Zig implementation of djbsort demonstrates significant performance improvements over traditional sorts, especially for native numeric types and SIMD optimization.
- Float sorting in djbsort uses a clever bit manipulation technique to impose a total order, maintaining performance close to integer sorting.
- Sorting networks, despite their higher theoretical complexity, can outperform traditional sorts in practice, especially for security-sensitive applications.