A Performant, Misuse-Resistant API for Primality Testing. / Massimo, Jake; Kenneth G. Paterson.

Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security 2020. 2020.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Forthcoming

Standard

A Performant, Misuse-Resistant API for Primality Testing. / Massimo, Jake; Kenneth G. Paterson.

Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security 2020. 2020.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Harvard

Massimo, J & Kenneth G. Paterson 2020, A Performant, Misuse-Resistant API for Primality Testing. in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security 2020. https://doi.org/10.1145/3372297.3417264

APA

Massimo, J., & Kenneth G. Paterson (Accepted/In press). A Performant, Misuse-Resistant API for Primality Testing. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security 2020 https://doi.org/10.1145/3372297.3417264

Vancouver

Massimo J, Kenneth G. Paterson. A Performant, Misuse-Resistant API for Primality Testing. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security 2020. 2020 https://doi.org/10.1145/3372297.3417264

Author

Massimo, Jake ; Kenneth G. Paterson. / A Performant, Misuse-Resistant API for Primality Testing. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security 2020. 2020.

BibTeX

@inproceedings{0df297a8e4e549dd85c19e0ef754d089,
title = "A Performant, Misuse-Resistant API for Primality Testing",
abstract = "Primality testing is a basic cryptographic task. But developers today are faced with complex APIs for primality testing, along with documentation that fails to clearly state the reliability of the tests being performed. This leads to the APIs being incorrectly used in practice, with potentially disastrous consequences. In an effort to overcome this, we present a primality test having a simplest-possible API: the test accepts a number to be tested and returns a Boolean indicating whether the input was composite or probably prime. For all inputs, the output is guaranteed to be correct with probability at least 1 - 2^{-128}. The test is performant: on random, odd, 1024-bit inputs, it is faster than the default test used in OpenSSL by 17%. We investigate the impact of our new test on the cost of random prime generation, a key use case for primality testing. The OpenSSL developers have adopted our suggestions in full; our new API and primality test are scheduled for release in OpenSSL 3.0. ",
keywords = "Primality testing, Prime generation, Miller-Rabin, Lucas, Baillie-PSW, API",
author = "Jake Massimo and {Kenneth G. Paterson}",
year = "2020",
month = aug,
day = "18",
doi = "10.1145/3372297.3417264",
language = "English",
booktitle = "Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security 2020",

}

RIS

TY - GEN

T1 - A Performant, Misuse-Resistant API for Primality Testing

AU - Massimo, Jake

AU - Kenneth G. Paterson

PY - 2020/8/18

Y1 - 2020/8/18

N2 - Primality testing is a basic cryptographic task. But developers today are faced with complex APIs for primality testing, along with documentation that fails to clearly state the reliability of the tests being performed. This leads to the APIs being incorrectly used in practice, with potentially disastrous consequences. In an effort to overcome this, we present a primality test having a simplest-possible API: the test accepts a number to be tested and returns a Boolean indicating whether the input was composite or probably prime. For all inputs, the output is guaranteed to be correct with probability at least 1 - 2^{-128}. The test is performant: on random, odd, 1024-bit inputs, it is faster than the default test used in OpenSSL by 17%. We investigate the impact of our new test on the cost of random prime generation, a key use case for primality testing. The OpenSSL developers have adopted our suggestions in full; our new API and primality test are scheduled for release in OpenSSL 3.0.

AB - Primality testing is a basic cryptographic task. But developers today are faced with complex APIs for primality testing, along with documentation that fails to clearly state the reliability of the tests being performed. This leads to the APIs being incorrectly used in practice, with potentially disastrous consequences. In an effort to overcome this, we present a primality test having a simplest-possible API: the test accepts a number to be tested and returns a Boolean indicating whether the input was composite or probably prime. For all inputs, the output is guaranteed to be correct with probability at least 1 - 2^{-128}. The test is performant: on random, odd, 1024-bit inputs, it is faster than the default test used in OpenSSL by 17%. We investigate the impact of our new test on the cost of random prime generation, a key use case for primality testing. The OpenSSL developers have adopted our suggestions in full; our new API and primality test are scheduled for release in OpenSSL 3.0.

KW - Primality testing

KW - Prime generation

KW - Miller-Rabin

KW - Lucas

KW - Baillie-PSW

KW - API

U2 - 10.1145/3372297.3417264

DO - 10.1145/3372297.3417264

M3 - Conference contribution

BT - Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security 2020

ER -