Soient f1,...,fp des polynômes quadratiques en n variables lacunaires (fewnomials) à coefficients dans un corps K, tels que le système f1 = ... = fp = 0 n'admette pas de solution sur la clôture algébrique de K. On s'intéresse dans cet exposé à une version effective du Nullstellensatz : sous quels conditions sur le support monomial de f1,...,fp existe-t-il probablement des polynômes g1,...,gp ``petits'' tels que f1g1 + ... + fpgp = 1 ? Nous montrerons que lorsque le nombre de carrés dans le support monomial excède n^(1/2+epsilon), que le support est tiré aléatoirement parmi ceux de cardinalité n+k+1 (pour une constante k fixée) et sous des hypothèses de généricité sur les coefficients, il existe des certificats (g1,...,gp) avec le même support monomial que (f1,...,fp) avec probabilité proche de 1, et que ceux-ci peuvent être calculés efficacement. Ce résultat et sa preuve sont fortement reliés à des propriétés combinatoires de graphes aléatoires dans le modèle d'Erdös-Renyi. Nous illustrerons ce résultat par des observations expérimentales et discuterons de ses liens avec le problème de la résolution de systèmes quadratiques lacunaires. Travail commun avec Jean-Charles Faugère et Jules Svartz