A privacy-preserving index system addresses the problem of providing a privacy-preserving search over distributed access-controlled content. Indexed documents can be readily reconstructed from inverted indexes used in the search. The privacy-preserving index system builds a centralized privacy-preserving index in conjunction with a distributed access-control enforcing search protocol. The privacy-preserving index utilizes a randomized algorithm for constructing a privacy-preserving index. The privacy-preserving index is strongly resilient to privacy breaches. The privacy-preserving index system allows content providers to maintain complete control in defining access groups and ensuring its compliance, and further allows system implementors to retain tunable knobs to balance privacy and efficiency concerns for their particular domains.