Error Correcting Codes, Block Designs, Perfect Secrecy and Finite Fields View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2006-09

AUTHORS

Aiden A. Bruen, David L. Wehlau, Mario Forcinito

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
  • 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: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "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", 
            "volumeNumber": "93"
          }
        ], 
        "name": "Error Correcting Codes, Block Designs, Perfect Secrecy and Finite Fields", 
        "pagination": "253-278", 
        "productId": [
          {
            "name": "readcube_id", 
            "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", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "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", 
        "url": "http://link.springer.com/10.1007%2Fs10440-006-9043-4"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    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'

    Turtle is a human-readable linked data format.

    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
    1 sg:pub.10.1007/s10440-006-9043-4 schema:about anzsrc-for:08
    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
    23 schema:productId N7d58791fa0bb4741a614d8838b0adee5
    24 N8d7104c2602a4d6d9447c993692f5dd9
    25 Nc7329e86ebed4834ad37b0ae526d66ae
    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
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher Nab62ed0c8fb64a639fc9028ac7c1bb35
    31 schema:url http://link.springer.com/10.1007%2Fs10440-006-9043-4
    32 sgo:license sg:explorer/license/
    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
    38 rdf:rest N8f2c2e9ad29040f29f2aa94decb9581b
    39 N7d58791fa0bb4741a614d8838b0adee5 schema:name readcube_id
    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
    45 N8f2c2e9ad29040f29f2aa94decb9581b rdf:first sg:person.011262114207.39
    46 rdf:rest N23584c0e631842c2af11003e422c439f
    47 N9b1520d2049f4e5d939e38b9a045e5e4 schema:volumeNumber 93
    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
    53 Nc7329e86ebed4834ad37b0ae526d66ae schema:name dimensions_id
    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
     




    Preview window. Press ESC to close (or click here)


    ...