Data can be protected in a centralized tokenization environment. A security value is received by a central server from a client device. The central server accesses a token table corresponding to the client device and generates a reshuffled static token table from the accessed token table based on the received security value. When the client device subsequently provides data to be protected to the central server, the central server tokenizes the provided data using the reshuffled static token table and stores the tokenized data in a multi-tenant database. By reshuffling token tables using security values unique to client devices, the central server can protect and store data for each of multiple tenants such that if the data of one tenant is compromised, the data of each other tenant is not compromised.