Is there a companion algorithm for OTP to ensure integrity and/or authentication? One-Time Padding is (theoretically) perfect encryption algorithm. Let's assume that these problems are solved:


Fast generation of independent and identically distributed random variables
Perfect key distribution system
Key only used once.
Key destroyed after use, without side channels that would allow any non-trusted third party to attain any key bits.


However, for modern information exchange, it is not sufficient to encrypt information (this is against Eve). In addition to encryption, it is necessary to also protect


integrity (this is against broken phone or cable) and
message authenticity (this is against Mallory).


Some recommendations in cryptography recommend to use security level similar for encryption keys and message authenticity keys (i.e. use 128-bit encryption key and 128-bit MAC key). For MAC tag, it is common convention for HMAC or to use at most half of the MAC key length as the output length. Some other algorithms use full block length of the function.

For information theoretic authentication tag security, I would expect that in order to transfer message with length $N$ bits, I would need at least another $N$ bits to transfer "authentication tag" matching with the message.

Choices for Integrity or Authentication

Here are some of example schemes:


Double the bits. I.e. when instead of 0110, process plaintext 00111100 with OTP. This'll eat twice as much key material than OTP, but will protect against any single bit errors, and many of other errors, because it is easy to check at the recipient. (If only worrying about integrity.) 
Process concatenation of $P$ (plaintext) and $T$ (mac tag) via OTP. There is problem how to calculate $T$. My first idea would be to use some operation on binary Galois Fields $GF(2^n)$, such as multiplication $C * C$ and use OTP to send that "checksum". (Only for integrity, but detects integrity problems with larger probability than option 1.)


Any suggestions how to efficiently calculate $T$?
Are there any schemes which would provide usual security without key length $K=2N$?
Are some of preconditions incorrect?

For authenticity it would appear that these are valid options:

3. encrypt-then-mac with an information-theoretically secure mac.

4. mac-then-encrypt with an information-theoretically secure mac.

What would be suitable information-theoretically secure mac for implementing alternative 3?
Alternative 4 uses more key material than alternative 3. Are there any situations where alternative 4 would be profitable over alternative 3?

Previous Questions About The Field

You could think of this question as sort of add-on question to:
"Having 4096 bit keys and short (&lt; 256 byte) messages, can I simply use the key as OTP?"
You can construct a one-time MAC that has similar properties to the OTP. Better still, it uses a fixed number of bits for each message.

Here's how it works. Choose the closest prime to your message block size. Let's say you plan to process 128-bit chunks of your message. Let's say there are $L$ such blocks.

The first job is to pick the first prime larger than $2^{128}$ which is $2^{128}+51$. Call this value $q$.

The key has two pieces. Let's call these $x$ and $y$ and choose these at random from the range $1$ to $q-1$.

Your MAC is then: 

$mac(m, x, y) = m_L\times x^L + m_{L-1} \times x^{L-1} + ... + m_{1} \times x + y \mod q $

You basically evaluate a polynomial with a term for each block of the message. The co-efficient is the message block and this is multiplied by the key raised to the power of the current block number. All operations are done mod $q$.

Provided $x$ and $y$ and are used precisely once, this MAC is secure against all adversaries.