Best lower bound for proof complexity of graph non-automorphism problem
If GNA is in CoNP, and by certificate you mean any string y such that x is in GNA iff xy is accepted by a deterministic turing machine in polynomial time, then a non-trivial lower bound on the certificate size would imply P!=NP. If P=NP, then CoNP=NP=P and there is a deterministic turing machine that accepts GNA without the need of a certificate, or with a certificate whose size is equal to zero.