*04:17* [Pub][ePrint]
The Multivariate Hidden Number Problem, by Steven D. Galbraith and Barak Shani
This work extends the line of research on the hidden number problem. Motivated by studying bit security in finite fields, we define the multivariate hidden number problem. Here, the secret and the multiplier are vectors, and partial information about their dot product is given. Using tools from discrete Fourier analysis introduced by Akavia, Goldwasser and Safra, we show that if one can find the significant Fourier coefficients of some function, then one can solve the multivariate hidden number problem for that function. This allows us to generalise the work of Akavia on the hidden number problem with (non-adaptive) chosen multipliers to all finite fields.We give two further applications of our results, both of which generalise previous works to all (finite) extension fields. The first considers the general (random samples) hidden number problem in F_{p^m} and assumes an advice is given to the algorithm. The second considers a model that allows changing representations, where we show hardness of individual bits for elliptic curve and pairing based functions for elliptic curves over extension fields, as well as hardness of any bit of any component of the Diffie-Hellman secret in F_{p^m} (m>1).

*04:17* [Pub][ePrint]
How to Compress Homomorphic Ciphertexts, by Anne Canteaut and Sergiu Carpov and Caroline Fontaine and Tancrède Lepoint and María Naya-Plasencia and Pascal Paillier and Renaud Sirdey
In typical applications of homomorphic encryption, the first step consists for Alice to encrypt some plaintext m under Bob\'s public key pk and to send the ciphertext c = HE_pk(m) to some third-party evaluator Charlie. This paper specifically considers that first step, i.e. the problem of transmitting c as efficiently as possible from Alice to Charlie. As previously noted, a form of compression is achieved using hybrid encryption. Given a symmetric encryption scheme E, Alice picks a random key k and sends a much smaller ciphertext c′ = (HE_pk(k), E_k(m)) that Charlie decompresses homomorphically into the original c using a decryption circuit.In this paper, we revisit that paradigm in light of its concrete implementation constraints; in particular E is chosen to be an additive IV-based stream cipher. We propose 2 new designs such that the decryption circuit has very small multiplicative depth, typically between 8 and 12 for 128-bit security. Our first construction of depth 12 is inspired by Trivium and reportedly the current fastest option. Our second construction, based on exponentiation in binary fields, is impractical but sets the lowest depth record to 8 for 128-bit security.

*04:17* [Pub][ePrint]
Comprehensive Efficient Implementations of ECC on C54xx Family of Low-cost Digital Signal Processors, by Muhammad Yasir Malik
Resource constraints in smart devices demand an efficient cryptosystem that allows for low power and memory consumption. This has led to popularity of comparatively efficient Elliptic curve cryptog-raphy (ECC). Prior to this paper, much of ECC is implemented on re-configurable hardware i.e. FPGAs, which are costly and unfavorable as low-cost solutions.We present comprehensive yet efficient implementations of ECC on fixed-point TMS54xx series of digital signal processors (DSP). 160-bit prime field GF(p) ECC is implemented over a wide range of coordinate choices. This paper also implements windowed recoding technique to provide better execution times. Stalls in the programming are mini-mized by utilization of loop unrolling and by avoiding data dependence. Complete scalar multiplication is achieved within 50 msec in coordinate implementations, which is further reduced till 25 msec for windowed-recoding method. These are the best known results for fixed-point low power digital signal processor to date.

*04:17* [Pub][ePrint]
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:\\begin{enumerate}[(a)]

\\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.

\\end{enumerate}

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.

*04:17* [Pub][ePrint]
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.

*22:17* [Pub][ePrint]
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.