Does partial public key pre-sharing and partial public key exchange improve security vs one-sided public key sharing

I have a small ARM M0 SoC and a smartphone as actors. Encryption keys used are Elliptic curve.

My current security is implemented such that:

1. the SoC has 128 bit hashes of phone public keys (vs 512 bit - due to storage space constraints)
2. the phone has the SoC's public key
3. the phone sends its own public key during negotiation
4. step 3 establishes grounds for ECDH on both sides. From here encrypted comms can follow

We are hoping that SoC having 128 bit hash should be secure enough for trying to brute-force guess the public/private key pair. We are assuming that phone is easily compromised where the attacker will gain the phone's complete key and the SoC's public key.

So now I have come up with a solution that I'm hoping might be better, but am not sure whether it actually is:

What changes:

1. The public key hashes are now such that public key can be restored from partial data
2. The phone only sends part of its public key
3. There is an "overlapping" region between the hash on the SoC and the sent public key portion
4. Neither device contains another device's full public key
5. Both devices have to assemble the complete public key as part of negotiation procedure

So, basically, in its simplest form, the SoC now has the leftmost 128 bits of the 512-bit phone's public key. The phone sends the rightmost 416, leaving 32 bits for overlapping region, like this:

HHHHHHHHHHHHBBBBTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

• H = SoC, B = Both, T = Telephone, each character = 8 bits of the public key
• uniqueness of the overlapping part is ensured within the system.

Is this system in any way more secure than the previous system we designed? Less secure?

I'm not clear on your exact security model, but I think that both in both schemes it is feasible for an adversary to repudiate their involvement with a transaction.

I assume that you are using a standard elliptic curve over a 256-bit prime field such as secp256k1 so that points are pairs of 256-bit values which are then stored as 512-bit sequences the first half of which is an $x$-coordinate and the second half of which is a $y$-coordinate. In the first scheme a 128-bit hash of these 512-bits is stored by the server (e.g. using a Davies-Mayer construction using a 128-bit block size). By generating roughly $2^{64}$ candidate public keys and adversary can produce a pair which have the same hash value using a birthday attack. This is a painful amount of computation, but not beyond the realms of current capability. The adversary can then register one of these public keys and then establish a connection with the other. If confronted with a transcript of the communications using the non-registered key, they can repudiate by saying that it does not match their registered key.

A similar attack applies in the second case, but we should also note that if the rightmost 256-bits correspond to an elliptic curve point's $y$-value, then these alone is almost enough information to recover the rest of the public key. This is because the $x$-coordinate satisfies the elliptic curve equation which may be something like $$x^3-ax+b=y^\pmod p$$ where $a$, $b$, $y$, and $p$ are all known. We anticipate only handful of possible solution. A similar idea allows the recovery of the $y$-coordinate from just the 256-bits of $x$-coordinate and a compression bit.

You're talking about public keys, so I assume these are actually public.

I don't think this can be used for authentication. An attacker only has to find a key with 32 (BBBB) matching bits to participate in the protocol and if he finds one with 128 matching bits (HHHHHHHHHHHHBBBB) it's completely broken.

At first glance (and I am no expert on this) this looks infeasible but I would certainly recommend sticking with the first approach. That approach verifies the entire public key and is quite standard.

BTW We discourage posts about home-grown crypto here. It's not always easy to falsify and it's usually a bad idea anyway. ;)