The issue in this case is the validity of an Immigration and Naturalization Service (“INS”) regulation requiring nonimmigrants to provide truthful answers to all questions asked of them by immigration officers, regardless of materiality. The Board of Immigration Appeals (“BIA”) upheld the immigration judge’s (“IJ”) finding that Conchita Romero was deportable because she had given a false statement to an INS officer. We hold that the Attorney General exceeded his authority when he promulgated 8 C.F.R. § 214.1 (f), which imposes as a condition of a nonimmigrant’s admission and continued stay in the United States, the full and truthful disclosure of all information requested by the INS, regardless of whether the information is material. The alleged false statement of Romero was immaterial to her immigration status, and we reverse the order of deportation.

Conchita Alicia Figueras Romero, a 43-year old citizen of the Philippines, last entered the United States on August 21, 1986, as a nonimmigrant treaty investor. She and her lawful permanent-resident former husband are the natural parents of three minor children, one of whom is a United States citizen. She owns and operates two fashion stores that employ from two to four other persons. She also owns four pieces of residential property.

At a party in November 1985, Rodolfo Santiago de Leon, a friend of Romero, asked her if she knew somebody who might be able to help him get an extension of his visa. Romero replied that she might. Whether she said anything further is disputed. Later, de Leon began cooperating with the Government in their investigation of an alleged visa fraud scheme.

When Romero re-entered the United States from the Philippines on August 21, 1986, she was questioned by INS Special Agent Randolph C. Smart about what she had told de Leon. According to Agent Smart, Romero admitted that she had tele phoned Cecilia Arrivas, wife of a United States immigration inspector, about de Leon’s immigration problem. Smart also reported that Romero denied having told de Leon that she knew a person who could help him with an extension of stay for a fee of $250 to $300.

On August 28, 1986, the INS issued an Order to Show Cause, alleging that Romero had violated the conditions of her nonimmi-grant status pursuant to 8 C.F.R. § 214.1 (f) by falsely stating to an INS special agent that she “had never told any alien that [she] could assist in obtaining an extension of non-immigrant status for money.” The order alleged that Romero had told de Leon that she knew someone who could get him an extension for $200 to $300.

On April 30, 1986, de Leon stated in a sworn affidavit that Romero mentioned the amount of $250 to $300. In exchange, he received immunity from prosecution and a work authorization. Later, at Romero’s deportation hearing, de Leon testified that Romero had mentioned $300 to $400 or even more. De Leon, however, also testified that he never paid any money to Inspector Arri-vas or his wife for the extension of his nonim-migrant status. Cecilia Arrivas spoke to de Leon about helping him fix the immigration papers and did not quote him a price, but asked him to take her out to dinner.

Agent Smart testified that he was working with the Customs Service to investigate alleged corruption among customs officers stationed at the San Francisco International Airport. Customs Inspector Alejandro Arri-vas was identified as the key target of the investigation. Smart described passport fraud involving Inspector Arrivas, Arrivas’ wife, Cecilia Arrivas, and Romero’s sister, Theresa Figueras. Smart testified that an alien could obtain an extension of stay for money through Cecilia Arrivas. Inspector Arrivas would provide a new stamp on the alien’s passport and a new 1-94, which is an arrival/departure record. Smart also testified that INS and Customs officers had monitored telephone conversations and a “body-wired” conversation between Cecilia Arrivas and de Leon, in which Cecilia Arrivas acknowledged that she had learned about the “transaction” through Romero, that she had received de Leon’s passport, and that her husband had placed the arrival/departure stamps in the passport. The INS offered into evidence an affidavit executed by de Leon and a photocopy of de Leon’s passport.

Romero testified that she had had a conversation with de Leon about his visa problem, but she did not tell him that someone would help him for money, although she referred him to Cecilia Arrivas.

The IJ found that Romero had made the false statement and entered an order of deportation. On appeal, the BIA deferred to the IJ’s credibility findings and held that the INS had established that Romero gave false information to an INS agent in violation of 8 C.F.R. § 214.1 (f), and was deportable under 8 U.S.C. § 1251 (a)(9). Romero was never charged with violating any other condition of her nonimmigrant status, any other immigration law, or any state or federal criminal law. On appeal, Romero vigorously contests the finding that she had mentioned any money to de Leon. She maintains that de Leon was not credible and there was not substantial evidence to support this finding of the IJ and the BIA. We do not reach this issue, because we reverse the deportation order on the ground discussed in the following section.

II.

We conclude that the Attorney General exceeded his authority when he promulgated 8 C.F.R. § 214.1 (f), which imposes as a condition of a nonimmigrant’s admission and continued stay in the United States the full and truthful disclosure of all information requested by the INS, regardless of whether the information is material. The regulation is an interpretation of 8 U.S.C. § 1251 (a)(1)(C)® (Supp. V 1993) (formerly 8 U.S.C. § 1251 (a)(9) (1982)). That statute provides:

The regulation provides:

8 C.F.R. § 214.1 (f) (1994) (formerly 8 C.F.R. § 214.1 (f) (1986)).

An agency’s interpretation of a statute that it is entrusted to administer is entitled to considerable weight unless it is “arbitrary, capricious, or manifestly contrary to the statute.” Chevron, U.S.A, Inc. v. Natural Resources Defense Council, Inc., 467 U.S. 837, 844 , 104 S.Ct. 2778, 2782 , 81 L.Ed.2d 694 (1984). In reviewing the agency’s interpretation, we must first look to the intent of Congress. If Congress has not directly addressed the issue, the question is whether the agency’s interpretation is reasonable and based on a permissible construction of the statute. Id. at 842-45 , 104 S.Ct. at 2781-83 .

The statute allows for deportation when an alien fails to maintain his status or to comply with the conditions of his status. No doubt, the failure to provide truthful information concerning immigration status is a legitimate requirement, and willful failure to provide such could constitute grounds for deportation; it is the parenthetical phrase eliminating any requirement of materiality that creates the problem. The IJ recognized this problem in stating:

Romero, File No. A-27-578-179, at 6 (Office Imm.J., Jan. 13, 1987) (oral decision).

We agree with Romero that the statute suggests that the conditions with which aliens must comply must have some nexus to maintaining their status. We find no evidence suggesting that Congress intended to bestow unfettered discretion on the INS to request any information it desires, and then deport an alien for failing to deliver it truthfully. The truthful disclosure requirement must have some relevance to the alien’s status.

Congress has already provided a comprehensive scheme for excluding and deporting aliens who make material misrepresentations regarding their immigration status or immigration benefits. Deportability or exclusion based upon misrepresentation is limited to willful misrepresentation of material facts. See 8 U.S.C. § 1182 (a)(6)(C)(i) (Supp. V 1993) (aliens who, by fraud or willful misrepresentation of a material fact, seek to procure immigration documentation or entry into the United States are excludable); 8 U.S.C. § 1251 (a)(1)(A) (Supp. V 1993) (aliens who were excludable under § 1182 at the time of their entry are deportable). Congress did not intend to allow the INS to deport aliens for nonmaterial misrepresentations.

Furthermore, Congress expressly gave the Attorney General the authority to waive the application of 8 U.S.C. § 1182 (a)(6)(C)(i) (ex-cludability based upon material misrepresentation) if the alien is the spouse, parent, or child of a United States citizen or legal permanent-resident immigrant. 8 U.S.C. § 1182 (i) (Supp. V 1993). If Romero had been charged with a willful and material misrepresentation under section 1182 or section 1251, she would have been eligible for a waiver because she is the mother of a United States citizen.

The regulation, under which the INS seeks to deport Romero, is harsher than the statutes concerning deportation and excludability for misrepresentation: The regulation does not require materiality or that the representation be for the purpose of obtaining an immigration benefit, and it does not provide for waiver. Thus, it is inconsistent with the statutory scheme.

A similar situation arose in United States v. Witkovich, 353 U.S. 194 , 77 S.Ct. 779 , 1 L.Ed.2d 765 (1957). There, the Government had interpreted a statute relating to the supervision of aliens under an order of deportation. Its interpretation gave the Attorney General unbounded authority to require an alien to furnish information unrelated to his availability for deportation. The Court held that:

Id. at 201-02, 77 S.Ct. at 783-84 . In this case, we are concerned with a regulation that interprets a statute in a way that would raise similar constitutional questions. Here, as in Witkovich, requiring that the information requested be relevant to the statutory purpose avoids the constitutional questions. Witko-vich provides further guidance in that, in both cases, the statutes and regulations are part of a single legislative scheme relating to deportation.

Clearly, the INA allows the Attorney General to promulgate regulations conditioning nonimmigrant admission and status. 8 U.S.C. § 1184 (a) (Supp. V 1993); 8 U.S.C. § 1251 (a)(l)(C)(i) (Supp. V 1993); see also Narenji v. Civilett% 617 F.2d 745, 747 (D.C.Cir.1979) (upholding the authority of the Attorney General under the INA to impose reporting requirements on nonimmi-grant Iranian students because the regulation was “directly and reasonably related to the Attorney General’s duties and authority under the Act”), cert. denied, 446 U.S. 957 , 100 S.Ct. 2928 , 64 L.Ed.2d 815 (1980). However, the regulation’s extension to furnishing “nonmaterial” information irrelevant to status or benefits is inconsistent with the statutory scheme. We hold that the parenthetical phrase of the regulation concerning materiality is invalid.

The deportation order was based solely upon a finding that Romero had made an untruthful statement to an immigration official, but that statement was not material in any way to her immigration status. The statement related only to a criminal investigation of other persons. The order of deportation is reversed.

REVERSED AND REMANDED FOR WITHDRAWAL OF THE ORDER OF DEPORTATION.