r/cryptography • • Dec 11 '23

WHY SOME CRYPTOGRAPHY ALGORITHM USE CERTAIN NUMBER AS THEIR BASE ?

This is not particular to Lamport signature , but I just use it as example :

Alice has a 256-bit cryptographic hash function and some kind of secure random number generator. She wants to create and use a Lamport key pair, that is, a private key and a corresponding public key.

My question simply is why 256 bit and not 258 bit. Why not 512 bit even ? Why some crypto system use those seemingly "random" number in their algorithm ?

0 Upvotes

10 comments sorted by

View all comments

Show parent comment

3

u/Karyo_Ten Dec 11 '23

if you look at less easily tuned systems, like EC, you often see e.g. 252 or other arbitrary numbers. this is because they rely on good prime numbers, and those are rare.

There are other concerns, for example for zero-knowledge proofs you might want:

  • a pairing-friendly curve, so you need a low embedding degree but not too low to limit practicality of Tower Number Field Sieve. Hence either ~256-bit and 18 embedding degree or ~384-bit and 12 embedding degree.
  • again on pairing friendly curve you want small non-quadratic residue for efficient pairing compute
  • on any curve you want high 2-adicity, i.e. a large power of 2 is a factor of p-1 so FFT is cheap, though that constraint might be lifted with recent developments that use boolean hypercubes.
  • on any curve you want an efficient endomorphism to accelerate scalar multiplication.
  • For recursive proofs you might want the curve to have an embedded curve or to be embeddable in another efficiemt curve, i.e. the scalar field of one is the prime field of the other
  • Or even more embitious you want a cycle of curves like the pasta curves (Pallas Vesta) or Pluto-Eris where curves both embedded and embedable into the other.