E <scp>xpress</scp> PQD <scp>elivery</scp> : Toward Efficient and Immediately Deployable Post-Quantum Key Delivery for Web-of-Things

Post-quantum cryptography (PQC) aims to develop quantum-safe algorithms against attacks by a quantum computer. As quantum-safe algorithms require much larger keys in their operation compared to the current RSA/ECC practice, the networking latency significantly increases when executing the protocols with sending such large keys. This problem gets more challenging in the era of Web-of-Things (WoT) with low-memory devices. To tackle the problem, we propose ExpressPQDelivery, which is, to the best of our knowledge, the first immediately deployable protocol to efficiently transport large keys. It leverages the DNS infrastructure, as DNS is close to clients, guaranteeing express key delivery with a short round-trip time (RTT). We split a large PQ key along with a server's signature and feed them into several DNS records. To show the feasibility of ExpressPQDelivery, we instantiate it with TLS 1.3 and demonstrate that it reduces 27% of network latency between a server and a client on average compared to the standard TLS 1.3. We deploy ExpressPQDelivery on a low-capability board with 256 KB RAM, showing a significant high gain (34%).