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

19:17 [Pub][ePrint] Online Authenticated-Encryption and its Nonce-Reuse Misuse-Resistance, by Viet Tung Hoang and Reza Reyhanitabar and Phillip Rogaway and Damian Vizár

  A definition of \\textit{online authenticated-encryption} (OAE), call it OAE1, was given by Fleischmann, Forler, and Lucks (2012). It has become a popular definitional target because, despite allowing encryption to be online, security is supposed to be maintained even if nonces get reused. We argue that this expectation is effectively wrong. OAE1 security has also been claimed to capture best-possible security for any online-AE scheme. We claim that this understanding is wrong, too. So motivated, we redefine OAE-security, providing a radically different formulation, OAE2. The new notion effectively \\textit{does} capture best-possible security for a user\'s choice of plaintext segmentation and ciphertext expansion. It is achievable by simple techniques from standard tools. Yet even for OAE2, nonce-reuse can still be devastating. The picture to emerge is that no OAE definition can meaningfully tolerate nonce-reuse, but, at the same time, OAE security ought neverhave been understood to turn on this question.

19:17 [Pub][ePrint] Multi-Client Non-Interactive Verifiable Computation, by Seung Geol Choi and Jonathan Katz and Ranjit Kumaresan and Carlos Cid

  Gennaro et al.\\ (Crypto 2010) introduced the notion of \\emph{non-interactive verifiable computation}, which allows a computationally weak client to outsource the computation of a function $f$ on a series of inputs $x^{(1)}, \\ldots$ to a more

powerful but untrusted server. Following a pre-processing phase (that is carried out only once), the client sends some representation of its current input $x^{(i)}$ to the server; the server returns an answer that allows the client to recover the correct result $f(x^{(i)})$, accompanied by a proof of correctness that ensures the client does not accept an incorrect result. The crucial property is that the work done by the client in preparing its input and verifying the server\'s proof is less than the time required for the client to compute~$f$ on its own.

We extend this notion to the \\emph{multi-client} setting, where $n$ computationally weak clients wish to outsource to an untrusted server the computation of a function $f$ over a series of {\\em joint} inputs $(x_1^{(1)}, \\ldots, x_{\\clients}^{(1)}), \\ldots$ without interacting with each other. We present a construction for this setting by combining the scheme of Gennaro et al.\\ with a primitive called proxy oblivious transfer.

19:17 [Pub][ePrint] iDASH Secure Genome Analysis Competition Using ObliVM, by Xiao Shaun Wang, Chang Liu, Kartik Nayak, Yan Huang and Elaine Shi

  This is a short note in supplement to our ObliVM paper.

19:17 [Pub][ePrint] Memory-saving computation of the pairing final exponentiation on BN curves, by Sylvain DUQUESNE and Loubna GHAMMAM

  In this paper, we describe and improve efficient methods for computing

the hard part of the final exponentiation of pairings on Barreto-Naehrig


Thanks to the variants of pairings which decrease the length of the Miller

loop, the final exponentiation has become a significant component of the

overall calculation. Here we exploit the structure of BN curves to improve

this computation.

We will first present the most famous methods in the literature that en-

sure the computing of the hard part of the final exponentiation. We are

particularly interested in the memory resources necessary for the implementation of these methods. Indeed, this is an important constraint in

restricted environments.

More precisely, we are studying Devegili et al. method, Scott et al. addition chain method and Fuentes et al. method. After recalling these methods and their complexities, we determine the number of required registers

to compute the final result, because this is not always given in the literature. Then, we will present new versions of these methods which require

less memory resources (up to 37%). Moreover, some of these variants are

providing algorithms which are also more efficient than the original ones.

19:17 [Pub][ePrint] Improving Modular Inversion in RNS using the Plus-Minus Method, by Karim Bigou and Arnaud Tisserand

  The paper describes a new RNS modular inversion algorithm based on the extended Euclidean algorithm and the plus-minus trick. In our algorithm, comparisons over large RNS values are replaced by cheap computations modulo 4. Comparisons to an RNS version based on Fermat\'s little theorem were carried out. The number of elementary modular operations is significantly reduced: a factor 12 to 26 for multiplications and 6 to 21 for additions. Virtex 5 FPGAs implementations show that for a similar area, our plus-minus RNS modular inversion is 6 to 10 times faster.

19:17 [Pub][ePrint] Practical Homomorphic MACs for Arithmetic Circuits, by Dario Catalano and Dario Fiore

  Homomorphic message authenticators allow the holder of a (public) evaluation key to perform computations over previously authenticated data, in such a way that the produced tag $\\sigma$ can be used to certify the authenticity of the computation. More precisely, a user knowing the secret key $\\sk$ used to authenticate the original data, can verify that $\\sigma$ authenticates the correct output of the computation. This primitive has been recently formalized by Gennaro and Wichs, who also showed how to realize it from fully homomorphic encryption. In this paper, we show new constructions of this primitive that, while supporting a smaller set of functionalities (i.e., polynomially-bounded arithmetic circuits as opposite to boolean ones), are much more efficient and easy to implement. Moreover, our schemes can tolerate any number of (malicious) verification queries. Our first construction relies on the sole assumption that one way functions exist, allows for arbitrary composition (i.e., outputs of previously authenticated computations can be used as inputs for new ones) but has the drawback that the size of the produced tags grows with the degree of the circuit. Our second solution, relying on the $D$-Diffie-Hellman Inversion assumption, offers somewhat orthogonal features as it allows for very short tags (one single group element!) but poses some restrictions on the composition side.

19:17 [Pub][ePrint] Zero-knowledge Argument for Polynomial Evaluation with Application to Blacklists, by Stephanie Bayer and Jens Groth

  Verification of a polynomial\'s evaluation in a secret committed value plays a role in cryptographic applications such as non-membership or membership proofs. We construct a novel special honest verifier zero-knowledge argument for correct polynomial evaluation. The argument has logarithmic communication cost in the degree of the polynomial, which is a significant improvement over the state of the art with cubic root complexity at best. The argument is relatively efficient to generate and very fast to verify compared to previous work. The argument has a simple public-coin 3-move structure and only relies on the discrete logarithm assumption.

The polynomial evaluation argument can be used as a building block to construct zero-knowledge membership and non-membership arguments with communication that is logarithmic in the size of the blacklist. Non-membership proofs can be used to design anonymous blacklisting schemes allowing online services to block misbehaving users without learning the identity of the user. They also allow the blocking of single users of anonymization networks without blocking the whole


19:17 [Pub][ePrint] Tighter Reductions for Forward-Secure Signature Schemes, by Michel Abdalla and Fabrice Benhamouda and David Pointcheval

  In this paper, we revisit the security of factoring-based signature schemes built via the Fiat-Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the $\\phi$-hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion recently introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-security setting based on ideas from the Itkis-Reyzin forward-secure signature scheme. Unlike the original Itkis-Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter security reduction. Finally, we show that the tighter security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-security setting, as long as the use of stronger security assumptions is deemed acceptable. All of our results hold in the random oracle model.

19:17 [Pub][ePrint] SCA Resistance Analysis of Sponge based MAC-PHOTON, by N. Nalla Anandakumar

  PHOTON is a lightweight hash function which was proposed

by Guo et al. in CRYPTO 2011 for low-resource ubiquitous computing

devices such as RFID tags, wireless sensor nodes and smart cards. In

this paper, we analyze Side-Channel Attack (SCA) resistance of FPGA

(Field-Programmable Gate Array) implementations of the PHOTON, when

it is used with a secret key to generate a Message Authentication Code (MAC). First, we describe three architectures of the MAC-PHOTON based on the concepts of iterative, folding and unrolling, and we provide their performance results on the Xilinx Virtex-5 FPGAs. Second, we analysed security of the MAC-PHOTON against side-channel attack using a SASEBOGII development board.

19:17 [Pub][ePrint] Side-Channel Protection by Randomizing Look-Up Tables on Reconfigurable Hardware - Pitfalls of Memory Primitives, by Pascal Sasdrich and Oliver Mischke and Amir Moradi and Tim Güneysu

  Block Memory Content Scrambling (BMS), presented at CHES 2011, enables an effective way of first-order side-channel protection for cryptographic primitives at the cost of a significant reconfiguration time for the mask update. In this work we analyze alternative ways to implement dynamic first-order masking of AES with randomized look-up tables that can reduce this mask update time. The memory primitives we consider in this work include three distributed RAM components (RAM32M, RAM64M, and RAM256X1S) and one BRAM primitive (RAMB8BWER). We provide a detailed study of the area and time overheads of each implementation technique with respect to the operation (encryption) as well as reconfiguration (mask update) phase. We further compare the achieved security of each technique to prevent first-order side-channel leakages. Our evaluation is based on one of the most general forms of leakage assessment methodology known as non-specific t-test. Practical SCA evaluations (using a Spartan-6 FPGA platform) demonstrate that solely the BRAM primitive but none of the distributed RAM elements can be used to realize an SCA-protected implementation.

19:17 [Pub][ePrint] Side-Channel Security Analysis of Ultra-Low-Power FRAM-based MCUs, by Amir Moradi and Gesine Hinterwälder

  By shrinking the technology and reducing the energy requirements of integrated circuits, producing ultra-low-power devices has practically become possible. Texas Instruments as a pioneer in developing FRAM-based products announced a couple of different microcontroller (MCU) families based on the low-power and fast Ferroelectric RAM technology. Such MCUs come with embedded cryptographic module(s) as well as the assertion that - due to the underlying ultra-low-power technology - mounting successful side-channel analysis (SCA) attacks has become very difficult. In this work we practically evaluate this claimed hardness by means of state-of-the-art power analysis attacks. The leakage sources and corresponding attacks are presented in order to give an overview on the potential risks of making use of such platforms in security-related applications. In short, we partially confirm the given assertion. Some modules, e.g., the embedded cryptographic accelerator, can still be attacked but with slightly immoderate effort. On the contrary, the other leakage sources are easily exploitable leading to straightforward attacks being able to recover the secrets.