What video?
What you described is a double spend. It becomes progressively more difficulty for Alice to build the longer chain unless she hash a majority of the computing power. It doesn't matter if Alice starts building the attack chain first or makes the legitimate deposit and then starts building the attack chain the probability she will outrace the network starting from a block behind is unlikely. The more confirmations the less likely it becomes.
For a deposit of 1,000 BTC the exchange should probably require more than three confirmations. Meni wrote a very good paper on the economics of double spending. If Alice has 10% of the network computing power her chance of being successful is 1.712% for 3 confirmations, 0.546% for 4 confirmations, 0.178% for 5 confirmations, and 0.059% for 6 confirmations. The exchange can also protect itself by validating KYC information for users involved in large transactions.
https://bitcoil.co.il/Doublespend.pdfAs for your quote. I don't know what Satoshi was talking about in the quoted section as it doesn't make any sense to me either. You are right, the attacker doesn't need the victims PubKey in order to build the chain because the "attack chain" will contain the double spend not the spend to the victim. I can only conclude that Satoshi was either mistaken or he is talking about something else and is unclear in the wording. The paper was written at a theoretical level about a year before the first version of the client was completed.
This video:
http://www.youtube.com/watch?v=Lx9zgZCMqXE . At around 14:00 minutes, it explains why one can't preparing blocks ahead of time. I think what it says is incorrect.
Meni assumes one block was pre-mined by the attacker. All his calculation is base on this assumption.
My case is that the attacker pre-mines all the blocks he needs, Which makes him sure he can double spend the coins. The calculation should be different between my case and Meni's case.
I think if someone really want to double spend coins, he should pre-mine all the blocks he needs.
The reasons are:
1. When he is successfully pre-mine the blocks he needs, he is 100% sure he can double spend the coins.
2. When he pre-mine the blocks, he can abandon his hidden chain when his chain becomes shorter than the honest chain, and works on another hidden chain after the honest chain. This is more efficient. In Meni's case, unless the attacker gives up his attack, after the he spent the coins in the honest chain, he can't abandon his hidden chain even if the honest chain becomes longer than his chain.