Yes. When you say it only works for logged in users, do you mean the results page or just the search box in general? If your root document is set to have permissions set to be authenticated, then the search will only work for authenticated users. The search index itself doesn't have permissions set on it so it's not specifically a search issue, it has to be more related to configuration of the page, template or webpart.