Field security origin?

[Nashtare]

In the conjectured security evaluation, we have:
let field_security = field_size - lde_domain_size.trailing_zeros();
( i.e. $\lambda \leq \log_2(\mathbb{K}) - \log_2(D)$ ) which bounds the security level of a given STARK proof by the bit size of the extension field on which we operate minus the bit size of the execution trace (after extension).
This conflicts with the conjectured security formulae given in EthSTARK paper, page 40, where for the field security we only consider the size of the extension field.

I was then wondering where this $- \log(D)$ was coming from? Would it have a link with the much more complex formula for proven security?

If that is the case, then wouldn't it make sense to stick to the "conjectured field security" estimate for the conjectured security level?

[irakliyk]

The formula came from item 3 of Measuring Security section in ethSTARK repo. There, the formula uses log2(trace_length) rather than log2(lde_domain_size). For Winterfell, log2(lde_domain_size) was used to be a bit more conservative (though, I don't have a strong reasoning for this).

It does appear as if the formal on Github contradicts the formula in the paper - but maybe I'm missing something?

[Nashtare]

Sorry I had completely forgotten about the issue. The reason why I asked this originally is because I realized that plonky2 was following the ethSTARK paper approach instead, which considers solely the extension field size for the field security. With the Goldilocks field, this allows to keep a quadratic extension while aiming at up to 128 bits of security, instead of a cubic one. Miden could benefit from this as RPO has 127 bits collision resistance, if the project was to target such security levels in the future. I'll try investigating this further when I have some free time.

[Nashtare]

After wrapping my head around it for some time, I believe that (for the conjectured security case), we don't need any check on the field security portion, else than the extension field size.

The mention on ethstark codebase doesn't match the proof associated to the toy problem security evaluation in the paper (which serves as basis for the conjecture). The proof is straightforward to understand. In addition, they don't even apply it in the codebase (although it may be because their extended field size is 122 for a two-adicity of 32 and a targeted security level of 80 bits, so even applying with the worst case scenario would still stay within desired bounds).

Removing this additional requirement from winterfell would allow proofs to achieve for instance up to 127 bits of security with f64 and a quadratic extension. Note that it seems every project, including STARKWARE, considers the conjectured security estimate as opposed to the proven one.

I noticed there is a TODO associated to the proven security estimate. I can take care of it if wanted (the requirements are heavy though with this target).

[Nashtare]

Another approach for the conjectured security case could be to leave it as is, if we lack confidence on the conjecture, to have a model closer to some extent to the proven security. Although I don't think this alone makes much sense as for regular set of parameters, the security loss would be much more consequent on the FRI side and the number of queries.