Efficient cryptographic schemes provably as secure as subset sum

No abstract is available for this paper.

• Publication year

  1989

• Venue

  30th Annual Symposium on Foundations of Computer Science

• Publication date

  1989-10-30

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/BF00189260
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Lattice basis reduction: Improved practical algorithms and solving subset sum problems

  1991cited by this paper
• Improving the Critical Density of the Lagarias-Odlyzko Attack Against Subset Sum Problems

  1991cited by this paper
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem

  1991cited by this paper
• An Improved Low-Denisty Subset Sum Algorithm

  1991influential reference
• One-way functions are necessary and sufficient for secure signatures

  1990cited by this paper
• Pseudo-random generators under uniform assumptions

  1990cited by this paper
• A hard-core predicate for all one-way functions

  1989influential reference
• How to recycle random bits

  1989cited by this paper
• Constant depth circuits, Fourier transform, and learnability

  1989cited by this paper
• Universal one-way hash functions and their cryptographic applications

  1989cited by this paper
• Pseudo-random generation from one-way functions

  1989cited by this paper
• Succinct Certificates for Almost All Subset Sum Problems

  1989cited by this paper
• Efficient, Perfect Random Number Generators

  1988cited by this paper
• On the existence of pseudorandom generators

  1988influential reference
• Minimum Disclosure Proofs of Knowledge

  1988influential reference
• A knapsack-type public key cryptosystem based on arithmetic in finite fields

  1988cited by this paper
• Random Oracles Separate PSPACE from the Polynomial-Time Hierarchy

  1987cited by this paper
• On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem

  1986cited by this paper
• A Simple Unpredictable Pseudo-Random Number Generator

  1986cited by this paper
• How to construct random functions

  1986influential reference
• One-Way Functions and Circuit Complexity

  1986cited by this paper
• Proofs that yield nothing but their validity and a methodology of cryptographic protocol design

  1986cited by this paper
• Almost optimal lower bounds for small depth circuits

  1986cited by this paper
• How to Construct Pseudo-Random Permutations from Pseudo-Random Functions (Abstract)

  1986cited by this paper
• Separating the polynomial-time hierarchy by oracles

  1985cited by this paper
• Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract)

  1984influential reference
• A Knapsack Type Public Key Cryptosystem Based On Arithmetic in Finite Fields

  1984cited by this paper
• Probabilistic Encryption

  1984cited by this paper
• Coin flipping by telephone

  1984cited by this paper
• ∑11-Formulae on finite structures

  1983cited by this paper
• Solving low density subset sum problems

  1983influential reference
• Coin flipping by telephone a protocol for solving impossible problems

  1983cited by this paper
• Solving Low Density Knapsacks

  1983influential reference
• Theory and Applications of Trapdoor Functions (Extended Abstract)

  1982cited by this paper
• Factoring polynomials with rational coefficients

  1982cited by this paper
• How to generate cryptographically strong sequences of pseudo random bits

  1982cited by this paper
• Theory and application of trapdoor functions

  1982cited by this paper
• Parity, circuits, and the polynomial-time hierarchy

  1981cited by this paper
• Universal Classes of Hash Functions

  1979cited by this paper
• A TcS2 = 0 (2n) time/space tradeoff for certain NP-complete problems

  1979cited by this paper
• Hiding information and signatures in trapdoor knapsacks

  1978cited by this paper
• Reducibility among combinatorial problems" in complexity of computer computations

  1972cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper

• Fog-Assisted Composite Attribute-Based Encryption for Secure Personal Health Data Sharing

  2026cites this paper
• Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space

  2025cites this paper
• Self-masking for hardening inversions

  2025cites this paper
• Public-Key Encryption from the MinRank Problem

  2025cites this paper
• From Subset-Sum to Decoding: Improved Classical and Quantum Algorithms via Ternary Representation Technique

  2025cites this paper
• “Check-Before-you-Solve”: Verifiable Time-Lock Puzzles

  2025cites this paper
• NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions

  2025cites this paper
• Optimizing Proof of Aliveness in Cyber-Physical Systems

  2024cites this paper
• Post Quantum Lightweight OWF Candidates - Based on Theoretically Secure Primitives: Xors, Error Detection Codes, Permutations, Polynomials, Interaction, and Nesting (Short Version)

  2024cites this paper
• Improved Space Bounds for Subset Sum

  2024cites this paper
• Locality Bounds for Sampling Hamming Slices

  2024cites this paper
• Does Subset Sum Admit Short Proofs?

  2024cites this paper
• Slalom at the Carnival: Privacy-preserving Inference with Masks from Public Knowledge

  2024cites this paper
• OWF Candidates Based on: Xors, Error Detection Codes, Permutations, Polynomials, Interaction and Nesting

  2023cites this paper
• Injective Rank Metric Trapdoor Functions with Homogeneous Errors

  2023cites this paper
• DiStefano: Decentralized Infrastructure for Sharing Trusted Encrypted Facts and Nothing More

  2023cites this paper
• Single Instance Self-Masking via Permutations

  2023cites this paper
• Sampling and Certifying Symmetric Functions

  2023cites this paper
• Commitments with Efficient Zero-Knowledge Arguments from Subset Sum Problems

  2023cites this paper
• No Polynomial Kernels for Knapsack

  2023cites this paper
• Fixed points of the subset sum pseudorandom number generators

  2023cites this paper
• Subset-optimized BLS Multi-signature with Key Aggregation

  2023cites this paper
• Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness

  2023cites this paper
• Programmable Distributed Point Functions

  2022cites this paper
• Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection

  2022cites this paper
• Tackling A Class of Hard Subset-Sum Problems: Integration of Lattice Attacks with Disaggregation Techniques

  2022cites this paper
• Bottom-up Trust Registry in Self Sovereign Identity

  2022cites this paper
• GCKSign: Simple and Efficient Signatures from Generalized Compact Knapsacks

  2022cites this paper
• On one-way functions from NP-complete problems

  2022cites this paper
• Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

  2021cites this paper
• Small Superset and Big Subset Obfuscation

  2021cites this paper
• On Treewidth, Separators and Yao's Garbling

  2021cites this paper
• A comprehensive review on collision-resistant hash functions on lattices

  2021cites this paper
• The Space Complexity of Sampling

  2021cites this paper
• PLCrypto: A Symmetric Cryptographic Library for Programmable Logic Controllers

  2021cites this paper
• One-Way Functions and a Conditional Variant of MKTP

  2021cites this paper
• Number Partitioning with Grover's Algorithm in Central Spin Systems

  2020cites this paper
• Multiparty Generation of an RSA Modulus

  2020cites this paper
• Succinctly Reconstructed Distributed Signatures and Balanced Byzantine Agreement

  2020cites this paper
• Solving subset sum with small space – Handling cryptanalytic Big Data

  2020cites this paper
• Big Subset and Small Superset Obfuscation

  2020cites this paper
• On subset sums of pseudo–recursive sequences∗

  2020cites this paper
• Sampling lower bounds: boolean average-case and permutations

  2020cites this paper
• Lattice signatures using NTRU on the hardness of worst-case ideal lattice problems

  2020cites this paper
• Breaking the $O(\sqrt n)$-Bits Barrier: Balanced Byzantine Agreement with Polylog Bits Per-Party.

  2020cites this paper
• Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum

  2020cites this paper
• Cryptographic Group Actions and Applications

  2020cites this paper
• Low Weight Discrete Logarithm and Subset Sum in 20.65n with Polynomial Memory

  2020cites this paper
• A Proficient Mechanism for Cloud Security Supervision in Distributive Computing Environment

  2020influential citation
• Examples of Upper Bounds and p-Simulations

  2019cites this paper
• Quantum hardness of learning shallow classical circuits

  2019cites this paper
• Public-Key Cryptography in the Fine-Grained Setting

  2019cites this paper
• Further Proof Systems

  2019cites this paper
• Beyond EF via the || . . . || Translation

  2019cites this paper
• Concepts and Problems

  2019cites this paper
• Preface

  2019cites this paper
• Fine-Grained Cryptography Revisited

  2019cites this paper
• Proof of aliveness

  2019cites this paper
• Fd and Logical Restrictions

  2019cites this paper
• The Nature of Proof Complexity

  2019cites this paper
• Obfuscated Fuzzy Hamming Distance and Conjunctions from Subset Product Problems

  2019cites this paper
• The Two Worlds of Bounded Arithmetic

  2019cites this paper
• Proof complexity

  2019cites this paper
• Bibliography

  2019cites this paper
• Threshold ECDSA from ECDSA Assumptions: The Multiparty Case

  2019cites this paper
• Equal-Subset-Sum Faster Than the Meet-in-the-Middle

  2019cites this paper
• Model Theory and Lower Bounds

  2019cites this paper
• Up to EF via the 〈. . .〉 Translation

  2019cites this paper
• Index

  2019cites this paper
• Feasible Interpolation: A Framework

  2019cites this paper
• Quantified Propositional Calculus

  2019cites this paper
• Basic Example of the Correspondence between Theories and Proof Systems

  2019cites this paper
• Sequent Calculus

  2019cites this paper
• Introduction

  2019cites this paper
• Algebraic and Geometric Proof Systems

  2019cites this paper
• Privacy-Preserving Distributed Learning with Secret Gradient Descent

  2019influential citation
• LKd+1/2 and Combinatorial Restrictions

  2019cites this paper
• Better Sample - Random Subset Sum in 20.255n and its Impact on Decoding Random Linear Codes

  2019cites this paper
• Optimality

  2019cites this paper
• R and R-Like Proof Systems

  2019cites this paper
• Tightly secure signature schemes from the LWE and subset sum assumptions

  2019cites this paper
• Hard Tautologies

  2019cites this paper
• Sublinear-Time Sparse Recovery, and Its Power in the Design of Exact Algorithms

  2019cites this paper
• Feasible Interpolation: Applications

  2019cites this paper
• Improved quantum algorithm for the random subset sum problem

  2019cites this paper
• Frege Systems

  2019cites this paper
• Pseudorandom Constructions: Computing in Parallel and Applications to Edit Distance Codes

  2019cites this paper
• Improved broadcast attacks against subset sum problems via lattice oracle

  2018cites this paper
• Handbook of Applied Cryptography

  2018cites this paper
• Secure Two-party Threshold ECDSA from ECDSA Assumptions

  2018cites this paper
• Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme

  2018cites this paper
• Asymptotically Efficient Lattice-Based Digital Signatures

  2018cites this paper
• On the Tightness of Forward-Secure Signature Reductions

  2018cites this paper
• Fractal and Multi-Fractal Analysis for A Family of Subset Sum Functions: Combinatorial Structures of Embedding Dimension 1

  2018cites this paper
• SETH-based Lower Bounds for Subset Sum and Bicriteria Path

  2017cites this paper
• Pseudo-free families of finite computational elementary abelian p-groups

  2017cites this paper
• Faster space-efficient algorithms for subset sum and k-sum

  2017cites this paper
• Prio: Private, Robust, and Scalable Computation of Aggregate Statistics

  2017cites this paper
• Chosen-Ciphertext Security from Subset Sum

  2016influential citation
• 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016, September 27-29, 2016, Berlin, Germany

  2016cites this paper