Rejection Sampling & Approximate Reconciliation - Paradigms for PKC/PQC.

This is a philosophical observation on various public-key cryptosystems, it's not in my opinion a rule or conjecture, but more of something empirical.

Examples

Data encryption ciphers, that is, symmetric-key systems, are exact, and they should be. But the same isn't necessarily applicable to PKC. That is not to say that PKC don't have correctness requirements, they do, but they achieve it differently.

Take RSA for example, it does in fact need rejection sampling - if one happen to bump into a ciphergram that is a multiply of one of the factors. In this case, RSA-KEM can regenerate key material, and RSA-FDH can regenerate salt for randomized hashing. The key-agreement schemes for Elliptic Curve cryptography are exact, no question here. There are however, steps in ECDSA where nonce is regenerated when r or s are not within the desired range.

SPHINCS+/SLH-DSA are exact, but they can be only securely used for limited number of times, even though scaling up the parameters allowed for faster increase in this limit, and not too drastic increase in communication bandwidth. Kyber/ML-KEM uses approximate reconciliation just as any lattice KEM, still, its occational decryption failure can be considered rejection sampling. Dilithium/ML-DSA literally has an estimated rejection sampling repetition count in its documented parameters, and uses hint for reconciling the dropped bits in the public key.

UOV occasionally encounter digest that is not invertible, hence rejection sampling. I'm not exactly familiar with SQIsign, but on skimming through a few pages, various subroutines within the spec do have the "loop until condition satisifed" compound step blocks, which can be considered rejection sampling.

What this all mean?

Previously, I believed public-key cryptography, are about making inverse operations difficult while making forward operations easy. The RSA trapdoor is exactly this. Elliptic Curves made division difficult, while addition and multiplication remain easy.

But I now have a new perspective, and I'm sharing it for the people that have real inspirations in devising/analyzing public-key cryptosystems. Namely:

You start with a mathematical relation - it doesn't have to be exact, there may be need to provide some kind of "hint" to the deterministic party, and you adjust the parameters, so that the hint is easy to produce for the authorized parties, and eliminate any excess degree of freedom for adversaries to choose these hints arbitrarily. There may be need to retry with different starting conditions, and the parameters should be chosen so that it doesn't take too much effort retrying for the authorized parties.