# How could public key cryptography evolve in a biological system?

Pssst! Come here!

Imagine an ecosystem where animals have evolved highly developed mimicry of each other’s calls (perhaps they have the universal vocal apparatus discussed in earlier questions). So predators lure prey, prey confuse predators, and rivals confuse prospective mates and each other.

So after that, they evolve an authentication mechanism. Think of the difference between a cheap garage door opener that is trivially defeated by recording the signal and playing it back later; vs the more advanced systems.

The animals evolve something like “code rotation” and use it as a signature on any call or cry (and later, language) so that simply replay attacks can’t work. They need to share a secret with the sender once to authenticate that sender going forward.

That’s the selection pressure. I'm asking: what are the biological mechanisms that provide for this? It needs to provide an evolutionary path for continuous improvement. It does noot need to be proof against our modern understanding of cryptography — just against other animals that have an incentive to evolve a way to forge them.

• the type of mimicry you are refering to is one type of what is called aggressive mimicry. I know if occurring in a different from of communication, firefly mating flashes, but not sound. When you read the paper take care the two genus have very similar names. entomology.ifas.ufl.edu/baldwin/webbugs/3005_5006/Docs/…
– John
Apr 20 '17 at 21:01
• Some would argue that the learned songs of some song birds exist to protect against something like this. By by having to learn mating songs in all their subtlety instead of instinctively knowing it it means less fit males can't fake it, they actually have to be that good.
– John
Apr 20 '17 at 21:08
• This is a good challenge. I cannot think of a complete answer, but my initial impression would be a dna sequence that produces a pheromone. But the dna sequence has a telomere like pattern in it so it changes every time the cell divides. Thus creating a regularly changing scent to use as an identifier. Problem is validating the scent. Apr 20 '17 at 21:36
• To clarify are you looking for encryption or will any evolving authentication scheme be good enough?
– user25818
Apr 20 '17 at 21:53
• Authentication is good enough. Apr 20 '17 at 22:35

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!

• humans already do this to a large extent naturally using things like cultural keys and euphemisms. you can't guess them reliably you actually have to live in the community for prolonged periods of times.
– John
Feb 24 '18 at 7:26
• "It turns out that proving whether two arbitrary graphs are isomorphisms of each other is also NP-complete." Graph isomorphism is not known to be NP-complete. Perhaps you're thinking of subgraph isomorphism. Jun 3 '18 at 0:46

Prey confuse predator is going to be great for prey. No evolutionary pressure for them to quit that.

Rivals confusing mates and each other means its harder to get some. But probably no-one dies.

Predator lure prey is where the selection pressure will come in. The fact that a predator can mimic the sounds of a lusty female of my species will mean it can eat me when I prance on in, if I am so hot to trot I show up for any lady noise I hear. That mimic ability does not mean it understands the context of the discourse occurring, or when a given sound is appropriate. I need to make sure the lady understand my worth.

The strategy by the prey is to modify calls into a call and response situation: each call by the prey should be answered by the appropriate response by a conspecific.

Call: where are the ladies who wants some musky male?
Response: I'm a lady and I want some musky male!
Call: Are you a lady who likes a guy with big bright eyes?
Response: I'm a lady and I want some musky male! - wrong. Her response should have to do with big bright eyes. She is a faker of some sort.

It is not a big step, evolutionarily. If you can make one call you can make more than one. If you wait to head over until you have heard one correct response, you can wait until you have heard 3 or 4 in a row. Instead of just repeating a call from a prey animal, the predator must repeat the correct call. If your lady messes up maybe she is young - give her another try. If she keeps getting it wrong maybe time for you to move on quietly. Maybe that's no lady.

But this can be overcome too - it is definitely a setup for an evolutionary arms race which might have very interesting end results.

• Mating is also a way for rapid evolution. Preference for some trait causes a rapid feedback to develop that trait. Apr 21 '17 at 3:38
• To expand on @JDługosz comment - "Rivals confusing mates and each other means its harder to get some. But probably no-one dies." You have overlooked the second half of Darwin's selection argument - sexual selection. It is not enough simply to survive. If an organism does not mate and pass on its genes, the evolutionary effect is the same as if it had died. Apr 25 '17 at 3:20
• If I do not produce offspring because my mate is actually a conspecific rival, I will not die. Hopefully we part on good terms. I can try again to mate tomorrow, and be more freaking careful. If I am eaten by a predator I get no additional chances. Thus the fitness impact by predation is greater. Apr 25 '17 at 15:57

Consider crickets

Male crickets create their chirps by rubbing their forewings together. One side of the wings contains a jagged edge. When the flat side of the wing rubs against the jagged side, this produces the chirp sound. [1]

So have your creature be highing sensitive to the variation in noise, then make the noise based off of an external element (skin, scales, feathers, etc). The slight variations in scale patterns (we are just going to use scales from here out as an example) will allow differential between creatures, but it's also something that would be genetically passed down. So the offspring would be similar to to the parents (allowing family/species identification).

Obviously, as the animal grow their scale pattern will change, however it will be like boiling a frog, the change brought by day to day growth will not be enough to cause confusion. One problem that will arise from this is if the creature don't encounter each other for quite some time. But then it would go back to "I know this is a male/female of xyz species" but it would no longer be as precise as "Oh this is my mate"

• But I postulate that other animals are able to mimic the sounds in some detail. It's not a different cricket using the same mechanism on his own legs; it’s a way of producing sound in a very robust way. Apr 20 '17 at 22:37
• This answer can be strengthened: crickets change the chirps by the air temperature and humidity. Only animals that can precisely sense the temp gradient can mimic the chirp. That would guard against naive replay attacks.
– SRM
Apr 21 '17 at 3:37

## Symbiotic relationship with some special bacteria

The biggest challenge to the question is the fact that a species can have a lot of biodiversity in it, and the best solution would be one that can work even with a lot of variations in the species even in one herd or pack. To help establish a randomly rotating cryptography key that can be shared amongst the species it makes sense to dump the responsibility onto something else, in this case bacteria.

### Pheromone producing bacteria

The bacteria in this relationship produce a number of unique pheromones at different levels that rotate seemingly at random, but are actually doing math based upon the DNA that result in a pheromone pattern. The bacteria when it divides keeps the random number sequence in sync. Much like cicadas can keep their cycles in sync, the bacteria likely would have similar mechanisms. With that said though different bacteria cultures may slowly drift or mutate causing a new key to form.

### Culture pouches

The species in question would have a number of pouches that feed the bacteria cultures and can release the pheromones before they broadcast a message. The other members of the species hear the message, but wait till they can smell the pheromone scent (which hopefully the wind is blowing in the correct direction). Upon picking up the scent, they sniff their own pouches to see if any match. If none match or they do not smell the scent they ignore it.

Multiple pouches allow them to keep different batches of bacteria cultures. Bacteria cultures will likely diverge as groups of animals go there own way. As such new herds or families likely would have some interesting rituals with either mixing their bacteria cultures up to generate a new mixture that all the members of a new herd or family can share or taking one of the cultures from the leader and share it with the others. Having multiple pouches allows them to keep their previous' family or herd's culture, so if others outside of their immediately family cry for help they can still authenticate the cry.