Circuit Judge.

Osama Musa Alferahin appeals his conviction under 18 U.S.C. § 1425 (a) for knowingly procuring naturalization “contrary to law.” The basis for this conviction was Alferahin’s failure to disclose, on an application for permanent resident status, that he had been previously married. On appeal, Alferahin contends that the district court erred by failing to instruct the jury that 18 U.S.C. § 1425 (a) contains a requirement of “materiality.” Alferahin further contends that his attorney’s failure to obtain an instruction on the issue of materiality constituted a denial of his right to effective assistance of counsel under the Sixth Amendment. We reverse his conviction and remand for a new trial.

I.

Osama Musa Alferahin was born in Kuwait as a citizen of Jordan. He has married twice. He married his first wife— Alicia Jaremo Y Pradeñas, a citizen of Spain — on February 27, 1995. According to Alferahin, he divorced her in a religious ceremony at the Islamic Cultural Center in Madrid, Spain, on September 1, 1997. That divorce, however, was not officially recorded in the Spanish civil registry until February 16, 2000.

Alferahin married his second wife— Reem Alferahin, a naturalized citizen of the United States — on December 31, 1997, in Amman, Jordan. A little more than one month later, on February 2, 1998, he applied for permanent residence in the United States based on his status as the spouse of an American citizen. Alferahin thus married his second wife and applied for permanent residence in the United States after the religious ceremony in Spain in which he claims to have divorced his first wife, but before the Spanish civil registry had recorded that divorce officially.

As part of Alferahiris application for permanent residence, his second wife signed and submitted a petition known as Form 1-130. Because Form 1-130 involves an application for permanent residence based on an alien’s marriage to an American citizen, this form requires the petitioner to disclose the existence of any and all *1152 previous marriages involving either the United States citizen or the alien-spouse, as well as the date of the dissolution of those marriages. Alferahin, who testified that he prepared Form 1-130 himself on behalf of his wife, provided inaccurate information on this form. In response to questions about the existence and dissolution of previous marriages, Alferahin responded “N/A,” implying that the questions were not applicable to him.

On the basis of the information submitted on Form 1-130, Alferahin obtained status as a permanent resident. Two years later, in May of 2002, Alferahin became a naturalized citizen. More than one year after obtaining citizenship — and more than five years after he submitted his application for permanent residence — -Alferahin was arrested and charged with the crime of knowingly procuring naturalization contrary to law. See 18 U.S.C. § 1425 (a)(pun-ishing those who “knowingly procure! ] or attempt! ] to procure, contrary to law, the naturalization of any person, or documentary or other evidence of naturalization or of citizenship”).

At trial, the government contended that Alferahin deliberately withheld information about his first marriage from his application. According to the government, Alferahin had explained to an INS investigator that he omitted the information because he “didn’t want to complicate the process.” The government further emphasized that the omitted information was pertinent to Alferahin’s application because his petition for permanent residence depended on the validity of his second marriage to an American citizen. The disclosure of truthful information, the government contended, would have led immigration officials to investigate the dissolution of Alferahin’s first marriage and to inquire into the validity of his second.

In opposition to the government’s position, Alferahin provided a culturally based explanation for the inaccuracies. He explained that, in Moslem culture, a man may have multiple wives and need not disclose his marital status; he claimed that due to this cultural background, he had responded “not applicable” based on his belief that the questions literally did not apply to him. The defense also downplayed the significance of the omitted information. For instance, Alferahin’s wife testified that they considered information about his marital status “just not important.” In addition, defense counsel cross-examined the government’s witnesses on the likely consequences of a complete disclosure by Alferahin, suggesting that the INS would have processed his application for permanent residence in exactly the same fashion if Alferahin had revealed the existence of his first marriage.

At the conclusion of the trial, the district court noted that there were “no stock instructions on this particular crime.” Since neither side had proposed jury instructions on the elements of the charged offense, the district court drafted instructions on its own for the attorneys to review. There was no mention of the need for an instruction on materiality.

During closing arguments, however, both the prosecution and the defense called the jury’s attention to the significance of the omitted information. The prosecution argued that Alferahin had “concealed a material fact,” adding that the existence of Alferahin’s first marriage “is a material fact because we need to know if there’s some sort of marriage fraud going on.” 1 By contrast, the de *1153 fense underscored the insignificance of the information, emphasizing that “we’re arguing over what is an irrelevant fact” and noting that the government’s witnesses had not testified that Alferahin’s application would have been denied even if Alferahin had properly disclosed his first marriage. Alferahin’s attorney argued: “No one is even suggesting that Osama would not have been granted citizenship if he had put Alicia’s name and their divorce dates ... on the 1-130.”

During the middle of closing arguments, the district court noted this emphasis on materiality and, sua sponte, raised the question of a materiality instruction. Pointing to the government’s argument that Alferahin’s omission had been material, the district judge noted that materiality was not one of the elements included in the jury instructions and suggested that “perhaps it should have been.” The government responded that the proposed instructions “mirror[ed] the statute.” But the government did not object to the materiality instruction, adding that “we have always put in all of our proof with respect to this case that it was material, to cover ourselves, ... because in other statutes that we were contemplating charging the defendant with, materiality was always an issue.”

When the district court asked defense counsel whether a materiality instruction was necessary, Alferahin’s attorney responded: “I don’t think it’s appropriate.” The defense noted that materiality was not part of the indictment, and he stated that, if there had been an allegation that the omitted information was material, he would have called an expert witness to discuss the meaning of materiality, adding that “now it’s sort of beyond the pale.” The district court asked: “Do you feel that the elements in the instruction are complete and accurate as far as what the government has to prove in the case?” Alferahin’s attorney replied: ‘Tes.” Satisfied that the defense considered the proposed instructions an accurate reflection of applicable law, the judge submitted the instructions to the jury unamended.

The jury convicted Alferahin, and the district court sentenced Alferahin to time served, as well as to thirty-six months of supervised release. The district court also revoked Alferahin’s United States citizenship. See 8 U.S.C. § 1451 (e) (“When a person shall be convicted ... of knowingly procuring naturalization in violation of law, the court in which such conviction is had shall thereupon revoke, set aside, and declare void the final order admitting such person to citizenship, and shall declare the certificate of naturalization of such person to be canceled.”).

Alferahin argues that his conviction is invalid. We have jurisdiction to consider his appeal under 28 U.S.C. § 1291 .,

II.

Alferahin makes two arguments on appeal: first, that the district court erred in failing to instruct the jury that to convict it must find beyond a' reasonable doubt that his misrepresentations were material; and second, that his attorney’s failure to procure an instruction on the issue of materiality constituted ineffective assistance of counsel under Strickland v. Washington, 466 U.S. 668 , 104 S.Ct. 2052 , 80 L.Ed.2d 674 (1984). We address each argument in turn.

A

Alferahin’s first contention is that the district court submitted legally erroneous jury instructions regarding the elements of the crime. Defense counsel, however, raised no objection at trial to the allegedly erroneous jury instructions. Indeed, Alferahin’s attorney not only failed *1154 to object to the omission of a materiality instruction, but he explicitly rejected the judge’s suggestion that such an instruction might be appropriate. When a defendant fails to raise a legal objection at trial but raises the objection for the first time on appeal, we review only for plain error. See FED. R. CRIM. P. 52(b); CHARLES ALAN WRIGHT ET AL., FEDERAL PRACTICE & PROCEDURE § 856, at 490-514 (3d ed.2004). Therefore, we must determine not only whether the jury instructions were incorrect, but whether their submission to the jury was plainly erroneous. 2

Under the plain error doctrine, a defendant must establish (1) that the proceedings below involved error, (2) that the error is plain, and (3) that the error affected the substantial rights of the aggrieved party. See United States v. Olano, 507 U.S. 725, 732-35 , 113 S.Ct. 1770 , 123 L.Ed.2d 508 (1993). In addition, a defendant must also show that the error “ ‘seriously affect[s] the fairness, integrity or public reputation of judicial proceedings’ ” before we will exercise our discretion pursuant to Rule 52(b) to correct the plain error. See id. at 736 , 113 S.Ct. 1770 (quoting United States v. Atkinson, 297 U.S. 157, 160 , 56 S.Ct. 391 , 80 L.Ed. 555 (1936)); see also United States v. Vences, 169 F.3d 611, 613 (9th Cir.1999).

i.

Federal law prohibits an alien from knowingly procuring United States citizenship “contrary to law.” 18 U.S.C. § 1425 (a). In United States v. Puerta, 982 F.2d 1297 (9th Cir.1992), we held that § 1425(a) contains a materiality requirement. See id. at 1305. We concluded that, in order to obtain a conviction under this section, the government must prove (1) that the false information provided by the defendant has a tendency to suggest that he was qualified for naturalization, (2) that the production of truthful information would have led to the discovery of facts relevant to the alien’s petition for naturalization, and (3) that there must be evidence sufficient to “give rise to a ‘fair *1155 inference’ ” that the applicant was statutorily ineligible for naturalization. Id. at 1300-01,1303-04 (quoting Kungys v. United States, 485 U.S. 759, 783 , 108 S.Ct. 1537 , 99 L.Ed.2d 839 (1988) (Brennan, J., concurring)). We thus reversed the conviction of an alien who had provided false information on his application for permanent residence as to his date and place of birth, finding that there was “no evidence” from which any finder of fact could fairly infer that Puerta was actually ineligible for naturalization. Id. at 1305.

We emphasized in Puerta the uniqueness of a denaturalization proceeding. Indeed, we stressed that we were “look[ing] to the standards governing materiality in the denaturalization context as a guide to determining what is ‘contrary to law under 18 U.S.C. § 1425 .” Id. at 1301 (emphasis added). As a result, in Puerta we relied on Kungys v. United States as the “leading denaturalization case.” Id.

In Kungys , the Supreme Court interpreted a statutory provision that directed United States attorneys to begin denaturalization proceedings against any naturalized citizen who procured citizenship “by concealment of a material fact or willful misrepresentation.” Kungys, 485 U.S. 759, 764 , 108 S.Ct. 1537 , 99-L.Ed.2d 839 (1988) (plurality opinion) (quoting 8 U.S.C. § 1451 (a)). While the Kungys Court produced multiple opinions on the meaning of “materiality,” all nine Justices agreed that a material misrepresentation must have at least “a natural tendency to produce the conclusion that the applicant was qualified” for citizenship. Id. at 771-72 , 108 S.Ct. 1537 . Additionally, the Justices all agreed that a misrepresentation would not be material unless an honest representation “would predictably have disclosed other facts relevant to [the applicant’s] qualifications.” Id. at 774 , 108 S.Ct. 1537 .

In addition to these requirements, however, Justice Brennan’s controlling opinion in Kungys emphasized that “citizenship is a most precious right, and as such should never be forfeited on the basis of mere speculation or suspicion.” Id. at 783-84 , 108 S.Ct. 1537 (Brennan, J., concurring) (citation omitted). Justice Brennan therefore opined that the government also had to support its assertion of materiality with “evidence sufficient to raise a fair inference that a statutorily disqualifying fact actually existed.” Id. at 783 , 108 S.Ct. 1537 . Thus, the Kungys decision established a more rigorous definition of materiality that is unique to the context of denaturalization proceedings.

Building on Kungys , we held in Puerta that the prohibition under 18 U.S.C. § 1425 (a) on the procurement of citizenship “contrary to law” incorporated not only á requirement of materiality, but the unique definition of materiality articulated in Justice Brennan’s controlling opinion in Kungys. See Puerta, 982 F.2d at 1301, 1303-04 . In doing so, we recognized “the potential anomaly in Justice Brennan’s test in Kungys , which contemplates a higher standard of materiality in immigration law than does the criminal law generally.” Id. at 1305. We concluded in Puerta — with complete awareness of potentially incongruous constructions in the criminal law — that relevant Supreme Court precedent in the context of denaturalization required us to read § 1425(a) as containing a heightened materiality requirement. Under Puerta , then, the crime charged against Alferahin includes not only a requirement of materiality, but the more substantial requirement that the government produce evidence sufficient to raise a fair inference that Alferahin was statutorily ineligible for permanent residence.

The government argues that Puerta was decided incorrectly and that § 1425(a) contains no materiality requirement. In support of this argument, the government re *1156 lies on United States v. Wells, 519 U.S. 482 , 117 S.Ct. 921 , 137 L.Ed.2d 107 (1997), a case in which the Supreme Court held that there was no materiality requirement in a statute that criminalized “knowingly mak[ing] any false statement or report” to a federal bank. Id. at 483 , 117 S.Ct. 921 (quoting 18 U.S.C. § 1014 (1994)) (alteration in original). We are unpersuaded that the Supreme Court’s decision in Wells undermines our decision in Puerta . First, Wells involved entirely different statutory language (whereas Wells construed a statute prohibiting “false statements,” Puerta involved a statute prohibiting the procurement of citizenship “contrary to law”) and pertains to an entirely different statutory context (whereas Wells involved a criminal statute, Puerta involved the unique context of denaturalization proceedings). Moreover, the Wells Court was careful to distinguish its holding from other cases involving the issue of materiality, including the Kungys decision upon which we relied in Puerta. See Wells, 519 U.S. at 491-94 , 117 S.Ct. 921 & n. 10 (acknowledging the continuing viability of Kungys and implicitly rejecting the broad rule that a requirement of materiality must'always be explicit in the statutory text). Given our reliance on “the standards governing materiality in the denaturalization context,” 982 F.2d at 1300-01 , and our explicit recognition of potentially incongruous materiality requirements in the criminal context, we think that Wells does little to undermine either the reasoning or the holding of Puerta. 3

Because we conclude that Puerta is still good law and that 18 U.S.C. § 1425 (a) contains a requirement of materiality, we find that it was error for the district court to fail to instruct the jury on this element of the crime. See United States v. Mendoza, 11 F.3d 126, 128-29 (9th Cir.1993).

ii.

Having determined that the jury instructions were erroneous, we must now determine whether the error was plain. Under the Supreme Court’s decision in United States v. Olano, an error is plain when it is “clear” or “obvious” under the law. 507 U.S. at 734 , 113 S.Ct. 1770 .

*1157 We conclude that the error contained in Alferahin’s jury instruction was indeed plain. Our decision in Puerta unambiguously established materiality as an element of the crime of knowingly procuring naturalization contrary to law under § 1425(a), and that decision was binding on the district court in this case. We thus hold that a district court’s error is plain when its jury instructions fail to incorporate an element of the crime that has been clearly established by Ninth Circuit precedent. See United States v. Perez, 116 F.3d 840, 846-47 (9th Cir.1997) (en banc) (finding plain error where a judge submitted incomplete jury instructions, despite the fact that months-old circuit court precedent “clearly and unambiguously required the submission of the ‘in relation to’ element to the jury” in a prosecution for use of a firearm in relation to drug trafficking); United States v. Gaudin, 28 F.3d 943, 951-52 (1994) (en banc) (finding plain error where a judge failed to submit a “materiality” instruction because fifteen-year-old Ninth Circuit precedent had established materiality as an element), aff'd 515 U.S. 506 , 115 S.Ct. 2310 , 132 L.Ed.2d 444 (1995).

Hi

We also conclude that the submission of the plainly erroneous jury instructions affected Alferahin’s substantial rights.

It is a basic tenet of due process that a criminal defendant’s conviction must rest upon a jury’s finding beyond a reasonable doubt that he is guilty of each element of the crime charged. See United States v. Gaudin, 515 U.S. 506, 511 , 115 S.Ct. 2310 , 132 L.Ed.2d 444 (1995) (“The Constitution gives a criminal defendant the right to demand that a jury find him guilty of all the elements of the crime with which he is charged; one of the elements in the present case is materiality; respondent therefore had a right to have the jury decide materiality.”); see also Sullivan v. Louisiana, 508 U.S. 275, 277-78 , 113 S.Ct. 2078 , 124 L.Ed.2d 182 (1993) (“The prosecution bears the burden of proving all elements of the offense charged, and must persuade the factfinder ‘beyond a reasonable doubt’ of the facts necessary to establish each of those elements” (citations omitted)); Carella v. California, 491 U.S. 263, 265 , 109 S.Ct. 2419 , 105 L.Ed.2d 218 (1989) (“The Due Process Clause of the Fourteenth Amendment denies States the power to deprive the accused of liberty unless the prosecution proves beyond a reasonable -doubt every element of the charged offense. Jury instructions relieving States of this burden violate a defendant’s due process rights.” (citing In re Winship, 397 U.S. 358, 364 , 90 S.Ct. 1068 , 25 L.Ed.2d 368 (1970))); Perez, 116 F.3d at 847 (“Failure to submit an essential element to a jury relieves the prosecution of its obligation to prove every element beyond a reasonable doubt.” (citing Carella v. California, 491 U.S. 263, 265 , 109 S.Ct. 2419 , 105 L.Ed.2d 218 (1989) (per curiam) (citing In re Winship, 397 U.S. 358, 364 , 90 S.Ct. 1068 , 25 L.Ed.2d 368 (1970)))). Simply put, Alferahin was not convicted of procuring naturalization contrary to law, as we have defined that crime; rather, he was convicted of committing only some of the elements of that crime. A defendant’s due process rights are unquestionably implicated when his purported conviction rests on anything less than a finding of guilt as to all the elements of the crime.

We recognize, as the government points out, that the omission of an element from jury instructions does not always “affect” a defendant’s substantial rights and that the failure to submit an element to the jury is not per se prejudicial. See, e.g., Neder v. United States, 527 U.S. 1, 15 , 119 S.Ct. 1827 , 144 L.Ed.2d 35 (1999) (holding that “the omission of an element is an *1158 error that is subject to harmless-error analysis”); United States v. Baldwin, 987 F.2d 1432, 1439 (9th Cir.1993) (holding that a defendant had failed to establish prejudice as a result of an omitted element because the defendant’s conviction on other counts was “the functional equivalent” of a finding as to the omitted element). For example, in United States v. Neder, 197 F.3d 1122 (11th Cir.1999), on remand from 527 U.S. 1 , 119 S.Ct. 1827 , 144 L.Ed.2d 35 (1999), the Eleventh Circuit held that the omission of a materiality instruction was harmless error. Id. at 1134. In that case, however, the government’s evidence “incontrovertibly established] that Neder’s false statements were material” to the charged crimes of tax and bank fraud, and the defendant’s attorney did not even argue to the jury or on appeal that it would be possible for a factfinder to conclude that the defendant’s false statements were immaterial. Neder, 527 U.S. at 16 , 119 S.Ct. 1827 . Other cases have also upheld convictions rendered on incomplete or erroneous jury instructions, but like Neder, these cases have relied on the existence of “strong and convincing evidence” that the missing element of the crime had been adequately proved by the prosecution. Perez, 116 F.3d at 848 ; see also United States v. Smith, 282 F.3d 758 (9th Cir.2002) (holding that the omission of an element from jury instructions was not plain error where the underlying fact supporting the element was “undisputed” based on the “uncontroverted testimony” of a government witness).

In this case, we are unpersuaded that the evidence against Alferahin was so strong or convincing that the omission of materiality from the jury instructions did not affect his substantial rights. Quite the opposite: the record contains ample support for Alferahin’s contention that he was prejudiced by the omission of the materiality requirement. Defense counsel presented evidence supporting the view that the information omitted from Form 1-130 was immaterial, including testimony by Alferahin’s wife that they considered the information about his first marriage unimportant and cross-examination of INS officials regarding what actions the agency would have taken if it had discovered the truth about Alferahin’s first marriage. Defense counsel’s effort to minimize the significance of information pertaining to Alferahin’s first marriage is also evident in his attorney’s closing statements, in which he argued that truthful disclosure would not have affected Alferahin’s application for permanent residence and emphasized that “we’re arguing over what is an irrelevant fact.”

Unquestionably, a materiality instruction would have buttressed the defense’s strategy of downplaying the importance of Alferahin’s misrepresentations. Obviously, if the district court had directed the jury to consider the materiality of Alferahin’s misrepresentations and explained the meaning of “materiality” in the context of a denaturalization proceeding, the defense would have had more traction. Indeed, the defense’s approach to the case was quixotic; without the materiality instruction, the jury properly would have disregarded Alferahin’s immateriality argument if it had followed the instructions submitted by the district court. Because Alferahin purported to contest — and, but for the omission from the jury instructions of one of the elements of the crime, might have effectively contested — the issue of materiality, we find that the incomplete jury instructions were in fact prejudicial to him. 4

*1159 iv.

Because the jury instructions were erroneous, the error was plain, and the error affected Alferahin’s substantial rights, we have “authority to order the correction” of the plain error under Rule 52(b). Olano, 507 U.S. at 735 , 113 S.Ct. 1770 . But the language of Rule 52(b) is permissive, not mandatory, and therefore we are not “required to do so.” Id.

As the Supreme Court has instructed, “[t]he court of appeals should correct a plain forfeited error affecting substantial rights if the error ‘seriously affect[s] the fairness, integrity or public reputation of judicial proceedings.’ ” Id. at 736 , 113 S.Ct. 1770 (quoting United States v. Atkinson, 297 U.S. 157, 160 , 56 S.Ct. 391 , 80 L.Ed. 555 (1936)). We have relied on this so-called “final, discretionary prong” of Olano and have declined to correct plain error where we concluded that the greater threat to the integrity and fairness of judicial proceedings would arise from the reversal of a conviction on flawed jury instructions rather than from affirming an imperfect verdict. See Perez, 116 F.3d at 848 (citing Johnson, 520 U.S. at 470, 117 S.Ct. 1544 ). Sitting en banc in Perez , for example, the Ninth Circuit declined to exercise its discretion to correct the plain error of incomplete jury instructions because the government’s “strong and convincing evidence” demonstrated that a different decision by the jury would be “extremely unlikely.” Id.; see also Johnson v. United States, 520 U.S. 461, 470 , 117 S.Ct. 1544 , 137 L.Ed.2d 718 (1997) (refusing to reverse plain error of an omitted materiality instruction where the evidence of materiality was “overwhelming”); United States v. Uchimura, 125 F.3d 1282, 1287 (9th Cir. 1997) (same). In conducting this final phase of plain error analysis, the Ninth Circuit has therefore instructed that “we consider all circumstances at trial including the strength of the evidence against the defendant.” Perez, 116 F.3d at 847 (quoting United States v. Campbell, 42 F.3d 1199, 1204 (9th Cir.1994), cert. denied, 514 U.S. 1091 , 115 S.Ct. 1814 , 131 L.Ed.2d 738 (1995) (internal quotation marks omitted)).

We conclude that it is appropriate to exercise our discretion to correct the plain error embodied in the incomplete jury instructions and remand for a new trial. The government produced evidence that the information about Alferahin’s first marriage was relevant, insofar as his application for permanent residence rested on the validity of his marriage to Reem Alferahin. But that evidence fell far short of proving materiality, as we have defined that term in the context of § 1425(a). In order to obtain a conviction against Alferahin under 18 U.S.C. § 1425 (a), the govern *1160 ment had to provide evidence “giving rise to a ‘fair inference’ of ineligibility.” Puerto, 982 F.2d at 1304 (quoting Kungys, 485 U.S. at 783 , 108 S.Ct. 1537 (Brennan, J., concurring)). Proof of materiality in Alferahiris case would therefore require the government to produce evidence showing that the disclosure of information about Alferahin’s first marriage would have given rise to evidence that fairly suggests the invalidity of Alferahiris second marriage. The government did not make, much less attempt, such a specific showing here. Indeed, the government’s evidence only hinted at the possibility of the invalidity of Alferahiris second marriage. 5 Accordingly, we reverse Alferahiris conviction and remand the case for a new trial.

B.

Alferahiris second contention is that his attorney deprived him of his Sixth Amendment right to effective assistance of counsel when he rejected the district court’s proffer of a materiality instruction. 6 Under Strickland , a defen *1161 dant who complains that his attorney has provided ineffective assistance must demonstrate two things to establish a claim under the Sixth Amendment. First, the defendant must show that his attorney’s performance “fell below an objective standard of reasonableness.” Strickland, 466 U.S. at 688 , 104 S.Ct. 2052 . Second, the defendant must show prejudice — that is, he must demonstrate “a reasonable probability that, but for counsel’s unprofessional errors, the result of the proceeding would have been different.” Id. at 694 , 104 S.Ct. 2052 .

As to the first element of the Strickland inquiry, we conclude that the performance of Alferahin’s attorney fell below an objective standard of reasonableness. As far as deficient performance is concerned, our holding in United States v. Span, 75 F.3d 1383 (9th Cir.1996), is precisely on point. In that case, as in the present one, the defense attorney failed to obtain an instruction on a critical element of the charged crime and thereby abandoned one of his client’s most promising defenses. Id. at 1390 . In Span , we observed: “Counsel’s errors with the jury instructions were not a strategic decision to forego one defense in favor of another. They were the result of a misunderstanding of the law.” Id. We held in Span that the attorney’s failure to procure favorable jury instructions constituted ineffective assistance of counsel. Id. at 1390-91 .

As in Span , defense counsel in this case considered the erroneous jury instructions “accurate as far as what the government has to prove in the case.” Moreover, during closing arguments defense counsel indicated to the district court that he would have produced additional testimony if he had understood that the prosecutor was obliged to prove the materiality of his client’s misrepresentations. It is thus clear from the record that Alferahin’s attorney did not intend strategically to- fore-go the materiality instruction. Instead, he had -no idea that such an instruction was available to his client as a matter of right. While the government suggests that there may be unarticulated strategic reasons for the actions of defense- counsel in this case, it does not offer any such plausible explanations, and we cannot imagine any. As we stated in Span : “We have a hard time seeing what kind of strategy, save an ineffective one, would lead a lawyer to deliberately omit his client’s only defense, a defense that had' a ... likelihood of success, and a defense that he specifically stated he *1162 [would have] had every intention of presenting.” Id. at 1390 .

We turn, then, to the second element of the Strickland inquiry: prejudice. For the reasons set forth in our plain error analysis above, we conclude that Alferahin was prejudiced by his lawyer’s decision to decline the proffered instruction on materiality. Defense counsel produced significant evidence relating to the immateriality of the defendant’s statements — indeed, one of Alferahin’s attorney’s tactics throughout the trial was to persuade the jury that the information omitted from his application for permanent residence was not germane to his admission to the country and that the INS would have handled the application in exactly the same way even if it had known about Alferahin’s first wife. A materiality instruction would have helped defense counsel’s strategy of emphasizing the unimportance of Alferahin’s misrepresentations, and the decision by Alferahin’s attorney to refuse the materiality instruction prevented the jury from considering the very theory of the case on which the attorney was relying. Under these circumstances, the attorney’s performance was prejudicial to Alferahin, thereby satisfying the second prong of Strickland 7

III.

We hold that the submission of incomplete jury instructions was plain error in this case and that Alferahin’s attorney provided constitutionally deficient assistance when he declined an offer by the judge to instruct the jury on the element of materiality. For these two independent reasons, Alferahin is entitled to a new trial. REVERSED and REMANDED.

. At trial, the government’s witness in fact testified that he did not know what influence multiple, simultaneous marriages would have had on the INS’s decision regarding Alferahin’s application for permanent residence, assuming the legality of those marriages in the jurisdiction where they took place.

. The government argues that the decision by Alferahin's attorney to reject the materiality instruction constitutes a waiver that makes the district court's error unreviewable on appeal. See, e.g., United States v. Guthrie, 931 F.2d 564, 567 (9th Cir.1991) (holding that a criminal defendant had waived his right to complain of an omitted jury instruction because defense counsel had refused the district court’s offer to provide it). Under Ninth Circuit law, however, it is not enough simply for the defense attorney to be implicated in the error. In order to constitute a waiver under Ninth Circuit law, defense counsel must make an "intentional relinquishment or abandonment of a known right.” Olano, 507 U.S. at 732 , 113 S.Ct. 1770 (distinguishing forfeiture, defined as "the failure to make the timely assertion of a right,” from waiver, defined as "the 'intentional relinquishment of a known right,' " (quoting Johnson v. Zerbst, 304 U.S. 458, 464 , 58 S.Ct. 1019 , 82 L.Ed. 1461 (1938))); see also United States v. Perez, 116 F.3d 840, 845 (9th Cir.1997) ("Until now, our invited error doctrine has focused solely on whether the defendant induced or caused the error.... We now recognize, however, that we must also consider whether the defendant intentionally relinquished or abandoned a known right.” (citations omitted)).

The record in this case clearly indicates that Alferahin's attorney did not intentionally relinquish a known right. Rather, both defense counsel and the district court were operating under a misapprehension of the applicable law. Alferahin's attorney explicitly stated that he considered the judge’s erroneous instructions "complete and accurate as far as what the government has to prove in the case.” In light of this record, it is impossible to say that Alferahin's attorney knowingly and intentionally abandoned a known right. See Perez, 116 F.3d at 845 (conducting plain error review, even where defense counsel had submitted erroneous juiy instructions, because "neither defendants, the government, nor the court was aware” that the instructions omitted an element).

. Even if we were inclined to credit the government’s construction of Wells and decide the Puerta case differently as a matter of first impression (which we are not), it would still be inappropriate for us to overrule the binding precedent of Puerta because there is still an adequate basis for reconciling our holding in Puerta with the Supreme Court’s decision in Wells. See Miller v. Gammie, 335 F.3d 889, 893, 900 (9th Cir.2003) (en banc) (noting that a panel may overhaul binding circuit precedent only when "the relevant court of last resort [has] undercut the theory or reasoning underlying the prior circuit precedent in such a way that the cases are clearly irreconcilable " (emphasis added)). For the same reasons, we are not persuaded by the government's reliance on two district court decisions — one post-Wells and one pre-Wells— holding that § 1425(a) does not contain a materiality requirement. See United States v. Biheiri, 293 F.Supp.2d 656, 658-59 (E.D.Va.2003); United States v. Rogers, 898 F.Supp. 219 (S.D.N.Y.1995). We believe these decisions are based on a flawed construction of § 1425(a) and that we are bound by our previous decision in Puerta notwithstanding these contrary holdings. The government’s citation to our decision in United States v. Hart, 291 F.3d 1084 (9th Cir.2002) (per curiam), is similarly unpersuasive. In Hart , we held that a "false statement” on a passport application need not be material in order to support a conviction under 18 U.S.C. § 1542 . See id. at 1085 (quoting Neder v. United States, 527 U.S. 1 , 23 n. 7, 119 S.Ct. 1827 , 144 L.Ed.2d 35 (1999) (citing Wells, 519 U.S. at 491 , 117 S.Ct. 921 )). That case, however, involved precisely the same statutory language as the Supreme Court’s decision in Wells . Our holding in Hart was therefore compelled by the Supreme Court's reasoning in Wells . Our holding in this case is not.

. Because we find that the omission of the materiality instruction was prejudicial to Alferahin, we need not address the question of whether an error can "affect” a defendant’s substantial rights for purposes of plain error analysis without actually prejudicing the de *1159 fendant. That question appears to be an open one, as both the Supreme Court and the Ninth Circuit have dodged it. See Olano, 507 U.S. at 735 , 113 S.Ct. 1770 (“We need not decide whether the phrase ‘affecting substantial rights’ is always synonymous with 'prejudicial.' "); Perez, 116 F.3d at 847 ("[W]e need not make the difficult determination of ... ‘whether the phrase “affecting substantial rights” is always synonymous with “prejudicial” ' ” (quoting Olano, 507 U.S. at 735 , 113 S.Ct. 1770 )). We express no opinion as to whether there is any difference between an error that prejudices a defendant and one that affects his rights, such that the error could be remedied on plain error review even though it did not prejudice the defendant. In the present case, we conclude that Alferahin has carried his burden of proving that the omission of the materiality instruction had a "prejudicial impact on the jury's deliberations” in that it permitted the jury to convict him without considering the very element his attorney attempted most vigorously to contest — namely, the materiality of the information omitted from his application for permanent residence. See Olano, 507 U.S. at 734 , 113 S.Ct. 1770 (quoting United States v. Young, 470 U.S. 1 , 17 n. 14, 105 S.Ct. 1038 , 84 L.Ed.2d 1 (1985)).

. The government contends that Alferahin has failed to controvert any of the government’s evidence regarding the materiality of his misrepresentations. Specifically, the government points to the testimony of INS Agent William Johnston, who explained at trial that information about an alien spouse’s previous marriages is material because the agency would have to determine whether those previous marriages had been terminated and whether the alien's present marriage to a United States citizen — on which his application for permanent residence depends — was valid. The government argues that the jury would have reached the same result even if the court had instructed on materiality, and it cites United States v. Wells for the proposition that the truthful disclosure of Alferahin's first marriage would have had a "natural tendency to influence, or be[en] capable of influencing, the decision of the decisionmaking body to which it was addressed.” Wells, 519 U.S. at 489 , 117 S.Ct. 921 (citing Kungys, 485 U.S. 759, 770 , 108 S.Ct. 1537 , 99 L.Ed.2d 839 (1988) (plurality opinion)).

The government’s argument, however, misunderstands what materiality requires in the present context. The government is correct to note, consistent with the plurality opinion of the Supreme Court in Kungys , that the truthful information must have a tendency to influence, or be capable of influencing, the government’s decision in order to be material. Nonetheless, as we explained above Justice Brennan's controlling opinion in Kungys and this court's decision in Puerta require more in the context of denaturalization. In order to be material, the government must also provide evidence "giving rise to a 'fair inference' of ineligibility.” Puerta, 982 F.2d at 1304 (quoting Kungys, 485 U.S. at 783 , 108 S.Ct. 1537 (Brennan, J., concurring)). It is this higher standard that the government has failed to prove beyond a reasonable doubt in Alferahin’s case.

. The government contends that we should not reach Alferahin's claim of ineffective assistance of counsel because of the Ninth Circuit’s preference for hearing such claims via habeas petitions, rather than on direct appeal. We acknowledge that, "as a general rule, we do not review challenges to the effectiveness of defense counsel on direct appeal.” United States v. Jeronimo, 398 F.3d 1149, 1155 (9th Cir.2005) (citing United States v. McKenna, 327 F.3d 830, 845 (9th Cir.2003)), cert. denied, - U.S. -, 126 S.Ct. 198 , 163 L.Ed.2d 188 (2005). And we reiterate here the policy concern that informs this rule— namely, that more complete development of the record in the context of a habeas petition allows for a more effective inquiry into the decisions of defense counsel. See United States v. Laughlin, 933 F.2d 786, 788-89 (9th Cir.1991) ("[A] a habeas corpus proceeding is preferable [for the adjudication of an ineffective assistance claim] as it permits the defendant to develop a record as to what counsel did, why it was done, and what, if any, prejudice resulted.”).

We have previously held, however, that a defendant need not wait for collateral proceedings to obtain relief from an ineffective attorney. Thus, we have made exceptions to our general rule, allowing claims of ineffective assistance of counsel to proceed "(1) where the record on appeal is sufficiently developed to permit determination of the issue, or (2) where the legal representation is so inadequate that it obviously denies a defendant his Sixth Amendment right to counsel.” Jeroni *1161 mo, 398 F.3d at 1156 (citing United States v. Daychild, 357 F.3d 1082, 1095 (9th Cir. 2004)). Alferahin's claim of ineffective assistance of counsel qualifies as an exceptional case that merits review on direct appeal. Defense counsel’s alleged ineffectiveness in this case stems from a specific and discrete conversation, recorded clearly in the record, in which Alferahin’s attorney declined a highly favorable instruction on a clearly established element of the crime with which his client was charged. The claim is limited specifically to this failure to request proper jury instructions and therefore does not require, as many other claims of ineffective assistance do, an assessment of defense counsel’s myriad decisions and actions throughout the course of trial. In United States v. Swanson, we held that "the record is sufficient for a review of the merits of [a defendant's] constitutional claim” for ineffective assistance of counsel when the defendant "relies solely on the reported statements made by [his attorney] during final argument.” 943 F.2d 1070, 1072 (9th Cir.1991). The instant case is similar to Swanson: Alferahin contends that his attorney provided unconstitutionally deficient assistance when, in a side bar conference following the prosecution's closing argument, the attorney rejected a proposed instruction that would have supported one of the strongest aspects of the defendant’s case. We therefore conclude that the record is sufficiently developed on this point to permit our assessment of Alferahin's Sixth Amendment claim on direct appeal.

. The government contends that the attorney's error was harmless — that is, not prejudicial — precisely because defense counsel argued to the jury that Alferahin's misrepresentations were immaterial. In other words, the government contends that the omission of a materiality instruction was harmless because the jury disbelieved Alferahin's contention that the misrepresentations were not germane. The hole in the government's logic is evident: without a jury instruction on the issue of materiality, it is impossible to tell whether the jury believed or disbelieved Alferahin's contentions. The instructions used by the jury to convict Alferahin said nothing of the government's burden of proving materiality, and the government cannot now argue it met a burden that was never imposed.