Abstract: In this paper, a probabilistic audit scheme is presented to determine whether it is by on-line or by off-line that the payments are verified in an anonymous divisible e-cash system to reduce the loss caused by users’ double-spending. A parallel processing method is used to eliminate the additional payment time by the probabilistic audit scheme.