The new chief minister of the province bordering Afghanistan and Iran urged security forces, who deny wrongdoing, to end a campaign of enforced disappearances to support his hopes of kindling dialogue, Reuters reported.
On Sunday, the day Abdul Malik took oath, five bullet-riddled bodies were found in the province.
The discoveries were interpreted by many as a signal that security forces were intent on continuing what human rights groups have dubbed a systematic campaign of "kill-and-dump."
"We have to create an environment in which we are in a position to invite insurgents for negotiations," Malik told the news agency in Pakistan's capital, Islamabad. "Before I go to them, we have to take certain measures to prove that we want change. "
But many Baluch doubt he can deliver. A low turnout in many areas and widespread allegations of irregularities in the province during Pakistan's May 11 general elections underscored the depths of alienation from the state.
The simmering conflicts between separatist fighters and security forces in Baluchistan receive scant attention even within Pakistan, but they have implications for the rest of Pakistan and the region.
Endowed with rich but largely unexploited reserves of copper and gold, Baluchistan also supplies much of the natural gas feeding Pakistan's lifeline textile industry in Eastern Punjab province, and is home to a deepwater port at Gwadar.
But the chronic instability in the province, which has experienced waves of revolt by Baluch nationalists since being incorporated into Pakistan in 1948, has served as a stubborn reminder of the broader fragility of the Pakistani state.
A 40-year veteran of Baluch politics and an ex-senator, Malik is the first chief minister to emerge from the province's educated middle-class rather than the ranks of tribal overlords the army has traditionally co-opted to maintain control.
Malik pledged to introduce "confidence-building measures" during the first 100 days of his government, including persuading the military to return missing persons believe to be held by security forces.
The main separatist leaders Malik plans to approach for talks include Allah Nazar Baloch, the leader of the Baluchistan Liberation Front, Brahamdagh Bugti, the Swiss-based chief of the Baluch Republican Party, and Harbiyar Marri, an exiled nationalist who leads the Baluchistan Liberation Army.
But Malik is regarded as a traitor by many hardened separatists, who point out that he welcomed Imam Bheel, a Baluch businessmen designated by the US government as a major heroin trafficker, into his National Party at a public meeting in 2010.
Most believe there is little chance of change in Baluchistan unless Prime Minister Nawaz Sharif, who has a long history of clashes with the powerful army, can become the first civilian leader to wrest control of Baluchistan policy from the security establishment and curb human rights violations by security forces.
"I cannot do this alone," Malik said. "We will all together, Nawaz Sharif and I, tell the security establishment that these things have to end. "
Hundreds of bodies bearing gunshot wounds have been found across the province in recent years. The military denies committing abuses. Separatist fighters have also been accused of killing civilians and assassinating teachers.
In a measure of the depths of the divisions, separatist insurgents have killed several senior members of Malik's National Party and tried to kill him twice during the muted election campaigning in Baluchistan.
"I may succeed, I may fail," Malik said. "But this is the first time that Pakistan's public at large is thinking that, maybe, Baluchistan might just be fixed."