According to the wiki:
After the completion of "The Eighth Heroine", Bozai can be found at a tent outside of the front of Gerudo Town.
Remember that you need to look like a girl to be able to talk with him, you will do the trick with the gerudo set.
This is essential since Bonzai plays an important role for the completion of the quest:
Be sure you are wearing the Gerudo Clothes and run counter-clockwise around Gerudo Town. You will run into a man named Bozai. Talk to him while wearing the Gerudo clothes and he will start talking to Link. After hearing that Link is interested in his Sand Boots, he will set Link off on a quest to find the Eighth Heroine, beginning the side quest.
Link can explore Gerudo Town in search of a clue about the Eighth Heroine. If he visits Patricia, the sand-seal of the Gerudo Chief Riju, he can feed her some Wildberries. Through Padda, who can translate Particia's words, Link learns that "Risoka Snowfield rests upon the shoulders of the eighth heroine..." Risoka Snowfield is a marked location on the map at the west end of the Gerudo Highlands. The Statue of the Eighth Heroine is located just to the north, in the valley that leads down to the Hemaar's Descent.
The fastest way to reach the area is to warp to the Kema Kosassa Shrine at the Risoka Snowfield. Alternatively, travel to the west end of the Tanagar Canyon and from there you can climb up Hemaar's Descent. Once you draw near to the statue, it becomes an actual discoverable location on the map. Take a picture of the upper portion of the statue, so the head is in the photograph.
Return to Gerudo Town and once again put on the Gerudo Clothes. Find Bozai running around Gerudo Town and show him the picture. As a thanks for finding the picture, he will give Link the Sand Boots. However, he will take back his snow boots.
After completing The Eighth Heroine, Link can speak with Bozai once again and begin
The Forgotten Sword side quest.
So, you don't need to complete the Vah Naboris dungeon for that.