1. A method comprises: identifying an encoded data slice to be rebuilt; selecting a decode threshold number of dispersed storage (DS) units of a storage set of DS units associated with the encoded data slice to be rebuilt; generating a decode threshold number of key pairs, wherein a key pair of the decode threshold number of key pairs corresponds to a DS unit of the decode threshold number of DS units; sending partial rebuilding requests to the decode threshold number of DS units, wherein a partial rebuilding request of the partial rebuilding requests includes the key pair and identity of the corresponding DS unit; receiving encrypted partial encoded data slices in response to the partial rebuilding requests, wherein an encrypted partial encoded data slice received from the corresponding DS unit includes a multiple encryption, using the key pair, of a partial encoded data slice; and decoding the encrypted partial encoded data slices to rebuild the encoded data slice.