A client receives sensitive data to be tokenized. The client queries a token table with a portion of the sensitive data to determine if the token table includes a token mapped to the value of the portion of the sensitive data. If the mapping table does not include a token mapped to the value of the portion of the sensitive data, a candidate token is generated. The client queries a central token management system to determine if the candidate token collides with a token generated by or stored at another client. In some embodiments, the candidate token includes a value from a unique set of values assigned by the central token management system to the client, guaranteeing that the candidate token does not cause a collision. The client then tokenizes the sensitive data with the candidate token and stores the candidate token in the token table.