When we deal with a matroid \({\mathcal {M}}=(U,{\mathcal {I}})\) ,we usually assume that it is implicitly given by means of the independence (IND) oracle. Time complexity of many existing algorithms is polynomially bounded with respect to |U| and the running time of the IND-oracle. However, they are not efficient anymore when U is exponentially large in some context. In this paper, we propose an algorithm for enumerating minimum-weight bases of a given matroid such that the time complexity does not depend on |U|. For some integer L, this algorithm enumerates the first L minimum-weight bases in incremental-polynomial time and the remaining ones in polynomial-delay. To design the algorithm, we assume two oracles other than the IND-oracle:the MinB-oracle that returns a minimum basis and the REL-oracle that returns the relevant elements one by one in non-decreasing order of weight. The proposed algorithm is applicable to enumeration of minimum bases of binary matroids from cycle spaces and cut spaces,both of which have exponentially large U with respect to a given graph.The highlight in this context is that,to design the REL-oracle for a cut space, we develop the first polynomial-delay algorithm that enumerates all relevant cuts of a given graph in non-decreasing order of weight.