Cycle-based arrival profiles can describe temporal demand distribution within a signal cycle for signalized intersections, which can be used to calculate indicators such as traffic volume, queue length, and facilitate fine-grained signal control. However, few studies address cycle-level arrival profile estimation based on connected vehicles (CVs). Besides, studies addressing privacy issues for cross-company collaboration in traffic management are still in their infancy. To fill these research gaps, this study proposes a data-driven method for privacy-preserving cycle-based arrival profile estimation using cross-company CV data. The cyclic arrival curve is discretized as an arrival rate vector whose elements are calculated using sampled CV trajectories, thus transforming the arrival profile estimation into a matrix completion problem. Considering cross-company collaboration, a privacy-preserving technique, secure multi-party computation, is used to encrypt initial arrival rate matrices of multiple companies. In particular, a perturbation approach is combined to enhance protection against inference attacks with prior knowledge of the matrix construction process. Then, matrix completion is realized through a singular value thresholding (SVT) algorithm, meanwhile achieving denoising. Empirical evaluation shows that the estimation accuracy of traffic volume and queue length derived from the proposed arrival profile estimation method can reach 87.6% and 78.4%, respectively, meanwhile protecting the privacy of multiple participating companies and outperforming existing methods. Simulation evaluation on a large-scale network further demonstrates the reliability of the proposed method considering ever-changing demand scenarios. A comprehensive sensitivity analyses exhibit its robustness to CV sample size, number of participating parties and data disparity, showing wide popularization and application prospects.