Sachverhalt: Sachverhalt: A. Y._ mietete unter seiner Firma A._ Büroräumlichkeiten in Basel. Per 1. August 2000 wurden diese Mietlokalitäten an die Firma B._ untervermietet. Nach neun Monaten kündigte X._, Inhaber der Firma B._, das Mietverhältnis auf Ende April 2001. Unmittelbar vor Rückgabe des Mietobjekts erlaubte X._ seinem Sohn und dessen Cousine, Graffiti an den Wänden der bereits geräumten Büroräumlichkeiten anzubringen. Am 4. Mai 2001 erstattete Y._ Strafanzeige wegen Sachbeschädigung gegen Unbekannt. Nach Bekanntwerden der Urheberschaft der Wandbemalungen stellte er am 15. Februar 2002 Strafantrag gegen X._ und machte gleichzeitig eine Entschädigung in der Höhe von Fr. 6'500.-- geltend. Die Graffiti liess er offenbar durch einen seiner Mitarbeiter überstreichen. Am 4. Mai 2001 erstattete Y._ Strafanzeige wegen Sachbeschädigung gegen Unbekannt. Nach Bekanntwerden der Urheberschaft der Wandbemalungen stellte er am 15. Februar 2002 Strafantrag gegen X._ und machte gleichzeitig eine Entschädigung in der Höhe von Fr. 6'500.-- geltend. Die Graffiti liess er offenbar durch einen seiner Mitarbeiter überstreichen. B. Der Strafgerichtspräsident Basel-Stadt verurteilte X._ am 29. Juli 2002 wegen Sachbeschädigung zu einer Busse von Fr. 700.--, bedingt löschbar nach einer Probezeit von einem Jahr, und verwies die Schadenersatzforderung an den Zivilrichter. Das Appellationsgericht des Kantons Basel-Stadt wies am 11. Juni 2003 die gegen den Schuldspruch erhobene Appellation von X._ ab und bestätigte das erstinstanzliche Urteil. Das Appellationsgericht des Kantons Basel-Stadt wies am 11. Juni 2003 die gegen den Schuldspruch erhobene Appellation von X._ ab und bestätigte das erstinstanzliche Urteil. C. X._ führt eidgenössische Nichtigkeitsbeschwerde und beantragt, das Urteil des Appellationsgerichts aufzuheben. Das Appellationsgericht und Y._ schliessen auf Abweisung der Beschwerde. Das Appellationsgericht und Y._ schliessen auf Abweisung der Beschwerde. D. Dem Gesuch um aufschiebende Wirkung der Beschwerde wurde mit Verfügung des Präsidenten des Kassationshofs vom 26. November 2003 stattgegeben.