Fast sorting networks, branchless by design
3 months ago
- #computer-science
- #algorithms
- #cryptography
- 排序是计算机科学中的关键问题，性能是大多数应用的核心考量因素。
- 传统排序算法如快速排序、归并排序和pdqsort容易受到时序侧信道攻击，可能导致敏感数据泄露。
- 排序网络通过提供固定操作序列来解决这个问题，使其具有数据无关性并能抵抗时序攻击。
- 冒泡排序是简单排序网络的代表，但对大型数据集效率低下。
- 奇偶置换排序通过引入并行性改进了冒泡排序，但仍保持O(n²)的时间复杂度。
- 双调序列和Batcher双调排序提供了更高效的O(n log²n)复杂度方案，使其适用于密码学应用。
- 由Daniel J. Bernstein开发的djbsort实现了Batcher排序网络，并针对速度、恒定时间执行和形式化验证进行了优化。
- Zig语言实现的djbsort相比传统排序算法展现出显著性能提升，尤其对原生数值类型和SIMD优化场景。
- djbsort中的浮点数排序采用巧妙的位操作技术建立全序关系，保持接近整数排序的性能。
- 尽管排序网络理论复杂度更高，但在实际应用中（尤其是安全敏感场景）可能超越传统排序算法。