We present an efficient NC algorithm for finding a sparse Ic-edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)(2) (log n)(2)) time using O(k(n + m')) processors on an ARBITRARY CRCW PRAM, where n and m' stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.