Enlarging image without quality loss

[Kabir]

I'm trying to do a minor enlargement on an image, but I'm experiencing a bit of quality loss in that. I tried Photoshop and IrfanView, but they both had a quality loss, and I can't afford any loss of quality for the image.

Just searched Google, and here are a few tools I found about. I need a FREE one.
- PhotoZoom
- STOIK Smart Resizer
- Focus Magic
and a few more

The enlargement isn't even too big...just making something 120% of its original size. My assumption is that the original picture (given to me for this work I'm doing) has been enlarged quite a bit...which is why I'm experiencing quality loss on any enlargement.

Any suggestions there, anyone?

Thanks in advance.