Defendant-Appellant Warren Nuzzo appeals from an order and judgment of the United States District Court for the Eastern District of New York (I. Leo Glasser, Judge) sentencing Nuzzo principally to 136 months’ incarceration following his guilty pleas to importing, possessing, and possessing with intent to distribute substantial quantities of cocaine, in violation of 21 U.S.C. §§ 952(a), 960(a)(1), 960(b)(l)(B)(ii) and 841(a)(1). Nuzzo appeals the order and judgment on the grounds that, inter alia, the District Court erred in enhancing his sentence for abuse of a position of trust pursuant to U.S.S.G. § 3B1.3. The Government cross-appeals on the grounds that the District Court erred both in awarding Nuzzo a safety-valve deduction, U.S.S.G. §§ 201.1(b)(6) and 601.2(a) and 18 U.S.C. § 3553(f), and in downwardly departing pursuant to U.S.S.G. § 5K2.0. We reverse the District Court’s decision to enhance Nuzzo’s sentence for an abuse of a position of trust, vacate with respect to both of the Government’s claims on cross-appeal, and remand the cause to the District Court for re-sentencing.
Background
On August 28, 2002, Nuzzo, a United States citizen, was arrested at John F. Kennedy International Airport (“JFK”) upon his disembarkment from a flight arriving from Guyana, for attempting to smuggle approximately twelve kilograms of cocaine into the United States. Nuzzo was indicted by a grand jury on October 21, 2002, for (1) importing more than five kilograms of cocaine in violation of 21 U.S.C. §§ 952(a), 960(a)(1) and 960(b)(l)(B)(ii); and (2) possessing with intent to distribute more than five kilograms of cocaine in violation of 21 U.S.C. § 841(a)(1). Each of the two counts carried a mandatory minimum ten-year sentence. See 18 U.S.C. §§ 3551 et seq., 841(b)(l)(A)(ii)(II). On March 5, 2003, Nuzzo pleaded guilty to both counts of the indictment and on October 9, 2003, the District Court entered judgment sentencing Nuzzo principally to 136 months’ imprisonment. Nuzzo now appeals that *111sentence on a variety of grounds. The Government cross-appeals.
I. The Arrest
Nuzzo was stationed at JFK as an inspector for the Immigration and Naturalization Service1 (“INS”) from June 1991 to April 2002. He was fired in April 2002 for conduct unbecoming an officer. Prior to his termination, however, Nuzzo was recruited by a Guyana-based drug-dealing operation to assist in the smuggling of cocaine into the United States from Guyana. Nuzzo has stated his belief that he was recruited due, at least in part, to knowledge of the immigration and customs processes he ostensibly gleaned from his service as an INS inspector.
On August 28, 2002 (subsequent to the termination of Nuzzo’s employment by the INS), Nuzzo and a woman named Jean Campbell arrived at JFK from Guyana. Because the Government had previously received a tip concerning Nuzzo’s trip, he and Campbell were arrested before reaching the usual customs declaration checkpoint. Nuzzo’s suitcase was found to have II.99 kilograms of cocaine.
Upon his arrest, Nuzzo waived his Miranda rights,2 and admitted to knowingly importing cocaine into the United States. He explained that Campbell, with others, had paid for his flight and assisted him in his smuggling activities. Those smuggling activities had been planned in Georgetown, Guyana, under the leadership of Mark Morgan, Campbell’s former son-in-law. Had he not been arrested, Nuzzo’s plan— in accordance with the instructions given to Mm under the leadership of Morgan in Guyana — was to proceed to his residence in Queens, where subsequently he would receive further instructions. Nuzzo would have been paid $5,000 for successfully smuggling the cocaine.
Nuzzo also admitted that in December 2001, while he was still employed as an inspector for the INS, he had successfully smuggled seventeen kilograms of cocaine from Guyana into the United States through JFK at the instance, and with the guidance, of Morgan. Nuzzo traveled to and from Guyana with his then-fiancée, Simone DeFreitas. DeFreitas and her sister, Marcia Figueroa, made arrangements to sell the seventeen kilograms of cocaine in the United States. The proceeds were wire-transferred to Morgan in Guyana and Nuzzo was paid $8,000.
Nuzzo also admitted that he helped launder drug proceeds. Although the amount of money that he admitted to helping launder and wire to Guyana varied in subsequent proffer sessions, upon questioning at JFK on August 28, 2002, Nuzzo admitted that he laundered $20,000.
Campbell, too, waived her Miranda rights. Although she equivocated on most matters during questioning, eventually she admitted that (1) her final destination *112within the United States was Nuzzo’s address; (2) she had received an unspecified amount of money from Nuzzo; and (3) Morgan, the cocaine-distribution leader in Guyana under whom Nuzzo had admitted he was operating, was her former son-in-law. Campbell’s purse contained a key that unlocked both her luggage and Nuz-zo’s matching luggage — the latter containing the 11.99 kilograms of cocaine.
Nuzzo consented to a search of his residence in Queens. That search yielded an INS uniform jacket, a nine-millimeter Beretta handgun, an INS raid vest with Kevlar inserts,3 a federal law enforcement inspector’s badge, an expandable baton, an INS date stamp, ammunition and miscellaneous documents.
Nuzzo and Campbell were charged together by complaint with conspiracy to import cocaine in violation of 21 U.S.C. §§ 952(a) and 960.
II. Nuzzo’s Inconsistent Statements
Nuzzo made some efforts to disclose his knowledge of, and participation in, the Guyana-based drug-smuggling operation in his post-arrest statements, and in the course of three proffer sessions with federal prosecutors (in October 2002, January and August 2003) and submissions and testimony at his sentencing proceeding, see Oct. 9, 2003, Tr., at 40-86. In doing so, Nuzzo was unable to provide a consistent account of his activities.
For example, he made conflicting statements about (1) how. many of his past trips to Guyana had a drug-related purpose;4 (2) whether Campbell was a participant in the drug-smuggling operation;5 (3) what amount of drug proceeds he wire-transferred to Guyana;6 (4) whether he had seen, and had a telephone number for, “Red Man,” a prominent Guyana-based cocaine exporter’ to the United States;7 and (5) whether he had personally delivered a *113suitcase full of drugs to a dealer in a parking lot in the United States.8
The District Court concluded at Nuzzo’s sentencing that “Mr. Nuzzo is incapable of answering questions truthfully and wasn’t telling the truth here [during the sentencing proceeding].... Any person with a modicum of common sense would be able to reach that conclusion without a moment’s hesitation.” Oct. 9, 2003, Tr., at 97.
III. Sentencing
The District Court set Nuzzo’s base offense level at 34, see Oct. 9, 2003, Tr., at 34, 111; U.S.S.G. § 2D1.1(c)(3),9 and applied the following adjustments: (1) a two-level enhancement, pursuant to U.S.S.G. § 3B1.3,10 for abuse of a position of trust, see Oct. 9, 2003, Tr., at 25; (2) a two-level enhancement, pursuant to U.S.S.G. § 3C1.1,11 for obstructing justice, see Oct. 9, 2003, Tr., at 29; (3) a two-level acceptance of responsibility adjustment, see Oct. 9, 2003, Tr., at 29; U.S.S.G. § 3E1.1(a);12 and (4) a two-level safety-valve deduction, see Oct. 9, 2003, Tr., at 109; U.S.S.G. §§ 2D1.1(b)(6)13 and 501.2(a);14 18 U.S.C. § 3553(f).15
The Court declined to grant Nuzzo (1) an additional one-level adjustment for ac*114ceptance of responsibility pursuant to U.S.S.G. § 3El.l(b);16 and (2) a mitigating-role adjustment pursuant to U.S.S.G. § 3B1.2(b).17
Having made these determinations, the Court should have sentenced Nuzzo based upon a final offense level of 3418 and, accordingly, within a range of 151 to 188 months’ incarceration.19 The Court made a computation error, however, and thought that its determinations had yielded a final offense level of 32, which would have yielded a range of 121 to 151 months’ incarceration. Laboring under that misunderstanding, the Court sentenced Nuzzo to the midpoint of what it thought was the appropriate range. See Oct. 9, 2003, Tr., at 109.
Judge Glasser subsequently realized his mistake (“I calculated a two-level adjustment twice for acceptance of responsibility,” see id. at 111) and admitted that, according to the sentencing determinations he had made, Nuzzo should have been sentenced at a final offense level of 34, within a range of 151 to 188 months. Nevertheless, Judge Glasser declined to change Nuzzo’s 136-month sentence, and explained that he would keep Nuzzo’s sentence at 136 months “by [sua sponte ] downwardly departing an additional two points pursuant to [U.S.S.G. § ] 5K2.0 and *115mitigating factors which weren’t contemplated.” Id. at 112.
Discussion
On appeal, Nuzzo challenges his sentence on the grounds that, inter alia,20 the District Court erred in enhancing his sentence two levels for abuse of trust. The Government cross-appeals, claiming that the District Court erred in (1) awarding Nuzzo a two-level safety-valve deduction; and (2) downwardly departing two levels for mitigating circumstances.
I. The Abuse of Trust Enhancement
The District Court applied a two-level enhancement, pursuant to U.S.S.G. § 3B1.3, see note 10, ante, for Nuzzo’s abuse of a position of trust in a manner that facilitated his offense conduct or concealment thereof. Nuzzo argues that that the District Court committed clear error in doing so. Proper application of § 3B1.3 requires satisfaction of two requirements: first, that Nuzzo occupied a “position of trust,” and second, that Nuzzo abused that position of trust to commit or conceal his crimes. See note 10, ante.
A. Whether Nuzzo Occupied a Position of Trust
Nuzzo does not dispute that his position as an INS inspector constituted a position of trust in certain respects. See Appellant’s Br. at 19; see also Government’s Br. at 15-16. Nuzzo admits that he “had discretion in the course of his employment ... checking the entry documents of persons entering the country ... [and had he] improperly admitted] someone with defective or deficient documentation,” then he would have been abusing a position of trust. Appellant’s Br. at 16. Cf. United States v. Brickey, 289 F.3d 1144, 1155 (9th Cir.2002) (“Clearly, [an INS border] position is one of public trust characterized by professional discretion.”). We turn, therefore, to a consideration of the second prong of § 3B1.3 — whether Nuzzo abused his position of trust in a manner that facilitated the commission or concealment of the offense conduct for which he was charged.
B. Whether Nuzzo Abused His Position of Trust Within the Meaning of § 3B1.3
We review for clear error the second prong of § 3B1.3. See United States v. Santoro, 302 F.3d 76, 80 (2d Cir.2002) (“We accord due deference to the district court’s application of the guidelines to the facts ... and we will not overturn the district court’s finding that the defendant abused a position of trust to significantly facilitate his offense unless it is clearly erroneous.”) (quotation marks and citation omitted).
The Government must meet its burden of proving satisfaction of the second prong of § 3B 1.3 by a preponderance of the evidence, see United States v. Desimone, 119 F.3d 217, 228 (2d Cir.1997), proving that “the position of ... trust must have contributed in some significant way to facilitating the commission or concealment of the offense (e.g., by making the detection of the offense ... more difficult),” U.S.S.G. § 3B1.3, comment. (n.1) (emphasis added).
It is not sufficient that a defendant enjoyed a position of trust, and thus had an opportunity to commit a difficult-to-detect wrong. That would merely satisfy the *116first of the two prongs of § 3B1.3. Rather, (1) the defendant must have enjoyed a “superior” position,, relative to other potential perpetrators, as a result of a trust relationship, see United States v. Castagnet, 936 F.2d 57, 62 (2d Cir.1991); and (2) the defendant must have capitalized on that superior position in committing the offense conduct, see U.S.S.G. § 3B1.3, comment, (n.1).
The Government argues that “relative to all people in a position to smuggle drugs through JFK Airport, Nuzzo was in a superior position as a result of his service as a JFK Airport INS inspector.” Government’s Br. at 16. In the Government’s view, Nuzzo’s “personal relationship with other inspectors, his insight into law enforcement’s methods of detecting drug smugglers and his INS credentials could do nothing but enhance Nuzzo’s ability to smuggle drugs through the airport.” Id. at 17. The Government offers Nuzzo’s successful smuggling of seventeen kilograms of cocaine through JFK in December 2001 as proof that he enjoyed such a position and that he capitalized on that position. Finally, the Government asks us to look to Nuzzo’s own statements, upon arrest, that he believed that he had been recruited to smuggle drugs for the Guyana outfit “due to his profession and [because] he knew his way through the Immigration and Customs processes.” Id. at 16-17.
In the particular circumstances presented here, these arguments are unconvincing and insufficient to establish, by a preponderance of the evidence, that Nuzzo’s position of-trust facilitated the commission or concealment of his crimes. The only evidence that Nuzzo was recruited for his criminal activity because of his INS position is Nuzzo’s own post-arrest statement (one of many that the District Court deemed could be disbelieved by anyone with a modicum of common sense).21 Even if Nuzzo’s testimony were credited in this respect, his asserted recruitment because of “special skills” relevant to the projected crime would not prove that he actually had such skills . or that he used them in a particular criminal enterprise. Indeed, it is altogether possible for an individual to be recruited for a specific job due to supposed special skills', and to succeed at that job, without actually having the skills or using them.
Although the Government suggests that Nuzzo’s personal relationships with other INS inspectors gave him “insight” into the law enforcement agencies’ drug-smuggling detection techniques, see Government Br. at 17, and that he used his credentials to facilitate the crimes with which he was charged, id., none of this is explained in any detail nor supported by the findings of the District Court. For example, nothing in the record supports the proposition that Nuzzo maintained personal relationships with government inspectors that facilitated his crime, or that Nuzzo had special knowledge about the detection of drug smuggling that he used in the commission of the offense with which he was charged. Moreover, there is no suggestion in the record that Nuzzo used any INS credentials in the (successful) December 2001 or in the (unsuccessful) March 2002 efforts to smuggle cocaine into the United States.
*117We find unconvincing the Government’s argument that Nuzzo’s successful importation of seventeen kilograms of cocaine in 2001 provides some proof that Nuzzo abused his position of trust in the commission of his crimes. First, it is surely possible successfully to smuggle cocaine into the country without the use of special skills or the abuse of a position of trust. Second, we know of no authority for the notion that evidence of a successful prior crime, standing alone, can support a conclusion that “special skills” or an abuse of a position of trust accounted for the success of later attempts.
The cases in which this Court has held that a position of trust was abused iii a manner appropriately relevant to a § 3B1.3 enhancement22 — and the cases from other courts that this Court has cited as illustrative of such abuse23 — contemplate a closer nexus between a defendant’s position of trust (or special skills learned or exercised in connection with such a position) and the defendant’s offense conduct than is present here. We do not doubt that Nuzzo occupied, for a time, a position of trust that might have afforded him opportunities to commit difficult-to-detect wrongs because of his superior position. Nor do we minimize society’s legitimate concern that an INS agent might engage in drug-smuggling - activities as a direct result of his designated port-of-entry post... But in the instant case, we do not find support in the record of a direct nexus between a position of trust, the abuse of that trust, and the facilitation of the commission or concealment of the relevant offense conduct.
Accordingly, we reverse, the District Court’s decision to enhance Nuzzo’s sentence for abuse of a position of trust pursuant to § 3B1.3, and we instruct the District Court, on remand, to resentence Nuzzo without such an enhancement.
II. The Safety-Valve Deduction
The District Court awarded Nuzzo a two-level “safety valve” deduction, see Oct. 9, 2003, Tr., at 109; U.S.S.G. §§ 2D1.1(b)(6) and 501.2(a); 18 U.S.C. § 3553(f); notes 13-15, ante. In order to award a safety-valve deduction, the District Court must find that an offender has proved, by a preponderance of the evidence, satisfaction of all five safety-valve criteria. See United States v. Conde, 178 *118F.3d 616, 621 (2d Cir.1999). At issue in this appeal is the fifth criterion, that “not later than the time of the sentencing hearing, the defendant [must have] truthfully-provided to the Government all information and evidence [he] has concerning the offense ... that were part of the same course of conduct or of a common scheme or plan ...U.S.S.G. § 501.2(a)(5).
The Government argues on cross-appeal that the District Court erred in awarding Nuzzo a safety-valve deduction, see Government’s Br. at 32-38, drawing our attention to the District Court’s statements with respect to Nuzzo’s untruthfulness and the host of inconsistent statements made by Nuzzo.
We review a district court’s factual findings for clear error, and its interpretation of the Sentencing Guidelines de novo. See United States v. Jeffers, 329 F.3d 94, 97 (2d Cir.2003). We acknowledge that “[t]he plain language of the statute [18 U.S.C. § 3553(f) ] requires the district court to make its own determination whether [a defendant] satisfied the safety-valve provision,” United States v. Gambino, 106 F.3d 1105, 1110 (2d Cir.1997), and that we owe a district court deference with respect to factual findings, especially those based on witness credibility, see Conde, 178 F.3d at 620.
It is precisely because we owe such deference to the District Court’s assessment of Nuzzo’s credibility that we conclude that the District Court erred in affording him the benefit of a safety-valve deduction. On the day of sentencing, the District Court stated:
I don’t have to really document my conclusion that Mr. Nuzzo is incapable of answering questions truthfully and wasn’t telling the truth here this morning or this afternoon. I don’t have to document that. Any person with a modicum of common sense would be able to reach that conclusion without a moment’s hesitation.
Oct. 9, 2003, Tr., at 97 (emphasis added). Shortly thereafter, the District Court stated:
I don’t believe that Mr. Nuzzo is entitled to the safety valve ... [because] I don’t believe that Mr. Nuzzo has provided the information which he has regarding the enterprise in which he was engaged. And I don’t think he has carried the burden of proof in that regard.
Id. at 100. Our review of the record shows that these statements by the District Court were amply justified. Nuzzo made inconsistent statements about a host of issues pertinent to his offense conduct, and his inconsistency spanned the long period (approximately thirteen months) between his post-arrest • statements and his statements before the District Court on the day of his sentencing. See Background II, ante.
We are unable to reconcile the District Court’s assessment of Nuzzo’s lack of credibility and the long record of Nuzzo’s untruthfulness with the fifth safety-valve criterion. U.S.S.G. § 5C1.2(a)(5) requires that the defendant provide complete24 in*119formation about his offense conduct and related activity, that he subjectively believes that information to be true, see United States v. Reynoso, 239 F.3d 143, 146-150 (2d Cir.2000), and that the information provided is objectively true, see id.
In these circumstances, we vacate so much of the sentence as granted Nuzzo a safety-valve deduction, and remand to the District Court for a reconsideration of the record, with instructions to re-sentence Nuzzo without such a deduction absent findings of fact by the District Court, supported by the record, to support a conclusion that he has met all five of the requisite criteria for such a deduction.25
III. The Downward Departure
Upon discovery of a Guideline range miscalculation, see Oct. 9, 2003, Tr., at 111; Background III, ante, and a mistaken sentence based upon that miscalculation, the District Court decided to stand firm on the sentence duration and, in order to reconcile the discrepancy, awarded a downward departure for “mitigating factors which weren’t contemplated.” Oct. 9, 2003, Tr., at 112. Subsequently, the District Court recorded the departure in its written order and judgment as “a 2 level departure pursuant to [U.S.S.G. § ] 5K2.0 for mitigating circumstances not contemplated by the [Sentencing] Commission.” [A 57]
The Government argues on cross-appeal that the District Court erred in awarding Nuzzo this departure on at. least three grounds: (1) the departure was unjustified, see Government’s Br. at 46-49; (2) the District Court failed to provide the Government advance notice that it was considering a departure, thereby depriving the Government of an opportunity to address the issue, see id. at 46; and (3) the District Court failed to satisfy the requirement of written, specific reasons for a departure as stated in the Prosecutorial Remedies and Other Tools to End the Exploitation of Children Today Act of 2003, Pub.L. No. 108-21, 117 Stat. 650 (2003), codified. at 18 U.S.C. § 3742(e)(3)(B) (“PROTECT Act” or *120Act ’), see id. at 39-46. We agree with each of these arguments.
It is undisputed that the District Court’s explanation of its decision to depart was conclusory and limited to a sentence in the written order and judgment invoking a provision of the Sentencing Guidelines. It is also undisputed that no notice was given to the Government by the District Court of its intention to depart downward.26
Accordingly, we vacate the District Court’s decision to depart downward, and we remand the cause with instructions that the District Court re-evaluate whether Nuzzo is entitled to a downward departure. If the District Court intends seriously to consider such a departure, it shall provide the Government prior notice of its intent to do so. If the District Court, following a hearing on notice, determines that a departure is indeed warranted, we direct the Court to adhere to the requirements of the PROTECT Act that the Court state in open court, as well as “with specificity in the written order and judgment,” reasons for imposing a sentence that differs from the prescription of the Sentencing Guidelines. See 18 U.S.C. §§ 3742(e)(3) and 3553(c)(2).
Conclusion
For the reasons stated above, we reverse the District Court’s decision to enhance Nuzzo’s sentence for abuse of a position of trust, and we vacate the District Court’s decisions to award Nuzzo a safety-valve deduction and a downward departure. We remand the cause to the District Court, and on remand, we instruct the District Court to (1) re-evaluate whether Nuzzo is entitled to a safety-valve deduction; (2) re-consider, on notice to the Government as appropriate, whether Nuz-zo is entitled to a downward departure; and, if it finds that such a departure is warranted, (3) state in open court, and in a written order and judgment, its reasoning in a manner that complies with the requirements of the PROTECT Act.
We have considered Nuzzo’s other arguments on appeal, see note 20, ante, and we hold that they are all without merit. Accordingly, in all other respects the judgment of the District Court is affirmed.