We tackle the problem of securing communication in Local Area Networks (LANs) and making it resistant against Denial-of-Service (DoS) attacks. Our first contribution is the Cryptographic Link Layer (CLL) - a comprehensive security protocol that provides authentication and confidentiality between neighboring hosts from the link layer upwards. Verifying digital signatures in the handshake phase of CLL is an expensive task compared to symmetric-key operations. Thus, it may become a target for new DoS attacks. We introduce a countermeasure against DoS flooding attacks on public-key handshakes in LANs, called counter-flooding. A known approach against DoS attacks in the Internet are client puzzles. However, existing client puzzle schemes have drawbacks when being applied in LANs. We propose a novel, non-parallelizable scheme for client puzzles based on the computation of square roots modulo a prime. By introducing a secure client puzzle architecture we provide a solid basis to safely employ non-interactive client puzzles. In our final contribution, we pursue the idea of cryptographic puzzles beyond DoS protection and propose an offline submission protocol based on RSA time-lock puzzles.