1,720,981 research outputs found
Universal secret-key and public-key encryption using combiners
No full text25 pagesWe construct universal secret-key and public-key encryption schemes using combiners, in the style of Levin’s universal one-way function. Given a finite list of candidate encryption schemes, our combiners produce a single scheme that is correct and semantically secure if and only if at least one of the input schemes satisfies these properties. Our constructions are efficient and require no assumptions beyond the existence of such a secure scheme within the list. We develop and analyze these combiners for both the secret-key and public-key settings, establishing correctness and many-message semantic security. We show that if there exists any encryption scheme that is efficiently computable and semantically secure, then the output of our combiner is also secure and efficient. By enumerating all possible polynomial-time encryption schemes and applying our construction, we obtain universal encryption schemes which are secure if and only if any such scheme exists
ADAPTIVE BOUNDS FOR INTERACTIVE LEARNING AND RELAXING THE REALIZABILITY ASSUMPTION
No full text32 pagesCharacterizing the learnability of interactive learning has posed to be a challenge for the longest time. It was not untill recently that a unifying theory of interactive learning was presented, where it was shown a single quantity is both necessary and sufficient for sample-efficient learning. However, learnability results for this setting rely on overly optimistic assumptions about the hypothesis class and simultaneously are not model-dependent. The focus of this dissertation is to address both these issues. In the first half of the dissertation, we attempt to understand how to adapt the model-independent results to characterize learnability for interactive learning in a way which adapts to the problem instance. Then, in the second half of the dissertation, we first work towards understanding the necessity of the assumption used to prove these learnability results and then try to relax these assumptions and find more practical alternatives that still provide us with similar information and guarantees. The work in this dissertation can be seen as progress in developing theoretical guarantees that have practical implications in algorithm choice and design for interactive learning and classification.2026-09-0
Towards Expressive and Robust Learning with Hyperbolic Geometry
No full text293 pagesMachine learning models traditionally operate within the confines of Euclidean space, assuming the Euclidean nature of data. However, there is a growing interest in learning within non-Euclidean hyperbolic space, particularly in scenarios where data exhibits explicit or implicit hierarchies, such as in natural languages (with taxonomies and lexical entailment) or in tree-like and graphical data (as seen in biological and social networks). Embracing the geometry of the data not only leads to more expressive models but also offers deeper insights into the underlying mechanisms governing complex datasets. An important foundation of machine learning lies in representing data as continuous values, a process known as embedding. Recent studies have demonstrated both theoretically and empirically that hyperbolic space can embed hierarchical data with lower dimensionality compared to Euclidean space. This insight has spurred the development of various hyperbolic networks, despite the challenge that hyperbolic space is not a vector space. To address this, we propose an end-to-end approach that adopts hyperbolic geometry from a manifold perspective. This approach includes an embedding framework that directly encodes data hierarchies, a method for hyperbolic-isometries-aware learning, and a demonstration of how our framework can enhance the performance of attention models, such as transformers, by capturing implicit hierarchies. While hyperbolic geometry offers theoretical advantages, its practical implementation faces challenges due to numerical errors stemming from floating-point computations, further exacerbated by the ill-conditioned hyperbolic metrics. This issue, often referred to as the ``NaN'' problem, arises when practitioners encounter Not-a-Number while running hyperbolic models. To address this, we introduce several robust and accurate representations using integer-based tilings and multi-component floating-point methods, which offer provably bounded numerical errors for the first time. Additionally, we present MCTensor, a PyTorch library that enables general-purpose and high-precision training of machine learning models. We demonstrate the effectiveness of our approach by applying multi-component floating-point to train large language models at low precision, mitigating the issue of reduced numerical accuracy and producing models of better performances. In conclusion, our work aims to empower individuals and organizations to leverage the potential of hyperbolic geometry in machine learning, drawing a broad audience towards this promising and evolving research direction
New Algorithms and Reductions for Hard Cryptographic Problems
No full text260 pagesConjectured hard problems are central to modern cryptography and thus to the security of the networked infrastructure on which modern society is built.We investigate the precise hardness of several such problems. In Chapter 1, we study preprocessing attacks aimed at the on-line inversion of arbitrary cryptographic functions. Thirty years ago, Fiat and Naor showed [FN91] that any function f: [N] ->[N] could be inverted in time essentially T using a preprocessed data structure of size S, so long as T S^3 >= O~(N^3). We present the first improvement to this result, showing how to improve the tradeoff curve in the important case S = O~(N^3). with the caveat that the on-line inversion procedure still requires S bits of temporary memory. We additionally give the first non-trivial non-adaptive algorithm for function inversion, show that it is optimal among a restricted class of non-adaptive algorithms, and present several equivalence results relating different versions of the function-inversion problem. In the remainder, we turn our attention to \emph{lattice problems}. Conjectured hard lattice problems form the basis for three of the four post-quantum secure cryptographic protocols selected by NIST in 2022 [NIS22a], and two of the three finalized in 2024 [NIS24]. Lattice problems are also the only widely accepted and reasonably practical foundation on which several advanced cryptographic functionalities, most notably fully homomorphic encryption (FHE), can be based. The best known attacks on conjectured hard lattice problems, first, run in nearly exponential time in the lattice dimension n, and second, make essential use of a family of techniques referred to as basis reduction algorithms. Regarding the first point, it is widely assumed by practitioners that such exponential-time attacks are best possible [APS15, ACD+18]. But from a theoretical perspective, the implications of this strengthened hardness assumption were largely unexplored. In Chapter 2, we study these implications. In particular, we show how to modify various important lattice algorithms, protocols, and reductions to make use of small-exponential running time. And, we show that both private- and public-key lattice-based cryptography exists assuming that lattice problems are hard to approximate to within smaller polynomial factors than previously known, when "hard" is meant relative to adversaries running in small-exponential time in addition to those running in polynomial time. Finally, in Chapter 3, we show an algorithmic framework for solving the same approximate lattice problems solved by basis reduction algorithms. More specifically, our framework solves the y-approximate Hermite shortest vector problem (y-HSVP), a central problem for attacks on lattice-based cryptography, with the same asymptotic running time (as a function of y) as basis reduction algorithms. The description and analysis of our framework are quite simple---considerably simpler, we feel, than the description and analysis of comparable basis reduction algorithms such as BKZ reduction. Our framework is also flexible, which we demonstrate by using it to improve on the best known algorithms for the Dense Sublattice Problem (a generalization of HSVP to sublattices of rank k >= 1) in the regime where k is large relative to the runtime budget
Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One
Full text linkWe show the first dimension-preserving search-to-decision reductions for approximate SVP and CVP. In particular, for any gamma <= 1 + O(log n/n), we obtain an efficient dimension-preserving reduction from gamma^{O(n/log n)}-SVP to gamma-GapSVP and an efficient dimension-preserving reduction from gamma^{O(n)}-CVP to gamma-GapCVP. These results generalize the known equivalences of the search and decision versions of these problems in the exact case when gamma = 1. For SVP, we actually obtain something slightly stronger than a search-to-decision reduction - we reduce gamma^{O(n/log n)}-SVP to gamma-unique SVP, a potentially easier problem than gamma-GapSVP
A Time-Distance Trade-Off for GDD with Preprocessing - Instantiating the DLW Heuristic
Full text linkFor 0 <= alpha <= 1/2, we show an algorithm that does the following. Given appropriate preprocessing P(L) consisting of N_alpha := 2^{O(n^{1-2 alpha} + log n)} vectors in some lattice L subset {R}^n and a target vector t in R^n, the algorithm finds y in L such that ||y-t|| <= n^{1/2 + alpha} eta(L) in time poly(n) * N_alpha, where eta(L) is the smoothing parameter of the lattice.
The algorithm itself is very simple and was originally studied by Doulgerakis, Laarhoven, and de Weger (to appear in PQCrypto, 2019), who proved its correctness under certain reasonable heuristic assumptions on the preprocessing P(L) and target t. Our primary contribution is a choice of preprocessing that allows us to prove correctness without any heuristic assumptions.
Our main motivation for studying this is the recent breakthrough algorithm for IdealSVP due to Hanrot, Pellet - Mary, and Stehlé (to appear in Eurocrypt, 2019), which uses the DLW algorithm as a key subprocedure. In particular, our result implies that the HPS IdealSVP algorithm can be made to work with fewer heuristic assumptions.
Our only technical tool is the discrete Gaussian distribution over L, and in particular, a lemma showing that the one-dimensional projections of this distribution behave very similarly to the continuous Gaussian. This lemma might be of independent interest
More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more
Full text linkWe expand on recent exciting work of Debris-Alazard, Ducas, and van Woerden [Transactions on Information Theory, 2022], which introduced the notion of basis reduction for codes, in analogy with the extremely successful paradigm of basis reduction for lattices. We generalize DDvW\u27s LLL algorithm and size-reduction algorithm from codes over to codes over , and we further develop the theory of proper bases. We then show how to instantiate for codes the BKZ and slide-reduction algorithms, which are the two most important generalizations of the LLL algorithm for lattices.
Perhaps most importantly, we show a new and very efficient basis-reduction algorithm for codes, called full backward reduction. This algorithm is quite specific to codes and seems to have no analogue in the lattice setting. We prove that this algorithm finds vectors as short as LLL does in the worst case (i.e., within the Griesmer bound) and does so in less time. We also provide both heuristic and empirical evidence that it outperforms LLL in practice, and we give a variant of the algorithm that provably outperforms LLL (in some sense) for random codes.
Finally, we explore the promise and limitations of basis reduction for codes. In particular, we show upper and lower bounds on how ``good\u27\u27 of a basis a code can have, and we show two additional illustrative algorithms that demonstrate some of the promise and the limitations of basis reduction for codes
More Basis Reduction for Linear Codes: Backward Reduction, BKZ, Slide Reduction, and More
Full text linkWe expand on recent exciting work of Debris-Alazard, Ducas, and van Woerden [Transactions on Information Theory, 2022], which introduced the notion of basis reduction for codes, in analogy with the extremely successful paradigm of basis reduction for lattices. We generalize DDvW’s LLL algorithm and size-reduction algorithm from codes over ₂ to codes over _q, and we further develop the theory of proper bases. We then show how to instantiate for codes the BKZ and slide-reduction algorithms, which are the two most important generalizations of the LLL algorithm for lattices.
Perhaps most importantly, we show a new and very efficient basis-reduction algorithm for codes, called full backward reduction. This algorithm is quite specific to codes and seems to have no analogue in the lattice setting. We prove that this algorithm finds vectors as short as LLL does in the worst case (i.e., within the Griesmer bound) and does so in less time. We also provide both heuristic and empirical evidence that it outperforms LLL in practice, and we give a variant of the algorithm that provably outperforms LLL (in some sense) for random codes.
Finally, we explore the promise and limitations of basis reduction for codes. In particular, we show upper and lower bounds on how "good" of a basis a code can have, and we show two additional illustrative algorithms that demonstrate some of the promise and the limitations of basis reduction for codes
A Reverse Minkowski Theorem
Full text link \newcommand{\R}{\mathbb{R}} \newcommand{\lat}{\mathcal{L}} We prove a
conjecture due to Dadush, showing that if \lat \subset \R^n is a lattice such
that \det(\lat') \ge 1 for all sublattices \lat' \subseteq \lat, then
\sum_{\vec y \in \lat} e^{-\pi t^2 \|\vec y\|^2} \le 3/2 \; , where . From this we derive bounds on the number of short lattice
vectors, which can be viewed as a partial converse to Minkowski's celebrated
first theorem. We also derive a bound on the covering radius
- …
