The Complexity of Public-Key Cryptography
From MaRDI portal
Publication:5021130
DOI10.1007/978-3-319-57048-8_2OpenAlexW2620689936MaRDI QIDQ5021130FDOQ5021130
Authors: Boaz Barak 
Publication date: 12 January 2022
Published in: Tutorials on the Foundations of Cryptography (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-57048-8_2
Recommendations
- scientific article; zbMATH DE number 3846870
- Complexity Measures for Public-Key Cryptosystems
- scientific article; zbMATH DE number 4106765
- Complexity and Cryptography
- scientific article; zbMATH DE number 2066371
- Cryptology and complexity theories
- Kolmogorov complexity and cryptography
- Complexity theoretic aspects of some cryptographic functions
- Some Perspectives on Complexity-Based Cryptography
- Public key cryptography and coding theory
Cites Work
- Title not available (Why is that?)
- Fully homomorphic encryption over the integers
- Fully homomorphic encryption using ideal lattices
- Public-key cryptosystems from the worst-case shortest vector problem
- Efficient Fully Homomorphic Encryption from (Standard) LWE
- On lattices, learning with errors, random linear codes, and cryptography
- Hiding cliques for cryptographic security
- A method for obtaining digital signatures and public-key cryptosystems
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Expander graphs and their applications
- New directions in cryptography
- Title not available (Why is that?)
- A Pseudorandom Generator from any One-way Function
- Title not available (Why is that?)
- Sum-of-squares proofs and the quest toward optimal algorithms
- Bit commitment using pseudorandomness
- A subexponential algorithm for discrete logarithms over hyperelliptic curves of large genus over \(\text{GF}(q)\)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Elliptic Curve Cryptosystems
- Title not available (Why is that?)
- Foundations of Cryptography
- Title not available (Why is that?)
- Inverse Problem Theory and Methods for Model Parameter Estimation
- Foundations of Cryptography
- Title not available (Why is that?)
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Classical hardness of learning with errors
- Length Based Attack and Braid Groups: Cryptanalysis of Anshel-Anshel-Goldfeld Key Exchange Protocol
- Secure communications over insecure channels
- Merkle Puzzles Are Optimal — An O(n2)-Query Attack on Any Key Exchange from a Random Oracle
- A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm
- Large Cliques Elude the Metropolis Process
- On colouring random graphs
- Cliques in random graphs
- Quantum Computation and Lattice Problems
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- On total functions, existence theorems and computational complexity
- Public-key cryptography from different assumptions
- Candidate one-way functions based on expander graphs
- Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
- Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
- Title not available (Why is that?)
- Sharp thresholds of graph properties, and the $k$-sat problem
- On the Existence of Pseudorandom Generators
- On the security of Goldreich's one-way function
- Noise-tolerant learning, the parity problem, and the statistical query model
- Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms
- Title not available (Why is that?)
- Candidate indistinguishability obfuscation and functional encryption for all circuits
- On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
- How to use indistinguishability obfuscation
- Hiding information and signatures in trapdoor knapsacks
- Constructing elliptic curve isogenies in quantum subexponential time
- Average Case Complete Problems
- Expected complexity of graph partitioning problems
- Lattice problems in NP ∩ coNP
- Title not available (Why is that?)
- Title not available (Why is that?)
- More on average case vs approximation complexity
- Discrete logarithms in \(\mathrm{GF}(p)\)
- New lattice based cryptographic constructions
- Pseudorandom generators with long stretch and low locality from random local one-way functions
- On the (im)possibility of obfuscating programs
- Simple permutations mix well
- Bonsai trees, or how to delegate a lattice basis
- Lossy Trapdoor Functions and Their Applications
- A decade of lattice cryptography
- How (not) to instantiate ring-LWE
- Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13
- A quantum algorithm for computing isogenies between supersingular elliptic curves
- Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity
- Limits on the power of indistinguishability obfuscation and functional encryption
- Cryptographic hardness of random local functions -- survey
- Breaking the sub-exponential barrier in obfustopia
- Recovering short generators of principal ideals in cyclotomic rings
- Substitution-permutation networks, pseudorandom functions, and natural proofs
- On the Security of HFE, HFEv- and Quartz
- Basing Weak Public-Key Cryptography on Strong One-Way Functions
- An Almost m-wise Independent Random Permutation of the Cube
- On public key encryption from noisy codewords
- Contemplations on Testing Graph Properties
- Title not available (Why is that?)
- Structure vs combinatorics in computational complexity
Cited In (17)
- Implementation of RSA cryptographic algorithm using SN P systems based on HP/LP neurons
- Public-key cryptography from different assumptions
- Complexity Measures for Public-Key Cryptosystems
- The combinatorial complexity of masterkeying
- Title not available (Why is that?)
- Minicrypt primitives with algebraic structure and applications
- Cryptographic assumptions: a position paper
- Advances in Cryptology - CRYPTO 2003
- Title not available (Why is that?)
- Multiparty noninteractive key exchange from ring key-homomorphic weak PRFs
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Public keys
- From laconic zero-knowledge to public-key cryptography. Extended abstract
- Title not available (Why is that?)
- On the impossibility of key agreements from quantum random oracles
- Distributed Merkle's puzzles
- The complexity of certain multi-exponentiation techniques in cryptography
Uses Software
This page was built for publication: The Complexity of Public-Key Cryptography
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5021130)
