The Internet of Things (IoT) has widespread applications covering from tiny wearable devices to large industrial systems. When building authentication channels among IoT devices for security enhancement, one of the biggest challenges is how to reduce the size of keys and authentication tags in systems since they do not have rich resources (such as, memory and bandwidth) in many cases. Although many solutions have been introduced to address this challenge so far, to the best of our knowledge, we do not have a solution to compress the size of keys and authentication tags simultaneously in a cryptographic manner. In this paper, as a core primitive to solve this problem, we propose a new cryptographic protocol called proxy re-authentication. In proxy re-authentication, we realize key compression by converting a (authentication) tag generated with a sender’s private key into another one so that a receiver can verify with his own private key through a proxy. In other words, in the systems equipped with proxy re-authentication, each user is required to have only its own key to communicate with other users. Moreover, in this protocol, it is possible to realize a compression of the size of tags by aggregating tags based on the idea used in aggregate message authentication. We provide two constructions of proxy re-authentication: one is based on the hardness of the computational Diffie-Hellman problem over cyclic groups and the other is based on the hardness of the learning with rounding problem over lattices. Then, we show that these constructions are practically efficient by implementing them.