In one embodiment, data at rest is securely stored. A data safe performing data plane processing operations in response to requests of received read data requests, received write data requests, and received read information responses, with the data safe being immutable to processing-related modifications resulting from said performing data plane processing operations. Performing these data plane processing operations does not expose any pilot keys outside the data safe in plaintext form nor in encrypted form. The pilot keys are used to encrypt information that is subsequently stored in a storage system. In one embodiment, the information encrypted and decrypted by the data safe includes data structure instances including feature-preserving encrypted entries generated using feature-preserving encryption on corresponding plaintext data items. In one embodiment, a data vault performs queries on the data structure instances including feature-preserving encrypted entries after retrieval from storage and decryption by the data safe.