I have been reading some papers on cryptography based on multivariate systems and I have a question. How does one relate the difficulty of calculating Gröbner basis (GB) of a multivariate system with its degree of regularity?
From what I understand, for a lot of cryptosystems, there are ways of getting a system of polynomial equations, and a solution for such a system will give us the secret key (let us suppose this is unique). Once we have such a system, we can 'linearize' and solve them (like in Arora-Ge) or we can attack the system by calculating its GB and finding the root from there.
From Bardet's paper, for semi-regular systems, there is a quantity called a degree of regularity (there is also a way to calculate it) and she also gives how to estimate the difficulty of GB calculation using this quantity.
My question is: what if we don't know if our system is semi-regular? This degree of regularity seems to be roughly the highest degree term in the GB. If so, how can I estimate the highest degree term of the GB of a system of polynomials that I have in my hand?
There seem to be a few papers which go into any sort of detail in these topics, so I will be glad if I could also get some papers to read.