Cigarettes, not guns or bombs, are the deadliest artifacts in the history of civilization. If we want to save lives and improve health, nothing else that is readily achievable would be as effective as an international ban on the sale of cigarettes. (Eliminating extreme poverty worldwide is about the only strategy that might save more lives, but it would be far more difficult to accomplish.)
AM: Really, Singer?
First, the war on drugs has been an astounding failure. Drug prohibition is probably the worst policy initiative of the 20th century in terms of cost, ineffectiveness, and unintended side effects. So lets keep that in mind before we up the ante.
You seem to have anticipated this response, but can you so easily write-off the war on drugs comparison? Prohibition has actually made drugs stronger and more dangerous: this was a black market innovation that directly resulted from illegality. Making tobacco illegal would do nothing to diminish the demand for tobacco, and everything to encourage the growth of a parallel economy. I mean, even high tax rates produce contraband. You can't keep a banned drug down. Your utilitarian calculation of costs and benefits drastically underestimates the harm caused by prohibition; and overestimates the benefits (effectiveness) of the policy.
Second, even if this could work, do you really think that the utilitarian notion of harm reduction overrides the basic principle of free choice? Granted, addiction and second hand smoke complicate the issue, but this remains, ultimately, a question of liberty. Don't ignore that.
Third, the negative externalities of smoking are better reduced through less coercive policies. In Canada, education, restrictions, and taxation have been pretty effective in cutting smoking rates and protecting the public. Smokers pay taxes; they can't smoke in most public places; and everyone is aware of the dangers. Tobacco companies can't advertise to children; and kids are educated on the risks of smoking, at an early age. This works. But we're not going to eliminate it entirely. Why go further and risk repeating a massive mistake like prohibition?