Leakage-Resilient Secret Sharing in Non-compartmentalized Models

Leakage-Resilient Secret Sharing in Non-compartmentalized Models. Lin, F., Cheraghchi, M., Guruswami, V., Safavi-Naini, R., & Wang, H. In Proceedings of the Conference on Information-Theoretic Cryptography (ITC), volume 163, of Leibniz International Proceedings in Informatics (LIPIcs), pages 7:1–7:24, 2020.

Link

Paper doi abstract bibtex

Non-malleable secret sharing was recently proposed by Goyal and Kumar in independent tampering and joint tampering models for threshold secret sharing (STOC18) and secret sharing with general access structure (CRYPTO18). The idea of making secret sharing non-malleable received great attention and by now has generated many papers exploring new frontiers in this topic, such as multiple-time tampering and adding leakage resiliency to the one-shot tampering model. Non-compartmentalized tampering model was first studied by Agrawal et.al (CRYPTO15) for non-malleability against permutation composed with bit-wise independent tampering, and shown useful in constructing non-malleable string commitments. In spite of strong demands in application, there are only a few tampering families studied in non-compartmentalized model, due to the fact that compartmentalization (assuming that the adversary can not access all pieces of sensitive data at the same time) is crucial for most of the known techniques. We initiate the study of leakage-resilient secret sharing in the non-compartmentalized model. Leakage in leakage-resilient secret sharing is usually modelled as arbitrary functions with bounded total output length applied to each share or up to a certain number of shares (but never the full share vector) at one time. Arbitrary leakage functions, even with one bit output, applied to the full share vector is impossible to resist since the reconstruction algorithm itself can be used to construct a contradiction. We allow the leakage functions to be applied to the full share vector (non-compartmentalized) but restrict to the class of affine leakage functions. The leakage adversary can corrupt several players and obtain their shares, as in normal secret sharing. The leakage adversary can apply arbitrary affine functions with bounded total output length to the full share vector and obtain the outputs as leakage. These two processes can be both non-adaptive and do not depend on each other, or both adaptive and depend on each other with arbitrary ordering. We use a generic approach that combines randomness extractors with error correcting codes to construct such leakage-resilient secret sharing schemes, and achieve constant information ratio (the scheme for non-adaptive adversary is near optimal). We then explore making the non-compartmentalized leakage-resilient secret sharing also non-malleable against tampering. We consider a tampering model, where the adversary can use the shares obtained from the corrupted players and the outputs of the global leakage functions to choose a tampering function from a tampering family $\mathcal{F}$. We give two constructions of such leakage-resilient non-malleable secret sharing for the case $\mathcal{F}$ is the bit-wise independent tampering and, respectively, for the case $\mathcal{F}$ is the affine tampering functions, the latter is non-compartmentalized tampering that subsumes the permutation composed with bit-wise independent tampering mentioned above.

@INPROCEEDINGS{ref:LCGSW20,
  author =	 {Fuchun Lin and Mahdi Cheraghchi and Venkatesan
                  Guruswami and Reihaneh Safavi-Naini and Huaxiong
                  Wang},
  title =	 {Leakage-Resilient Secret Sharing in
                  Non-compartmentalized Models},
  year =	 2020,
  booktitle =	 {Proceedings of the {Conference on
                  Information-Theoretic Cryptography (ITC)}},
  pages =	 {7:1--7:24},
  volume =	 163,
  series =	 {Leibniz International Proceedings in Informatics
                  (LIPIcs)},
  url_Link =	 {https://drops.dagstuhl.de/opus/volltexte/2020/12112},
  url_Paper =	 {https://arxiv.org/abs/1902.06195},
  doi =		 {10.4230/LIPIcs.ITC.2020.7},
  keywords =	 {Leakage-resilient cryptography, Secret sharing
                  scheme, Randomness extractor},
  abstract =	 {Non-malleable secret sharing was recently proposed
                  by Goyal and Kumar in independent tampering and
                  joint tampering models for threshold secret sharing
                  (STOC18) and secret sharing with general access
                  structure (CRYPTO18). The idea of making secret
                  sharing non-malleable received great attention and
                  by now has generated many papers exploring new
                  frontiers in this topic, such as multiple-time
                  tampering and adding leakage resiliency to the
                  one-shot tampering model. Non-compartmentalized
                  tampering model was first studied by Agrawal et.al
                  (CRYPTO15) for non-malleability against permutation
                  composed with bit-wise independent tampering, and
                  shown useful in constructing non-malleable string
                  commitments. In spite of strong demands in
                  application, there are only a few tampering families
                  studied in non-compartmentalized model, due to the
                  fact that compartmentalization (assuming that the
                  adversary can not access all pieces of sensitive
                  data at the same time) is crucial for most of the
                  known techniques.  We initiate the study of
                  leakage-resilient secret sharing in the
                  non-compartmentalized model.  Leakage in
                  leakage-resilient secret sharing is usually modelled
                  as arbitrary functions with bounded total output
                  length applied to each share or up to a certain
                  number of shares (but never the full share vector)
                  at one time. Arbitrary leakage functions, even with
                  one bit output, applied to the full share vector is
                  impossible to resist since the reconstruction
                  algorithm itself can be used to construct a
                  contradiction. We allow the leakage functions to be
                  applied to the full share vector
                  (non-compartmentalized) but restrict to the class of
                  affine leakage functions. The leakage adversary can
                  corrupt several players and obtain their shares, as
                  in normal secret sharing. The leakage adversary can
                  apply arbitrary affine functions with bounded total
                  output length to the full share vector and obtain
                  the outputs as leakage. These two processes can be
                  both non-adaptive and do not depend on each other,
                  or both adaptive and depend on each other with
                  arbitrary ordering. We use a generic approach that
                  combines randomness extractors with error correcting
                  codes to construct such leakage-resilient secret
                  sharing schemes, and achieve constant information
                  ratio (the scheme for non-adaptive adversary is near
                  optimal).  We then explore making the
                  non-compartmentalized leakage-resilient secret
                  sharing also non-malleable against tampering. We
                  consider a tampering model, where the adversary can
                  use the shares obtained from the corrupted players
                  and the outputs of the global leakage functions to
                  choose a tampering function from a tampering family
                  $\mathcal{F}$. We give two constructions of such
                  leakage-resilient non-malleable secret sharing for
                  the case $\mathcal{F}$ is the bit-wise independent
                  tampering and, respectively, for the case
                  $\mathcal{F}$ is the affine tampering functions, the
                  latter is non-compartmentalized tampering that
                  subsumes the permutation composed with bit-wise
                  independent tampering mentioned above.  }
}

Downloads: 0