*09:17* [Pub][ePrint]
Affine-evasive Sets Modulo a Prime, by Divesh Aggarwal
In this work, we describe a simple and efficient construction of a large subset S of F_p, where p is a prime, such that the set A(S) for any non-identity affine map A over F_p has small intersection with S. Such sets, called affine-evasive sets, were defined and constructed in~\\cite{ADL14} as the central step in the construction of non-malleable codes against affine tampering over F_p, for a prime p. This was then used to obtain efficient non-malleable codes against split-state tampering.

Our result resolves one of the two main open questions in~\\cite{ADL14}. It improves the rate of non-malleable codes against affine tampering over F_p from log log p to a constant, and consequently the rate for non-malleable codes against split-state tampering for n-bit messages is improved from n^6 log^7 n to n^6.

*09:17* [Pub][ePrint]
Explicit Optimal Binary Pebbling for One-Way Hash Chain Reversal, by Berry Schoenmakers
We present explicit optimal binary pebbling algorithms for reversing one-way hash chains. For a hash chain of length $2^k$, the number of hashes performed per output round is at most $\\lceil \\tfrac{k}{2}\\rceil$, whereas the number of hash values stored throughout is at most $k$. This is optimal for binary pebbling algorithms characterized by the property that the midpoint of the hash chain is computed just once and stored until it is output, and that this property applies recursively to both halves of the hash chain.We develop a framework for easy comparison of explicit binary pebbling algorithms, including simple speed-1 binary pebbles, Jakobsson\'s binary speed-2 pebbles, and our optimal binary pebbles. Explicit schedules describe for each pebble exactly how many hashes need to be performed in each round. The optimal schedule exhibits a nice recursive structure, which allows fully optimized implementations that can readily be deployed. In particular, we develop in-place implementations with minimal storage overhead (essentially, storing only hash values), and fast implementations with minimal computational overhead.

*09:17* [Pub][ePrint]
Machine Learning Classification over Encrypted Data, by Raphael Bost and Raluca Ada Popa and Stephen Tu and Shafi Goldwasser
Machine learning classification is used in numerous settings nowadays, such as medical or genomics predictions, spam detection, face recognition, and financial predictions. Due to privacy concerns in some of these applications, it is important that the data and the classifier remain confidential.In this work, we construct three major classification protocols that satisfy this privacy constraint: hyperplane decision, Na\\\"ive Bayes, and decision trees. These protocols may also be combined with AdaBoost. They rely on a library of building blocks for constructing classifiers securely, and we demonstrate the versatility of this library by constructing a face detection classifier.

Our protocols are efficient, taking milliseconds to a few seconds to perform a classification when running on real medical datasets.

*09:17* [Pub][ePrint]
From Single-Bit to Multi-Bit Public-Key Encryption via Non-Malleable Codes, by Sandro Coretti and Ueli Maurer Björn Tackmann and Daniele Venturi}
One approach towards basing public-key encryption schemes on weak and credible assumptions is to build ``stronger\'\' or more general schemes generically from ``weaker\'\' or more restricted schemes. One particular line of work in this context, which has been initiated by Myers and Shelat (FOCS \'09) and continued by Hohenberger, Lewko, and Waters (Eurocrypt \'12), is to build a multi-bit chosen-ciphertext (CCA) secure public-key encryption scheme from a single-bit CCA-secure one. While their approaches achieve the desired goal, it is fair to say that the employed techniques are complicated and that the resulting ciphertext lengths are impractical.We propose a completely different and surprisingly simple approach to solving this problem. While it is well-known that encrypting each bit of a plaintext string independently is insecure---the resulting scheme is malleable---we show that applying a suitable non-malleable code (Dziembowski et al., ICS \'10) to the plaintext and subsequently encrypting the resulting codeword bit-by-bit results in a secure scheme. To the best of our knowledge, our result is the first application of non-malleable codes in a context other than memory tampering.

The original notion of non-malleability is, however, not sufficient. We therefore prove that (a simplified version of) the code of Dziembowski et al.\\ is actually continuously non-malleable (Faust et al., TCC \'14). Then, we show that this notion is sufficient for our application. Since continuously non-malleable codes require to keep a single bit of (not necessarily secret) state in the decoding, the decryption of our scheme also has to keep this state. This slight generalization of the traditional formalization of public-key encryption schemes seems appropriate for applications. Compared to the previous approaches, our technique leads to conceptually simpler and more efficient schemes.

*09:17* [Pub][ePrint]
A practical forgery and state recovery attack on the authenticated cipher PANDA-s, by Xiutao FENG, Fan ZHANG and Hui WANG
PANDA is a family of authenticated ciphers submitted to CARSAR, which consists of two ciphers: PANDA-s and PANDA-b. In this work we present a state recovery attack against PANDA-s with time complexity about $2^{41}$ under the known-plaintext-attack model, which needs 137 pairs of known plaintext/ciphertext and about 2GB memories. Our attack is practical in a small workstation. Based on the above attack, we further deduce a forgery attack against PANDA-s, which can forge a legal ciphertext $(C,T)$ of an arbitrary plaintext $P$. The results show that PANDA-s is insecure.

*09:17* [Pub][ePrint]
Some Remarks on Honeyword Based Password-Cracking Detection, by Imran Erguler
Recently, Juels and Rivest proposed honeywords (decoy pass-words) to detect attacks against hashed password databases. For each

user account, the legitimate password is stored with several honeywords in order to sense impersonation. If honeywords are selected properly, an adversary who steals a file of hashed passwords cannot be sure if it is the real password or a honeyword for any account. Moreover, entering with a honeyword to login will trigger an alarm notifying the administrator about a password file breach. At the expense of increasing storage requirement by 20 times, the authors introduce a simple and effective solution to detection of password file disclosure events. In this study, we scrutinize the honeyword system and present some remarks to highlight possible weak points. Also, we suggest an alternative approach that selects honeywords from existing user passwords in the system to provide

realistic honeywords - a perfectly flat honeyword generation method - and also to reduce storage cost of the honeyword scheme.

*18:21* [News]
Volunteers wanted for IACR online services
The IACR Board of Directors is searching for volunteers to help with
the website, the Cryptology ePrint Archive, and other IACR online
services. Maintenance and future expansion of the online services of
the IACR are crucial part for the interaction among cryptographers.
We are interested in motivated cryptographers who would like to
exploit their systems skills in a LAMP environment.

If you are interested in serving the community in this way, please
contact the President of the IACR at president@iacr.org.