In the real world, the sorts of reply attacks you mention don't exist because the threat model is different. Instead of trying to create something digital, which is hard, which has some mathematical properties to implement a signature, which is hard, they tend to rely on more affordable analog techniques.
Fairy Wrens are an excellent example. Fairy Wrens have to worry about brood parasites: Horsfield bronze Cuckoos. If the Cuckoo eggs hatch, they're similar enough to the Wrens that they will get fed by the Wren mother. They then kick the baby Wrens out of the nest, one by one, so that they get more food from the mother.
The solution is sweet. Each Fairy Wren mother has a unique incubation song. It's the "shared secret" for the family. She sings it after the chicks have developed in-egg enough to hear the song, but before the Cuckoos can get to the nest to lay their eggs. When they all hatch, the real chicks incorporate that shared secret into their calls for food. Any chick that doesn't is assumed to be a Cuckoo and is destroyed.
This technique avoids a replay attack not using fancy mathematics, but by the raw difficulty in identifying the essential part of the shared secret before it's too late. It's simply too difficult to find the shared secret by listening to the other animal. Even with a "universal vocal apparatus," the Cuckoo would have to learn the shared secret the hard way because trying to do a perfect replay every time would immediately be detected as a replay. Unlike digital messages, our analog interactions are always within a context. It's very easy to detect when someone is just speaking to a script.
This obviously only occurs within the nest, which is a short time period. However, it would be easy to develop a constantly changing scheme which is very hard to follow unless you have the neural wiring to make the scheme work and had been raised to nurture the skill of using it.
If you really wanted a system where you can indoctrinate an individual once and they know their identity from there on, it would probably be easier to do a zero-information proof rather than some complex mathematical trick. Zero information proofs are fascinating systems which involve three messages between the Subject and the Interrogator:
- First, the Subject announces a pair of related problems. The problems are chosen around a coin flip. One problem would be easy for a forger to fake, while the other would be very difficult unless you really knew the shared secret. The pair is chosen such that it should not be obvious to the Interrogator which solution is easy to forge and which one is hard.
- The Interrogator then picks one problem and demands the subject Solve it.
- If the Subject is the real, deal, they know the secret, so either problem is easy, so they announce the solution. If the Subject is a fake, then they have a 50% chance of the Interrogator asking for the easy question, and a 50% chance of them asking for the question they don't have an answer for.
This process can then be repeated many times to achieve a high level of confidence that the subject is the real deal: they know the shared secret.
An example of this which could be reasonable for biology to act on involves a shared secret which is a Hamiltonian cycle through a graph: a path through a graph which visits each vertex once. It's very easy to generate such a graph. All you have to do is create a cycle of the desired length, and then add enough edges to make it hard to find the cycle. As a general rule, finding a Hamiltonian cycle on an arbitrary graph is NP-complete.
The way we set things up, the graph itself is going to act like a public key (of sorts), while the Hamiltonian cycle is the private key.
Obviously, we can't just show our Hamiltonian cycle to every Interrogator, or else the Interrogator gets to know the cycle, even if they shouldn't. But we have a trick up our sleeve. There's another graph problem which is difficult: identifying an isomorphism of a graph. An isomorphism of a graph is a relabeling of a graph. You relabel all the vertexes, and you relabel all the edges. It turns out that proving whether two arbitrary graphs are isomorphisms of each other is also NP-complete.
So here's our algorithm:
- The Subject creates an isomorphism of the graph. This just involves relabeling all of the vertexes and edges and encoding that across your universal vocal device. The subject then announces "Here is my graph for this interaction. It is an isomorphism of the public-key graph, and I know a Hamiltonian cycle on it."
- The Interrogator then demands either "prove your graph is an isomorphism of the public-key graph" or "prove that you know a Hamiltonian cycle."
- The Subject then reveals what the Interrogator asked for. If they ask for the isomorphism, the subject simply reveals the isomorphism they created at the start. If they ask for the Hamiltonian cycle, the subject uses its isomorphism (which has not been shared with anyone) to convert the private-key Hamiltonian cycle into the one for this graph.
If the Subject is a fake, they would have needed to create the graph in step 1. If they created this by taking the public-key graph and making an isomorphism (like a true Subject would), then they won't know the Hamiltonian cycle for that graph because it's the shared key, and finding such a cycle is NP-complete. They have a 50% chance of the Interrogator asking for the cycle, which they cannot provide.
On the other hand, the fake Subject might instead create a Hamiltonian cycle of the correct length, add the correct number of edges to make it look like an isomorphism of the public-key. If the Interrogator asks for the cycle here, they can provide it. However, if the Interrogator asks for the isomorphism, they won't be able to provide it, because finding an isomorphism between two graphs is also NP-complete. Once again, they have a 50% chance of the Interrogator discovering them.
Now interestingly, the zero information proof also lets us consider a fake Interrogator. This is the case you are worried about where the predator learns to mimic the prey. At the beginning, the Subject provides a graph. The Interrogator is then allowed to ask either for the isomorphism or the Hamiltonian cycle. If they were given the privilege of asking for both, they would have enough information to reconstruct the private key shared secret. However, they don't get that privilege. They either get the isomorphism, or the Hamiltonian cycle, but not both.
The neat thing about this process is how little it actually requires. Graphs are easy to implement with neurons, and isomorphisms and cycles are equally easy. The hardest part is picking a good graph and cycle. The problems here are NP-complete because we can prove that there exist graphs for which these decision problems take NP time. This is not a guarantee that every graph has this property. Obviously, a boring ring graph A->B->C->D->A is extremely easy to find the Hamiltonian cycle for, and is extremely easy to find an isomorphism for. The arms race would be finding a good graph and cycle to use. Fortunately, this is an easy process! If a graph is broken, you can generate a new one very quickly. Then you just need to disseminate it!
