dissenting:
The right guaranteed by law to a defendant [to testify on his own behalf] is narrowly the right to testify truthfully in accordance with the oath — unless we are to say that the oath is mere ritual without meaning. This view of the right involved is confirmed by the unquestioned constitutionality of perjury statutes, which punish those who willfully give false testimony.
United States v. Grayson, 438 U.S. 41, 54, 98 S.Ct. 2610, 57 L.Ed.2d 582 (1978).
We have repeatedly insisted that when defendants testify, they must testify truthfully or suffer the consequences.
United States v. Havens, 446 U.S. 620, 626, 100 S.Ct. 1912, 64 L.Ed.2d 559 (1980).
In this case, we must decide whether the doctrine of collateral estoppel precludes the government from prosecuting Buena-ventura Castillo-Basa for perjury arising from what appears to be a material lie under oath he gave in an earlier trial, where a jury acquitted him of the crime of being a deported alien found in the United States. The government alleges that Castillo-Basa testified falsely in that prior trial when he insisted that he never attended the deportation hearing that resulted in his physical removal from the United States. I conclude from the record that Castillo-Basa has not carried his burden of showing that the precise question of his nonessential attendance at the deportation hearing was “necessarily decided” by the jury in his previous trial, and therefore conclude — as did the trial judge — that collateral estoppel does not bar the government from prosecuting Castillo-Basa for perjury.
I
In June 2004, Buenaventura Castillo-Basa1 was indicted for being a deported alien found in the United States, in violation of 8 U.S.C. § 1326. The elements of this crime are (1) that the defendant is an alien, (2) that he was deported from the United States, and (3) that he reentered without the permission of the proper authorities. See 9th Cir. Crim. Jury Instr. 9.5 (2007). As the government correctly argues, an alien may be deported in absen-tia. United States v. Hinojosa Perez, 206 F.3d 832, 836-37 (9th Cir.2000) (affirming § 1326 conviction founded upon deportation entered in absentia). Thus, presence at the deportation hearing is not an element of this crime. The defense conceded during his trial that Castillo-Basa is an alien and that he was found within the United States without permission to enter. The only disputed element of the charge was whether Castillo-Basa had previously been deported.
The government informed the district court that an audio tape recording of Castillo-Basa’s deportation hearing existed, but that the tape recording could not be located. The district court ordered the government to produce the tape recording, but, after further searching, the government could not find it.
After the government disclosed that it could not locate the tape recording, Castillo-Basa announced that he had never at*907tended a deportation hearing, which, he argued, created an inference that he had not been deported. To support this theory, Castillo-Basa submitted a signed declaration in support of a motion in limine to dismiss the indictment stating that he never appeared before an immigration judge prior to his physical removal from the United States. Relying on official documents and testimony indicating that Castillo-Basa had been deported, as described in the majority opinion, the district court denied the motion to dismiss.
Castillo-Basa testified in his own defense at trial. He told the jury that he was served with a notice to appear at his April 30, 1996, deportation hearing, but that on that day, no one came to get him out of his cell. Castillo-Basa’s attorney identified Castillo-Basa’s testimony as only one of eight reasons why the government failed to prove that Castillo-Basa had been deported. The defects counsel identified with respect to the elements of deportation included:
1. No fingerprint or photograph on the deportation order;
2. The government’s failure to call the Immigration Judge as a witness;
3. The government’s failure to present the “master list” from the proceedings, which should have included Castillo-Basa’s name if he had been deported;
4. The absence of a tape recording or transcript of the deportation proceedings;
5. The failure to produce detention records; and
6. The “fact” that persons in deportation hearings often give false names.
The jury returned a general verdict form finding Castillo-Basa not guilty.
Less than two weeks after the jury returned its verdict, the government discovered the tape recording of Castillo-Basa’s deportation hearing. The government alleges that all of the information heard on the tape recording indicates that the individual who responded to the questions directed at Castillo-Basa actually was Castillo-Basa. On the tape, the Immigration Judge read the names of twenty-four individuals present at the deportation hearing, including “Buenaventura Castillo-Basa.” The Immigration Judge then questioned each person individually. When he read Buenaventura Castillo-Basa’s name, an individual responded. That individual admitted that he was convicted in December 1985 in San Diego County for a serious crime that he committed in August 1985, for which he received a sentence of seven years. The individual indicated also that he was imprisoned for ten years and eight months. The Immigration Judge ordered that individual deported.
Buenaventura Castillo-Basa, the defendant in this case, had in fact been arrested in August 1985 in San Diego County for robbery with use of a weapon, robbery, sodomy with force, oral copulation with force, and kidnaping. He pleaded guilty and was convicted in December 1985. The highest sentence that he received on a single count was seven years for the sodomy charge. The sentences were ordered to run consecutively for a total of twenty-one years. Finally, Castillo-Basa served ten years and eight months in prison.
After reviewing the tape recording, the government decided to pursue perjury charges against Castillo-Basa. The government presented the tape recording to a grand jury, which returned a two count indictment against him. The first count alleges that Castillo-Basa committed perjury in violation of 18 U.S.C. § 1621(2) when he submitted a declaration indicating that he had never appeared before an immigration judge prior to May 2, 1996. The second count alleges that he committed perjury in violation of 18 U.S.C. § 1621(1) *908when he testified at trial that he had not appeared before an immigration judge in April or May of 1996.
On September 9, 2005, Castillo-Basa filed a motion based upon grounds of double jeopardy and collateral estoppel to dismiss the indictment. The district court denied the motion, concluding that the issue of Castillo-Basa’s veracity with regard to whether he attended the deportation hearing was not necessarily decided in the first trial. The district court determined also that Castillo-Basa had taken unfair advantage of the government’s inability to locate the tape recording by giving perjured testimony, and in so doing, violated public policy and denigrated the integrity of the judicial process. The district court certified the issue for interlocutory appeal, and Castillo-Basa now appeals the denial of the motion to dismiss the indictment.
II
Castillo-Basa argues that collateral es-toppel bars the government from prosecuting him for perjury because the jury from his previous trial, by acquitting him, necessarily determined that Castillo-Basa was not present at the deportation hearing. I disagree.
Collateral estoppel applies to criminal cases through the Fifth Amendment protection against double jeopardy. Ashe v. Swenson, 397 U.S. 436, 443-46, 90 S.Ct. 1189, 25 L.Ed.2d 469 (1970). Collateral estoppel differs markedly from double jeopardy itself.2 The doctrine “bars a perjury prosecution after acquittal on substantive charges when an issue of fact or law [upon which the perjury charge is based] is actually litigated and determined by a final and valid judgment, and the determination is essential to the judgment.” United States v. Richard, 892 F.2d 761, 762 (9th Cir.1989) (per curiam) (quotation marks and citation omitted). Moreover, when the term “issue” is used in this context, it refers not to secondary or subsidiary points of contention in a trial, but normally to “issues of ultimate fact.” “[In Ashe v. Swenson,] [w]e defined the collateral-estoppel doctrine as providing that ‘when an issue of ultimate fact has once been determined by a valid and final judgment, that issue cannot again be litigated between the same parties in any future lawsuit.’ ” Dowling v. United States, 493 U.S. 342, 347, 110 S.Ct. 668, 107 L.Ed.2d 708 (1990) (quoting Ashe, 397 U.S. at 443, 90 S.Ct. 1189) (emphasis added). What is an issue of “ultimate fact?” It is either (1) an essential element of the crime, or (2) the identity of the perpetrator of the offense of which the defendant is charged, not just a dispute about a fact from which inferences might be drawn about the elements. The Court did not say “an issue of fact,” it said an issue of “ultimate fact.”
In cases involving a prior judgment of acquittal announced in a general verdict, a three-step process determines whether collateral estoppel applies:
(1) An identification of the issues in the two actions for the purpose of determin*909ing whether the issues are sufficiently similar and sufficiently material in both actions to justify invoking the doctrine; (2) an examination of the record of the prior case to decide whether the issue was “litigated” in the first case; and (3) an examination of the record of the prior proceeding to ascertain whether the issue was necessarily decided in the first case.
United States v. Hernandez, 572 F.2d 218, 220 (9th Cir.1978). The defendant bears the burden of proving that collateral estop-pel applies. Dowling, 493 U.S. at 350-51, 110 S.Ct. 668 (1990); see also Richard, 892 F.2d at 763; United States v. Gugliaro, 501 F.2d 68, 70 (2d Cir.1974).
We need not decide whether Castillo-Basa’s claim satisfies the first two requirements of this test, because his defense runs aground on the third: whether the issue was “necessarily decided” in the first case. Did the jury “necessarily decide” one way or the other — as an issue of ultimate fact — whether Castillo-Basa attended his deportation hearing? My answer is “no.”
I note that we are applying part of a test that is comprised of two words, not one. The words are (1) “necessarily” and (2) “decided.” In Ashe, the two words are “actually determined.” 397 U.S. at 442, 90 S.Ct. 1189. With all respect, where the majority opinion’s analysis errs is in failing to accord sufficient weight and meaning to “necessarily.” In my view, the addition of this demanding modifier means something, and it means at a minimum that short of a special verdict, and as indicated in Ashe and Dowling, disputes that are not themselves issues of ultimate fact, i.e., including the identity of the perpetrator elements of the crime charged are not “necessarily” decided by a general verdict, one way or the other. My colleagues are certainly correct that not guilty verdicts are sometimes difficult to decipher, but collateral estoppel — or issue preclusion' — is different from double jeopardy. Their analysis, however, blurs the distinction and mistakenly brings unwarranted double jeopardy atmospherics into the equation where they do not belong, highlighting those principles in the first sentence of their opinion as well as in the opening paragraphs. The majority opinion apparently disfavors trying anyone twice, no matter what the distinctions are, and I’m afraid this basic premise drives the result in this case. Double jeopardy per se does not protect a perjurer from a subsequent prosecution for perjury, even if he is an acquitted defendant; and collateral estoppel saves a perjurer only if somehow the precise issue he lied about was “actually determined” as an issue of ultimate fact by the fact finder.
The proof of this pudding is in the unconvincing argument based upon inconclusive circumstantial evidence that the jury had to have decided that Castillo-Basa was telling the truth about his absence from the hearing in order to acquit. My colleagues claim that the jury “necessarily decided that Castillo-Basa’s statements were not false.” I do not agree. It is just as likely that all that happened is that the defendant’s testimony raised circumstantially a reasonable doubt in the minds of the jurors that he had been deported, not that they “actually determined” that he did not attend the hearing. I would concede that if the perjury charge were based on his testimony to the effect that he was “not deported,” collateral estoppel might apply, but the perjury allegation is based on his specific testimony that he did not attend the hearing. In the present equation, and given the importance of the truth to our justice system, therein resides a difference with a distinction. To conclude otherwise ignores strong public policy consideration. As my colleagues concede, there is sufficient reason to believe that Castillo-Basa *910has gamed the process and cheated an acquittal from the system.
Three sets of facts and circumstances demonstrate that the jury did not “necessarily decide” (or “actually determine”) whether Castillo-Basa attended the deportation hearing.
First, we evaluate the district court’s instructions to the jury. See United States v. Sarno, 596 F.2d 404, 408 (9th Cir.1979) (evaluating the jury instructions to determine what the jury “necessarily decided”). If the issue is an element of the underlying offense or is an integral part of an element, then the issue was “necessarily decided” in the first trial. Here, Castillo-Basa’s presence at the deportation hearing was neither an element of the crime nor an integral part of an element. The jury instruction reads,
As to the element of a prior deportation, the government must prove beyond a reasonable doubt that a deportation proceeding occurred as to that defendant and as a result, a warrant of deportation was issued and executed by the removal of the defendant from the United States.
Indeed, the district court rejected Castillo-Basa’s request to give an instruction that would have made his presence at the deportation hearing an element of the crime. The rejected instruction reads,
In order for you to find that Mr. Castillo was deported, the government must prove beyond a reasonable doubt that an [sic] Mr. Castillo was physically present at a hearing before an immigration judge, and that the immigration judge entered a final order of deportation against Mr. Castillo.
(emphasis added). The district court’s rejection of this proposed instruction demonstrates that the jury did not “necessarily decide” whether Castillo-Basa was present at his deportation hearing.
Second, we consider the trial court’s response to jury questions to determine whether it sheds light on what the jury “necessarily decided.” See Sarno, 596 F.2d at 408 (evaluating the jury’s questions to determine what the jury “necessarily decided”). During deliberations, the jury submitted a question to the trial judge. The judge responded,
The first question is, in a deportation hearing must a defendant be present in front of a judge when not in absentia? The answer is as follows: No, but you can consider whether or not the defendant was present before the immigration judge in deciding whether or not a deportation proceeding actually occurred as to the defendant.
(emphasis added). In other words, the jury was not required to decide whether Castillo-Basa was present at the hearing, but the jury could consider by way of inference his assertion of absence as a factor in determining whether he had been deported. This evidence, coupled with the rejected jury instruction, demonstrates convincingly that the jury did not “necessarily decide” whether Castillo-Basa attended his deportation hearing.
Third, Castillo-Basa’s attorney gave the jury additional significant reasons to acquit based upon other alleged flaws in the government’s case, such as no photograph or fingerprint on the Immigration Judge’s Order of Deportation, demonstrating (1) in counsel’s words that his client “was not, in fact, deported,” and (2) that the government has simply failed to prove its case beyond a reasonable doubt.
The case of United States v. Williams supports my analysis. 341 U.S. 58, 71 S.Ct. 595, 95 L.Ed. 747 (1951). In that case, the police officer defendants had testified in a previous trial that they had not seen another defendant, Williams, abuse a prisoner. The three were acquitted of the abuse which they allegedly aided and abetted. How could they aid and abet some*911thing they did not even see? Then, the government charged the three with perjury on the ground that they lied under oath about not witnessing the abuse. The district court dismissed the perjury indictment against the three, reasoning that “the jury’s finding that [the three defendants] had not been guilty of the substantive offenses in the first trial, was a determination of their innocence ‘whether as principals or accessories,’ and therefore none of the three could be found guilty of the charge made by the perjury indictment: testifying falsely that they had not seen or observed Williams beating the victims.” 341 U.S. at 61, 71 S.Ct. 595. The Supreme Court disagreed with both the district court and with counsel on appeal, who argued that the issue at the heart of the perjury trial had been “necessarily determined” by the acquittal. The Court said,
We do not think the facts bring any of these defendants within the protection of res judicata ... The substantive former charge against appellees here was abuse of a prisoner by police officers under color of state law. An acquittal of such a crime or of aiding and abetting was certainly not a determination that [the three officers] did not see Williams assaulting the prisoners.
Id. at 64-65, 71 S.Ct. 595.
Richard is to the same effect. 892 F.2d 761. Richard, a taxi driver, was tried by a jury for transporting illegal aliens. He offered a purported log of his trips in his defense. The government contested the authenticity of the log, but Richard was acquitted nonetheless. Subsequently, Richard was charged and tried with respect to the use of the log at his trial with giving false testimony, obstructing justice, and using a false document. Against these charges, he asserted that the jury in his previous trial had “necessarily determined” that the log was authentic. We disagreed, concluding that the authenticity of the log had not necessarily been determined by his acquittal.
I suppose that had O.J. Simpson testified in his criminal case that he never owned the type of shoes that left bloody footprints at the scene of the slaughter of Nicole Simpson and Ron Goldman, he could not have been prosecuted for perjury when dozens of photographs showed up after the trial showing him wearing those shoes. The jury must have decided in order to acquit him that he did not own the shoes, because if they had disbelieved him, they certainly would have convicted — or so goes the fallacious logic and argument.
Had Simpson testified that he could not have been the killer because he was in Cleveland at the time of the crimes, could he not be prosecuted for demonstrable perjury about being in Cleveland because he had been acquitted of murder? Do the rules of logic and fair inference dictate that the jury “actually determined” that he was in Cleveland in order to acquit him of murder? The jury can be fairly said to have determined that he was not the murderer, an element of the crime, but not that he was in Cleveland. See Lipscomb v. United States, 33 F.2d 33 (8th Cir.1929) (An acquittal from a charge occurring in a specified city on a specified date was not a bar to the defendant’s subsequent prosecution for perjury at the trial arising from his testimony that he was in another city on the day in question.). Castillo-Basa’s claim that he was not at the deportation hearing is no different than a claim that he was someplace else — such as Cleveland.
Ashe v. Swenson presents a distinguishable scenario from the circumstances in this case. 397 U.S. 436, 90 S.Ct. 1189, 25 L.Ed.2d 469. There, the government tried Ashe for the same robbery of participants in a poker game of which he had previously been acquitted, the only difference being that the named victim in the second case *912was different from the victim in the first. The Supreme Court concluded that the jury by its verdict in the first case had determined that he was not one of the robbers, an issue of ultimate fact, and therefore that he could not be tried again on the theory that yes, he was one of the robbers. Here, to repeat, Castillo-Basa is not being charged with perjury because he said he was not deported, but because he said he did not attend a court hearing. Attendance at a deportation hearing is not necessary for deportation. This variance to me is enough degrees of separation to remove the perjury case from the reach of collateral estoppel. Nevertheless, under the majority’s theory, both the substantive crimes and the perjury needed somehow to have been prosecuted together, or perjury is on the house. How do you amend an indictment during trial and charge perjury on the basis of a defendant’s immediate testimony? Might that be slightly heavy handed? The majority’s approach unwittingly insulates perjury from the reach of the law. After United States v. Booker, 543 U.S. 220, 125 S.Ct. 738, 160 L.Ed.2d 621 (2005), a sentencing court probably cannot enhance the sentence of a guilty defendant for perjury during the trial for the lack of a jury finding on the issue, and an acquitted defendant now skates.
Ill
Castillo-Basa argues, however, that the government would be merely “rehashing” old evidence before a new jury if it were allowed to proceed with the perjury trial. In Samo, we noted that “unless the subsequent perjury indictment is based upon evidence which was not available at the first trial, it would appear that the government would be merely trying to recover from its initial failure to convince the trier of fact of the falsity of defendant’s testimony at the first trial.” 596 F.2d at 407 (internal citations omitted). We concluded, “Such a rehashing of evidence previously presented would clearly be prohibited by the collateral estoppel doctrine.” Id. Although we subsequently dismissed as dicta this language from Sarno, Richard, 892 F.2d at 763, we need not resolve that issue here because the government has new material evidence that was not presented during the first trial — the tape recording.
Although the misplaced tape recording was in the government’s possession during the first trial, the district court in the current perjury trial expressly found that the tape recording was unavailable to the government for use in the prior trial. Specifically, the district court stated,
[T]he government has evidence that was not available to it at the first trial. Now, I take the argument that the evidence was in the government’s possession seriously. However, the court finds that the evidence was not available to the government during the first trial.
As we have previously concluded, the fact that evidence was in the government’s possession during the first trial does not bar the government from using the evidence in a later trial for perjury. See United States v. Dipp, 581 F.2d 1323, 1326, 1330 (9th Cir.1978) (affirming defendant’s perjury conviction even though the tapes used to prove perjury were in the government’s possession during the initial trial and were requested by the defendant). Accordingly, the government is not merely “rehashing” evidence from the first trial because it may use the tape recording as evidence in the perjury trial. “To construe Samo so broadly [as contended by Castillo-Basa] would create a ‘per se bar’ to subsequent perjury prosecutions.” Richard, 892 F.2d at 763.
IV
I am not moved by the Assistant United States Attorney’s superfluous offering during oral argument before the district court that the jury “necessarily decided” wheth*913er Castillo-Basa was present at the deportation hearing. The district court, not the parties, is charged with the task of examining “the record of the prior proceeding to ascertain whether the issue was necessarily decided in the first case.” Hernandez, 572 F.2d at 220. While the parties may aid the court in evaluating the record from the prior proceeding, the parties cannot complete this task for the court. See United States v. Ogles, 440 F.3d 1095, 1099 (9th Cir.2006) (en banc) (“We are not bound by a party’s concession as to the meaning of the law, even if that party is the government and even in the context of a criminal case”).
y
“The requirement of sworn testimony, backed by punishment for perjury, is as much a protection for the accused as it is a threat. All testimony, from third-party witnesses and the accused, has greater value because of the witness’ oath and the obligations or penalties attendant to it.” United States v. Dunnigan, 507 U.S. 87, 97, 113 S.Ct. 1111, 122 L.Ed.2d 445 (1993) abrogated on other grounds, United States v. Wells, 519 U.S. 482, 117 S.Ct. 921, 137 L.Ed.2d 107 (1997). An acquittal does not constitute an automatic bar against a subsequent prosecution for perjury during that trial. “[A] defendant’s right to testify [in his own defense] does not include a right to commit perjury.” Dunnigan, 507 U.S. at 96, 113 S.Ct. 1111. It does now. My colleagues’ analysis is tantamount to overruling this basic precept. Any material lie a defendant uses to get an acquittal whether it relates to an element of the crime or the identity of the perpetrator, will now be immune from prosecution for perjury because after all, the jurors must have believed it in order to acquit.
CONCLUSION
I believe that the collateral issue identified in the indictment Castillo-Basa now seeks to dismiss was not “necessarily decided” because (1) his presence at the deportation hearing was not an element of the crime charged or an issue of “ultimate fact,” (2) the district court rejected a proposed instruction that would have required the jury to decide whether he was present at the hearing, or not, (3) the district court instructed the jury that it need not resolve the presence or absence dispute, and (4) “a rational jury could have grounded its verdict upon an issue other than that which the defendant seeks to foreclose from consideration.” Ashe, 397 U.S. at 444, 90 S.Ct. 1189 (quotation marks and citation omitted). The best one can say for Castillo-Basa on the record is that the jury was not convinced beyond a reasonable doubt that he had been deported, not that they believed his lie about not attending the hearing against a mountain of evidence to the contrary.
Accordingly, because I conclude that collateral estoppel does not bar the government from prosecuting Castillo-Basa in this case, I respectfully dissent.
. Two spellings of “Castillo-Basa" appear in the record. I use the spelling from Castillo-Basa's appellate briefs.
. The Supreme Court has recognized that collateral estoppel is a separate doctrine from double jeopardy. Ashe, 397 U.S. at 442-43, 90 S.Ct. 1189. Double jeopardy protects against a second prosecution for the same offense after acquittal or conviction. "It would be no service to the administration of justice to enlarge the conception of former jeopardy to afford a defendant immunity from prosecution for perjury while giving testimony in his own defense.” United States v. Williams, 341 U.S. 58, 62, 71 S.Ct. 595, 95 L.Ed. 747 (1951). Castillo-Basa’s double jeopardy argument fails because the elements of perjury are different from the elements of being a deported alien found in the United States. See Blockburger v. United States, 284 U.S. 299, 304, 52 S.Ct. 180, 76 L.Ed. 306 (1932).