Definition and Efficient Construction of Encrypted k–anonymization Scheme

In this paper, we propose an encrypted k–anonymization scheme (EAS) to k–anonymize an encrypted database using a domain generalized hierarchy while maintaining the encryption state. Preparation of the domain generalized hierarchy is optional; the proposed EAS can generate domain generalized hierarchies using a Huffman code tree from a database encrypted with searchable encryption. As a result, the user can delegate k–anonymization processing to a third party organization such as the cloud while retaining the confidentiality of the database without preparing a generalized hierarchy. In addition, third-party organizations that are entrusted also have the advantage to eliminate possible of misconduct such as information leakage. In a standard computer experiment, we performed a generalization process, which is the major procedure for our EAS. The generalization process takes around 168 seconds only to achieve k–anonymity with k = 3 on 1,000,000 records consisting of 4 attributes. As a consequence, this high-speed performance means our EAS is applicable to not only batch processing but also real-time processing.