Without introducing more magic and without there being at least some kind of database, this is an unsolvable problem. I would say use a one-time pad, but the key would have to be stored in a database.
If the technology of the time is at least that of, say, the 1940′s, you could use quantum key distribution to at least be alerted if the crypto is broken (more useful than any other solutions), but would still require a database.
Without introducing more magic and without there being at least some kind of database, this is an unsolvable problem. I would say use a one-time pad, but the key would have to be stored in a database.
If the technology of the time is at least that of, say, the 1940′s, you could use quantum key distribution to at least be alerted if the crypto is broken (more useful than any other solutions), but would still require a database.