Patent ID: 8533489

Claim:
A method comprising: receiving at least one update-related token that provides update information used to perform an updating operation on encrypted index information; processing a pool of free list entries of the encrypted index information based on the update information to modify at least one free list entry according to the updating operation; and modifying a main indexing structure of the encrypted index information based on the update information, the main indexing structure having a set of main list entries corresponding to lists of documents associated with respective words, the encrypted index information including encrypted linking information that identifies positions of the set of main list entries of the main indexing structure, wherein the encrypted linking information has been encrypted using a malleable encryption scheme, said modifying of the main indexing structure comprising modifying at least one instance of the encrypted linking information that identifies an individual position of a corresponding main list entry in the main indexing structure, wherein the modifying uses the at least one free list entry and is performed without decrypting said at least one instance of the encrypted linking information that identifies the individual position of the corresponding main list entry, wherein at least the modifying the main indexing structure is performed by a processing device.