Re: PK Key exchange scheme involving 3 parties

The program doesnt need to be public, but there's no way to protect it
during transmission to S in a secure way.

What do you mean by "protect"? Can't Alice sign the program? Can't
Alice and S establish a secure channel (using, e.g., TLS), and then have
Alice send the program over this secure channel from Alice to S?

I'm still having problems understanding the problem statement. Maybe
it would help if you described your threat model, your security goals,
the trust relationships between the parties, and any other constraints
(e.g., who knows which other parties' public keys, restrictions on
connectivity, and so on) concisely in a single place.