ATProto Browser

Record data

{
  "uri": "at://did:plc:fwa55bujvdrwlwlwgqmmxmuf/app.bsky.feed.post/3loe5kxv43d2p",
  "cid": "bafyreidwmxsyraaek4d6dva4j7u5mx36jmhaurzvdur25drnhyjtxlioei",
  "value": {
    "text": "Non-Adaptive Cryptanalytic Time-Space Lower Bounds via a Shearer-like Inequality for Permutations (Itai Dinur, Nathan Keller, Avichai Marmor) ia.cr/2025/783",
    "$type": "app.bsky.feed.post",
    "embed": {
      "$type": "app.bsky.embed.images",
      "images": [
        {
          "alt": "Abstract. The power of adaptivity in algorithms has been intensively studied in diverse areas of theoretical computer science. In this paper, we obtain a number of sharp lower bound results which show that adaptivity provides a significant extra power in cryptanalytic time-space tradeoffs with (possibly unlimited) preprocessing time.\n\nMost notably, we consider the discrete logarithm (DLOG) problem in a generic group of N elements. The classical `baby-step giant-step’ algorithm for the problem has time complexity $T=O(\\sqrt{N})$, uses $O(\\sqrt{N})$ bits of space (up to logarithmic factors in N) and achieves constant success probability.\n\nWe examine a generalized setting where an algorithm obtains an advice string of S bits and is allowed to make T arbitrary non-adaptive queries that depend on the advice string (but not on the challenge group element for which the DLOG needs to be computed).\n\nWe show that in this setting, the $T=O(\\sqrt{N})$ online time complexity of the baby-step giant-step algorithm cannot be improved, unless the advice string is more than $\\Omega(\\sqrt{N})$ bits long. This lies in stark contrast with the classical adaptive Pollard’s rho algorithm for DLOG, which can exploit preprocessing to obtain the tradeoff curve ST² = O(N). We obtain similar sharp lower bounds for the problem of breaking the Even-Mansour cryptosystem in symmetric-key cryptography and for several other problems.\n\nTo obtain our results, we present a new model that allows analyzing non-adaptive preprocessing algorithms for a wide array of search and decision problems in a unified way.\n\nSince previous proof techniques inherently cannot distinguish between adaptive and non-adaptive algorithms for the problems in our model, they cannot be used to obtain our results. Consequently, we rely on information-theoretic tools for handling distributions and functions over the space S_(N) of permutations of N elements. Specifically, we use a variant of Shearer’s lemma for this setting, due to Barthe, Cordero-Erausquin, Ledoux, and Maurey (2011), and a variant of the concentration inequality of Gavinsky, Lovett, Saks and Srinivasan (2015) for read-k families of functions, that we derive from it. This seems to be the first time a variant of Shearer’s lemma for permutations is used in an algorithmic context, and it is expected to be useful in other lower bound arguments.\n",
          "image": {
            "$type": "blob",
            "ref": {
              "$link": "bafkreichv7dovowpxhsas4t3y4jnipy5awwxmtnx2zbvty4jpxua6mwdfy"
            },
            "mimeType": "image/png",
            "size": 88020
          },
          "aspectRatio": {
            "width": 1200,
            "height": 800
          }
        },
        {
          "alt": "Image showing part 2 of abstract.",
          "image": {
            "$type": "blob",
            "ref": {
              "$link": "bafkreicvww2popkpidcb5q56fnybwkshrs3esri5ncrt6cba5cquoh47va"
            },
            "mimeType": "image/png",
            "size": 93020
          },
          "aspectRatio": {
            "width": 1200,
            "height": 800
          }
        },
        {
          "alt": "Image showing part 3 of abstract.",
          "image": {
            "$type": "blob",
            "ref": {
              "$link": "bafkreieaa3r3oyib3jug744ev2sbbaqtycthuc3hastxxexzquk5mexb2e"
            },
            "mimeType": "image/png",
            "size": 50424
          },
          "aspectRatio": {
            "width": 1200,
            "height": 800
          }
        }
      ]
    },
    "facets": [
      {
        "index": {
          "byteEnd": 156,
          "byteStart": 142
        },
        "features": [
          {
            "uri": "https://ia.cr/2025/783",
            "$type": "app.bsky.richtext.facet#link"
          }
        ]
      }
    ],
    "createdAt": "2025-05-04T15:17:23.003361Z"
  }
}