Differential privacy, owing to its strong privacy protection capacity, is applied to the random forest algorithm to address the privacy leakage problem. However, the direct application of differential privacy to the random forest algorithm leads to a significant decline in the model’s classification accuracy. To balance the contradiction between privacy protection and model accuracy, this study proposes an efficient differential privacy random forest training algorithm, efficient differential privacy random forest (eDPRF). Specifically, the study designs a decision tree construction method based on the permute-and-flip mechanism. By introducing the efficient query output advantage of the permute and flip mechanism, the corresponding utility functions are further designed to achieve the precise output of split features and labels, effectively enhancing the learning ability of the tree model for data information under perturbation circumstances. At the same time, the study designs a privacy budget allocation strategy based on the composition theorem, which improves the privacy budget utilization rate of nodes by obtaining training subsets without replacement sampling and adjusting internal budgets through differentiation. Finally, through theoretical analysis and experimental evaluation, it is demonstrated that the proposed algorithm outperforms similar algorithms in terms of the model’s classification accuracy when given the same privacy budget.