To solve the problem of unfairness for verifier in the traditional universal designated verifier signature proof scheme because of the strong privacy-preserving property, the notion of traceable universal designated verifier signature proof (TUDVSP) was proposed. In this new kind of conditional privacy-preserving authentication scheme, a tracing center was introduced which can recover the transformed signature to the original one, and thus avoid the signer collude the delegator to cheat the verifier. Based on the consideration of real-word applications, security model which contains unforgeability, security against impersonation attack, and traceability for TUDVSP scheme was proposed. By using bilinear map, a concrete TUDVSP scheme was proposed, and the unforgeability, security against impersonation attack, and traceability of the proposed scheme were also proved. The experimental results indicate that it only takes about 21 ms of computation cost and 120 byte of communication overhead.