Nothing Up My Sleeve Lim-Lee Primes A few days ago I asked a question about the security of the Lim-Lee Prime Generation algorithm used by GNU Privacy Guard’s libgcrypt library.  L. Carvalho provided a good answer to that question.  

As a follow up question, I am wondering whether one could use Lim-Lee Prime Generation as a means of creating a “Nothing Up My Sleeve” prime for use in Diffie-Hellman key exchanges? 

It seems to me that if one wanted a 2048-bit prime (p) with no prime (other than 2) dividing p-1 less that 256 bits in length then by choosing a set of maximum prime divisors of p-1 that give a prime p, one would have a good construction of unique, "Nothing up my Sleeve" (NUMS) numbers for a given prime size and prime order subgroup size.  

I'm thinking that for a 2048-bit Lim-Lee Prime (p), p-1 could be divisible by 2, the largest 255-bit prime, and the 7 largest 256-bit primes such that p is prime. That would be unique – right?
While I agree that there exists a largest Lim-Lee prime I think it may be computationally infeasible to construct/find this prime in a provable way.  The set of 256-bit primes is very large and you would need to search through every product of 7 such primes to find the greatest such product that makes the resulting number a prime.

You could add an additional though rather artificial constraint to make the problem tractable.  You could say that you want to look at products of 7 primes chosen from the 20 largest 256-bit prime and choose the largest such product such that when multiplied by 2 times the largest 255-bit prime (2^255 - 19) and added to 1 the result is a prime number.

There are 20 choose 7 or 77520 products of 7 primes to look at. One would expect there to be many primes formed from these products.

Your criteria for the NUMS prime would be:


Pick the size of the prime.  This size is chosen to make the cost of the Number Field Sieve Discrete logarithm prohibitively high
Pick the size of the sub-primes in the Lim-Lee algorithm.  The base 2 log of this size should be twice the desired security strength.  For 128-bits of security one should use 256-bit primes.  For n bits of security one should use primes of 2n bits.
Pick the size (n) of the set of primes to examine. Given the size of the desired prime (a), the size of the sub-primes (b), c = the greatest integer less than (a/b)-1, you choose n such that n choose c is large enough to expect a prime in the set of putative primes that will be generated.
Choose the n largest primes of size b for the set.


You have then described a family of primes that are unique given choices of 

a = size of the prime

b = size of the sub-primes

c = size of the pool of primes

With those three constraints you will have a unique result.  For some sets of parameters there will be ZERO primes that satisfy the criteria.
....
Looking back on your question about Lim-Lee primes from several days ago, many people would recommend staying with the original idea of Lim-Lee's algorithm for ephemeral prime generation rather than using fixed NUMS values.  If you were going to use a NUMS value you might consider using a 3072-bit prime to give an extra hedge against rich adversaries.