Then why not publish all the phone numbers in clear.
Please accept my genuine apologies here, I think I must have crossed some wires / be operating under different assumptions / be talking past you somehow.
To clearly state my position, I believe:
a) Publishing a list of sha256(.au phone number) is equivalent to publishing the list in clear
b) We are discussing the set of phone numbers of affected Medibank customers, which could be described in a variety of ways (e.g. bitmap, dumb list, hashed list, bloom / cuckoo / xor filter etc).
c) There is basically nothing efficiency wise you need to think about to provide lookups in a database of phone numbers if you don't care about security. It is "laughably small data". All Australian phone numbers will fit comfortably in an Excel spreadsheet, Sqlite database, greppable text file etc.
Finally: Phone numbers and emails are a little weird. They are PII but the seriousness of their disclosure depends on context. Imagine a publicly posted list of porn purchases or medical conditions by phone number. It has a sort of "casual privacy" about it but is quite transparent to each user's contacts.
You could just keep the data on your server in plain text, even if it would get hacked, there would be no real additional damage as the data is already in the wild. There might however be legal reasons why you can not do this.
So as an exercise in how to handle such data properly or in order to comply with the law, you want a secure solution, i.e. assuming the data is not already in the wild, how do you implement this in a way that getting your server hacked does not leak the data?
The idea was then to just hash everything with SHA-256, but this does not work because SHA-256 is fast and the search space relatively small, so the hashes can be more or less easily reversed. The next better option would be to hash the data with something slow like bcrypt, that would make reversing the hashes orders of magnitude slower with a well chosen work factor.
haveibeenpwned.com also had an article discussing the decisions they made in quite some detail.
Unfortunately, the leaked data is available to anyone. There is no point of putting an extra effort of recovering the data from its hashed form.
Agree, all the data being public already renders everything a bit moot.