THIS month's deadly attack in Jakarta, claimed by Islamic State, convinced many Indonesian officials that existing counter-terrorism efforts are not sufficient to stop another attack.
Indonesia's Corruption Eradication Commission has warned that high corruption, especially around the country's military, may lead to increased recruitment for terrorists.
The remote region of West Papua is believed to be particularly vulnerable, and so too neighbouring Papua New Guinea.
John Tekwie is a community leader in Vanimo, the PNG town closest to the border. He says that via the border, terrorism is a threat to the Pacific region.
"In the case of our Pacific region, the hotspot is West Papua, the threat of ISIS, if there's any degree of threat at all, it would be West Papua, because of the issue of West Papuan independence."
The flow of illegal guns into PNG is already a big problem and poses a risk to major development projects, according to Akat Mai, the Governor of PNG's West Sepik province, along the border.
"It's a major problem I'm facing now because of drug smuggling and arm smuggling as well. As a governor I am scared about gun smuggling because I do not want to see these guns end up at the LNG in the southern highlands, where some of our big businesses."
Mr Tekwie says it's become easy for people to come over from Indonesia to live and work in PNG without visas.
"We have a problem with intelligence gathering, we have security problems and we do certainly need help from Australia and New Zealand, PNG defence force and the foreign affairs department and the border development authority up at the border to do intelligence gathering. This is our main problem. The threat to our border is real and we cannot underestimate it."
Across on the Indonesian side, church leaders are concerned about religious extremism which exists in small pockets of West Papua.
Father Neles Tebay of the West Papuan Catholic Justice and Peace Secretariat says all mainstream churches in Papua, including Christian and Muslim faiths, have agreed not to accept fundamentalist groups in the region, and have pushed for local police to expel them.
"They have not been identified as terrorist group but they need to be watched closely in order to prevent them from creating violence in the land of Papua."
Melanesian leaders are wary of Indonesian security forces' counter-terrorist efforts, knowing that in the past, these have targeted peaceful West Papuan pro-independence groups.
However, on the other side, the message is clear that Australia, and New Zealand, should be worried about PNG's lack of capacity to control its side of the border.