We propose a (universally composable) Two-Factor Authenticated Key Exchange (TFA-KE), a notion which extends asymmetric PAKE (aPAKE) with a 2nd authentication factor, a \(t\) -bit one-time code computed by a personal device based on a clock or a counter. Our notion strengthens the security of standard integration of an aPAKE with short authentication codes by slowing down offline brute-force password search in case of server compromise by a factor of \(2^t\) . In other words, our TFA-KE notion uses \(t\) -bit authentication codes not only to improve on-line security of password authentication, as is the current practice, but also to strengthen password security on server corruption. We show a generic framework for implementing TFA-KE, with two efficient instantiations. Our key enabling tool is a tight one-way function (TOWF) with an algebraic structure that allows for efficient function evaluation on secret-shared inputs. We initiate the study of such functions, and we provide two proposals which we show to be tightly one-way in the Generic Group Model. Tightness means that a function evaluation on an input sampled from domain \(\mathcal {X}\) takes \(\varOmega (|\mathcal {X}|)\) time to invert, which in our application implies that offline password search attacks are slowed to \(\varOmega (|D|\cdot 2^t)\) for passwords sampled from dictionary D.