# Error Correcting Codes, Block Designs, Perfect Secrecy and Finite Fields

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2006-09

AUTHORS ABSTRACT

The ancient difficulty for establishing a common cryptographic secret key between two communicating parties Alice and Bob is nicely summarized by the Catch-22 dictum of S.J. Lomonaco [1999], to wit: “in order to communicate in secret one must first communicate in secret”. In other words, to communicate in secret, Alice and Bob must already have a shared secret key. In this paper we analyse an algorithm for establishing such a common secret key by public discussion, under the modest and practical requirement that Alice and Bob are initially in possession of keys \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$A$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$B$\end{document}, respectively, of a common length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$N$\end{document} which are not necessarily equal but are such that the mutual information \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$I(A,B)$\end{document} is non-zero. This assumption is tantamount to assuming only that the corresponding statistical variables are correlated. The common secret key distilled by the algorithm will enjoy perfect secrecy in the sense of Shannon. The method thus provides a profound generalization of traditional symmetric key cryptography and applies also to quantum cryptography. Here, by purely elementary methods, we give a rigorous proof that the method proposed by Bennett, Bessette, Brassard, Salvail, and Smolin will in general converge to a non-empty common key under moderate assumptions on the choice of block lengths provided the initial bit strings are sufficiently long. Full details on the length requirements are presented. Furthermore, we consider the question of which block lengths should be chosen for optimal performance with respect to the length of the resulting common key. A new and fundamental aspect of this paper is the explicit utilization of finite fields and error-correcting codes both for checking equality of the generated keys and, later, for the construction of various hash functions. Traditionally this check has been done by performing a few times a comparison of the parity of a random subset of the bits. Here we give a much more efficient procedure by using the powerful methods of error-correcting codes. More general situations are treated in Section 8. More... »

PAGES

253-278

### References to SciGraph publications

• 2006-05-17. Privacy amplification secure against active adversaries in ADVANCES IN CRYPTOLOGY — CRYPTO '97
• 1992-01. Experimental quantum cryptography in JOURNAL OF CRYPTOLOGY
• ### Journal

TITLE

Acta Applicandae Mathematicae

ISSUE

1-3

VOLUME

93

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10440-006-9043-4

DOI

http://dx.doi.org/10.1007/s10440-006-9043-4

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1041716008

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Data Format",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "University of Calgary",
"id": "https://www.grid.ac/institutes/grid.22072.35",
"name": [
"Department of Mathematics, University of Calgary, Calgary, Alberta, Canada"
],
"type": "Organization"
},
"familyName": "Bruen",
"givenName": "Aiden A.",
"id": "sg:person.010620072145.82",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010620072145.82"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Royal Military College of Canada",
"id": "https://www.grid.ac/institutes/grid.217211.6",
"name": [
"Department of Mathematics and Statistics, Royal Military College of Canada, K7K 7B4, Kingston, Ontario, Canada"
],
"type": "Organization"
},
"familyName": "Wehlau",
"givenName": "David L.",
"id": "sg:person.011262114207.39",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011262114207.39"
],
"type": "Person"
},
{
"affiliation": {
"name": [
"SUR CiES Inc., 86 Anaheim Green NE, T1Y 7A6, Calgary, Alberta, USA"
],
"type": "Organization"
},
"familyName": "Forcinito",
"givenName": "Mario",
"id": "sg:person.010671767071.38",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010671767071.38"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/bf00191318",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1000187285",
"https://doi.org/10.1007/bf00191318"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/j.1538-7305.1949.tb00928.x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1009908265"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0052244",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012602811",
"https://doi.org/10.1007/bfb0052244"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0052244",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012602811",
"https://doi.org/10.1007/bfb0052244"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1080/0161-119991887739",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024191906"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/j.1538-7305.1948.tb01338.x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052867467"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/18.256484",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061098983"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1109/18.476316",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1061099776"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/0217014",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062842033"
],
"type": "CreativeWork"
}
],
"datePublished": "2006-09",
"datePublishedReg": "2006-09-01",
"description": "The ancient difficulty for establishing a common cryptographic secret key between two communicating parties Alice and Bob is nicely summarized by the Catch-22 dictum of S.J. Lomonaco [1999], to wit: \u201cin order to communicate in secret one must first communicate in secret\u201d. In other words, to communicate in secret, Alice and Bob must already have a shared secret key. In this paper we analyse an algorithm for establishing such a common secret key by public discussion, under the modest and practical requirement that Alice and Bob are initially in possession of keys \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$A$\\end{document} and \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$B$\\end{document}, respectively, of a common length \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$N$\\end{document} which are not necessarily equal but are such that the mutual information \\documentclass[12pt]{minimal} \\usepackage{amsmath} \\usepackage{wasysym} \\usepackage{amsfonts} \\usepackage{amssymb} \\usepackage{amsbsy} \\usepackage{mathrsfs} \\usepackage{upgreek} \\setlength{\\oddsidemargin}{-69pt} \\begin{document}$I(A,B)$\\end{document} is non-zero. This assumption is tantamount to assuming only that the corresponding statistical variables are correlated. The common secret key distilled by the algorithm will enjoy perfect secrecy in the sense of Shannon. The method thus provides a profound generalization of traditional symmetric key cryptography and applies also to quantum cryptography. Here, by purely elementary methods, we give a rigorous proof that the method proposed by Bennett, Bessette, Brassard, Salvail, and Smolin will in general converge to a non-empty common key under moderate assumptions on the choice of block lengths provided the initial bit strings are sufficiently long. Full details on the length requirements are presented. Furthermore, we consider the question of which block lengths should be chosen for optimal performance with respect to the length of the resulting common key. A new and fundamental aspect of this paper is the explicit utilization of finite fields and error-correcting codes both for checking equality of the generated keys and, later, for the construction of various hash functions. Traditionally this check has been done by performing a few times a comparison of the parity of a random subset of the bits. Here we give a much more efficient procedure by using the powerful methods of error-correcting codes. More general situations are treated in Section 8.",
"genre": "research_article",
"id": "sg:pub.10.1007/s10440-006-9043-4",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1028030",
"issn": [
"0167-8019",
"1572-9036"
],
"name": "Acta Applicandae Mathematicae",
"type": "Periodical"
},
{
"issueNumber": "1-3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"name": "Error Correcting Codes, Block Designs, Perfect Secrecy and Finite Fields",
"pagination": "253-278",
"productId": [
{
"type": "PropertyValue",
"value": [
"c6b7cc870e37e4a0c8098109aaeb0d731e4b05afba0eb357a90536263b2b45de"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s10440-006-9043-4"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1041716008"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s10440-006-9043-4",
"https://app.dimensions.ai/details/publication/pub.1041716008"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T14:29",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000373_0000000373/records_13084_00000001.jsonl",
"type": "ScholarlyArticle",
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10440-006-9043-4'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10440-006-9043-4'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10440-006-9043-4'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10440-006-9043-4'

This table displays all metadata directly associated to this object as RDF triples.

106 TRIPLES      21 PREDICATES      35 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0804
3 schema:author N4a035fda8d6243a2ae7a0c58a6634ef3
4 schema:citation sg:pub.10.1007/bf00191318
5 sg:pub.10.1007/bfb0052244
6 https://doi.org/10.1002/j.1538-7305.1948.tb01338.x
7 https://doi.org/10.1002/j.1538-7305.1949.tb00928.x
8 https://doi.org/10.1080/0161-119991887739
9 https://doi.org/10.1109/18.256484
10 https://doi.org/10.1109/18.476316
11 https://doi.org/10.1137/0217014
12 schema:datePublished 2006-09
13 schema:datePublishedReg 2006-09-01
14 schema:description The ancient difficulty for establishing a common cryptographic secret key between two communicating parties Alice and Bob is nicely summarized by the Catch-22 dictum of S.J. Lomonaco [1999], to wit: “in order to communicate in secret one must first communicate in secret”. In other words, to communicate in secret, Alice and Bob must already have a shared secret key. In this paper we analyse an algorithm for establishing such a common secret key by public discussion, under the modest and practical requirement that Alice and Bob are initially in possession of keys \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$A$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$B$\end{document}, respectively, of a common length \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$N$\end{document} which are not necessarily equal but are such that the mutual information \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$I(A,B)$\end{document} is non-zero. This assumption is tantamount to assuming only that the corresponding statistical variables are correlated. The common secret key distilled by the algorithm will enjoy perfect secrecy in the sense of Shannon. The method thus provides a profound generalization of traditional symmetric key cryptography and applies also to quantum cryptography. Here, by purely elementary methods, we give a rigorous proof that the method proposed by Bennett, Bessette, Brassard, Salvail, and Smolin will in general converge to a non-empty common key under moderate assumptions on the choice of block lengths provided the initial bit strings are sufficiently long. Full details on the length requirements are presented. Furthermore, we consider the question of which block lengths should be chosen for optimal performance with respect to the length of the resulting common key. A new and fundamental aspect of this paper is the explicit utilization of finite fields and error-correcting codes both for checking equality of the generated keys and, later, for the construction of various hash functions. Traditionally this check has been done by performing a few times a comparison of the parity of a random subset of the bits. Here we give a much more efficient procedure by using the powerful methods of error-correcting codes. More general situations are treated in Section 8.
15 schema:genre research_article
16 schema:inLanguage en
17 schema:isAccessibleForFree false
18 schema:isPartOf N9b1520d2049f4e5d939e38b9a045e5e4
19 Nf24faf147e6f4c258d7bbee7e282068d
20 sg:journal.1028030
21 schema:name Error Correcting Codes, Block Designs, Perfect Secrecy and Finite Fields
22 schema:pagination 253-278
24 N8d7104c2602a4d6d9447c993692f5dd9
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041716008
27 https://doi.org/10.1007/s10440-006-9043-4
28 schema:sdDatePublished 2019-04-11T14:29
30 schema:sdPublisher Nab62ed0c8fb64a639fc9028ac7c1bb35
33 sgo:sdDataset articles
34 rdf:type schema:ScholarlyArticle
35 N23584c0e631842c2af11003e422c439f rdf:first sg:person.010671767071.38
36 rdf:rest rdf:nil
37 N4a035fda8d6243a2ae7a0c58a6634ef3 rdf:first sg:person.010620072145.82
40 schema:value c6b7cc870e37e4a0c8098109aaeb0d731e4b05afba0eb357a90536263b2b45de
41 rdf:type schema:PropertyValue
42 N8d7104c2602a4d6d9447c993692f5dd9 schema:name doi
43 schema:value 10.1007/s10440-006-9043-4
44 rdf:type schema:PropertyValue
46 rdf:rest N23584c0e631842c2af11003e422c439f
48 rdf:type schema:PublicationVolume
49 Na7d47f5219264ef4a486b9bd3849418e schema:name SUR CiES Inc., 86 Anaheim Green NE, T1Y 7A6, Calgary, Alberta, USA
50 rdf:type schema:Organization
51 Nab62ed0c8fb64a639fc9028ac7c1bb35 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
54 schema:value pub.1041716008
55 rdf:type schema:PropertyValue
56 Nf24faf147e6f4c258d7bbee7e282068d schema:issueNumber 1-3
57 rdf:type schema:PublicationIssue
58 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
59 schema:name Information and Computing Sciences
60 rdf:type schema:DefinedTerm
61 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
62 schema:name Data Format
63 rdf:type schema:DefinedTerm
64 sg:journal.1028030 schema:issn 0167-8019
65 1572-9036
66 schema:name Acta Applicandae Mathematicae
67 rdf:type schema:Periodical
68 sg:person.010620072145.82 schema:affiliation https://www.grid.ac/institutes/grid.22072.35
69 schema:familyName Bruen
70 schema:givenName Aiden A.
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010620072145.82
72 rdf:type schema:Person
73 sg:person.010671767071.38 schema:affiliation Na7d47f5219264ef4a486b9bd3849418e
74 schema:familyName Forcinito
75 schema:givenName Mario
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010671767071.38
77 rdf:type schema:Person
78 sg:person.011262114207.39 schema:affiliation https://www.grid.ac/institutes/grid.217211.6
79 schema:familyName Wehlau
80 schema:givenName David L.
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011262114207.39
82 rdf:type schema:Person
83 sg:pub.10.1007/bf00191318 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000187285
84 https://doi.org/10.1007/bf00191318
85 rdf:type schema:CreativeWork
86 sg:pub.10.1007/bfb0052244 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012602811
87 https://doi.org/10.1007/bfb0052244
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1002/j.1538-7305.1948.tb01338.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1052867467
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1002/j.1538-7305.1949.tb00928.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1009908265
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1080/0161-119991887739 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024191906
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1109/18.256484 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061098983
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1109/18.476316 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061099776
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1137/0217014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842033
100 rdf:type schema:CreativeWork
101 https://www.grid.ac/institutes/grid.217211.6 schema:alternateName Royal Military College of Canada
102 schema:name Department of Mathematics and Statistics, Royal Military College of Canada, K7K 7B4, Kingston, Ontario, Canada
103 rdf:type schema:Organization
104 https://www.grid.ac/institutes/grid.22072.35 schema:alternateName University of Calgary
105 schema:name Department of Mathematics, University of Calgary, Calgary, Alberta, Canada
106 rdf:type schema:Organization