2019 · 87 citations · 20 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureCryptographyCryptographic AlgorithmsCryptographic ComplexityCryptographic ImplementationDeductive VerificationElliptic Curve CryptographyElliptic CurvesArithmetic Of Finite FieldsCryptographic AccelerationCryptographic OperationsElliptic Curve ArithmeticElliptic Curve Cryptography ImplementationFinite Field ArithmeticFunctional CorrectnessPartial Evaluation
We introduce a new approach for implementing cryptographic arithmetic in short high-level code with machine-checked proofs of functional correctness. We further demonstrate that simple partial evaluation is sufficient to transform into the fastest-known C code, breaking the decades-old pattern that the only fast implementations are those whose instruction-level steps were written out by hand. These techniques were used to build an elliptic-curve library that achieves competitive performance for 80 prime fields and multiple CPU architectures, showing that implementation and proof effort scales with the number and complexity of conceptually different algorithms, not their use cases. As one outcome, we present the first verified high-performance implementation of P-256, the most widely used elliptic curve. implementations from our library were included in BoringSSL to replace existing specialized code, for inclusion in several large deployments for Chrome, Android, and CloudFlare.
20
The Design and Implementation of FFTW3
Matteo Frigo, Steven G. Johnson · Proceedings of the IEEE · 2005 · 5.2K citations
SPIRAL: Code Generation for DSP Transforms
Markus Püschel, José M. F. Moura, Jeremy Johnson et al. · Proceedings of the IEEE · 2005 · 829 citations
Simplify: a theorem prover for program checking
David Detlefs, Greg Nelson, James B. Saxe · Journal of the ACM · 2005 · 781 citations
Template meta-programming for Haskell
Tim Sheard, Simon Peyton Jones · 2002 · 548 citations
Translation validation for an optimizing compiler
George C. Necula · 2000 · 487 citations