@inproceedings{15007, abstract = {Traditional blockchains grant the miner of a block full control not only over which transactions but also their order. This constitutes a major flaw discovered with the introduction of decentralized finance and allows miners to perform MEV attacks. In this paper, we address the issue of sandwich attacks by providing a construction that takes as input a blockchain protocol and outputs a new blockchain protocol with the same security but in which sandwich attacks are not profitable. Furthermore, our protocol is fully decentralized with no trusted third parties or heavy cryptography primitives and carries a linear increase in latency and minimum computation overhead.}, author = {Alpos, Orestis and Amores-Sesar, Ignacio and Cachin, Christian and Yeo, Michelle X}, booktitle = {27th International Conference on Principles of Distributed Systems}, isbn = {9783959773089}, issn = {1868-8969}, location = {Tokyo, Japan}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks}}, doi = {10.4230/LIPIcs.OPODIS.2023.12}, volume = {286}, year = {2024}, } @inproceedings{17051, abstract = {Memory-hard functions (MHF) are functions whose evaluation provably requires a lot of memory. While MHFs are an unkeyed primitive, it is natural to consider the notion of trapdoor MHFs (TMHFs). A TMHF is like an MHF, but when sampling the public parameters one also samples a trapdoor which allows evaluating the function much cheaper. Biryukov and Perrin (Asiacrypt’17) were the first to consider TMHFs and put forth a candidate TMHF construction called Diodon that is based on the Scrypt MHF (Percival, BSDCan’09). To allow for a trapdoor, Scrypt’s initial hash chain is replaced by a sequence of squares in a group of unknown order where the order of the group is the trapdoor. For a length n sequence of squares and a group of order N, Diodon’s cumulative memory complexity (CMC) is O(n2log N) without the trapdoor and O(n log(n) log(N)2) with knowledge of it. While Scrypt is proven to be optimally memory-hard in the random oracle model (Alwen et al., Eurocrypt’17), Diodon’s memory-hardness has not been proven so far. In this work, we fill this gap by rigorously analyzing a specific instantiation of Diodon. We show that its CMC is lower bounded by Ω( n2log nlog N) which almost matches the upper bound. Our proof is based Alwen et al.’s lower bound on Scrypt’s CMC but requires non-trivial modifications due to the algebraic structure of Diodon. Most importantly, our analysis involves a more elaborate compression argument and a solvability criterion for certain systems of Diophantine equations.}, author = {Auerbach, Benedikt and Günther, Christoph Ullrich and Pietrzak, Krzysztof Z}, booktitle = {43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques}, isbn = {9783031587337}, issn = {1611-3349}, location = {Zurich, Switzerland}, pages = {315--344}, publisher = {Springer Nature}, title = {{Trapdoor memory-hard functions}}, doi = {10.1007/978-3-031-58734-4_11}, volume = {14653}, year = {2024}, } @article{17283, abstract = {We consider the problems of statically refuting equivalence and similarity of output distributions defined by a pair of probabilistic programs. Equivalence and similarity are two fundamental relational properties of probabilistic programs that are essential for their correctness both in implementation and in compilation. In this work, we present a new method for static equivalence and similarity refutation. Our method refutes equivalence and similarity by computing a function over program outputs whose expected value with respect to the output distributions of two programs is different. The function is computed simultaneously with an upper expectation supermartingale and a lower expectation submartingale for the two programs, which we show to together provide a formal certificate for refuting equivalence and similarity. To the best of our knowledge, our method is the first approach to relational program analysis to offer the combination of the following desirable features: (1) it is fully automated, (2) it is applicable to infinite-state probabilistic programs, and (3) it provides formal guarantees on the correctness of its results. We implement a prototype of our method and our experiments demonstrate the effectiveness of our method to refute equivalence and similarity for a number of examples collected from the literature.}, author = {Chatterjee, Krishnendu and Kafshdar Goharshadi, Ehsan and Novotný, Petr and Zikelic, Dorde}, issn = {2475-1421}, journal = {Proceedings of the ACM on Programming Languages}, publisher = {Association for Computing Machinery}, title = {{Equivalence and similarity refutation for probabilistic programs}}, doi = {10.1145/3656462}, volume = {8}, year = {2024}, } @article{14820, abstract = {We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity on increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+E) . (1+3) for some arbitrary E>0.}, author = {Schmid, Stefan and Svoboda, Jakub and Yeo, Michelle X}, issn = {0304-3975}, journal = {Theoretical Computer Science}, keywords = {General Computer Science, Theoretical Computer Science}, publisher = {Elsevier}, title = {{Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation}}, doi = {10.1016/j.tcs.2023.114353}, volume = {989}, year = {2024}, } @inproceedings{17126, abstract = {Functional encryption (FE) is a primitive where the holder of a master secret key can control which functions a user can evaluate on encrypted data. It is a powerful primitive that even implies indistinguishability obfuscation (iO), given sufficiently compact ciphertexts (Ananth-Jain, CRYPTO’15 and Bitansky-Vaikuntanathan, FOCS’15). However, despite being extensively studied, there are FE schemes, such as function-hiding inner-product FE (Bishop-Jain-Kowalczyk, AC’15, Abdalla-Catalano-Fiore-Gay-Ursu, CRYPTO’18) and compact quadratic FE (Baltico-Catalano-Fiore-Gay, Lin, CRYPTO’17), that can be only realized using pairings. This raises the question if there are some mathematical barriers that hinder us from realizing these FE schemes from other assumptions. In this paper, we study the difficulty of constructing lattice-based compact FE. We generalize the impossibility results of Ünal (EC’20) for lattice-based function-hiding FE, and extend it to the case of compact FE. Concretely, we prove lower bounds for lattice-based compact FE schemes which meet some (natural) algebraic restrictions at encryption and decryption, and have ciphertexts of linear size and secret keys of minimal degree. We see our results as important indications of why it is hard to construct lattice-based FE schemes for new functionalities, and which mathematical barriers have to be overcome.}, author = {Tairi, Erkan and Ünal, Akin}, booktitle = {Advances in Cryptology – EUROCRYPT 2024}, isbn = {9783031587221}, issn = {1611-3349}, location = {Zurich, Switzerland}, pages = {249--279}, publisher = {Springer Nature}, title = {{Lower bounds for lattice-based compact functional encryption}}, doi = {10.1007/978-3-031-58723-8_9}, volume = {14652}, year = {2024}, } @inproceedings{18755, abstract = {A universalthresholdizer (UT), constructed from a threshold fully homomorphic encryption by Boneh et. al , Crypto 2018, is a general framework for universally thresholdizing many cryptographic schemes. However, their framework is insufficient to construct strongly secure threshold schemes, such as threshold signatures and threshold public-key encryption, etc. In this paper, we strengthen the security definition for a universal thresholdizer and propose a scheme which satisfies our stronger security notion. Our UT scheme is an improvement of Boneh et. al ’s construction at the level of threshold fully homomorphic encryption using a key homomorphic pseudorandom function. We apply our strongly secure UT scheme to construct strongly secure threshold signatures and threshold public-key encryption.}, author = {Ebrahimi, Ehsan and Yadav, Anshu}, booktitle = {30th International Conference on the Theory and Application of Cryptology and Information Security}, isbn = {9789819608904}, issn = {1611-3349}, location = {Kolkata, India}, pages = {207--239}, publisher = {Springer Nature}, title = {{Strongly secure universal thresholdizer}}, doi = {10.1007/978-981-96-0891-1_7}, volume = {15486}, year = {2024}, } @inproceedings{18974, abstract = {Reinforcement Learning (RL) from temporal logical specifications is a fundamental problem in sequential decision making. One of the basic and core such specification is the reachability specification that requires a target set to be eventually visited. Despite strong empirical results for RL from such specifications, the theoretical guarantees are bleak, including the impossibility of Probably Approximately Correct (PAC) guarantee for reachability specifications. Given the impossibility result, in this work we consider the problem of RL from reachability specifications along with the information of expected conditional distance (ECD). We present (a) lower bound results which establish the necessity of ECD information for PAC guarantees and (b) an algorithm that establishes PAC-guarantees given the ECD information. To the best of our knowledge, this is the first RL from reachability specifications that does not make any assumptions on the underlying environment to learn policies.}, author = {Svoboda, Jakub and Bansal, Suguman and Chatterjee, Krishnendu}, booktitle = {41st International Conference on Machine Learning}, location = {Vienna, Austria}, pages = {47331--47344}, publisher = {ML Research Press}, title = {{Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance}}, volume = {235}, year = {2024}, } @phdthesis{18088, abstract = {Instant messaging applications like Whatsapp, Signal or Telegram have become ubiquitous in today's society. Many of them provide not only end-to-end encryption, but also security guarantees even when the key material gets compromised. These are achieved through frequent key update performed by users. In particular, the compromise of a group key should preserve confidentiality of previously exchanged messages (forward secrecy), and a subsequent key update will ensure security for future ones (post-compromise security). Though great protocols for one-on-one communication have been known for some time, the design of ones that scale efficiently for larger groups while achieving akin security guarantees is a hard problem. A great deal of research has been aimed at this topic, much of it under the umbrella of the Messaging Layer Security (MLS) working group at the IETF. Started in 2018, this joint effort by academics and industry culminated in 2023 with the publication of the first standard for secure group messaging [IETF, RFC9420]. At the core of secure group messaging is a cryptographic primitive termed Continuous Group Key Agreement, or CGKA [Alwen et al. 2021], that essentially allows a changing group of users to agree on a common key with the added functionality security against compromises is achieved by users asynchronously issuing a key update. In this thesis we contribute to the understanding of CGKA across different angles. First, we present a new technique to effect dynamic operations in groups, i.e., add or remove members, that can be more efficient that the one employed by MLS in certain settings. Considering the setting of users belonging to multiple overlapping groups, we then show lowerbounds on the communication cost of constructions that leverage said overlap, at the same time showing protocols that are asymptotically optimal and efficient for practical settings, respectively. Along the way, we show that the communication cost of key updates in MLS is average-cost optimal. An important feature in CGKA protocols, particularly for big groups, is the possibility of executing several group operations concurrently. While later versions of MLS support this, they do at the cost of worsening the communication efficiency of future group operations. In this thesis we introduce two new protocols that permit concurrency without any negative effect on efficiency. Our protocols circumvent previously existing lower bounds by satisfying a new notion of post-compromise security that only asks for security to be re-established after a certain number of key updates have taken place. While this can be slower than MLS in terms of rounds of communication, we show that it leads to more efficient overall communication. Additionally, we introduce a new technique that allows group members to decrease the information they need to store and download, which makes one of our protocols enjoy much lower download cost than any other existing CGKA constructions. }, author = {Pascual Perez, Guillermo}, issn = {2663-337X}, pages = {239}, publisher = {Institute of Science and Technology Austria}, title = {{On the efficiency and security of secure group messaging}}, doi = {10.15479/at:ista:18088}, year = {2024}, } @inproceedings{18086, abstract = {Abstract. Continuous group key agreement (CGKA) allows a group of users to maintain a continuously updated shared key in an asynchronous setting where parties only come online sporadically and their messages are relayed by an untrusted server. CGKA captures the basic primitive underlying group messaging schemes. Current solutions including TreeKEM (“Messaging Layer Security” (MLS) IETF RFC 9420) cannot handle concurrent requests while retaining low communication complexity. The exception being CoCoA, which is concurrent while having extremely low communication complexity (in groups of size n and for m concurrent updates the communication per user is log(n), i.e., independent of m). The main downside of CoCoA is that in groups of size n, users might have to do up to log(n) update requests to the server to ensure their (potentially corrupted) key material has been refreshed. In this work we present a “fast healing” concurrent CGKA protocol, named DeCAF, where users will heal after at most log(t) requests, with t being the number of corrupted users. While also suitable for the standard central-server setting, our protocol is particularly interesting for realizing decentralized group messaging, where protocol messages (add, remove, update) are being posted on some append-only data structure rather than sent to a server. In this setting, concurrency is crucial once the rate of requests exceeds, say, the rate at which new blocks are added to a blockchain. In the central-server setting, CoCoA (the only alternative with concurrency, sub-linear communication and basic post-compromise security) enjoys much lower download communication. However, in the decentralized setting – where there is no server which can craft specific messages for different users to reduce their download communication – our protocol significantly outperforms CoCoA. DeCAF heals in fewer epochs (log(t) vs. log(n)) while incurring a similar per epoch per user communication cost.}, author = {Alwen, Joel F and Auerbach, Benedikt and Cueto Noval, Miguel and Klein, Karen and Pascual Perez, Guillermo and Pietrzak, Krzysztof Z}, booktitle = {Security and Cryptography for Networks: 14th International Conference}, editor = {Galdi, Clemente and Phan, Duong Hieu}, isbn = {9783031710728}, issn = {1611-3349}, location = {Amalfi, Italy}, pages = {294–313}, publisher = {Springer Nature}, title = {{DeCAF: Decentralizable CGKA with fast healing}}, doi = {10.1007/978-3-031-71073-5_14}, volume = {14974}, year = {2024}, } @article{18961, abstract = {Automated contact tracing (ACT) emerged as a promising measure to curb the spread of Covid-19. Users enable ACT on their smartphones to automatically record contacts with other users. If a user tests positive for the disease, they report their diagnosis to alert their contacts. Designing effective ACT protocols is challenging since they need to be efficient and secure while also ensuring users' privacy. As ACT protocols necessarily leak some information by design, defining privacy is difficult. For example, a user cannot deny having met another user. Ideally, however, the user can plausibly deny everything else, in particular, when they met. We call this privacy property contact-time deniability. While some early works discussed contact-time deniability informally, it has received little attention since then. We investigate deniability from a rigorous, theoretical point of view and arrive at the following impossibility result: A decentralized protocol with unidirectional communication cannot be contact-time deniable and replay-secure. This holds even if malicious users treat smartphones as black-boxes. Unidirectional protocols are usually very efficient and many proposals are unidirectional, e.g., the widely-deployed Google-Apple Exposure Notifications. So the impossibility result considerably constrains the design space of efficient, secure, and private ACT protocols. However, it can also be used as a guide; we discuss several possibilities to achieve contact-time deniability in practice.}, author = {Günther, Christoph Ullrich and Pietrzak, Krzysztof Z}, issn = {2299-0984}, journal = {Proceedings on Privacy Enhancing Technologies}, location = {Bristol, UK/Virtual}, number = {4}, pages = {636--648}, publisher = {Privacy Enhancing Technologies Symposium Advisory Board}, title = {{Deniability in automated contact tracing: Impossibilities and possibilities}}, doi = {10.56553/popets-2024-0134}, volume = {2024}, year = {2024}, } @article{18554, abstract = {We prove the Eigenstate Thermalization Hypothesis for general Wigner-type matrices in the bulk of the self-consistent spectrum, with optimal control on the fluctuations for obs ervables of arbitrary rank. As the main technical ingredient, we prove rank-uniform optimal local laws for one and two resolvents of a Wigner-type matrix with regular observables. Our results hold under very general conditions on the variance profile, even allowing many vanishing entries, demonstrating that Eigenstate Thermalization occurs robustly across a diverse class of random matrix ensembles, for which the underlying quantum system has a non-trivial spatial structure.}, author = {Erdös, László and Riabov, Volodymyr}, issn = {1432-0916}, journal = {Communications in Mathematical Physics}, number = {12}, publisher = {Springer Nature}, title = {{Eigenstate Thermalization Hypothesis for Wigner-type matrices}}, doi = {10.1007/s00220-024-05143-y}, volume = {405}, year = {2024}, } @article{13975, abstract = {We consider the spectrum of random Laplacian matrices of the form Ln=An−Dn where An is a real symmetric random matrix and Dn is a diagonal matrix whose entries are equal to the corresponding row sums of An. If An is a Wigner matrix with entries in the domain of attraction of a Gaussian distribution, the empirical spectral measure of Ln is known to converge to the free convolution of a semicircle distribution and a standard real Gaussian distribution. We consider real symmetric random matrices An with independent entries (up to symmetry) whose row sums converge to a purely non-Gaussian infinitely divisible distribution, which fall into the class of Lévy–Khintchine random matrices first introduced by Jung [Trans Am Math Soc, 370, (2018)]. Our main result shows that the empirical spectral measure of Ln converges almost surely to a deterministic limit. A key step in the proof is to use the purely non-Gaussian nature of the row sums to build a random operator to which Ln converges in an appropriate sense. This operator leads to a recursive distributional equation uniquely describing the Stieltjes transform of the limiting empirical spectral measure.}, author = {Campbell, Andrew J and O’Rourke, Sean}, issn = {1572-9230}, journal = {Journal of Theoretical Probability}, pages = {933--973}, publisher = {Springer Nature}, title = {{Spectrum of Lévy–Khintchine random laplacian matrices}}, doi = {10.1007/s10959-023-01275-4}, volume = {37}, year = {2024}, } @article{17281, abstract = {We extend the free convolution of Brown measures of R-diagonal elements introduced by Kösters and Tikhomirov [ 28] to fractional powers. We then show how this fractional free convolution arises naturally when studying the roots of random polynomials with independent coefficients under repeated differentiation. When the proportion of derivatives to the degree approaches one, we establish central limit theorem-type behavior and discuss stable distributions.}, author = {Campbell, Andrew J and O'Rourke, Sean and Renfrew, David T}, issn = {1687-0247}, journal = {International Mathematics Research Notices}, number = {13}, pages = {10189--10218}, publisher = {Oxford University Press}, title = {{The fractional free convolution of R-diagonal elements and random polynomials under repeated differentiation}}, doi = {10.1093/imrn/rnae062}, volume = {2024}, year = {2024}, } @article{14408, abstract = {We prove that the mesoscopic linear statistics ∑if(na(σi−z0)) of the eigenvalues {σi}i of large n×n non-Hermitian random matrices with complex centred i.i.d. entries are asymptotically Gaussian for any H20-functions f around any point z0 in the bulk of the spectrum on any mesoscopic scale 0