Paper 2023/416
Single Instance Self-Masking via Permutations
Abstract
Self-masking allows the masking of success criteria, part of a problem instance (such as the sum in a subset-sum instance) that restricts the number of solutions. Self-masking is used to prevent the leakage of helpful information to attackers; while keeping the original solution valid and, at the same time, not increasing the number of unplanned solutions.
Self-masking can be achieved by xoring the sums of two (or more) independent subset sum instances \cite{DD20, CDM22}, and by doing so, eliminate all known attacks that use the value of the sum of the subset to find the subset fast, namely, in a polynomial time; much faster than the naive exponential exhaustive search.
We demonstrate that the concept of self-masking can be applied to a single instance of the subset sum and a single instance of the permuted secret-sharing polynomials.
We further introduce the benefit of permuting the bits of the success criteria, avoiding leakage of information on the value of the
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- One way functionsSubset sumComplexity
- Contact author(s)
-
coasaf @ bgu ac il
cyprysp @ post bgu ac il
dolev @ cs bgu ac il - History
- 2024-09-07: revised
- 2023-03-22: received
- See all versions
- Short URL
- https://ia.cr/2023/416
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/416, author = {Asaf Cohen and Paweł Cyprys and Shlomi Dolev}, title = {Single Instance Self-Masking via Permutations}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/416}, year = {2023}, url = {https://eprint.iacr.org/2023/416} }