Part II of some off-and-on work to quantify just how rigid rigid curves are.
Part I, which needs revision, was here: https://moderncrypto.org/mail-archive/curves/2014/000315.html ## Minimal-cost curve parameters Minimal curve parameters. Let `c(x)` be a cost function, and choose the value of a free parameter `x` such that there does not exist another `x' != x` with `c(x') <= c(x)`. Safe curves. Set `c(x) == \inf` if `#E/h` and `#Et/ht` are not prime, or if some set of safety criteria are not satisfied. Choosing curve parameters. Suppose that we want an Edwards curve; so we have a cofactor != 1. Cofactor choices: - q == 1 mod 4 - h = 2^n, ht = 2^m, n <= 3, m <= 3 - h = 8, ht = 4 - q == 3 mod 4 - h = 4, ht = 4 Curve parameter, *x*: - Proposed: - BLE form, a=-1: d - BLE form, a=+1: d - Montgomery form: A - Possible: - Weierstrass, a=-3: b - For mathematicians, mainly: - Legendre form: lambda - j-invariant Cost functions, *c(x)*: - Proposed: - min(x) - min(abs(x)) - Possible: - min( (hamming(x), x) ) Am I missing any plausible proposals? (This gives 6 proposed methods of choosing Edwards curves for 3 mod 4 primes, and (perhaps) 12 for choosing Edwards curves for 1 mod 4 primes. Perhaps the cofactor requirement is more appropriately handled in a discussion of the rigidity of "safety" definitions...) ## More exotic things that seem possible "Signature-friendly" curves: Require, in addition, that #E/h be pleasant to reduce modulo. (By choosing a sufficiently dense family of reduction-friendly primes, not by CM.) ## "Verifiably random" curve parameters How much less rigid is the choice of "verifiably random" curve parameters? How to sample: - by rejection of candidates of bitlength ceil(log2(q)) - by modular reduction of candidates of bitlength 2*ceil(log2(q)) (And then by rejection of unsafe proposals.) PRF keys: - 0 - {big,little}-endian representation of ceil(log2(q)) - (is anything else plausible if you make a choice before knowing the maximum key-length of the PRF -- i.e., in the equivalent of Rawlsian ignorance?) PRFs: - AES{128,256}-CTR - {ChaCha,Salsa}20 - SHAKE{128,256} (This gives 36 choices for verifiably random curves. This, of course, would need to be multiplied by 6 or 12.) _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
