Paper 2023/416

Single Instance Self-Masking via Permutations

Asaf Cohen, Ben-Gurion University of the Negev
Paweł Cyprys, Ben-Gurion University of the Negev
Shlomi Dolev, Ben-Gurion University of the Negev

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 $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.

Available format(s)
Publication info
One way functionsSubset sumComplexity
Contact author(s)
coasaf @ bgu ac il
cyprysp @ gmail com
dolev @ cs bgu ac il
2023-03-24: approved
2023-03-22: received
See all versions
Short URL
No rights reserved


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.