In various embodiments, a dataset generation application generates a new dataset based on an original dataset. The dataset generation engine perturbs a first data item included in the original dataset to generate a second data item. The dataset generation application then generates a test dataset based on the original dataset and the second data item. The test dataset includes the second data item instead of the first data item. Subsequently, the dataset generation application determines that the test dataset is characterized by a first property value that is substantially similar to a second property value that characterizes the original dataset. The first property value and the second property value are associated with the same property. Finally, the dataset generation application generates a new dataset based on the test dataset. The new dataset conveys aspect(s) of the original dataset without revealing the first data item.