Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection
From MaRDI portal
Publication:6132417
DOI10.1007/978-3-031-22966-4_13zbMATH Open1519.94117OpenAlexW4316590254MaRDI QIDQ6132417FDOQ6132417
Authors: Thibauld Feneuil, Jules Maire, Matthieu Rivain, Damien Vergnaud 
Publication date: 16 August 2023
Published in: Advances in Cryptology – ASIACRYPT 2022 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-22966-4_13
Recommendations
- MPC-in-multi-heads: a multi-prover zero-knowledge proof system (or: how to jointly prove any NP statements in ZK)
- On Efficient Zero-Knowledge PCPs
- scientific article; zbMATH DE number 1107670
- Zero-knowledge proofs from secure multiparty computation
- Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments
- Zero knowledge protocols from succinct constraint detection
- scientific article; zbMATH DE number 5485433
- Round-optimal zero-knowledge proofs of knowledge for NP
- scientific article; zbMATH DE number 1759795
- Promise zero knowledge and its applications to round optimal MPC
Cites Work
- TFHE: fast fully homomorphic encryption over the torus
- On lattices, learning with errors, random linear codes, and cryptography
- Reducibility among combinatorial problems
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems
- Computing Partitions with Applications to the Knapsack Problem
- The Knowledge Complexity of Interactive Proof Systems
- Fiat-Shamir with aborts: applications to lattice and factoring-based signatures
- Improved zero-knowledge proofs of knowledge for the ISIS problem, and applications
- Efficient cryptographic schemes provably as secure as subset sum
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- Improved low-density subset sum algorithms
- Hiding information and signatures in trapdoor knapsacks
- A new identification scheme based on syndrome decoding
- On the modular inversion hidden number problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- New generic algorithms for hard knapsacks
- Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
- Zero-knowledge proofs from secure multiparty computation
- Sigma protocols for MQ, PKP and SIS, and fishy signature schemes
- Aurora: transparent succinct arguments for R1CS
- Scalable zero knowledge with no trusted setup
- Concretely-efficient zero-knowledge arguments for arithmetic circuits and their application to lattice-based cryptography
- LegRoast: efficient post-quantum signatures from the Legendre PRF
- How to prove knowledge of small secrets
- Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems
- On the size of pairing-based non-interactive arguments
- New results on Modular Inversion Hidden Number problem and inversive congruential generator
- Inferring sequences produced by nonlinear pseudorandom number generators using Coppersmith's methods
- Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection
- Algebraic techniques for short(er) exact lattice-based zero-knowledge proofs
- Shorter lattice-based zero-knowledge proofs via one-time commitments
- Practical exact proofs from lattices: new techniques to exploit fully-splitting rings
- Improved classical and quantum algorithms for subset-sum
- Fiat-Shamir bulletproofs are non-malleable (in the algebraic group model)
- Syndrome decoding in the head: shorter signatures from zero-knowledge proofs
- Title not available (Why is that?)
- Computing inverses over a shared secret modulus
Cited In (11)
- PERK: compact signature scheme based on a new variant of the permuted kernel problem
- Promise zero knowledge and its applications to round optimal MPC
- Practical and efficient FHE-based MPC
- Threshold linear secret sharing to the rescue of MPC-in-the-head
- ZK-for-Z2K: MPC-in-the-head zero-knowledge proofs for \(\mathbb{Z}_{2^k}\)
- Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection
- Efficient isogeny proofs using generic techniques
- Vector commitments with proofs of smallness: short range proofs and more
- A short note on Merlin-Arthur protocols for subset sum
- Commitments with efficient zero-knowledge arguments from subset sum problems
- Efficient zero-knowledge arguments and digital signatures \textit{via} sharing conversion \textit{in the head}
This page was built for publication: Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6132417)
