Security protocol for server-side shared secret generation

I am trying to implement a security system that has the following requirements:

• All clients share a password, which is not known to the server
• Each client has a unique client-id, which is known to the server
• All clients with knowledge of the password must be able to generate the same shared secret on the server (this secret can be anything, it just needs to be the same for all clients and unique across passwords)
• The password needs to remain secure, even if the server or the transport get hacked
• It must be impossible for another party with a different client-id to generate the same server-side secret without knowledge of the password

Let me try to give a graphical representation of this:

            Client                         Server
.--------------^-----------.       .----------^----------.

          f(client-id 1)              g(client-id 1)
PASSWORD ----------------> request 1 ----------------> KEY
   || equal                                             || equal
PASSWORD ----------------> request 2 ----------------> KEY
          f(client-id 2)              g(client-id 2)

Here, f() [g()] are functions that the client [server] applies to the password [request] to obtain the request [key]. These functions may depend on the client-id.

There's two approaches that I have come up with that might do this, but I am hoping for something simpler that requires less traffic and less server load:

1. "No-brainer": The clients hash the password. The clients and server each use a standard mechanism (like SSL) to secure their connection and send the hash over this connection.

2. "A little more clever": The server has a fixed private-key coded into it and each client has the public-key coded into it. The clients hash the password, XOR it with their client-id, encrypt the result with RSA/PGP using the public key. The server then decrypts the request using the private key and XORs the result with the client-id to arrive at the password hash.

In both cases, the server ends up with the same secret for the clients: the password hash. The advantage of the second version is that there is no need for the overhead of a full-fledged key exchange and encryption system, since unfortunately I won't be able to rely on SSL in all cases. In fact, it allows me to generate the server secret in a single request without any handshake. The client-id-XOR in the second version are used to prevent replay-attacks, where a third party with a different client-id could otherwise simply send the same encrypted message to the server to generate the same secret. Basically it's a no-overhead way to add a salt.

Now the question:

Since I don't really have any requirements on the server-side secret, not even that the clients can generate this secret locally, is there an even simpler way to do this that doesn't require expensive modular exponentiation of arbitrary-precision numbers like RSA does? I'm thinking of maybe some sort of other trapdoor function for f() and g() above that allows me to achieve the same result.

No takers, I guess... The question is probably too vague...

In any case: For now I've decided to use RSA (i.e. approach 2 from above). It's simple enough to implement and with the right libraries, it's not too expensive to run either.