Consider the following paper based OTP
How to introduce data integrity/ MAC in it which can be calculated using pen & paper.
Use SHA3-224 HMAC.
Define a security parameter $\kappa$, and both sides consume that much $K_i$ keying material. A paper based OTP will probably choose a smaller parameter than a TCP-based protocol would choose.
Compute and append the $\kappa$ prefix of the HMAC result to the message, encoded as base 11 digits.
Transmit the $C_i$ message as above.
Receiver computes HMAC and verifies that the prefix matches.
EDIT
...which can be calculated using pen & paper.
Oohhhh. Well there's a new wrinkle.
Define a new security parameter $D$, number of check digits to send.
Define a base $B$. It most naturally would be 11, but for human convenience we may choose to make it 10. It is possible that some casting out nines procedure would motivate using 9.
Find a running total of the various $M_i$ figures, $\mod B$, and write the number down beneath each $M_i$.
Append the final $D$ such numbers to the message.
Transmit this augmented message as OP describes. Notice that each check digit is protected by its own $K_i$.
Receiver performs the same steps to verify.
Observation: Mallet has a much better chance for undetected corruption of one of the final $D$ characters of the original message under this "scheme-A", especially if he wants to corrupt its final character.
Remedy: In "scheme-B", consume $D$ characters of the $K_i$ keying material and append those to the original message at the very beginning of the procedure, so we're transmitting a checksum of characters both unknown and known to the recipient.
Assume that "keying material is cheap", so for example we are willing to consume 200 characters of $K_i$ to send a message of length 100. Could we use that to improve robustness? Assume that "$D$ is small", that is, $D < \sqrt{ |M| }$ where $|M|$ is length of message.
Second observation: Humans are fallible. Sometimes we write down arithmetic mistakes. Could we rescue parts of a message that Alice accidentally garbled?
Remedy: Starting from the message's end, break out $D$ message chunks. Most will be of equal size; the first few are likely to be shorter by one. Compute and transmit per-chunk checksums independently.
At this point I also want to send "more than one" (how many?) combined checksum digits which summarize the individual transmitted checksums. Maybe one for the odds, one for the evens? Or a tree that transmits eight checksums, then four checksums of pairs, then two checksums, then finally a master checksum?
Leaning on the "fallibility" aspect, maybe spend part of our checksum budget on computing / transmitting checksums of reversed message characters?
There's a problem with the above answer. One expects that when you use an OTP system, that no amount of computational power from the adversary can compromise the security of the system. However, with any HMAC scheme the attacker can simply run a bruteforce on the HMAC key. Once they recover the HMAC key they can just simply create their own forgery(albeit at extreme cost assuming the underlying PRF is computationally secure).
We can just use any universal hash algorithm for a one time MAC that will be informational theoretic secure. For all universal hashes, the probability of a collision for any chosen input(adversarial or not) given an independently and uniformly randomly chosen hash key(ie one that is not known to the attacker) over a sufficiently large domain (ie 2^128) is guaranteed to be very low. The algorithm looks something like this:
def compute_mac(hash_key, blinding_key, ciphertext):
# Ensure that hash_key and blinding_key are uniformly random, sufficiently large, and fresh for each invocation of this function
# Also ensure that the universal hash is large enough to make the probability of a collision sufficiently low
collision_resistant_output = universal_hash(hash_key, ciphertext)
blinded_output = OTP_encrypt(collision_resistant_output, blinding_key)
return(blinded_output)
This is essentially an Carter-Wegman authenticator but instead of using a block cipher or similar to generate a pseduorandom one time pad to conceal the universal hash's output, we just grab some additional random pad data instead. The security of this one time MAC depends on the two keys being uniformly random and fresh for each time it is used and on how collision resistant the universal hash is(choosing a small universal hash will give a worse bound for collision resistance and therefore make it easier to create a forgery). As an example, you can look at using Poly-1305 as an one time authenticator (see link). If you use this instantiation, the security bound is 8 * ceil(ciphertext_length_in_bytes/16)/2^106 chance of a successful forgery for each attempted forgery no matter how much computational power an attacker throws at it.
