*06:17* [Pub][ePrint]
Recomputing with Permuted Operands: A Concurrent Error Detection Approach, by Xiaofei Guo and Ramesh Karri
Naturally occurring and maliciously injected faults reduce the reliability of cryptographic hardware and may leak confidential information. We develop a concurrent error detection (CED) technique called Recomputing with Permuted Operands (REPO). We show that it is cost effective in Advanced Encryption Standard (AES) and a secure hashfunction Grøstl. We provide experimental results and formal proofs to show that REPO detects all single-bit and single-byte faults. Experimental results show that REPO achieves close to 100% fault coverage for multiple byte faults. The hardware and throughput overheads are compared with those of previously reported CED techinques on two Xilinx Virtex FPGAs. The hardware overhead is 12.4-27.3%, and the throughput is 1.2-23Gbps, depending on the AES architecture, FPGA family, and detection latency. The performance overhead ranges from 10% to 100% depending on the security

level. Moreover, the proposed technique can be integrated into various block cipher modes of operation. We also discuss the limitation of REPO and its potential vulnerabilities.

*06:17* [Pub][ePrint]
Modelling Time, or A Step Towards Reduction-based Security Proofs for OTP and Kerberos, by Jörg Schwenk
The notion of time plays an important role in many practically deployed cryptographic protocols, ranging from One-Time-Password (OTP) tokens to the Kerberos protocol. However, time is difficult to model in a Turing machine environment.We propose the first such model, where time is modelled as a global counter T . We argue that this model closely matches several implementations of time in computer environments. The usefulness of the model is shown by giving complexity-theoretic security proofs for OTP protocols, HMQV-like one-round AKE protocols, and a variant of the basic Kerberos building block.

*06:17* [Pub][ePrint]
Revocable quantum timed-release encryption, by Dominique Unruh
Timed-release encryption is a kind of encryption scheme that arecipient can decrypt only after a specified amount of time T

(assuming that we have a moderately precise estimate of his computing

power). A revocable timed-release encryption is one where,

before the time T is over, the sender can \"give back\" the

timed-release encryption, provably loosing all access to the data. We

show that revocable timed-release encryption without trusted parties

is possible using quantum cryptography (while trivially impossible

classically).

Along the way, we develop two proof techniques in the quantum random

oracle model that we believe may have applications also for other

protocols.

Finally, we also develop another new primitive, unknown recipient

encryption, which allows us to send a message to an

unknown/unspecified recipient over an insecure network in such a way

that at most one recipient will get the message.

*06:17* [Pub][ePrint]
How to Further Increase Leakage Exploitation Rate in Profiled Side-Channel Attacks?, by Guangjun Fan and Yongbin Zhou and Hailong Zhang and Dengguo Feng
Template Attack is widely accepted to be one of the most powerful side-channel attacks, because it is assumed that one has full knowledge of targeted crypto devices and thus be well capable of characterizing the side-channel leakages. However, whether or not Template Attack exploits side-channel leakages to the fullest is still not clear. In this paper, we present a negative answer to this central question, by introducing a normalization process into original Template Attack. We present Normalized Template Attack, which has the normalization process. Furthermore, we prove that Normalized Template Attack is better that its original counterpart in terms of leakage exploitation rate. We evaluate the key-recovery efficiency of Normalized Template Attack and original Template Attack as well under identical scenarios, by performing attacks against both simulated and real power traces. Our experimental results show that our method is valid end effective. Remarkably enough, this normalization process is of extremely low computation cost. Therefore, we argue that thenormalization process should be integrated as a necessary part of profile attacks in order to better understand the practical threats of these attacks.

*06:17* [Pub][ePrint]
Limited-birthday Distinguishers for Hash Functions - Collisions Beyond the Birthday Bound can be Meaningful, by Mitsugu Iwamoto and Thomas Peyrin and Yu Sasaki
In this article, we investigate the use of limited-birthday distinguishers to the context of hash functions. We first provide a proper understanding of the limited-birthday problem and demonstrate its soundness by using a new security notion Differential Target Collision Resistance (dTCR) that is related to the classical Target Collision Resistance (TCR) notion. We then solve an open problem and close the existing security gap by proving that the best known generic attack proposed at FSE 2010 for the limited-birthday problem is indeed the best possible method.Moreover, we show that almost all known collision attacks are in fact more than just a collision finding algorithm, since the difference mask for the message input is usually fixed. A direct and surprising corollary is that these collision attacks are interesting for cryptanalysis even when their complexity goes beyond the $2^{n/2}$ birthday bound and up to the $2^{n}$ preimage bound, and can be used to derive distinguishers using the limited-birthday problem. Interestingly, cryptanalysts can now search for collision attacks beyond the $2^{n/2}$ birthday bound.

Finally, we describe a generic algorithm that turns a semi-free-start collision attack on a compression function (even if its complexity is beyond the birthday bound) into a distinguisher on the whole hash function when its internal state is not too wide. To the best of our knowledge, this is the first result that exploits classical semi-free-start collisions on the compression function to exhibit a weakness on the whole hash function. As an application of our findings, we provide distinguishers on reduced or full version of several hash functions, such as RIPEMD-128, SHA-256, Whirlpool, etc.

*06:17* [Pub][ePrint]
Sub-linear Blind Ring Signatures without Random Oracles, by Essam Ghadafi
Ring signatures allow a signer to anonymously sign a message on behalf of a set of arbitrarily chosen signers called a ``ring\'\'. Blind signatures, on the other hand, allow a user to obtain a signature on a message while maintaining the privacy of the message.

Blind ring signatures combine properties of both primitives and hence provide a strong notion of anonymity where the privacy of both the identity of the signer and the message is preserved.

Blind ring signatures find applications in various systems; including multi-authority e-voting and distributed e-cash systems.

In this paper we provide the first provably secure blind ring signature construction that does not rely on random oracles, which solves an open problem raised by Herranz and Laguillaumie at ISC 2006. We present different instantiations all of which are round-optimal (i.e.\\ have a two-move signing protocol), yield sub-linear size signatures, and meet strong security requirements.

In order to realize our constructions efficiently, we construct a sub-linear size set membership proof which works in the different bilinear group settings, which may be of independent interest.

As a secondary contribution, we show how to generically combine our set membership proof with any secure signature scheme meeting some conditions to obtain ring signatures whose security does not rely on random oracles. All our constructions work over the efficient prime-order bilinear group setting and yield signatures of sub-linear size. In addition, our constructions meet strong security requirements: namely, anonymity holds under full key exposure and unforgeability holds against insider-corruption.

Finally, we provide some example instantiations of the generic construction.