Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Cryptography and Communications
Published in: Cryptography and Communications 2/2011

01-06-2011

Error decodable secret sharing and one-round perfectly secure message transmission for general adversary structures

Authors: Keith M. Martin, Maura B. Paterson, Douglas R. Stinson

Published in: Cryptography and Communications | Issue 2/2011

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

An error decodable secret-sharing scheme is a secret-sharing scheme with the additional property that the secret can be recovered from the set of all shares, even after a coalition of participants corrupts the shares they possess. In this paper, schemes that can tolerate corruption by sets of participants belonging to a monotone coalition structure are considered. This coalition structure may be unrelated to the authorised sets of the secret-sharing scheme. This is generalisation of both a related notion studied in the context of multiparty computation, and the well-known error-correction properties of threshold schemes based on Reed-Solomon codes. Necessary and sufficient conditions for the existence of such schemes are deduced, and methods for reducing the storage requirements of a technique of Kurosawa for constructing error-decodable secret-sharing schemes with efficient decoding algorithms are demonstrated. In addition, the connection between one-round perfectly secure message transmission (PSMT) schemes with general adversary structures and secret-sharing schemes is explored. We prove a theorem that explicitly shows the relation between these structures. In particular, an error decodable secret-sharing scheme yields a one-round PSMT, but the converse does not hold. Furthermore, we are able to show that some well-known results concerning one-round PSMT follow from known results on secret-sharing schemes. These connections are exploited to investigate factors affecting the performance of one-round PSMT schemes such as the number of channels required, the communication overhead, and the efficiency of message recovery.
previous article Construction of quaternary sequences of length pq with low autocorrelation
next article Permutation sequences and coded PAM signals with spectral nulls at rational submultiples of the symbol frequency

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
Ideally we would like to be able to decode in time polynomial in n, which requires l itself to be polynomial in n. This is the case for most known dedicated constructions of linear secret-sharing schemes for specific access structures, such as Shamir’s threshold secret-sharing scheme. However, generic constructions for arbitrary access structures tend to result in a value of l that is exponential in n.
 
Literature
1.
Bellare, M., Rogaway, P.: Robust computational secret sharing and a unified account of classical secret-sharing goals. In: Ning, P., di Vimercati, S.D.C., Syverson, P.F. (eds.) ACM Conference on Computer and Communications Security, pp. 172–184. ACM (2007)
2.
Berlekamp, E.R., McEliece, R.J., van Tilborg, H.C.: On the inherent intractability of certain coding problems. IEEE Trans. Inf. Theory 24(3), 384–386 (1978)CrossRefMATH
3.
Blakley, G.R.: Safeguarding cryptographic keys. In: Proc. 1979 National Comp. Conf., vol. 48, pp. 313–317. AFIPS Press (1979)
4.
Blundo, C., Santis, A.D., Vaccaro, U.: Efficient sharing of many secrets. In: Enjalbert, P., Finkel, A., Wagner, K.W. (eds.) STACS ’93. LNCS, vol. 665, pp. 692–703. Springer (1993)
5.
Chen, H., Cramer, R.: Algebraic geometric secret sharing schemes and secure multi-party computations over small fields. In: Dwork, C. (ed.) CRYPTO ’06. LNCS, vol. 4117, pp. 521–536. Springer (2006)
6.
Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In: FOCS ’85, pp. 383–395. IEEE (1985)
7.
Cramer, R., Damgard, I., Maurer, U.: General secure multi-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316–334. Springer (2000)
8.
Cramer, R., Daza, V., Gracia, I., Urroz, J.J., Leander, G., Martí-Farré, J., Padró, C.: On codes, matroids and secure multi-party computation from linear secret sharing schemes. In: Shoup, V. (ed.) CRYPTO ’05. LNCS, vol. 3621, pp. 327–343. Springer (2005)
9.
Desmedt, Y., Wang, Y., Burmester, M.: A complete characterization of tolerable adversary structures for secure point-to-point transmissions without feedback. In: Deng, X., Du, D.Z. (eds.) ISAAC ’05. LNCS, vol. 3827, pp. 277–287. Springer (2005)
10.
11.
Fehr, S., Maurer, U.M.: Linear vss and distributed commitments based on secret sharing and pairwise checks. In: Yung, M. (ed.) CRYPTO ’02. LNCS, vol. 2442, pp. 565–580. Springer (2002)
12.
Fitzi, M., Franklin, M.K., Garay, J.A., Vardhan, S.H.: Towards optimal and efficient perfectly secure message transmission. In: Vadhan, S.P. (ed.) TCC ’07. LNCS, vol. 4392, pp. 311–322. Springer (2007)
13.
Fitzi, M., Hirt, M., Maurer, U.M.: General adversaries in unconditional multi-party computation. In: Lam, K.Y., Okamoto, E., Xing, C. (eds.) ASIACRYPT ’99. LNCS, vol. 1716, pp. 232–246. Springer (1999)
14.
Hirt, M., Maurer, U.: Player simulation and general adversary structures in perfect multiparty computation. J. Cryptol. 13(1), 31–60 (2000)CrossRefMATHMathSciNet
15.
Hirt, M., Maurer, U.M.: Complete characterization of adversaries tolerable in secure multi-party computation (extended abstract). In: PODC, pp. 25–34 (1997)
16.
Huffman, W.C., Pless, V.: Fundamentals of Error-correcting Codes. Cambridge Univ. Press (2003)
17.
18.
Jackson, W.A., Martin, K.M.: Cumulative arrays and geometric secret sharing schemes. In: Seberry, J., Zheng, Y. (eds.) AUSCRYPT ’92. LNCS, vol. 718, pp. 48–55. Springer (1992)
19.
Jackson, W.A., Martin, K.M.: A combinatorial interpretation of ramp schemes. Australas. J. Combin. 14, 51–60 (1996)MATHMathSciNet
20.
21.
Kurosawa, K., Obana, S., Ogata, W.: t-cheater identifiable (k, n) threshold secret sharing schemes. In: Coppersmith, D. (ed.) CRYPTO ’95. LNCS, vol. 963, pp. 410–423. Springer (1995)
22.
Martin, K.M.: Challenging the adversary model in secret sharing schemes. In: Coding and Cryptography II, Proceedings of the Royal Flemish Academy of Belgium for Science and the Arts, pp. 45–63 (2008)
23.
24.
25.
Obana, S., Araki, T.: Almost optimum secret sharing schemes secure against cheating for arbitrary secret distribution. In: Lai, X., Chen, K. (eds.) ASIACRYPT ’06. LNCS, vol. 4284, pp. 364–379. Springer (2006)
26.
Ogata, W., Kurosawa, K., Stinson, D.: Optimum secret sharing scheme secure against cheating. SIAM J. Discrete Math. 20, 79–95 (2006)CrossRefMATHMathSciNet
27.
Rees, R.S., Stinson, D.R., Wei, R., van Rees, G.H.J.: An application of covering designs: determining the maximum consistent set of shares in a threshold scheme. Ars Comb. 53 (1999)
28.
29.
Stinson, D.R., Zhang, S.: Algorithms for detecting cheaters in threshold schemes. J. Comb. Math. Comb. Comput. 61, 169–191 (2007)MATHMathSciNet
30.
Tso, R., Miao, Y., Okamoto, E.: A new algorithm for searching a consistent set of shares in a threshold scheme with cheaters. In: Lim, J.I., Lee, D.H. (eds.) ICISC ’03. LNCS, vol. 2971, pp. 377–385. Springer (2004)
31.
Ye, Q., Steinfeld, R., Pieprzyk, J., Wang, H.: Efficient fuzzy matching and intersection on private datasets. In: Lee, D., Hong, S. (eds.) ICISC ’09. LNCS, vol. 5984, pp. 211–228. Springer (2009)
32.
Zhang, Z., Liu, M., Chee, Y.M., Ling, S., Wang, H.: Strongly multiplicative and 3-multiplicative linear secret sharing schemes. In: Pieprzyk, J. (ed.) ASIACRYPT ’08. LNCS, vol. 5350, pp. 19–36. Springer (2008)
Metadata
Title
Error decodable secret sharing and one-round perfectly secure message transmission for general adversary structures
Authors
Keith M. Martin
Maura B. Paterson
Douglas R. Stinson
Publication date
01-06-2011
Publisher
Springer US
Published in
Cryptography and Communications / Issue 2/2011
Print ISSN: 1936-2447
Electronic ISSN: 1936-2455
DOI
https://doi.org/10.1007/s12095-010-0039-6

Premium Partner

    Image Credits