David Elkouss

Regarding minimal assumptions, most of classical cryptography is known to depend on the existence of One-Way Functions (OWFs). However, recent evidence has shown that this is not the case when considering quantum resources. Besides the well known unconditional security of Quantum Key Distribution, it is now known that computational cryptography may be built on weaker primitives than OWFs, e.g., pseudo-random states [JLS18], one-way state generators [MY23], or EFI pairs of states [BCQ23]. We consider a new quantum resource, pseudo-entanglement, and show that the existence of EFI pairs, one of the current main candidates for the weakest computational assumption for cryptography (necessary for commitments, oblivious transfer, secure multi-party computation, computational zero-knowledge proofs), implies the existence of pseudo-entanglement, as defined by [ABF+24, ABV23] under some reasonable adaptations. We prove this by constructing a new family of pseudo-entangled quantum states given only EFI pairs. Our result has important implications for the field of computational cryptography. It shows that if pseudo-entanglement does not exist, then most of cryptography cannot exist either. Moreover, it establishes pseudo-entanglement as a new minimal assumption for most of computational cryptography, which may pave the way for the unification of other assumptions into a single primitive. Finally, pseudo-entanglement connects physical phenomena and efficient computation, thus, our result strengthens the connection between cryptography and the physical world.

The fundamental distance limit for quantum key distribution due to photon loss can be overcome by intermediate nodes called quantum repeaters. We provide analytical bounds on the mean and quantiles of the entanglement delivery time for a very general class of repeater schemes, which significantly improve upon existing work. Our bounds enable the analytical assessment of repeater in the presence of time-dependent noise, such as imperfect memories, and are useful for the design and analysis of network sizes beyond the reach of numerics.

Losses in the physical transmission medium fundamentally limit the distance that quantum key distribution schemes can cover. By means of quantum repeaters, the reach of these schemes can be extended and chains of quantum repeaters could in principle cover arbitrarily long distances. Here, we first provide an efficient algorithm for completely characterizing the behaviour of a large class of repeater chain protocols. The algorithm determines the fidelity and generation time (waiting time) of the first generated entangled pair between the end nodes of a quantum repeater chain. It has polynomial runtime in the size of the support of the waiting time probability distribution. This runtime improves upon the exponential runtime of existing algorithms and allows us to analyze repeater chains of thousands of segments for some parameter regimes. Second, we use the algorithm for optimizing the achievable secret key rate. For this, we consider a family of repeater schemes generalizing the BDCZ scheme. In particular, the schemes incorporate a cut-off condition that enables to mitigate the effects of decoherence. We find that the use of the optimal cut-off extends the parameter regime for which secret key can be generated and moreover significantly increases the secret-key rate for a large range of parameters. Our algorithms thus serve as useful tools for the design and realization of long-distance quantum key distribution networks.

Quantum networks will allow to implement communication tasks beyond the reach of their classical counterparts. A pressing and necessary issue for the design of quantum network protocols is the quantification of the rates at which these tasks can be performed. Here, we propose a simple recipe that yields efficiently computable lower and upper bounds on the maximum achievable rates. For this we make use of the max-flow min-cut theorem and its generalization to multi-commodity flows to obtain linear programs. We exemplify our recipe deriving the linear programs for bipartite settings, settings where multiple pairs of users obtain entanglement in parallel as well as multipartite settings, covering almost all known situations. We also make use of a generalization of the concept of paths between user pairs in a network to Steiner trees spanning a group of users wishing to establish Greenberger-Horne-Zeilinger states.

We study how to use quantum key distribution (QKD) in common optical network infrastructures and propose a method to overcome its distance limitations. QKD is the first technology offering information theoretic secret-key distribution that relies only on the fundamental principles of quantum physics. Point-to-point QKD devices have reached a mature industrial state; however, these devices are severely limited in distance, since signals at the quantum level (e.g. single photons) are highly affected by the losses in the communication channel and intermediate devices. To overcome this limitation, intermediate nodes (i.e. repeaters) are used. Both, quantum-regime and trusted, classical, repeaters have been proposed in the QKD literature, but only the latter can be implemented in practice. As a novelty, we propose here a new QKD network model based on the use of not fully trusted intermediate nodes, referred as weakly trusted repeaters. This approach forces the attacker to simultaneously break several paths to get access to the exchanged key, thus improving significantly the security of the network. We formalize the model using network codes and provide real scenarios that allow users to exchange secure keys over metropolitan optical networks using only passive components.