Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (4 results)

  • Article
  • Peer Reviewed
Technical Reports (2000)
We investigate the following approach to symmetric encryption: first encode the message in some trivial way (eg., prepend a counter and append a checksum), and then encipher the encoded message. Here "encipher" means to apply a cipher (i.e.~pseudorandom permutation) $F_\key$, where~$\key$ is the shared key. We show that if the encoding step incorporates a nonce (counter or randomness), in any way at all, then the resulting encryption scheme will be semantically secure. And we show that if the encoding step incorporates redundancy, in any form at all, then, as long as the receiver verifies the presence of this redundancy in the deciphered string, the resulting encryption scheme achieves message authenticity. The second result helps explain and justify the prevalent misunderstanding that encrypting messages which have redundancy is enough to guarantee message authenticity: the statement is actually true if "encrypting" is understood as "enciphering." Encode-then-encipher encryption can be used to robustly and efficiently exploit structured message spaces. If one is presented with messages known a~priori to contain something that behaves as a nonce, then privacy can be obtained with no increase in message length, and no knowledge of the structure of the message, simply by enciphering the message. Similarly, if one is presented with messages known a~priori to contain adequate redundancy, then message authenticity can be obtained with no increase in message length, and no knowledge of the structure of the message, simply by enciphering the message.

Pre-2018 CSE ID: CS2000-0646

    Cover page: Encode-then-encipher encryption: How to exploit nonces or redundacy in plaintexts for efficient cryptography
    • Thesis
    • Peer Reviewed
    UC Davis Electronic Theses and Dissertations (2022)

    Authenticated encryption (AE) is a cryptographic primitiveproviding message privacy and authenticity simultaneously. From a standard definition of AE, several natural assumptions may arise. (1) An observer of an encrypted message learns nothing about its origin. (2) If one attempts to decrypt a ciphertext using a different key (or any other decryption input) from what was used at encryption, then decryption should fail. One might conclude the former from promises of privacy and the latter from promises of authenticity.

    We observe that the validity of those assumptions do notfollow from standard AE definitions of privacy and authenticity. For (1), when sending a ciphertext, there is typically other information sent along with it. This information, commonly referred to as metadata, can be message numbers that mark the message's position in a sequence or information that identifies the sender among other possibilities. For (2), it is possible to validly decrypt a ciphertext with the ``wrong'' arguments.

    This dissertation's main contribution consists of definitions and constructions that address these assumptions. With respect to the first, it offers an AE variant, anonymous AE (anAE)---a primitive that folds all cryptographically relevant metadata directly into its ciphertexts. For the second, it furthers the study of committing AE (cAE)---a variant of AE that ensures that decryption of a ciphertext is only possible with the ``correct'' inputs. These two primitives provide security that users may have mistakenly assumed AE satisfied. Lastly, we give concrete constructions for these primitives along with their proofs of security.

      Cover page: Regarding Assumptions Made of Authenticated Encryption
      • Article
      • Peer Reviewed
      UC Davis Previously Published Works (2004)

      We propose a block-cipher mode of operation, EAX, for solving the problem of authenticated-encryption with associated-data (AEAD). Given a nonce N, a message M, and a header H, our mode protects the privacy of M and the authenticity of both M and H. Strings N, M, and H are arbitrary bit strings, and the mode uses 2[I\M\/n] + [\H\/n] + [\N\/n] block-cipher calls when these strings are nonempty and n is the block length of the underlying block cipher. Among EAX's characteristics are that it is on-line (the length of a message isn't needed to begin processing it) and a fixed header can be preprocessed, effectively removing the per-message cost of binding it to the ciphertext.

        Cover page: The EAX mode of operation
        • Article
        • Peer Reviewed
        UC San Diego Previously Published Works (2016)
        This paper aims to move research in the bounded retrieval model (BRM) from theory to practice by considering symmetric (rather than public-key) encryption, giving efficient schemes, and providing security analyses with sharp, concrete bounds. The threat addressed is malware that aims to exfiltrate a user’s key. Our schemes aim to thwart this by using an enormously long key, yet paying for this almost exclusively in storage cost, not speed. Our main result is a general-purpose lemma, the subkey prediction lemma, that gives a very good bound on an adversary’s ability to guess a (modest length) subkey of a big-key, the subkey consisting of the bits of the big-key found at random, specified locations, after the adversary has exfiltrated partial information about the big-key (e.g., half as many bits as the big-key is long). We then use this to design a new kind of key encapsulation mechanism, and, finally, a symmetric encryption scheme. Both are in the random-oracle model. We also give a less efficient standard-model scheme that is based on universal computational extractors (UCE). Finally, we define and achieve hedged BRM symmetric encryption, which provides authenticity in the absence of leakage.
          Top