Scalable Distributed Data Structures (SDDS) store data in a file of key-based records distributed over many storage sites. The number of storage sites utilized grows and shrinks with the storage needs of applications, but transparently to them. An application can search records by key or by content in parallel at all storage sites. The need for privacy of the data at the storage sites might require the encryption of the records. However, the scheme needs to preserve the capability to search in parallel. We propose a scheme that achieves this goal. We create a collection of additional SDDS indices. We encrypt these so that we can still perform string searches performed in parallel at the storage sites. We present the scheme and evaluate its strength as well as storage and access performance.