This paper presents a new efficient black-box attribution method based onHilbert-Schmidt Independence Criterion (HSIC), a dependence measure based onReproducing Kernel Hilbert Spaces (RKHS). HSIC measures the dependence betweenregions of an input image and the output of a model based on kernel embeddingsof distributions. It thus provides explanations enriched by RKHS representationcapabilities. HSIC can be estimated very efficiently, significantly reducingthe computational cost compared to other black-box attribution methods. Ourexperiments show that HSIC is up to 8 times faster than the previous bestblack-box attribution methods while being as faithful. Indeed, we improve ormatch the state-of-the-art of both black-box and white-box attribution methodsfor several fidelity metrics on Imagenet with various recent modelarchitectures. Importantly, we show that these advances can be transposed toefficiently and faithfully explain object detection models such as YOLOv4.Finally, we extend the traditional attribution methods by proposing a newkernel enabling an ANOVA-like orthogonal decomposition of importance scoresbased on HSIC, allowing us to evaluate not only the importance of each imagepatch but also the importance of their pairwise interactions. Ourimplementation is available athttps://github.com/paulnovello/HSIC-Attribution-Method.