Elliptic Curve Diffie-Hellman (ECDH) with
Public parameters: Ep (a,b) and G = (x, y)
Private Keys: Na, Nb
Public Key: Pa = Na x G, Pb = Nb x G
Secret key: k = Na x Pb = Nb x Pa
Is the algorithm still secure if public key Pb is used more than once with different private keys Nb? Or are there any requirements to use use a public key more than once in a secure way?
Is the algorithm still secure if public key Pb is used more than once? Or are there any requirements to use use a public key more than once in a secure way?
I'll amend the question to what I think you mean ("is ECDH secure if we reuse our private value across multiple exchanges"), and answer it, "yes, it can be done securely, but (under some scenarios) you MUST perform validity checking on the value you receive from the peer".
The biggest thing you need to check is "is the value you receive a point on the curve?". After all, you take the values $x_b, y_b$ that you received, and plug them into the EC point multiplication routine, and perform a series of point additions/doublings. These routines generally assume the point they're given is already on the curve; if not, they'll assume a curve that the point is on. That is, you are performing the operations on a curve which may be $y^2 = x^3 + ax + c'$, for a $c'$ that the attacker selected. The attacker can select such a curve to have an order with a small factor $r$, give you a point of order $r$, and so the shared secret would be one of $r$ values (and which one would indicate the value $N_a \bmod r$. By doing this several times with different curves (and different values of $r$), he can deduce the value $N_a$.
Now, one variant of ECDH is for both sides exchange only the $x$ values (and have the shared secret depend only on $x$); this largely avoids this problem (but not entirely, unless you have a curve with "twist security"), and is done by (for example) Curve25519 . However, it is not universal; sometimes you are implementing an existing protocol that insists on exchanging $x, y$ values.
If you must exchange both $x$ and $y$ values, the fix is actually pretty easy: just plug the values you receive into the curve equation and see if it satifies it; that is, if $y_b^2 = x_b^3 + ax_b + c$; if not, abort the key exchange.
There is also a second (far less serious) issue; suppose that you receive a public value that's a valid point on the curve (and so passes the above check), is not the point at infinity (you do check for that, don't you?), but isn't in the prime order subgroup that $G$ is in. We normally do ECDH in a curve of order $hq$, where $h$ is a small integer, and $q$ is a large prime (and is the order of $G$). By giving us a point that's in the larger curve, the attacker can potentially learn $N_a \bmod h$. This isn't nearly as serious (as the attacker can't try different values of $h$), however it is still a leakage.
Things we can do about this:
Use a prime order curve; that is, one where $h=1$. In that case, the attacker learns nothing (as any point on the curve he gives us is also within the subgroup)
Do "cofactor DH" instead; this modifies the secret derivation to $k = (hN_a)P_b = (hN_b)P_a$; by including $h$ in the final computation, this attack would give the attacker the value $hN_a \bmod h$, but that's always 0, independent of what $N_a$ is. Of course, this may not be an option if you're implementing an existing protocol.
Verify that $qN_b = 0$ (that point at infinity); this works, but this is a fairly expensive computation; no cheaper than selecting a fresh ECDH private value each time.
Just live with it; even if $h>1$, it is typically a small value, such as 4 or 8; giving the attacker a few bits of the private value doesn't help him that much
(I assume what you are asking is: Is it secure to use an ECDH key pair for more than one key agreement?)
Actually, using an (EC)DH key for more than one key agreement is the norm rather than the exception. We do it all the time: Any TLS cipher suite with DH or ECDH in its name (rather than DHE and ECDHE) uses one static key pair for all the connections using that cipher suite, and if you use newer GnuPG versions' X25519 support, the key pair used to encrypt messages is fixed as well.
Somehow, since generating (EC)DH key pairs is so cheap (as opposed to RSA keys, which require expensive primality testing), it has become standard to talk only about ephemeral DH in literature and teaching, even though the variant with long-lived public keys is quite common and useful!
The only "issue" with this is that it provides no forward secrecy, i.e., if a static private key is leaked at any later point in time, it may still be used to recover the shared secret (and thus decrypt messages) of all agreements made using that key. (Ephemeral DH avoids this by simply destroying the private key after the shared secret has been established.) However, I consider that a property of the way DH is used, not of the system itself.
From the math, it certainly appears that knowledge of one private key would not likely provide much information about other private keys. This thought experiment supports the same conclusion:
Although one can theoretically eliminate a large number of public keys by knowing a private key, one cannot use this fact to limit the range of other possible matching private keys because the public key is already known. So the intermediate set is fixed in causal connection between two private keys.
From the conservative and practical perspective, most development testing and production use of the ECDH (as well as others) were done with key pairs generated in typical ways (for instance openssl's command line utility run once for the private key and then again to extract the embedded public key from the bundle).
Thus, if you generate multiple private keys for one public key, you may not fully benefit from either continuous integration with the cipher's test suite or the years of field testing by corporations and government entities.
In the question quoted below, I'll assume the private key in the end is Nb, not Pb
Is the algorithm still secure if public key Pb is used more than once with different private keys Pb?
Yet, the question is still impossible to answer as asked: Pbis obtained from Nb by the stated relation Pb = Nb x G, and different private keys Nb will lead to different public keys Pb (either certainly or with overwhelming likelihood, depending on parameters); hence the hypothesis of reuse of the same public key with different private key won't happen, and discussing its safety is moot.
Meaningful questions would be:
Pb/Nb pair be safely reused by one party? That depends on the definition of safely; the simplest answer is no, because the party reusing a Pb/Nb pair is vulnerable to replay.