Die Rechtmäßigkeit der Verarbeitung ist die Voraussetzung für die Verarbeitung personenbezogener Daten. Auch unter der Datenschutz-Grundverordnung bleibt es also bei dem Prinzip eines Verbotes mit Erlaubnisvorbehalt.
Zentrale Regelung ist Art. 5 Abs. 1 lit. a DSGVO (Vgl. Grundsätze für die Verarbeitung personenbezogener Daten folgend Art. 6 Abs. 1 UA 1 DSGVO:
Die Verarbeitung ist nur rechtmäßig, wenn mindestens eine der nachstehenden Bedingungen erfüllt ist:
a) Die betroffene Person hat ihre Einwilligung zu der Verarbeitung der sie betreffenden personenbezogenen Daten für einen oder mehrere bestimmte Zwecke gegeben;
b) die Verarbeitung ist für die Erfüllung eines Vertrags, dessen Vertragspartei die betroffene Person ist, oder zur Durchführung vorvertraglicher Maßnahmen erforderlich, die auf Anfrage der betroffenen Person erfolgen;
c) die Verarbeitung ist zur Erfüllung einer rechtlichen Verpflichtung erforderlich, der der Verantwortliche unterliegt;
d) die Verarbeitung ist erforderlich, um lebenswichtige Interessen der betroffenen Person oder einer anderen natürlichen Person zu schützen;
e) die Verarbeitung ist für die Wahrnehmung einer Aufgabe erforderlich, die im öffentlichen Interesse liegt oder in Ausübung öffentlicher Gewalt erfolgt, die dem Verantwortlichen übertragen wurde;
f) die Verarbeitung ist zur Wahrung der berechtigten Interessen des Verantwortlichen oder eines Dritten erforderlich, sofern nicht die Interessen oder Grundrechte und Grundfreiheiten der betroffenen Person, die den Schutz personenbezogener Daten erfordern, überwiegen, insbesondere dann, wenn es sich bei der betroffenen Person um ein Kind handelt.
Die immer wieder - vor allem von Nicht-Fachleuten - als „Königsweg“ propagierte Einwilligung nach Buchstabe a) sollte für öffentliche Stellen die Ausnahme bleiben, weil die Voraussetzungen und Folgen der Einwilligung meist nicht handhabbar sind (zu Details siehe Artikel Einwilligung). Regelfall werden vielmehr die Verarbeitung zur Erfüllung einer rechtlichen Verpflichtung und die Verarbeitung für die Wahrnehmung einer Aufgabe sein. Die Verarbeitung zur Wahrung berechtigter Interessen scheidet in der Regel für öffentliche Stellen aus - „Behörde“ ist hier weit zu fassen.
Die Prüfreihenfolge lautet daher (seltene Fälle in Klammern):
Wichtig: Auch wenn auf die Einwilligung als Erlaubnistatbestand möglichst verzichtet werden soll, braucht es dennoch eine Datenschutzerklärung, denn die Art. 12ff. DSGVO gelten auch bei den anderen Erlaubnistatbeständen. Dementsprechend sollte auch begrifflich sauber unterschieden werden bei vorbereiteten Erklärungen der betroffenen Person:„Ich bin einverstanden“ oder ähnliches nur bei Einwilligung. „Habe ich gelesen“ oder ähnliches bei Verarbeitungen aufgrund der anderen Erlaubnistatbestände. Ebenso müssen auch bei Lösungen ohne Einwilligung das Prinzip der Datenminimierung beachtet und Technische und organisatorische Maßnahmen (TOM) ergriffen werden.
Das Thüringer Datenschutzgesetz regelt die Rechtmäßigkeit der Verarbeitung in § 16 ThürDSG. Dabei knüpft § 16 Abs. 1 ThürDSG an Art. 6 Abs. 1 UA 1 Buchstabe e DSGVO (Verarbeitung für die Wahrnehmung einer Aufgabe) an, wobei vorläufig offen bleiben muss, ob die Vorschrift einen eigenständigen Regelungsgehalt besitzt. § 16 Abs. 2 ThürDSG erlaubt Besondere Kategorien personenbezogener Daten unter im Einzelfall möglicherweise etwas anderen Voraussetzungen zu verarbeiten, als Art. 9 DSGVO das zulässt.
Das Erfordernis nach Rechtmäßigkeit der Verarbeitung ist umfassend zu verstehen. Art. 6, insbesondere Absatz 1 UA 1, DSGVO sind also nur eine notwendige aber nicht unbedingt auch hinreichende Voraussetzung für die Rechtmäßigkeit.
Auch aus anderen Vorschriften können sich Anforderungen für die Rechtmäßigkeit ergeben, wenn diese als Schutzzweck zumindest auch den Datenschutz haben. Das ist zum Beispiel der Fall bei der notwendigen Anhörung/Mitwirkung von Betriebs- oder Personalrat (Siehe Personalrat#Mitwirkung in Datenschutzangelegenheiten.). Andererseits wäre es für eine datenschutzrechtlich rechtswidrige Verarbeitung beispielsweise nicht ausreichend, dass die ausführenden Beschäftigten unter Verstoß gegen das Mindestlohngesetz (MiLoG) bezahlt werden.
Weiterhin muss sich der Schutzzweck der Norm gerade auch die Betroffene Person erfassen. Im vorgenannten Beispiel kann sich also auf eine unterlassene Anhörung des Personalrats nur ein Beschäftigter berufen, der von diesem Personalrat vertreten wird, aber keine Dritte Person.