Paper 2023/416
Single Instance SelfMasking via Permutations
Abstract
Selfmasking allows the masking of success criteria, part of a problem instance (such as the sum in a subsetsum instance) that restricts the number of solutions. Selfmasking 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. Selfmasking 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 selfmasking can be applied to a single instance of the subset sum and a single instance of the permuted secretsharing polynomials. We further introduce the benefit of permuting the bits of the success criteria, avoiding leakage of information on the value of the $i$'th bit of the success criteria, in the case of a single instance, or the parity of the $i$'th bit of the success criteria in the case of several instances. In the case of several instances, we permute the success criteria bits of each instance prior to xoring them with each other. One basic permutation and its nesting versions (e.g., $\pi^i$) are used, keeping the solution space small and at the same time, attempting to create an ``all or nothing'' effect, where the result of a wrong $\pi$ trials does not imply much.
Metadata
 Available format(s)
 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
 20240907: revised
 20230322: 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 SelfMasking via Permutations}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/416}, year = {2023}, url = {https://eprint.iacr.org/2023/416} }