Nonuniform Indistinguishability and Unpredictability Hardcore Lemmas: New Proofs and Applications to Pseudoentropy, by Maciej Skorski
Hardcore lemmas are results in complexity theory which state that average-case hardness must have a very hard ``kernel\'\', that is a subset of instances where the given problem is extremely hard. They find important applications in hardness amplification. In this paper we revisit the following two fundamental results:
\\item The hardcore lemma for unpredictability, due to Impagliazzo (FOCS \'95). It states that if a boolean function $f$ is ``moderately\'\' hard to predict on average, then there must be a set of noticeable size on which $f$ is ``extremely\'\' hard to predict.
\\item The hardcore lemma for indistinguishability, proved by Maurer and Tessaro (TCC\'10), states that for two random variables $X$ and $Y$ which are $\\epsilon$-computationally close, there are events $A$ and $B$ of probability $1-\\epsilon$ such that the distributions of $X|A$ and $Y|B$ are ``computationally\'\' identical.
Using only the standard min-max theorem and some basic facts about convex approximations in $L_p$ spaces, we provide alternative modular proofs and some generalizations of these results in the nonuniform setting, achieving best possible bounds for (a) and slightly improving the known bounds for (b). As an interesting application, we show a strengthening of the transformation between two most popular pseudoentropy variants: HILL and Metric Entropy, and apply it to show how to extract pseudorandomness from a sequence of metric-entropy sources of poor quality. In this case we significantly improve security parameters, comparing to the best known techniques.
Constructing and Understanding Chosen Ciphertext Security via Puncturable Key Encapsulation Mechanisms, by Takahiro Matsuda and Goichiro Hanaoka
In this paper, we introduce and study a new cryptographic primitive that we call \"puncturable key encapsulation mechanism\" (PKEM), which is a special class of KEMs that satisfy some functional and security requirements that, combined together, imply chosen ciphertext security (CCA security). The purpose of introducing this primitive is to capture certain common patterns in the security proofs of the several existing CCA secure public key encryption (PKE) schemes and KEMs based on general cryptographic primitives which (explicitly or implicitly) use the ideas and techniques of the Dolev-Dwork-Naor (DDN) construction (STOC\'91), and \"break down\" the proofs into smaller steps, so that each small step is easier to work with/verify/understand than directly tackling CCA security.
To see the usefulness of PKEM, we show (1) how several existing constructions of CCA secure PKE/KEM constructed based on general cryptographic primitives can be captured as a PKEM, which enables us to understand these constructions via a unified framework, (2) its connection to detectable CCA security (Hohenberger et al. EUROCRYPT\'12), and (3) a new security proof for a KEM-analogue of the DDN construction from a set of assumptions: \"sender non-committing encryption\" (SNCE) and non-interactive witness indistinguishable proofs.
Then, as our main technical result, we show how to construct a PKEM satisfying our requirements (and thus a CCA secure KEM) from a new set of general cryptographic primitives: \"SNCE\" and \"symmetric key encryption secure for key-dependent messages\" (KDM secure SKE). Our construction realizes the \"decrypt-then-re-encrypt\"-style validity check of a ciphertext which is powerful but in general has a problem of the circularity between a plaintext and a randomness.We show how SNCE and KDM secure SKE can be used together to overcome the circularity. We believe that the connection among three seemingly unrelated notions of encryption primitives, i.e. CCA security, the sender non-committing property, and KDM security, to be of theoretical interest.
Generalization of Statistical Criteria for Sboxes, by S. M. Dehnavi and A. Mahmoodi Rishakani and M. R. Mirzaee Shamsabad and Einollah Pasha
Linear and differential cryptanalysis and their generalizations are the most important tools in ststistical analysis of symmetric ciphers.
These attacks make use of linear and differential properties of Sboxes and component functions of symmetric ciphers. In this
article, we investigate generalized statistical properties for Sboxes. We justify the application of linear, differential and differential-linear
cryptanalysis from the mathematical viewpoint. We verify some well-known Sboxes and vectotial Boolean functions by the proposed
criteria and show that these functions have larger biases compared with previous criteria presentesd up to now.