OPINION

IKUTA, Circuit Judge:

This appeal challenges the constitutionality of certain key provisions of the Sex Offender Registration and Notification Act (SORNA). Pub.L. 109-248, Tit. I, 120 Stat. 590 (2006) (codified in scattered sections of the U.S.C.). Defendant Mark Steven Elk Shoulder was prosecuted under 18 U.S.C. § 2250(a) for failing to comply with the sex offender registration requirements set forth in 42 U.S.C. § 16913. He now argues that his conviction was invalid, because SORNA violates the Ex Post Facto Clause and the Due Process Clause, and because Congress lacked the constitutional authority to enact SORNA. We reject these constitutional challenges, and affirm the judgment of the district court.

I

SORNA was enacted in response to "Congress' awareness that pre-[SORNA] registration law consisted of a patchwork of federal and 50 individual state registration systems." Reynolds v. United States, ___ U.S. ___, 132 S.Ct. 975, 978, 181 L.Ed.2d 935 (2012) (citing 73 Fed.Reg. 38045 (2008)). SORNA sought to improve the uniformity and effectiveness of those systems by, among other things, "creating federal criminal sanctions applicable to those who violate the Act's registration requirements." Id. To effectuate this goal, SORNA's registration requirement, 42 U.S.C. § 16913, requires all state and federal sex offenders, as defined,1 to "register, and keep the registration current, in each jurisdiction where the offender" resides, works, or goes to school.2 A person who fails to register as required by § 16913 may be criminally prosecuted under 18 U.S.C. § 2250(a). This provision requires the government to prove that the defendant: (1) is required to register under SORNA, (2) is a "sex offender" as defined due to a conviction under federal law (or the law of certain other listed jurisdictions) or a person who "travels in interstate or foreign commerce, or enters or leaves, or resides in, Indian country" and, (3) knowingly failed to register or update a registration as required by SORNA.3

These SORNA provisions provide the backdrop to the facts of this case. In 1991, Elk Shoulder was convicted in a federal district court in Montana of sexual abuse of a six-year-old child in violation of 18 U.S.C. § 2241(c).4 Elk Shoulder was sentenced to 172 months in prison, followed by five years supervised release. When Elk Shoulder was released in December 2003, officials informed him that he was required to register as a sex offender under Montana law. He registered in Yellowstone County, Montana, where he signed and initialed the state's "Sexual and Violent Offender Registration Form." By doing so, Elk Shoulder acknowledged that under state law, he was required to maintain a current and updated registration and that his duty to register would continue for the rest of his life, even after the expiration of probation or parole.

Weeks later, in February 2004, Elk Shoulder violated the terms of his supervised release and was sentenced to thirty months in prison, followed by thirty months of supervised release. Upon his release from prison a second time in April 2006, he again registered as a sex offender in Yellowstone County. SORNA was enacted three months later. In August 2006, Elk Shoulder again violated the terms of his supervised release and was sentenced to another twenty-four months in prison.

After his release from prison a third time in May 2008, Elk Shoulder moved around Montana, living at various times in the Northern Cheyenne Indian Reservation, Bozeman, Lame Deer, Billings, and Wolf Point. He did not register as a sex offender in any of these locales.

In 2009, Elk Shoulder was indicted under 18 U.S.C. § 2250(a) for violating the SORNA registration requirements in 42 U.S.C. § 16913. Before trial, Elk Shoulder brought two motions to dismiss the indictment. In the first, he asserted that SORNA's registration provision exceeded Congress's authority under the Commerce Clause. In the second, he claimed that the retroactive application of these provisions violated the Ex Post Facto Clause. The district court denied both motions. After a bench trial, the court found Elk Shoulder guilty beyond a reasonable doubt. He was sentenced to a term of thirty months imprisonment, to be followed by five years supervised release.

On appeal, Elk Shoulder argues that the district court erred in rejecting his constitutional challenges to SORNA. We address each of his arguments in turn.

II

We first consider Elk Shoulder's argument that SORNA's statutory scheme for requiring sex offenders to register and criminalizing certain failures to register violates the Ex Post Facto Clause.

The Constitution provides: "No ... ex post facto Law shall be passed." U.S. Const. art. I § 9, cl. 3. As the Supreme Court has succinctly explained, "[l]egislatures may not retroactively alter the definition of crimes or increase the punishment for criminal acts." Collins v. Youngblood, 497 U.S. 37, 43, 110 S.Ct. 2715, 111 L.Ed.2d 30 (1990); see also United States v. Elkins, 683 F.3d 1039, 1044 (9th Cir.2012) (holding that the Ex Post Facto Clause "bars the enactment of any law that imposes a punishment for an act which was not punishable at the time it was committed; or imposes additional punishment to that then prescribed.") (quoting Russell v. Gregoire, 124 F.3d 1079, 1083 (9th Cir.1997) (internal quotation marks omitted)).

Elk Shoulder asserts that SORNA's registration requirement constitutes an additional punishment for his federal sex offense, which he committed in 1991. Because SORNA was not enacted until 2006, he argues that the Ex Post Facto Clause prohibited Congress from applying the registration requirement to him.5

Elk Shoulder's argument is foreclosed by our recent decision in United States v. Elkins, 683 F.3d 1039. In Elkins, a defendant who had been convicted of a sex offense under Washington law in 1994 failed to register when he moved from Washington to California in 2010, and was indicted under § 2250. Id. at 1041-42. Elkins filed a motion to dismiss the indictment arguing, among other things, that the requirement to register violated the Ex Post Facto Clause in his case because it was punitive in nature and was based on a prior conviction that occurred before SORNA was enacted. Id. at 1043-44. We concluded that SORNA's registration requirement was not punitive in nature, and therefore did not violate Elkins's constitutional rights. Id. at 1045. We based this conclusion on Smith v. Doe, 538 U.S. 84, 123 S.Ct. 1140, 155 L.Ed.2d 164 (2003), in which the Supreme Court applied a five factor test,6 and concluded that Alaska's Sex Offender Registration Act, which is similar to SORNA in all material ways, was not punitive in nature. Id. at 105-06, 123 S.Ct. 1140. We thus rejected the ex post facto challenge to SORNA, and in doing so joined all of our sister circuits that have considered the issue. Elkins, 683 F.3d at 1045.7 Because Elk Shoulder also argues that SORNA's registration requirement cannot be applied to him because it is punitive in nature, Elkins's reasoning is equally applicable to Elk Shoulder.

Despite this precedent, Elk Shoulder argues that the Court's analysis in Smith "no longer hold[s] true in today's society," and the purpose and effect of SORNA's registration requirement is punitive in nature. Elk Shoulder focuses on the Supreme Court's holding that the Alaska registration statute does not resemble shaming punishments of the colonial period (the first factor of Doe's five-factor test), and that there was "no evidence that [the registration requirement] has led to substantial occupational or housing disadvantages for former sex offenders that would not have otherwise occurred through the use of routine background checks by employers and landlords." 538 U.S. at 100, 123 S.Ct. 1140 (the second factor). According to Elk Shoulder, today SORNA's registration requirement imposes significant hardships on offenders, who are "held to public ridicule by community members," and face difficulty finding and maintaining both employment and housing. He notes that local newspapers frequently maintain interactive maps of the registered residences of sex offenders, and cites "reports of incidents of citizens standing on street corners bearing signs with the names and addresses of offenders blaz[o]ned across the front."

This argument fails. Most important, we have recently reaffirmed the nonpunitive nature of SORNA in Elkins, which we are bound to follow. Miller v. Gammie, 335 F.3d 889, 899 (9th Cir.2003) (en banc). Further, Smith v. Doe contemplated that information from the Alaska sex registration statute would be available on the internet, but determined that such internet notification was nonpunitive because its principal effect was to "inform the public for its own safety, not to humiliate." 538 U.S. at 99, 123 S.Ct. 1140. The Court further noted that there was no evidence that the Alaska act had "led to substantial occupational or housing disadvantages that would not have otherwise occurred through the use of routine background checks by employers and landlords." Id. at 100, 123 S.Ct. 1140. Because "only the clearest proof will suffice to override legislative intent and transform what has been denominated a civil remedy into a criminal penalty," id. at 92, 123 S.Ct. 1140 (internal citation and quotation marks omitted), Elk Shoulder's conclusory statements and handful of anecdotal examples cannot carry the heavy burden of showing substantial changes in society that would require us to revisit the Supreme Court's conclusion.

We thus reject Elk Shoulder's argument that application of the SORNA registration requirements to him on the basis of his earlier conviction violates the Ex Post Facto Clause.

III

We next turn to Elk Shoulder's arguments that SORNA's registration requirement violates his rights under the Fifth Amendment, which bars the federal government from depriving persons of "life, liberty, or property, without due process of law." U.S. Const. amend. V.

Elk Shoulder first asserts that he was deprived of his right to due process because it was impossible for him to comply with SORNA. As noted above, in order to convict Elk Shoulder under § 2250(a), the government had to prove that Elk Shoulder knowingly failed "to register or update a registration as required by" SORNA. § 2250(a)(3) (emphasis added). Elk Shoulder points out that SORNA required states to adopt the new procedures for sex offender registries established by the Act, or lose part of their federal funding. 42 U.S.C. §§ 16924(a), 16925. Elk Shoulder argues that, because Montana had not yet conformed its sex offense registry to SORNA's requirements, it was impossible for him to register "as required by" SORNA.

We have previously rejected this argument, both in United States v. George, 625 F.3d 1124, 1128-29 (9th Cir.2010), vacated on other grounds, 672 F.3d 1126 (9th Cir. 2012), and in Elkins, 683 F.3d at 1046. As we stated in Elkins, "the federal government's prosecution of an alleged violation of SORNA is not dependent on the individual state's implementation of the administrative portion of SORNA." Elkins, 683 F.3d at 1046; accord id. at 1046 n. 9 (the "duty to register in a state registry is independent of a state's degree of implementation of SORNA." (quoting Felts, 674 F.3d at 603)); see also Guzman, 591 F.3d at 93; Gould, 568 F.3d at 464. Because Elk Shoulder could have registered with the State of Montana's registry, and because this would have allowed him to register "as required by" SORNA, it was not impossible for Elk Shoulder to meet the requirements of § 2250(a). Thus, this case presents no impossibility-based due process problems.

Second, Elk Shoulder asserts that he did not receive notice that failure to register as a sex offender would violate SORNA, and therefore he did not receive notice sufficient to comply with the Due Process Clause. This argument is meritless. In order to convict a defendant under § 2250(a), "the government [must] prove that a convicted sex offender knew of a registration requirement and knowingly failed `to register or update a registration.'" United States v. Crowder, 656 F.3d 870, 876 (9th Cir.2011) (quoting § 2250(a)(3)). A SORNA defendant's knowledge of his failure to "register or update a registration" as required by state law is sufficient to satisfy the "notice" requirement of the Due Process Clause. Elkins, 683 F.3d at 1049-50; accord United States v. Brown, 586 F.3d 1342, 1351 (11th Cir.2009) ("[W]e join our sister circuits in concluding that `notice of a duty to register under state law is sufficient to satisfy the Due Process Clause.'" (internal quotation marks omitted)). The defendant need not know that the same failure also violates SORNA. Thus, because Elk Shoulder received notice of his obligation to register under Montana state law, he received all the notice the Due Process Clause requires.

IV

Finally, Elk Shoulder argues that Congress lacks the Constitutional authority to punish his failure to register under SORNA. At issue is whether Congress has the authority to impose SORNA registration requirements on individuals who, like Elk Shoulder, are convicted of federal sex crimes.8

"The Federal Government `is acknowledged by all to be one of enumerated powers.'" Nat'l Fed'n of Ind. Bus. (NFIB) v. Sebelius, ___ U.S. ___, 132 S.Ct. 2566, 2576, 183 L.Ed.2d 450 (2012) (quoting McCulloch v. Maryland, 17 U.S. (4 Wheat.) 316, 405, 4 L.Ed. 579 (1819)). No clause in Article I expressly authorizes Congress to impose registration requirements on federal convicts such as Elk Shoulder. Nevertheless, the government argues that because Congress had authority to enact § 2241(c) (Elk Shoulder's statute of conviction) under the Constitution's Property Clause, U.S. Const., art. IV, § 3, cl. 2,9 Congress also had the authority to enact §§ 16913 and 2250(a) under the Necessary and Proper Clause, which empowers Congress "[t]o make all laws which shall be necessary and proper for carrying into Execution the foregoing Powers, and all other Powers vested by this Constitution in the Government of the United States," U.S. Const. art. I, § 8, cl. 18.

A

The Supreme Court provided a framework for analyzing such arguments in United States v. Comstock, ___ U.S. ___, 130 S.Ct. 1949, 176 L.Ed.2d 878 (2010). In Comstock, the Court upheld a civil commitment statute that allowed the government to detain, past their release dates, sexually dangerous individuals who were already in federal custody, as a valid use of Congress's power under the Necessary and Proper Clause. Id. at 1954. In analyzing this issue, the Court weighed five considerations, id. at 1956, which (it was careful to explain), did not constitute a test to be satisfied, id. at 1965. As explained in more detail below, these considerations included whether the Congressional enactment: (1) was rationally related to the implementation of a constitutionally enumerated power; (2) was "a modest addition" to existing federal legislation; (3) was reasonably adapted to its ends; (4) accommodated state interests and state sovereignty; and (5) was not "too sweeping in scope," and was linked to a constitutionally enumerated power in a manner that was not too attenuated. Id. at 1956-65.

Comstock's analysis of these five factors is directly applicable to the SORNA registration statute.

First, Comstock determined that the civil commitment statute at issue in that case was rationally related to the constitutionally enumerated powers that authorized Congress to enact and enforce laws. Id. at 1956. The Court reasoned that because Congress had the power to "ensure the enforcement of federal criminal laws enacted in furtherance of its enumerated powers," id. at 1958, it likewise "can cause a prison to be erected at any place within the jurisdiction of the United States," and direct that it be used for the imprisonment of federal criminals. Id. (quoting Ex parte Karstendick, 93 U.S. 396, 400, 23 L.Ed. 889 (1876)) (internal quotation marks omitted). Congress, "having enacted a prison system, can enact laws that seek to ensure that system's safe and responsible administration." Comstock, 130 S.Ct. at 1958. It may also seek to "ensure the safety of... those in the surrounding communities" with the enactment of further criminal laws. Id. Each link in this chain, the Court explained, is rationally related to the underlying enumerated power; the powers authorizing the prisoners' statutes of conviction. By extension, this gave Congress the authority to confine "mentally ill and sexually dangerous persons who are already in federal custody, even if doing so detains them beyond the termination of their criminal sentence." Id. at 1961.

We apply Comstock's analysis here. The parties do not dispute that Congress had the power to enact § 2241(c), Elk Shoulder's crime of conviction, under the Property Clause. This constitutional authority gave Congress the power to enact laws to ensure the safety of the surrounding communities by regulating and monitoring post-release behavior. See Comstock, 130 S.Ct. at 1958. SORNA's registration requirement, see § 16913, and the criminal penalties for the violation of the registration requirements, see § 2250, are rationally related to public safety, "which is advanced by alerting the public to the risk of sex offenders in their community," Smith, 538 U.S. at 102-03, 123 S.Ct. 1140. Accordingly, SORNA was rationally related to an enumerated power.

Second, Comstock determined that the civil commitment statute was "a modest addition to a set of federal prison-related mental-health statutes that ha[d] existed for many decades." Id. at 1958, 1961. The same conclusion is applicable here. Requiring sex offenders to register and update their addresses is "a modest addition" to the federal government's long history of regulating federal offenders after their release from incarceration through probation, parole and supervised release. See, e.g., Sentencing Reform Act of 1984, Pub.L. No. 98-473, 98 Stat.1987; Act of June 25, 1910, 36 Stat. 819 (establishing parole for federal prisoners). Federal law has required states to maintain sex offender registration and community notification systems since 1994. See Carr v. United States, ___ U.S. ___, 130 S.Ct. 2229, 2233, 176 L.Ed.2d 1152 (2010). A registration requirement "imposes the more minor condition of registration," Smith, 538 U.S. at 104, 123 S.Ct. 1140, compared to the custodial requirements of parole, probation, and supervised release.

Third, Comstock held that the civil commitment statute at issue was reasonably adapted to its ends. Among other things, "Congress could have reasonably concluded that federal inmates who suffer from a mental illness that causes them to have serious difficulty in refraining from sexually violent conduct, would pose an especially high danger to the public if released." Comstock, 130 S.Ct. at 1961 (internal citation and quotation marks omitted). Here, Congress's decision to enact SORNA to enhance public safety by imposing a registration requirement on convicted federal sex offenders and criminalizing the failure to register, is also "reasonably adapted to the attainment of a legitimate end," id. at 1957 (internal quotation marks omitted), namely to "protect the public from sex offenders and offenders against children," 42 U.S.C. § 16901, by improving the "patchwork of federal and ... state registration systems" that pre-dated SORNA, Reynolds, 132 S.Ct. at 978 (citing 73 Fed.Reg. 38045). Congress determined that the deficiencies in the pre-SORNA systems "had enabled sex offenders to slip through the cracks" resulting in some 100,000 "missing" sex offenders, and that SORNA's comprehensive registries, public notification, information sharing and dissemination, and criminal enforcement penalties, Carr, 130 S.Ct. at 2240-41, are reasonable means for addressing this problem, see id., at 2238. Further, because SORNA registration requirements are imposed only on individuals who were convicted of sexual offenses, it regulates only "those who by some preexisting activity bring themselves within the sphere of federal regulation." NFIB, 132 S.Ct. at 2592.

Fourth, Comstock determined that the civil commitment statute "properly accounts for state interests," and does not "invade state sovereignty or otherwise improperly limit the scope of powers that remain with the States." Id. at 1962 (internal quotation marks omitted). SORNA likewise reasonably accommodates state interests. Although Congress gave the states primary responsibility in supervising sex offenders, SORNA is applicable only to federal sex offenders, over whom the federal government has a "direct supervisory interest," and those state offenders "who threaten the efficacy of the statutory scheme by traveling in interstate commerce," thus placing themselves outsides of the state's reach. Carr, 130 S.Ct. at 2238-39.

Additionally, SORNA's requirement that states implement SORNA-compliant registration and notification systems in order to receive certain funds, see 42 U.S.C. § 16925, does not improperly invade state interests. A state that fails to "substantially implement" the requirement of SORNA may lose ten percent of federal funding under the Omnibus Crime Control and Safe Streets Act of 1968. § 16925(a). This financial loss is a "relatively mild encouragement" rather than "a gun to the head." NFIB, 132 S.Ct. at 2604 (striking down legislation conditioning "over 10 percent of a State's overall budget" on state expansion of Medicaid programs). Indeed, as of July 27, 2011, the statutory deadline for jurisdictions to implement SORNA, only 14 states had done so. See Melissa Hamilton, Public Safety, Individual Liberty, and Suspect Science: Future Dangerousness Assessments and Sex Offender Laws, 83 Temp. L.Rev. 697, 706 n.53 (2011).

Fifth, Comstock held that the links between Congress's enumerated powers and the federal civil commitment statute "are not too attenuated." 130 S.Ct. at 1963. The Court rejected the argument that "when legislating pursuant to the Necessary and Proper Clause, Congress's authority can be no more than one step removed from a specifically enumerated power." Id. Rather, the Court explained, its precedents allow for many links in the chain. Here, the links between Congress's enumerated powers and SORNA are no more attenuated than those in Comstock. It is a small step from Congress's power to enact laws, criminalize their violation, place the violators in custody, and protect the public from federal convicts even after release, see id. at 1964-65, to requiring federal convicts who may be dangerous to the public to provide information regarding their residences, and punishing those who fail to do so.

Further, Comstock concluded that the civil commitment statute was not "too sweeping in scope." Id. at 1963. The SORNA registration requirements are likewise not "too sweeping in scope." Contrary to Elk Shoulder's assertion that authorization of lifelong registration requirements would grant a "general police power" to Congress, the requirement to register is not nearly as significant a burden as the indefinite detention authorized in Comstock. See id. at 1954-55. Although the Necessary and Proper Clause provides no justification for laws effecting "a substantial expansion of federal authority," NFIB, 132 S.Ct. at 2592, SORNA's registration requirement is "narrow in scope" and "incidental to the exercise" of enumerated powers. Id. at 2592 (opinion of C.J. Roberts) (citations and internal quotation marks omitted).

Accordingly, we join the Tenth Circuit Court of Appeals in concluding that SORNA's registration requirement, § 16913, and by extension, the statute penalizing failure to register, § 2250, were within the scope of Congress's authority under the Necessary and Proper Clause. See United States v. Yelloweagle, 643 F.3d 1275, 1277 (10th Cir.2011) (assuming the constitutionality of the registration provision, and concluding that § 2250 was "a valid exercise of congressional authority under the Necessary and Proper Clause."); United States v. Carel, 668 F.3d 1211, 1217 (10th Cir.2011) (upholding the constitutionality of § 16913 "[b]ased on Congress's authority to enact [defendant's federal] statute of conviction" and the Necessary and Proper Clause).

B

We recognize that the Fifth Circuit has disagreed with this conclusion, and held that Congress did not have the authority to require federal convicts who had "been unconditionally released from federal custody or supervision" before SORNA was enacted to comply with its registration requirements.10 See United States v. Kebodeaux, 687 F.3d 232, 244, 253 (5th Cir. 2012). The Fifth Circuit reasoned that "[a]fter the federal government has unconditionally let a person free, [ ] the fact that he once committed a crime is not a jurisdictional basis for subsequent regulation and possible criminal prosecution." Id. at 234-35. In effect, the Fifth Circuit deemed the links between SORNA's registration requirement and an enumerated Article I power to be per se too attenuated when applied to federal convicts already released from federal custody. The Fifth Circuit distinguished Comstock because the civil commitment statute in that case applied to prisoners still in federal custody. Id. at 236.

We disagree. The Supreme Court has "made clear that, in determining whether the Necessary and Proper Clause grants Congress the legislative authority to enact a particular federal statute, we look to see whether the statute constitutes a means that is rationally related to the implementation of a constitutionally enumerated power." Comstock, 130 S.Ct. at 1956. Nothing in this jurisprudence supports Kebodeaux's per se rule that a Congressional enactment cannot be rationally related to implementing an enumerated power if it applies to federal convicts who have been released from custody before the date of the enactment. Rather, as explained above, a registration requirement aimed at informing the public of the identity and location of individuals convicted of sex offenses is reasonably related to Congress's authority to ensure the safety of the public, which in turn flows from its authority to enact and enforce criminal laws. Indeed, in Smith v. Doe, the Supreme Court relied on this reasonable relation between a registration requirement and a state's safety objectives in concluding that a state could constitutionally apply its sex offender registration statute to a person who had been released from custody before the statute was enacted. See 538 U.S. at 102-03, 123 S.Ct. 1140 (agreeing with the appellate court that the statute had the "legitimate nonpunitive purpose of public safety, which is advanced by alerting the public to the risk of sex offenders in their communit[y].") (internal quotation marks omitted, alteration in original). While Comstock may be distinguishable on its facts, we see no reasoned basis for holding that a law authorizing the federal government to exercise indefinite civil custody over former federal prisoners even after they have served their sentences, Comstock, 130 S.Ct. at 1979 (Thomas, J., dissenting), has less of a rational relationship to an enumerated power than an enactment requiring such former federal prisoners to provide registration information, even after they have been released from custody.

Because we reject the Fifth Circuit's conclusion that Congress cannot "reassert jurisdiction over someone it had long ago unconditionally released from custody," Kebodeaux, 687 F.3d at 238, a proposition for which the Fifth Circuit provided no support, we disagree with its analysis of the Comstock considerations, which it based almost exclusively on that conclusion.

V

Because SORNA violates neither the Ex Post Facto Clause nor Elk Shoulder's constitutional right to due process, and because Congress acted within its enumerated powers in enacting it, we affirm the judgment of the district court.

AFFIRMED.