×

All or nothing at all. (English) Zbl 1351.05036

Summary: We continue a study of unconditionally secure all-or-nothing transforms (AONT) begun by D. R. Stinson [Des. Codes Cryptography 22, No. 2, 133–138 (2001; Zbl 0985.94030)]. An AONT is a bijective mapping that constructs \(s\) outputs from \(s\) inputs. We consider the security of \(t\) inputs, when \(s-t\) outputs are known. Previous work concerned the case \(t=1\); here we consider the problem for general \(t\), focussing on the case \(t=2\). We investigate constructions of binary matrices for which the desired properties hold with the maximum probability. Upper bounds on these probabilities are obtained via a quadratic programming approach, while lower bounds can be obtained from combinatorial constructions based on symmetric BIBDs and cyclotomy. We also report some results on exhaustive searches and random constructions for small values of \(s\).

MSC:

05B05 Combinatorial aspects of block designs

Citations:

Zbl 0985.94030
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] V. Canda and Tran van Trung. A new mode of using all-or-nothing transforms. ISIT 2002, p. 296. · Zbl 1174.68404
[2] R. Canetti, Y. Dodis, S. Halevi, E. Kushilevitz and A. Sahai. Exposure-resilient functions and all-or-nothing transforms. Lecture Notes in Computer Science 1807 (2000), 453-469 (EUROCRYPT 2000). · Zbl 1082.94508
[3] R. G. Cascella, Z. Cao, M. Gerla, B. Crispo and R. Battiti. Weak data secrecy via obfuscation in network coding based content distribution. Wireless Days, 2008, pp. 1-5.
[4] C. J. Colbourn and J. H. Dinitz, eds. The CRC Handbook of Combinatorial Designs, Second Edition, CRC Press, 2006.
[5] A. Desai. The security of all-or-nothing encryption: protecting against exhaustive key search. Lecture Notes in Computer Science 1880 (2000), 359-375 (CRYPTO 2000). · Zbl 0995.94539
[6] Q. Guo, M. Luo, L. Li and Y. Yang. Secure network coding against wiretapping and Byzantine attacks. EURASIP Journal on Wireless Communications and Networking 2010 (2010), article No. 17.
[7] S. A. Katre and A. R. Rajwade. Resolution of the sign ambiguity in the determination of the cyclotomic numbers of order 4 and the corresponding Jacobsthal sum. Math. Scand. 60 (1987), 52-62. · Zbl 0602.12005
[8] J. Liu, H. Wang, M. Xian and K. Huang. A secure and efficient scheme for cloud storage against eavesdropper. Lecture Notes in Computer Science 8233 (2013), 75-89 (ICICS 2013).
[9] A. Proano and L. Lazos. Packet-hiding methods for preventing selective jamming attacks. IEEE Transactions on Dependable and Secure Computing 9 (2012), 101– 114.
[10] R. L. Rivest. All-or-nothing encryption and the package transform. Lecture Notes in Computer Science 1267 (1997), 210-218 (Fast Software Encryption 1997). · Zbl 1385.94067
[11] Y.-J. Song, K.-Y. Park and J.-M. Kang. The method of protecting privacy capable of distributing and storing of data efficiently for cloud computing environment. Computers, Networks, Systems and Industrial Engineering 2011, pp. 258-262.
[12] D. R. Stinson. Something about all or nothing (transforms). Designs, Codes and Cryptography 22 (2001), 133-138. the electronic journal of combinatorics 23(4) (2016), #P4.1021 · Zbl 0985.94030
[13] M. Tawarmalani and N. V. Sahinidis. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming 103 (2005), 225-249. · Zbl 1099.90047
[14] R. A. Vasudevan, A. Abraham and S. Sanyal. A novel scheme for secured data transfer over computer networks Journal of Universal Computer Science 11 (2005), 104-121.
[15] Q. Zhang and L. Lazos. Collusion-resistant query anonymization for location-based services. 2014 IEEE International Conference on Communications, pp. 768-774. AMatrices Yielding Good or Exact Lower Bounds for N2(M ) Example 36. An invertible 5 by 5 matrix having 70 invertible 2 × 2 submatrices: 0 0 1 1 1 0 1 0 1 1 M5×5=1 0 0 1 1. 1 1 1 0 1 1 1 1 1 0 Example 37. An invertible 6 by 6 matrix having 150 invertible 2 × 2 submatrices:  0 0 1 1 1 1 0 1 0 1 1 1  M6×6=1 0 1 0 1 1 1 1 0 1 0 1  1 1 1 0 0 1 1 1 1 1 1 0     .    Example 38. An invertible 7 by 7 matrix having 287 invertible 2 × 2 submatrices: 0 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 M7×7=1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 Example 39. An invertible 8 by 8 matrix having 485 invertible 2 × 2 submatrices: 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1  M8×8= 1 1 0 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 0 0 the electronic journal of combinatorics 23(4) (2016), #P4.1022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.