QKD parameter estimation by two-universal hashing leads to faster convergence to the asymptotic rate

in Quantum (2021)

This paper proposes and proves security of a QKD protocol which uses two-universal hashing instead of random sampling to estimate the number of bit flip and phase flip errors. This protocol dramatically ... [more ▼]

This paper proposes and proves security of a QKD protocol which uses two-universal hashing instead of random sampling to estimate the number of bit flip and phase flip errors. This protocol dramatically outperforms previous QKD protocols for small block sizes. More generally, for the two-universal hashing QKD protocol, the difference between asymptotic and finite key rate decreases with the number $n$ of qubits as $cn^{-1}$, where $c$ depends on the security parameter. For comparison, the same difference decreases no faster than $c'n^{-1/3}$ for an optimized protocol that uses random sampling and has the same asymptotic rate, where $c'$ depends on the security parameter and the error rate. [less ▲]

An introduction to the theory of unconditionally secure message authentication using the constructive cryptography framework

E-print/Working paper (2019)

We provide an introduction to certain ideas from the theory of unconditionally secure message authentication. We explain the notions of impersonation and substitution attacks, and explain how protection ... [more ▼]

We provide an introduction to certain ideas from the theory of unconditionally secure message authentication. We explain the notions of impersonation and substitution attacks, and explain how protection against these two types of attack implies composable, information theoretic security. We explain the relation of authentication protocols to universal hashing. We give both probabilistic and explicit constructions proving the existence of one way authentication protocols using a short secret key and we prove matching lower bounds on the required secret key size. Then, we turn attention to interactive authentication protocols. We explain the message size reduction technique used by Gemmell and Naor and later Naor, Segev and Smith, and how it leads to protocols with secret key size independent of the message length. We also prove a matching lower bound on the secret key entropy. We generalize the lower bound proof of Naor, Segev and Smith and remove the assumption that the message is revealed in the first flow of the protocol. [less ▲]

On the Relation Between SIM and IND-RoR Security Models for PAKEs with Forward Secrecy

in E-Business and Telecommunications - 2019 (2019)

Password-based Authenticated Key-Exchange (PAKE) protocols allow the establishment of secure communication entirely based on the knowledge of a shared password. Over the last two decades, we have ... [more ▼]

Password-based Authenticated Key-Exchange (PAKE) protocols allow the establishment of secure communication entirely based on the knowledge of a shared password. Over the last two decades, we have witnessed the debut of a number of prominent security models for PAKE protocols, whose aim is to capture the desired security properties that such protocols must satisfy when executed in the presence of an active adversary. These models are usually classified into (i) indistinguishability-based (IND-based) or (ii) simulation-based (SIM-based). However, the relation between these two security notions is unclear and mentioned as a gap in the literature. In this work, we prove that SIM-BMP security from Boyko et al. (EUROCRYPT 2000) implies IND-RoR security from Abdalla et al. (PKC 2005) and that IND-RoR security is equivalent to a slightly modified version of SIM-BMP security. We also investigate whether IND-RoR security implies (unmodified) SIM-BMP security. The results obtained also hold when forward secrecy is incorporated into the security models in question. [less ▲]

Entanglement of Approximate Quantum Strategies in XOR Games

in Quantum Information and Computation (2018), 18(7&8), 06170631

We characterize the amount of entanglement that is sufficient to play any XOR game near-optimally. We show that for any XOR game $G$ and $\eps>0$ there is an $\eps$-optimal strategy for $G$ using $\lceil ... [more ▼]

We characterize the amount of entanglement that is sufficient to play any XOR game near-optimally. We show that for any XOR game $G$ and $\eps>0$ there is an $\eps$-optimal strategy for $G$ using $\lceil \eps^{-1} \rceil$ ebits of entanglement, irrespective of the number of questions in the game. By considering the family of XOR games CHSH($n$) introduced by Slofstra (Jour. Math. Phys. 2011), we show that this bound is nearly tight: for any $\eps>0$ there is an $n = \Theta(\eps^{-1/5})$ such that $\Omega(\eps^{-1/5})$ ebits are required for any strategy achieving bias that is at least a multiplicative factor $(1-\eps)$ from optimal in CHSH($n$). [less ▲]

Deniability in Quantum Cryptography

Poster (2017, June 14)

This poster describes ongoing work on deniability in quantum cryptography, an area of research that remains almost entirely unexplored in the quantum information processing literature. Deniability is a ... [more ▼]

This poster describes ongoing work on deniability in quantum cryptography, an area of research that remains almost entirely unexplored in the quantum information processing literature. Deniability is a well-known and fundamental concept in classical cryptography and it can be defined as the ability for the sender of a message to deny the contents of a message or the very act of having participated in an exchange, e.g. having sent the said message. We discuss deniability in the context of quantum key exchange and address a particular problem, first discovered by Donald Beaver, where he claims that all QKD protocols are undeniable. The claim is that while we do get a one-time pad (OTP) using QKD, it does not provide the property of key equivocation as it is expected in the Shannon sense for a OTP. Intuitively, this difficulty lies in the quantum channel alone and it has to do with the fact that in QKD, while we generate entropy by expanding an initially short pre-shared key into an arbitrary longer secret key, we do so by exchanging information over a quantum as well as a classical channel, which could potentially leave a binding transcript of Alice's decisions to the final secret key. This is in contrast with the implicit assumption that Eve knows nothing about how two given parties have established their shared OTP in the first place. We discuss the importance of deniability in cryptography and its wide range of applications, along with cryptographic primitives other than key exchange where deniability might be a desired property. Finally, we present a series of fundamental open questions in this area of research and discuss quantum cryptographic primitives that lend themselves to devising deniable protocols. [less ▲]