International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

08:27 [Job][New] Cloud Security R&D Engineers, Applied Science and Technology Research Institute (ASTRI), Hong Kong

  We are looking for R&D engineers to work on network and system security. The positions offered are at the Senior Engineer/Engineer level, depending on qualifications and experiences. The candidates should have hands on experiences in implementing systems, network security and cloud computing, and a good knowledge of SeLinux and secure sandboxes. Knowledge of MAC (Mandatory Access Control) policies, honeypots, proxy re-encryption would be an advantage. The candidates are expected to create intellectual properties, develop demo systems and deliver projects.

If interested, please submit your CV to Dr. Aldar Chan (aldarchan (at)

19:17 [Pub][ePrint] Non-Malleable Extractors with Shorter Seeds and Min-Entropy Rate $

  Motivated by the problem of how to communicate over a public channel with an active adversary, Dodis and Wichs [DW09] introduced the notion of a non-malleable extractor, as a much stronger version of a strong extractor. A non-malleable extractor $\\textsf{nmExt}$ takes two inputs, a weakly-random $W$ and a uniformly random seed $S$, and outputs a string which is nearly uniform, given $S$ as well as $\\textsf{nmExt}(W, \\mathcal{A}(S))$, for an arbitrary function $\\mathcal{A}$ with $\\mathcal{A}(S) \\neq S$.

Cohen, Raz and Segev in CCC\'12 presented an explicit construction of a non-malleable extractor with short seeds. For any integers $n$ and $d$ such that $2.01 \\cdot \\log n \\leq d \\leq n$, they proposed an explicit construction of a non-malleable extractor $\\textsf{nmExt}: \\{0, 1\\}^n \\times \\{0, 1\\}^d \\rightarrow \\{0, 1\\}^m$ with error exponentially small in $m$. However, their result suffers from some drawbacks: First, the non-malleable extractor is constructed based on Raz\'s etractor in SOTC\'05, while the error estimation in that construction is too rough. Second, though they aimed to shorten the length of the seed, the lower bound of the seed length is not optimal. Moreover, their construction requires the min-entropy rate to be greater than $\\frac{1}{2}$.

In this paper, we improve the error estimation of Raz\'s extractor, which plays an extremely important role in the constraints of the non-malleable extractor parameters including the seed length. Then we present an improved explicit construction of non-malleable extractors with shorter seed length by using biased variable sequence for linear tests. More precisely, we construct an explicit $(1016, \\frac{1}{2})-1-$non-malleable extractor $\\textsf{nmExt}: \\{0, 1\\}^{2^{10}} \\times \\{0, 1\\}^d \\rightarrow \\{0, 1\\}$ with seed length 19, while it should be no less than $\\frac{46}{63} + 66$ according to Cohen et al. in CCC\'12. Therefore, it beats the condition ``$2.01 \\cdot \\log n \\leq d \\leq n$\", since $d$ is just $1.9 \\cdot \\log n$ in our construction. We also give a general explicit construction of non-malleable extractors and analyze the simplification of the constraints on the parameters.

Furthermore, we show an explicit construction of non-malleable extractors for the min-entropy $k = ( \\frac{1}{2} - \\delta)n$ for some constant $ \\delta > 0$, while the min-entropy should be greater than $ \\frac{1}{2} n$ by Cohen et al. in CCC\'12. We also propose a general construction of non-malleable extractors with min-entropy $k = ( \\frac{1}{2} - \\delta)n$ from any non-malleable extractor with min-entropy $k > \\frac{1}{2} n$ by employing a special encoding technique and the property of statical distance. Compared with Li\'s construction in FOCS\'12 by using inner product function, our construction is more general. Finally, we give their application to privacy amplification.

19:17 [Pub][ePrint] CLOC: Authenticated Encryption for Short Input, by Tetsu Iwata and Kazuhiko Minematsu and Jian Guo and Sumio Morioka

  We define and analyze the security of a blockcipher mode of operation, CLOC, for provably secure authenticated encryption with associated data. The design of CLOC aims at optimizing previous schemes, CCM, EAX, and EAX-prime, in terms of the implementation overhead beyond the blockcipher, the precomputation complexity, and the memory requirement. With these features, CLOC is suitable for handling short input data, say 16 bytes, without needing precomputation nor large memory. This property is especially beneficial to small microprocessors, where the word size is typically 8 bits or 16 bits, and there are significant restrictions in the size and the number of registers. CLOC uses a variant of CFB mode in its encryption part and a variant of CBC MAC in the authentication part. We introduce various design techniques in order to achieve the above mentioned design goals. We prove CLOC secure, in a reduction-based provable security paradigm, under the assumption that the blockcipher is a pseudorandom permutation. We also present our preliminary implementation results.

16:17 [Pub][ePrint] Security Analysis of Key-Alternating Feistel Ciphers, by Rodolphe Lampe and Yannick Seurin

  We study the security of \\emph{key-alternating Feistel} ciphers, a class of key-alternating ciphers with a Feistel structure. Alternatively, this may be viewed as the study of Feistel ciphers where the pseudorandom round functions are of the form $F_i(x\\oplus k_i)$, where $k_i$ is the (secret) round key and $F_i$ is a \\emph{public} random function that the adversary is allowed to query in a black-box way. Interestingly, our results can be seen as a generalization of traditional results \\emph{à la} Luby-Rackoff in the sense that we can derive results for this model by simply letting the number of queries of the adversary to the public random functions $F_i$ be zero in our general bounds. We make an extensive use of the coupling technique. In particular (and as a result of independent interest), we improve the analysis of the coupling probability for balanced Feistel schemes previously carried out by Hoang and Rogaway (CRYPTO 2010).

16:17 [Pub][ePrint] A Statistics-based Fundamental Model for Side-channel Attack Analysis, by Yunsi Fei and A. Adam Ding and Jian Lao and Liwei Zhang

  ide-channel attacks (SCAs) exploit leakage from the physical implementation of cryptographic algorithms to recover the otherwise secret information. In the last decade, popular SCAs like differential power analysis (DPA) and correlation power analysis (CPA) have been invented and demonstrated to be realistic threats to many critical embedded systems. However, there is still no sound and provable theoretical model that illustrates precisely what the success of these attacks depends on and how. Based on the maximum likelihood estimation (MLE) theory, this paper proposes a general statistical model for side-channel attack analysis that takes characteristics of both the physical implementation and cryptographic algorithm into consideration. The model establishes analytical relations between the success rate of attacks and the cryptographic system. For power analysis attacks, the side-channel characteristic of the physical implementation is modeled as signal-to-noise ratio (SNR), which is the ratio between the single-bit unit power consumption and the standard deviation of power distribution. The side-channel property of the cryptographic algorithm is extracted by a novel algorithmic confusion analysis. Experimental results of DPA and CPA on both DES and AES verify this model with high accuracy and demonstrate effectiveness of the algorithmic confusion analysis and SNR extraction. We expect the model to be extendable to other SCAs, like timing attacks, and would provide valuable guidelines for truly SCA-resilient system design and implementation.

16:17 [Pub][ePrint] Verifiable Oblivious Storage, by Daniel Apon and Jonathan Katz and Elaine Shi and Aishwarya Thiruvengadam

  We formalize the notion of Verifiable Oblivious Storage (VOS), where a client outsources the storage of data to a server while ensuring data confidentiality, access pattern privacy, and integrity and freshness of data accesses. VOS generalizes the notion of Oblivious RAM (ORAM) in that it allows the server to perform computation, and also explicitly considers data integrity and freshness.

We show that allowing server-side computation enables us to

construct asymptotically more efficient VOS schemes whose bandwidth overhead cannot be matched by any ORAM scheme, due to a known lower bound by Goldreich and Ostrovsky. Specifically, for large block sizes

we can construct a VOS scheme with constant bandwidth per query; further, answering queries requires only poly-logarithmic

server computation. We describe applications of VOS to Dynamic Proofs of Retrievability, and RAM-model secure multi-party computation.

16:17 [Pub][ePrint] Non-Interactive Cryptography in the RAM Model of Computation, by Daniel Apon and Xiong Fan and Jonathan Katz and Feng-Hao Liu and Elaine Shi and Hong-Sheng Zhou

  Using recently developed techniques for program obfuscation, we show several constructions of non-interactive cryptosystems in the random-access machine (RAM) model of computation that are asymptotically more efficient than what would be obtained using generic RAM-to-circuit compilation. In particular, let $T$ denote the running time and $n$ the memory size of a RAM program. We show that using differing-inputs obfuscation, functional encryption for arbitrary RAM programs can be achieved with evaluation time $\\tilde{O}(T+n)$.

Additionally, we provide a number of RAM-model constructions assuming

the stronger notion of virtual black-box (VBB) obfuscation. We view these as initial feasibility results and leave instantiating similar protocols from weaker assumptions for future work. Specifically, using VBB obfuscation we show how to construct RAM-model functional encryption with function privacy, fully homomorphic encryption, and stateful, privacy-preserving verifiable computation in the memory-delegation model.

16:17 [Pub][ePrint] Honey Encryption: Security Beyond the Brute-Force Bound, by Ari Juels and Thomas Ristenpart

  We introduce {\\em honey encryption} (HE), a simple, general approach to encrypting messages using low min-entropy keys such as passwords. HE is designed to produce a ciphertext which, when decrypted with any of a number of {\\em incorrect} keys, yields plausible-looking but bogus plaintexts called {\\em honey messages}. A key benefit of HE is that it provides security in cases where too little entropy is available to withstand brute-force attacks that try every key; in this sense, HE provides security beyond conventional brute-force bounds. HE can also provide a hedge against partial disclosure of high min-entropy keys.

HE significantly improves security in a number of practical settings. To showcase this improvement, we build concrete HE schemes for password-based encryption of RSA secret keys and credit card numbers. The key challenges are development of appropriate instances of a new type of randomized message encoding scheme called a {\\em distribution-transforming encoder} (DTE), and analyses of the expected maximum loading of bins in various kinds of balls-and-bins games.

01:17 [Pub][ePrint] On the Effective Prevention of TLS Man-In-The-Middle Attacks in Web Applications, by Nikolaos Karapanos and Srdjan Capkun

  In this paper we consider TLS MITM attacks in the context of web applications, where the attacker\'s goal is to impersonate the user to the legitimate server, and thus gain access to the user\'s online account. We describe in detail why the recently proposed TLS Channel ID-based client authentication, as well as client web authentication in general, cannot fully prevent such attacks.

We then leverage TLS Channel ID-based authentication and combine it with the concept of sender invariance to create a novel mechanism that we call SISCA: Server Invariance with Strong Client Authentication. SISCA resists user impersonation via TLS MITM attacks even if the attacker has obtained the private key of the legitimate server. We analyze our proposal and show how it can be integrated in today\'s web infrastructure.

22:17 [Pub][ePrint] The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields, by Razvan Barbulescu and Cécile Pierrot

  In this paper, we study the discrete logarithm problem in medium and

high characteristic finite fields. We propose a variant of the Number Field Sieve (NFS) based on numerous number fields. Our improved algorithm computes discrete logarithms in $\\mathbb{F}_{p^n}$ for the whole range of applicability of NFS and lowers the asymptotic complexity from $L_{p^n}(1/3, (128/9)^{1/3})$ to $L_{p^n}(1/3, (2^{13} /3^6)^{1/3})$ in the medium characteristic case, and from $L_{p^n} (1/3, (64/9)^{1/3})$ to $L_{p^n}(1/3,((92 + 26\\sqrt{13})/27))^{1/3})$ in the high characteristic case.

22:17 [Pub][ePrint] Outsourcing Private RAM Computation, by Craig Gentry and Shai Halevi and Mariana Raykova and Daniel Wichs

  We construct the first schemes that allow a client to privately outsource arbitrary program executions to a remote server while ensuring that: (I) the client\'s work is small and essentially independent of the complexity of the computation being outsourced, and (II) the server\'s work is only proportional to the run-time of the computation on a random access machine (RAM), rather than its potentially much larger circuit size. Furthermore, our solutions are non-interactive and have the structure of reusable garbled RAM programs, addressing an open question of Lu and Ostrovsky (Eurocrypt 2013). We also construct schemes for an augmented variant of the above scenario, where the client can initially outsource a large private and persistent database to the server, and later outsource arbitrary program executions with read/write access to this database.

Our solutions are built from non-reusable garbled RAM in conjunction with new types of reusable garbled circuits that are more efficient than prior solutions but only satisfy weaker security. For the basic setting without a persistent database, we can instantiate the required reusable garbled circuits using indistinguishability obfuscation. For the more complex setting with a persistent database we need stronger notions of obfuscation. Our basic solution also requires the client to perform a one-time preprocessing step to garble a program at the cost of its RAM run-time, and we can avoid this cost using stronger notions of obfuscation. It remains an open problem to instantiate these new types of reusable garbled circuits under weaker assumptions, possibly avoiding obfuscation altogether.