1. A system comprising: secure hardware; at least one hardware device processor; and a computer-readable storage medium storing executable instructions that, when executed, cause the at least one hardware device processor to: receive, from an untrusted module, an encrypted search key value of a search key and a sorted vector representation of an index of a tree structure, the sorted vector representation of the index comprising encrypted key values; using the secure hardware, decrypt the encrypted search key value to obtain a decrypted search key value; using the secure hardware, perform a binary search over the sorted vector representation to identify a lookup position of the decrypted search key value in the sorted vector representation; and provide an identifier of the lookup position to the untrusted module, wherein the secure hardware is configured to: perform the binary search by decrypting specific encrypted key values in the sorted vector representation that are used in comparison operations during the binary search; and perform the binary search without decrypting at least some other encrypted key values in the sorted vector representation that are not used in the comparison operations during the binary search.