Sachverhalt: A. In der Nacht vom 11. auf den 12. Februar 2006 brannte das Restaurant Q._ in U._. Die Staatsanwaltschaft des Kantons Bern erhob am 3. März 2015 Anklage gegen Z._ wegen Brandstiftung und Gehilfenschaft zum Betrug. Das Kantonale Wirtschaftsstrafgericht sprach Z._ am 18. Januar 2016 vom Vorwurf der Gehilfenschaft zum Betrug frei und verurteilte ihn wegen Brandstiftung zu einer bedingten Freiheitsstrafe von 22 Monaten. Gleichzeitig befand es über die Zivilklage der Gebäudeversicherung des Kantons Bern. Dagegen erhoben Z._, die Staatsanwaltschaft und die Gebäudeversicherung des Kantons Bern Berufung. B. Das Obergericht des Kantons Bern erklärte Z._ am 15. September 2017 der Brandstiftung und der Gehilfenschaft zum Betrug schuldig. Es bestrafte ihn mit einer bedingten Freiheitsstrafe von 19 Monaten. Gleichzeitig hiess das Obergericht die Zivilforderungen der Gebäudeversicherung des Kantons Bern in der Höhe von Fr. 775'000.-- gut. C. Z._ führt Beschwerde in Strafsachen. Er beantragt, er sei freizusprechen. Ihm sei eine Genugtuung von mindestens Fr. 5'000.-- sowie eine Aufwandsentschädigung in der Höhe von Fr. 1'000.-- zulasten des Kantons Bern zuzusprechen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Für das bundesgerichtliche Verfahren sei ihm die unentgeltliche Rechtspflege und Verbeiständung zu gewähren. D. Das Obergericht und die Generalstaatsanwaltschaft des Kantons Bern verzichten auf eine Vernehmlassung. Die Gebäudeversicherung des Kantons Bern beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Z._ replizierte.