You really want them redrawn as some form of vector (i.e. in Illustrator not Photoshop), as then you can resize them as much as you want, and not lose any detail.