搜索结果: 1-13 共查到“subset sum”相关记录13条 . 查询时间(1.033 秒)
Low Weight Discrete Logarithms and Subset Sum in 20.65n with Polynomial Memory
Low weight dlog subset sum representations Nested Rho
2019/8/19
We propose two polynomial memory collision finding algorithms for the low Hamming weight discrete logarithm problem in any abelian group GG. The first one is a direct adaptation of the Becker-Coron-Jo...
Improved Low-Memory Subset Sum and LPN Algorithms via Multiple Collisions
time-memory trade-off representations parallel collision search
2019/7/15
For enabling post-quantum cryptanalytic experiments on a meaningful scale, there is a strong need for low-memory algorithms. We show that the combination of techniques from representations, multiple c...
Iterative collision search procedures play a key role in developing combinatorial algorithms for the subset sum and learning parity with noise (LPN) problems. In both scenarios, the single-list pair-w...
Chosen-Ciphertext Security from Subset Sum
public-key cryptography chosen-ciphertext security subset sum
2016/1/27
We construct a public-key encryption (PKE) scheme whose
security is polynomial-time equivalent to the hardness of the Subset Sum
problem. Our scheme achieves the standard notion of indistinguishabil...
Solving Random Subset Sum Problem by $l_{p}$-norm SVP Oracle
SVP random subset sum problems lattice
2016/1/26
SHipher: Families of Block Ciphers based on SubSet-Sum Problem
Block cipher SubSet-Sum problem Framework
2016/1/25
In this paper, we describe the families of block ciphers named SHipher. We
show a symmetric encryption framework based on the SubSet-Sum problem.
This framework can provide families of secure, flexi...
Quantum algorithms for the subset-sum problem
subset sum quantum search quantum walks radix trees decoding SVP CVP
2013/4/18
This paper introduces a subset-sum algorithm with heuristic asymptotic cost exponent below 0.25. The new algorithm combines the 2010 Howgrave-Graham--Joux subset-sum algorithm with a new streamlined d...
On the sparse subset sum problem from Gentry-Halevi's implementation of fully homomorphic encryption
public-key cryptography / sparse subset sum lattice reduction dimension reduction method geometric progression homomorphic encryption
2012/3/23
In Gentry's fully homoomrphic cryptosystem, a sparse subset sum problem is used and a big set is included in the public key. In the implementation of a variant of Gentry's scheme, to reduce the size o...
A Note on the Density of the Multiple Subset Sum Problems
Lattice Low-Density Multiple Subset Sum Problem Multiple Modular Subset Sum Problem
2012/3/26
It is well known that the general subset sum problem is NP-complete. However, almost all subset sum problems with density less than $0.9408\ldots$ can be solved in polynomial time with an oracle that ...
Subset sum phase transitions and data compression
Number partitioning integer partitioning subset sum data compression source coding entropy phase transitions
2011/9/6
Abstract: We propose a rigorous analysis approach for the subset sum problem in the context of lossless data compression, where the phase transition of the subset sum problem is directly related to th...
On the Distribution of the Subset Sum Pseudorandom Number Generator on Elliptic Curves
Pseudorandom numbers Subset sum problem Knapsack Exponential sums
2011/2/23
Given a prime $p$, an elliptic curve $\mathcal{E}/\mathbb{F}_p$ over the finite field $\mathbb{F}_p$ of $p$ elements and a binary linear recurrence sequence $\(u(n)\)_{n =1}^\infty$ of order~$r$, we s...
On the Distribution of the Subset Sum Pseudorandom Number Generator on Elliptic Curves
Number Generator elliptic curve
2012/3/29
Given a prime $p$, an elliptic curve $\mathcal{E}/\mathbb{F}_p$ over the finite field $\mathbb{F}_p$ of $p$ elements and a binary linear recurrence sequence $\(u(n)\)_{n =1}^\infty$ of order~$r$, we s...
Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
Public-Key Cryptographic Primitives Secure Subset Sum
2009/12/29
We propose a semantically-secure public-key encryption scheme whose security is polynomial-
time equivalent to the hardness of solving random instances of the subset sum problem. The subset sum
assu...