While many commentators have described this as a complex problem, I believe the solution is simple. Either the government of Uzbekistan must make immediate, fundamental changes in the way it operates, or America’s relations with it must change fundamentally.

First, a few facts. Last month the security services of Islam Karimov, Uzbek president, fired on demonstrators after protesters stormed a prison and local government headquarters. The government contends that fewer than 200 people were killed by the troops, all of them armed Islamic militants. Eyewitnesses, journalists and independent groups tell a darker, much different, story. They estimate the dead at somewhere between 500 and 1,000, and say the vast majority were unarmed men, women and children protesting against the government’s corruption, lack of opportunity and continued oppression. In addition to those killed, many others were wounded, and at least 500 fled across the border into Kyrgyzstan.

Two weeks ago, senators Lindsey Graham, John Sununu and I travelled to central Asia, stopping briefly in Uzbekistan. There we saw photographs and heard other evidence that was as compelling as it was shocking, and it is clear that the Uzbek government’s account of the events in Andijan simply does not add up. It is also apparent that the killings were just the latest and most dramatic example of government repression in Uzbekistan.

In that country today there are no independent media or true opposition parties. The government’s human rights record is appalling, and political rights are virtually unknown. Often in the name of fighting Islamist terrorism, the government rounds up those opposed to its rule, sometimes subjecting prisoners to torture.

The government has provided genuine assistance to the US in the war on terror, and was particularly helpful during the height of our operations against the Taliban. But in a recent editorial in The Weekly Standard, Stephen Schwarz and William Kristol point out: “The Uzbek regime that was part of the solution in 2001 is now, with its bloody suppression of protests, part of the problem.” They are right. Uzbekistan today does have a real problem with violent Islamic extremism, but this will worsen because of the regime’s record of repression, not in spite of it. The Karimov regime must alter its governance radically, and it should begin by accepting an international inquiry into the Andijan events.

Unfortunately, the only change one sees today is movement in the wrong direction. Since Andijan the regime has rounded up opponents, refused to allow the European Union’s human rights envoy to enter the country, denied the Red Cross access to the wounded and imprisoned, and forced the termination of the American Peace Corps operation in Uzbekistan. During our brief visit two weeks ago, no government official would agree to meet us.

If this trend continues, the US has no choice but to re-evaluate all aspects of its relationship with Uzbekistan, and this includes our military relations. While we review our policy, we should suspend any talk of a long-term basing arrangement and look very critically at our continued presence at the Karshi-Khanabad air base.

To do otherwise risks damaging America’s credibility as the US puts ever greater priority on the promotion of human rights and democracy abroad. We cannot remain idle while a government with which we have close ties so blatantly contravenes the ideal of freedom. This does not mean that we simply walk away – in fact, allowing Uzbekistan to retreat into isolation poses its own dangers – but it does imply a different kind of relationship, one in which the US explicitly and publicly presses Mr Karimov to change.

Using sticks and carrots to encourage positive change may not be successful, but it would put the US on the right side of history. It would show the Uzbek people that we support their freedom, not simply our narrow security interests, and would actually strengthen our security in the long run. For if we have learnt any lesson from the attacks of September 11 2001, it is that, where repression and despair rule, extremism and violence breed.

This is a lesson that applies just as much to Mr Karimov’s government as it does to the US government. And so I hope his regime will realise that the only way to true security is to embrace fundamental freedoms and human rights. But if the US cannot induce change in Uzbekistan, we can at least avoid a close and continuing relationship with its current government. The world will expect no less of us, and we should expect no less of ourselves.