Yes, you're right, perhaps I oversimplified too much. That is the main hurdle Waters and Sahai have overcome. They do this by not using a counter, but randomly

Yes, you're right, perhaps I oversimplified too much. That is the main hurdle Waters and Sahai have overcome. They do this by not using a counter, but randomly-selected nonces that feed a keyless stream generator (like AES-CTR with a fixed known key), and use a mechanism (puncturing) to 'blacklist' previously-used nonces so that they reveal nothing about previous keystreams used. Without being able to ask for encryptions of arbitrary messages using a previous nonce, the attacker has little options. Granted, this is annoying because you have to 'recompile' the obfuscated encryptor for each new nonce, but that is of no concern in the model being used.