We construct new protocols for the tasks of converting noisy multipartite quantum correlations into noiseless classical and quantum ones using local operations and classical communications (LOCC). For the former, known as common randomness (CR) distillation, two new lower bounds on the "distillable common randomness", an operational measure of the total genuine (classical) correlations in a quantum state, are obtained. Our proof relies on a generalization of communication for omniscience (CO) [Csiszar and Narayan, IEEE Trans. Inf. Theory 50:3047-3061, 2004]. Our contribution here is a novel simultaneous decoder for the compression of correlated classical sources by random binning with quantum side information at the decoder. For the latter, we derive two new lower bounds on the rate at which Greenberger-Horne-Zeilinger (GHZ) states can be asymptotically distilled from any given pure state under LOCC. Our approach consists in "making coherent" the proposed CR distillation protocols and recycling of resources [Devetak et al. IEEE Trans. Inf. Theory 54(10):4587-4618, 2008]. The first lower bound is identical to a recent result by Vrana and Christandl [IEEE Trans. Inf. Theory 65(9):5945-5958, 2019], which is based on a combinatorial method to achieve the same rate. Our second lower bound generalises and improves upon this result, and unifies a number of other known lower bounds on GHZ distillation.