whose implementation we want to keep secret
This is usually an indicator that your scheme is insecure. The implementation itself should not need to be secret. The secret should be key material, not the alghorithm or implementation itself. This all falls under Kerckhoffs's principle.
Now the question is, can we ever realistically hope to prevent an attacker from gaining access to the key?
Absolutely not. I can think of at least five attacks off the top of my head that'd break this, starting with dumping all memory via PCI-e DMA.
As an example of how utterly impossible it is to keep keys hidden away when an attacker has physical access, look at the games console homebrew scene. The Xbox 360 and PS3 had a whole range of security controls built right into the CPU's silicon, with on-die secret key storage, isolated RAM for secure execution units, cryptographic chain-of-trust from the bootloader all the way to the applications (games), and all sorts of other clever controls... and it only took 12 months for people to break each platform (in the case of the PS3 it was 12 months after Sony killed Linux support). Physical access means the attacker will ultimately make it do as they wish and gain access to every last bit of data on the device.
I'm saying that to secure this system, A or B needs to somehow be connected to an external validation source C, that the attacker does NOT have phyiscal access to. Is this correct?
I'm not sure how "validation" applies here, but essentially you need to keep
f(x) from ever being leaked, so it must be stored and executed on a system which the user (or an attacker) does not have access to.
You'll also need to consider the effects of an attacker employing your remote service as an oracle, which it essentially is. As an example, the PS3's hard disk was encrypted and nobody could access the decryption keys (these were on-die and only accessed from an isolated execution unit) but, due to a flaw in the encryption process - they used the same key and IV for every sector - you could take a snapshot of the disk, upload a movie to the PS3, look for the big block of sectors that changed, then overwrite those sectors with any others from the disk (say, the operating system itself), boot the PS3 back up, download the movie again, and the system decrypts the disk sectors (without you ever knowing what the key was!) and gives you the original plaintext back. Homebrew devs used this oracle attack to decrypt data without ever needing to know what the key was. You should consider similar attacks against your system.