A Novel Forward-Secure Key Establishment Protocol from Physically Related Functions

Abstract Physically Related Functions (PReFs) are fundamentally similar to strong Physically Unclonable Functions (PUFs). Their study was driven by the goal of realizing “Cryptophasia in hardware"—a phenomenon where two hardware devices can securely establish an authenticated key without the need for long-term cryptographic key storage. Chatterjee et al . demonstrated that devices using PReFs can achieve Authenticated Key Exchange (AKE) without the burden of intensive cryptographic computations, making this approach desirable for lightweight environments. However, to ensure forward secrecy, they employed an elliptic curve Diffie-Hellman protocol, with PReFs replacing long-term keys typically used in traditional public key-based AKE systems. This paper proposes a method to eliminate dependence on conventional public key cryptography for achieving forward-secure AKE under minimal and practical assumptions. Our forward-secure AKE protocol is constructed using PReFs, error-correction codes, and collision-resistant hash functions, and is proven secure under CK and eCK security models.