Search

In ICISC-05, and in the ePrint 2010/287, Patarin claimed a lower bound on the number of $2 q$ tuples of $n$ -bit strings $(P_{1}, \ldots, P_{2q}) \in ({\{0,1\}}^{n})^{2q}$ satisfying $P_{2i - 1} \oplus P_{2i} = \lambda _{i}$ for $1 \leq i \leq q$ such that $P_{1}, P_{2}, \ldots $ , $P_{2q}$ are distinct and $\lambda _{i} \in {\{0,1\}} ^{n} \setminus \{0^{n}\}$. This result is known as Mirror theory and widely used in cryptography. It stands as a powerful tool to provide a high-security guarantee for many block cipher-(or even ideal permutation-) based designs. In particular, Mirror theory has a direct application in the security of XOR of block ciphers. Unfortunately, the proof of Mirror theory contains some unverifiable gaps and several mistakes. This paper provides a simple and verifiable proof of Mirror theory. [ABSTRACT FROM AUTHOR]

The Coefficients H technique (also called the H-technique), developed by Patarin circa 1991, is a tool used to obtain the upper bounds on distinguishing advantages. This tool is known to provide relatively simple and (in some cases) tight bound proofs in comparison to some other well-known tools, such as the game-playing technique and random systems methodology. In this systematization of knowledge (SoK) paper, we aim to provide a brief survey on the H-technique. The SoK is presented in four parts. First, we redevelop the necessary nomenclature and tools required to study the security of any symmetric-key design, especially in the H-technique setting. Second, we provide a full description of the H-technique and some related tools. Third, we present (simple) H-technique-based proofs for some popular symmetric-key designs, across different paradigms. Finally, we show that the H-technique can actually provide optimal bounds on distinguishing advantages. [ABSTRACT FROM AUTHOR]

Recently, Attrapadung (Eurocrypt 2014) proposed a generic framework for fully (adaptively) secure predicate encryption (PE) based on a new primitive, called pair encodings. The author shows that if the underlying pair encoding scheme is either perfectly secure or computationally (doubly-selectively) secure, then the PE scheme will be fully secure. Although the pair encodings were solely introduced for PE, we show that these can also be used to construct predicate signatures, a signature analogue of PE. More precisely, we propose a generic construction of predicate signature (PS) from pair encoding schemes. Our construction provides unconditional signer privacy, and unforgeability in the adaptive model. Thereafter, we instantiate many PS schemes with new results, e.g., the first practical PS schemes for regular languages, the first attribute-based signature (ABS) scheme with constant-size signatures in the adaptive model, unbounded ABS with large universes in key-policy flavor, etc. [ABSTRACT FROM AUTHOR]

Predicate encryption (PE), a generalization of attribute-based encryption (ABE), is a versatile tool for providing access control over data. The underlying predicate for a PE is parametrized by an index, called system parameter or simply system-index. A system-index, in general, consists of component(s) from $$\mathbb {N}$$ . Yamada et al. in PKC 2011 proposed a verifiability-based conversion from CPA to CCA-secure ABE. This conversion was generalized by Yamada et al. in PKC 2012 from ABE to PE. In the later conversion, the authors considered the system-index to be a single component. In practice, there are many schemes, e.g., functional encryption for general relations and hierarchical-inner product (HIP) encryption schemes of Okamoto-Takashima in CRYPTO 2010, CANS 2011 and EUROCRYPT 2012, where system-indices consist of more than a single component. Therefore, for these schemes, the conversion of Yamada et al. (in PKC, 2012) is out of scope. In this paper, we revisit the CPA to CCA conversion for PE and propose a new conversion based on verifiability. The proposed conversion works irrespective of the number of components in the system-indices. It generalizes the existing conversion of Yamada et al. (in PKC, 2011) from ABE to PE. The PE schemes which are realized by the conversion of Yamada et al. (2011) are also realized by our conversion. Therefore, the conversion of ours has more scope than the conversion proposed in 2012. We show that all the aforementioned CPA-secure schemes for general relations and HIP relation are easily converted to the corresponding CCA-secure schemes by our conversion. Further, we show a generic conversion from CPA to CCA-secure functional encryption for regular languages which captures the existing PE schemes for regular languages. [ABSTRACT FROM AUTHOR]

In [2], Bellare, Pietrzak and Rogaway proved an O(ℓq2/2n) bound for the PRF (pseudorandom function) security of the CBC-MAC based on an n-bit random permutation II, provided ℓ< 2n/3. Here an adversary can make at most q prefix-free queries each having at most ℓ many "blocks" (elements of {0, 1}n). In the same paper an O(ℓo(1)q2/2n) bound for EMAC (or encrypted CBC-MAC) was proved, provided ℓ < 2n/4. Both proofs are based on structure graphs representing all collisions among "intermediate inputs" to II during the computation of CBC. The problem of bounding PRF-advantage is shown to be reduced to bounding the number of structure graphs satisfying certain collision patterns. In the present paper, we show that [2, Lemma 10], stating an important result on structure graphs, is incorrect. This is due to the fact that the authors overlooked certain structure graphs. This invalidates the proofs of the PRF bounds. In [31], Pietrzak improved the bound for EMAC by showing a tight bound O(q2/2n) under the restriction that ℓ < 2n/8. As he used the same flawed lemma, this proof also becomes invalid. In this paper, we have revised and sometimes simplified these proofs. We revisit structure graphs in a slightly different mathematical language and provide a complete characterization of certain types of structure graphs. Using this characterization, we show that PRF security of CBC-MAC is about σq/2n provided ℓ < 2n/3 where σ is the total number of blocks in all queries. We also recover tight bound for PRF security of EMAC with a much relaxed constraint (ℓ < 2n/4) than the original (ℓ < 2n/8). [ABSTRACT FROM AUTHOR]

In 2002, An et al. [1] proposed three generic conversions of signcryption, EtS, StE and CtE&S from the primitive encryption scheme and signature scheme. But, the security proof of confidentiality in the CtE&S paradigm was ambiguous. In this paper, we revisit these paradigms again and provide a more transparent proof for the aforementioned paradigm. None of these paradigms preserves both stronger securities: strong unforgeability and IND-CCA security. We extend the above paradigms to new signcryption paradigms, EtStS, StEtS and CtE&StS, by applying one-time signature (OTS) cautiously at the outside layer. In these new paradigms, the stronger security of the primitive encryption and signature schemes are maintained. We also obtain a new paradigm, "Encrypt and Sign then Sign (E&StS)", which is surprisingly better than the CtE&StS paradigm in all aspects except that E&StS does not guarantee the non-repudiation. Moreover, the IND-CCA security and strong unforgeability of the proposed signcryptions are achieved from the IND-gCCA secure encryption scheme and weak unforgeable signature scheme, respectively. Further, we extend these paradigms to capture signcryptions in attribute-based setting, also known as attribute-based signcryption (ABSC). We show that the IND-CCA security and strong unforgeability under chosen message attack of ABSC can be obtained from IND-CPA security of ABE and unforgeability under no message attack of ABS, respectively. Furthermore, our generic constructions are applicable to a combined setup, where the public parameters and keys for the primitives ABS and ABE are identical. The security of all the generic constructions is proven in the standard model. [ABSTRACT FROM AUTHOR]

We show several concrete attacks on an authenticated encryption (AE) scheme PAE, which appeared in the IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 56, no. 8, pp. 4025–4037. In addition, we show some flaws and oversights in the analysis (presented in the same paper) used to prove PAE to be a secure AE scheme. [ABSTRACT FROM PUBLISHER]

This paper shows that the advantage of any q-query adversary (which makes at most q queries) for distinguishing OMAC from a uniform random function is roughly Lq2/2 n. Here L is the number of blocks of the longest query and n is the output size of the uniform random function. The so far best bound is roughly σσ2/2 n == O( L2 q2/2 n) and hence our new bound is an improved bound. Our improved security analysis also works for OMAC1 and CMAC which has been recommended by NIST as a candidate of blockcipher based MAC. [ABSTRACT FROM AUTHOR]

A multicollision for a function is a set of inputs whose outputs are all identical. A. Joux showed multicollision attacks on the classical iterated hash function. He also showed how these multicollision attacks can be used to get a collision attack on a concatenated hash function. In this paper, we study multicollision attacks in a more general class of hash functions which we term "generalized sequential hash functions." We show that multicollision attacks exist for this class of hash functions provided that every message block is used at most twice in the computation of the message digest. [ABSTRACT FROM AUTHOR]

Offset codebook or ${\mathsf {OCB}}$ mode is a popular block cipher mode of operation for authenticated encryption. The latest version of this cipher, called ${\mathsf {OCB3}}$ , is one of the finalists in CAESAR. In this paper, we explore the scope of random read access and out-of-sequence decryption in ${\mathsf {OCB}}$. We observe that the current versions of ${\mathsf {OCB}}$ are inefficient in this respect owing to the ineptness of the underlying mask generating function (MGF). We propose new candidates for MGF based on ${\mathsf {AES}}$ round function, which are efficient in direct computation and provide comparable performance in the usual setting. Our schemes are not the obvious choices for MGF in conventional sense as they do not have optimal almost XOR universal (AXU) bound. In existing ${\mathsf {OCB}}$ designs, the MGFs are required to have $ 2^{-n} $ , i.e. optimal, AXU bound in order to upper bound the distinguishing advantage to $ O(\sigma ^{2}/2^{n}) $ , where $ n $ is the block size of the underlying block cipher and $ \sigma $ is the total number of blocks among all queries. We find this specific requirement too restrictive. We abstract the ${\mathsf {OCB}}$ design, termed as ${\mathsf {GOCB}}$ , to look into the universal notion required from the underlying MGF. We propose a relaxed notion of AXU, called locally imperfect XOR universal (LIXU) hash, which can be of independent interest. Using LIXU as the underlying MGF, we recover reasonable security bounds for our schemes. [ABSTRACT FROM AUTHOR]

A block is an n-bit string, and a (possibly keyed) block-function is a non-linear mapping that maps one block to another, e.g., a block-cipher. In this paper, we consider various symmetric key primitives with ℓ {\ell} block inputs and raise the following question: what is the minimum number of block-function invocations required for a mode to be secure? We begin with encryption modes that generate ℓ ′ {\ell^{\prime}} block outputs and show that at least (ℓ + ℓ ′ - 1) {(\ell+\ell^{\prime}-1)} block-function invocations are necessary to achieve the PRF security. In presence of a nonce, the requirement of block-functions reduces to ℓ ′ {\ell^{\prime}} blocks only. If ℓ = ℓ ′ {\ell=\ell^{\prime}} , in order to achieve SPRP security, the mode requires at least 2 ⁢ ℓ {2\ell} many block-function invocations. We next consider length preserving r-block (called chunk) online encryption modes and show that, to achieve online PRP security, each chunk should have at least 2 ⁢ r - 1 {2r-1} many and overall at least 2 ⁢ r ⁢ ℓ - 1 {2r\ell-1} many block-functions for ℓ {\ell} many chunks. Moreover, we show that it can achieve online SPRP security if each chunk contains at least 2 ⁢ r {2r} non-linear block-functions. We next analyze affine MAC modes and show that an integrity-secure affine MAC mode requires at least ℓ {\ell} many block-function invocations to process an ℓ {\ell} block message. Finally, we consider affine mode authenticated encryption and show that in order to achieve INT-RUP security or integrity security under a nonce-misuse scenario, either (i) the number of non-linear block-functions required to generate the ciphertext is more than ℓ {\ell} or (ii) the number of extra non-linear block-functions required to generate the tag depends on ℓ {\ell}. [ABSTRACT FROM AUTHOR]

In cryptography, counters (classically encoded as bit strings of fixed size for all inputs) are employed to prevent collisions on the inputs of the underlying primitive which helps us to prove the security. In this paper we present a unified notion for counters, called counter function family, and identify some necessary and sufficient conditions on counters which give (possibly) simple proof of security for various counter-based cryptographic schemes. We observe that these conditions are trivially true for the classical counters. We also identify and study two variants of the classical counter which satisfy the security conditions. The first variant has message length dependent counter size, whereas the second variant uses universal coding to generate message length independent counter size. Furthermore, these variants provide better performance for shorter messages. For instance, when the message size is 2^19 bits, AES-LightMAC with $64$ -bit (classical) counter takes $1.51$ cycles per byte (cpb), whereas it takes $0.81$ cpb and $0.89$ cpb for the first and second variant, respectively. We benchmark the software performance of these variants against the classical counter by implementing them in MACs and HAIFA hash function. [ABSTRACT FROM PUBLISHER]

Authenticated encryption schemes which resist misuse of nonce at some desired level of privacy are two-pass or Mac-then-Encrypt constructions (inherently inefficient but provide full privacy) and online constructions like McOE, sponge-type authenticated encryptions (such as duplex) and COPA. Only the last one is almost parallelizable except that for associated data processing, the final block-cipher call is sequential (it needs to wait for the encryption of all the previous ones). In this paper, we design a new online secure authenticated encryption, called ELmD or Encrypt-Linear mix-Decrypt, which is completely (two-stage) parallel (even in associated data) and fully pipeline implementable. It also provides full privacy when associated data is not repeated. Like COPA, our construction is based on EME, an Encrypt-Mix-Encrypt type SPRP construction (secure against chosen plaintext and ciphertext). But unlike EME, we have used an online computable efficient linear mixing instead of a non-linear mixing. We have also provided the hardware implementation of the construction and compare the performance with similar constructions like COPA and EME2. [ABSTRACT FROM AUTHOR]