Paper 2022/1033

A Complete Characterization of Security for Linicrypt Block Cipher Modes

Tommy Hollenberg, Google (United States)
Mike Rosulek, Oregon State University
Lawrence Roy, Oregon State University

We give characterizations of IND\$-CPA security for a large, natural class of encryption schemes. Specifically, we consider encryption algorithms that invoke a block cipher and otherwise perform linear operations (e.g., XOR and multiplication by fixed field elements) on intermediate values. This class of algorithms corresponds to the Linicrypt model of Carmer & Rosulek (Crypto 2016). Our characterization for this class of encryption schemes is sound but not complete. We then focus on a smaller subclass of block cipher modes, which iterate over the blocks of the plaintext, repeatedly applying the same Linicrypt program. For these Linicrypt block cipher modes, we are able to give a sound and complete characterization of IND\$-CPA security. Our characterization is linear-algebraic in nature and is easy to check for a candidate mode. Interestingly, we prove that a Linicrypt block cipher mode is secure if and only if it is secure against adversaries who choose all-zeroes plaintexts.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. IEEE 35th Computer Security Foundations Symposium (CSF 2022)
modes of operation chosen plaintext
Contact author(s)
tommyhollenberg @ gmail com
rosulekm @ oregonstate edu
royl @ oregonstate edu
2022-08-11: approved
2022-08-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Tommy Hollenberg and Mike Rosulek and Lawrence Roy},
      title = {A Complete Characterization of Security for Linicrypt Block Cipher Modes},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1033},
      year = {2022},
      doi = {10.1109/CSF54842.2022.00028},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.