In an interview with an auditor examining the controversial program, Paulson, now RCMP commissioner, expressed concerns about excessive state secrecy in certificate proceedings.
The national security certificate is a seldom-used tool for removing non-citizens suspected of terrorism or espionage from Canada.
"In my view, we over claim the protection of sources and methods and this is convenient if you can get away with it," say notes from the October 2009 interview, recently released under the Access to Information Act.
Paulson was assistant RCMP commissioner for national security at the time of the interview. Two years later, he was picked by the Harper government to become commissioner.
The discussion was part of a 2009-10 federal evaluation of the "relevance and performance" of the security certificate initiative, which had been revamped in 2008 after elements were found to be unconstitutional.
Despite the changes, civil libertarians have persistently criticized the national security certificate because the person named sees only a bare-bones summary of the case against them.
Opponents say federal authorities should criminally charge someone who is believed to be involved in terrorism, not try to deport them based on evidence put forward behind closed doors.
"The security certificate is an odd beast as it has come to be understood," Paulson told the interviewer. "If we had the threshold belief that we could take criminal action, we would do so."
When the review took place, four certificates had been on the books for several years, all against Muslim men accused of terrorist ties.
The government had withdrawn one certificate just a month earlier, in September 2009, in order to avoid sensitive intelligence being presented in court. Another certificate would be tossed out by the courts in early 2010.
Currently, three people arrested under security certificates — Mohamed Harkat of Algeria, and Mahmoud Jaballah and Mohamed Zeki Mahjoub, both from Egypt — are out on bail under strict surveillance as their cases slowly grind through the courts.
"If we were careful about how we brought the (security certificates) to bear upon these people it may have worked better," Paulson said in the interview. "As it is being applied now the (security certificate) is completely off the rails."
Paulson decried what he saw as a failure to make certificate detainees reasonably apprised of the case against them.
"Instead we are going to make the subject 'work' for the information. 'Take our word for it' approach," say the notes.
The internal records were obtained under the federal access law by Mike Larsen, a criminology instructor at Kwantlen Polytechnic University in British Columbia, who provided a copy to The Canadian Press.
In perhaps the most significant extremism case since Paulson took over, two non-citizens were charged in April under the Anti-Terrorism Act — not arrested using security certificates — for allegedly plotting to derail a passenger train.
Paulson's comments were "very forthright" and "refreshing" in suggesting the security certificate program was dysfunctional, Larsen said. "It seems that he feels that transparency and accountability have not been fully respected in the certificate proceedings."
In the 2009 interview, Paulson also took a swipe at the interdepartmental process for sharing input on the security certificate system.
"I would assess the co-ordination as being characteristic of typical departments involved in security. Siloed and self-interested," say the notes.
"Typically these interdepartmental initiatives are absent of leadership and decision-making ability. It usually turns on the goodwill of the participants rather than the co-operation delivered by leadership."
Portions of the two-page interview summary — including Paulson's recommendations for improving federal policy-making on the certificate program — were deemed too sensitive to disclose.
The RCMP has no additional comment, said Sgt. Greg Cox, a force spokesman.
The government revamped the certificate process after the Supreme Court of Canada declared it unconstitutional in 2007. A key change was the addition of special advocates — lawyers who serve as watchdogs and test federal evidence against the person facing deportation.
However, the special advocates do their work behind closed doors due to the sensitive nature of the classified information before the court in such cases.
The Supreme Court of Canada has agreed to revisit the question of just how open the process should be in response to a challenge brought by Harkat.
Also on HuffPost