Methods and apparatuses for performing oblivious transfer using a trusted intermediate environment are described. A data object identifier is used to identify requested data object. The requested data object is stored as a plurality of corresponding data chunks over a plurality of data buckets. The data object identifier is encoded with information identifying each of the plurality of corresponding data chunks within each respective data bucket. A trusted intermediate environment receives a data stream that includes data chunks stored in an assigned data bucket. Using the encoded information from the data object identifier, the trusted intermediate environment determines which of the data chunks in the data stream is the corresponding data chunk streamed from the assigned data bucket.