Privacy Preservation in Data Mining (PPDM) including for Privacy Preserving Association Rule Mining (PPARM) has attracted lots of attention in recent research and practice. However, the current method or approach still have drawbacks in the sense that there are trade-offs between efficiency and privacy preservation. This paper describes our work towards providing a new efficient PPARM protocol. We reviewed current literature on PPARM and mapped the methods or approaches involved. As previous research showed that Elliptic Curve Cryptography (ECC) perform better than the other Public Key systems such as RSA and Diffie-Hellman, we will utilize ECC for reducing the computational cost of the new PPARM protocol. In choosing good elliptic curves for ECC, we measured the running time of the key generation for various group of recommended elliptic curves i.e. Brainpool curves (by Brainpool), Prime, C2pnb, C2tnb curves (by ANSI X9.62), Secp curves (by SECG), and PrimeCurve curves (by CDC Group). As the result, Secp curves outperformed all of the other curves on overall average ratio of running time and key size of key generation by 4.4% up to 357.6%.