A5023640008- Cryptography and Data Security
- Complexity and Algorithms in Graphs
- Coding theory and cryptography
- Cryptographic Implementations and Security
- Chaos-based Image/Signal Encryption
- Privacy-Preserving Technologies in Data
- Cryptography and Residue Arithmetic
- Advanced Authentication Protocols Security
- semigroups and automata theory
- Computability, Logic, AI Algorithms
- graph theory and CDMA systems
- Security in Wireless Sensor Networks
- Optimization and Search Problems
- Internet Traffic Analysis and Secure E-voting
- Machine Learning and Algorithms
- Digital Image Processing Techniques
- Advanced Steganography and Watermarking Techniques
- Cooperative Communication and Network Coding
- Cloud Data Security Solutions
- Logic, programming, and type systems
- Distributed systems and fault tolerance
- Security and Verification in Computing
- User Authentication and Security Systems
- Advanced Algebra and Logic
- Geometric and Algebraic Topology
UC San Diego Health System
2011-2025
University of California, San Diego
2015-2024
Duality (United States)
2021-2023
Meta (United States)
2021
Menlo School
2021
University of California System
2002-2017
University of California, San Francisco
2010
University of California, Los Angeles
2008
Alfred P. Sloan Foundation
2007
Massachusetts Institute of Technology
1997-2003
We show that finding small solutions to random modular linear equations is at least as hard approximating several lattice problems in the worst case within a factor almost dimension of lattice. The we consider are shortest vector problem, independent vectors covering radius and guaranteed distance decoding problem (a variant well‐known closest problem). approximation obtain $n \log^{O(1)} n$ for all four problems. This greatly improves on previous work subject starting from Ajtai’s seminal...
Multicast communication is becoming the basis for a growing number of applications. It therefore critical to provide sound security mechanisms multicast communication. Yet, existing protocols offer only partial solutions. We first present taxonomy scenarios on Internet and point out relevant concerns. Next we address two major problems communication: source authentication, key revocation. Maintaining authenticity in much more complex problem than unicast; particular, known solutions are...
Fully Homomorphic Encryption (FHE) is a powerful cryptographic primitive that enables performing computations over encrypted data without having access to the secret key. We introduce OpenFHE, new open-source FHE software library incorporates selected design ideas from prior projects, such as PALISADE, HElib, and HEAAN, includes several concepts ideas. The main features can be summarized follows: (1) we assume very beginning all implemented schemes will support bootstrapping scheme...
We show that solving modular linear equation on the average is at least as hard approximating several lattice problems in worst case within a factor almost rank of lattice. The we consider are shortest vector problem, independent vectors problem and covering radius problem. approximation obtain O(n) for all three problems. This greatly improves previous work subject starting from Ajtai's seminal paper (STOC, 1996), up to strongest previously known results by Micciancio 2002). Our also bring...
We investigate the average-case complexity of a generalization compact knapsack problem to arbitrary rings: given m (random) ring elements 1,..., ∈ R and target value b R, find coefficients x 1, ..., S (where is an appropriately chosen subset R) such that ∑ i · = b. consider versions generalized where set large number weights small. Most variants this considered in past (e.g., when $$R={\mathbb{Z}}$$ integers) can be easily solved polynomial time even worst case. propose new choice yields...
We give deterministic ~O(22n+o(n))-time algorithms to solve all the most important computational problems on point lattices in NP, including Shortest Vector Problem (SVP), Closest (CVP), and Independent Vectors (SIVP). This improves nO(n) running time of best previously known for CVP (Kannan, Math. Operation Research 12(3):415--440, 1987) SIVP (Micciancio, Proc. SODA, 2008), gives a asymptotically faster alternative 2O(n)-time (and space) randomized algorithm SVP (Ajtai, Kumar Sivakumar,...
We give a new simple proof of the NP-hardness closest vector problem. In addition to being much simpler than all previously known proofs, yields interesting results about complexity problem with preprocessing. This is variant in which lattice specified advance, and can be preprocessed for an arbitrarily long amount time before target revealed. show that there are lattices remains hard, regardless
We show that approximating the shortest vector problem (in any $\ell_p$ norm) to within constant factor less than $\sqrt[p]2$ is hard for NP under reverse unfaithful random reductions with inverse polynomial error probability. In particular, not in RP (random time), unless equals RP. also prove a proper NP-hardness result (i.e., hardness deterministic many-one reductions) reasonable number theoretic conjecture on distribution of square-free smooth numbers. As part our proof, we give an...