International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service 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).

2013-11-25
22:17 [Pub][ePrint] Misuse Resistant Parallel Authenticated Encryptions, by Mridul Nandi and Nilanjan Datta

  The authenticated encryptions which resist misuse of initial value (or nonce) at some desired level of privacy are two-pass or Mac-then-Encrypt constructions (inherently inefficient but provide full privacy) and online constructions, e.g., McOE, sponge-type authenticated encryptions (such as duplex, AEGIS) and COPA. Only the last one is almost parallelizable with some bottleneck in processing associated data. In this paper, {\\em we design a new online secure authenticated encryption, called \\tx{ELmE} or Encrypt-Linear mix-Encrypt, which is completely (two-stage) {\\bf parallel} (even in associated data) and {\\bf pipeline implementable}}. It also provides full privacy when associated data (which includes initial value) is not repeated. The basic idea of our construction and COPA are based on \\tx{EME}, an Encrypt-Mix-Encrypt type SPRP constructions (secure against chosen plaintext and ciphertext). Unlike \\tx{EME}, we consider (so does COPA) online computable {\\bf linear mixing}. In addition with getting rid of bottleneck, our construction optionally supports {\\bf intermediate tags} which can be verified faster with less buffer size. Intermediate tag provides security against block-wise adversaries which is meaningful in low-end device implementation.



22:17 [Pub][ePrint] VMPC-R Cryptographically Secure Pseudo-Random Number Generator Alternative to RC4, by Bartosz Zoltak

  We present a new Cryptographically Secure Pseudo-Random Number Generator. It uses permutations as its internal state, similarly to the RC4 stream cipher. We describe a statistical test which revealed non-random patterns in a sample of $2^{16.6}$ outputs of a 3-bit RC4.

Our new algorithm produced $2^{46.8}$ undistinguishable from random 3-bit outputs in the same test. We probed $2^{51}$ outputs of the algorithm in different statistical tests with different word sizes

and found no way of distinguishing the keystream from a random source. The size of the algorithm\'s internal state is $2^{3424}$ (for an 8-bit implementation). The algorithm is cryptographically secure to the extent we were able to analyse it. Its design is simple and easy to implement. We present the generator along with a key scheduling algorithm processing both keys and initialization vectors.



22:17 [Pub][ePrint] Broadcast Amplification, by Martin Hirt and Ueli Maurer and Pavel Raykov

  A $d$-broadcast primitive is a communication primitive that allows a

sender to send a value from a domain of size $d$ to a set of parties.

A broadcast protocol emulates the $d$-broadcast primitive using only

point-to-point channels, even if some of the parties cheat, in

the sense that all correct recipients agree on the same value $v$

(consistency), and if the sender is correct, then $v$ is the value

sent by the sender (validity). A celebrated result by Pease, Shostak

and Lamport states that such a broadcast protocol exists if and only if $t 3$ no broadcast amplification

is possible, i.e., $\\phi_n(d)=d$ for any $d$.

However, if other parties than the sender can also broadcast some

short messages, then broadcast amplification is possible for

\\emph{any}~$n$. Let $\\phi^*_n(d)$ denote the minimal $d\'$ such that

$d$-broadcast can be constructed from primitives $d\'_1$-broadcast,

\\ldots, $d\'_k$-broadcast, where $d\'=\\prod_i d\'_i$ (i.e., $\\log

d\'=\\sum_i \\log d\'_i$). Note that $\\phi^*_n(d)\\leq\\phi_n(d)$.

We show that broadcasting $8n\\log n$ bits in

total suffices, independently of $d$, and that at least $n-2$ parties,

including the sender, must broadcast at least one bit. Hence

$\\min(\\log d,n-2) \\leq \\log \\phi^*_n(d) \\leq 8n\\log n$.



22:17 [Pub][ePrint] Efficient Template Attacks, by Omar Choudary and Markus G. Kuhn

  Template attacks remain a powerful side-channel technique to

eavesdrop on tamper-resistant hardware. They model the probability

distribution of leaking signals and noise to guide a

search for secret data values. In practice, several numerical

obstacles can arise when implementing such attacks

with multivariate normal distributions.

We propose

efficient methods to avoid these. We also demonstrate how to achieve

significant performance improvements, both in terms of information

extracted and computational cost, by pooling covariance estimates

across all data values. We provide a detailed and systematic

overview of many different options for implementing such

attacks. Our experimental evaluation of all these methods based on

measuring the supply current of a byte-load instruction executed in

an unprotected 8-bit microcontroller leads to practical guidance for

choosing an attack algorithm.



22:17 [Pub][ePrint] TOT, a Fast Multivariate Public Key Cryptosystem with Basic Secure Trapdoor, by Wuqiang Shen and Shaohua Tang

  In this paper, we design a novel one-way trapdoor function, and then propose a new multivariate public key cryptosystem called $\\rm TOT$, which can be used for encryption, signature and authentication. Through analysis, we declare that $\\rm TOT$ is secure, because it can resist current known algebraic attacks if its parameters are properly chosen. Some practical implementations for $\\rm TOT$ are also given, and whose security level is at least $2^{90}$. The comparison shows that $\\rm TOT$ is more secure than $\\rm HFE$, $\\rm HFEv$ and $\\rm Quartz$ (when $n \\ge 81$ and $D_{HFE} \\ge 129$, $\\rm HFE$ is still secure), and it can reach almost the same speed of computing the secret map by $\\rm C^\\ast$ and $\\rm Sflash^{v2}$ (even though $\\rm C^\\ast$ was broken, its high speed has been affirmed).



22:17 [Pub][ePrint] Beyond Modes: Building a Secure Record Protocol from a Cryptographic Sponge Permutation, by Markku-Juhani O. Saarinen

  BLINKER is a light-weight cryptographic suite and record protocol built from a single permutation. Its design is based on the Sponge construction used by the SHA-3 algorithm KECCAK. We examine the SpongeWrap authenticated encryption mode and expand its padding mechanism to offer explicit domain separation and enhanced security for our specific requirements: shared secret half-duplex keying, encryption, and a MAC-and-continue mode. We motivate these enhancements by showing that unlike legacy protocols, the resulting record protocol is secure against a two-channel synchronization attack while also having a significantly smaller implementation footprint. The design facilitates security proofs directly from a single cryptographic primitive (a single security assumption) rather than via idealization of multitude of algorithms, paddings and modes of operation. The protocol is also uniquely suitable for an autonomous or semi-autonomous hardware implementation of protocols where the secrets never leave the module, making it attractive for smart card and HSM designs.



22:17 [Pub][ePrint] CBEAM: Efficient Authenticated Encryption from Feebly One-Way $\\phi$ Functions, by Markku-Juhani O. Saarinen

  We show how efficient and secure cryptographic mixing functions can be constructed from low-degree rotation-invariant $\\phi$ functions rather than conventional S-Boxes. These novel functions have surprising properties; many exhibit inherent feeble (Boolean circuit) one-wayness and offer speed/area tradeoffs unobtainable with traditional constructs. Recent theoretical results indicate that even if the inverse is not explicitly computed in an implementation, its degree plays a fundamental role to the security of the iterated composition. To illustrate these properties, we present CBEAM, a Cryptographic Sponge Permutation based on a single $5 \\times 1$-bit Boolean function. This simple nonlinear function is used to construct a 16-bit rotation-invariant$\\phi$ function of Degree 4 (but with a very complex Degree 11 inverse), which in turn is expanded into an efficient 256-bit mixing function. In addition to flexible tradeoffs in hardware we show that efficient implementation strategies exist for software platforms ranging from low-end microcontrollers to the very latest x86-64 AVX2 instruction set. A rotational bit-sliced software implementation offers not only comparable speeds to AES but also increased security against cache side channel attacks. Our construction supports Sponge-based Authenticated Encryption, Hashing, and PRF/PRNG modes and is highly useful as a compact ``all-in-one\'\' primitive for pervasive security.



22:17 [Pub][ePrint] Multi-Input Functional Encryption, by S. Dov Gordon and Jonathan Katz and Feng-Hao Liu and Elaine Shi and Hong-Sheng Zhou

  \\emph{Functional encryption} (FE) is a powerful primitive enabling fine-grained access to encrypted data. In an FE scheme, secret keys (``tokens\'\') correspond to functions; a user in possession of a

ciphertext $\\ct = \\enc(x)$ and a token $\\tkf$ for the function~$f$

can compute $f(x)$ but learn nothing else about~$x$. An active area of research over the past few years has focused on the development of ever more expressive FE schemes.

In this work we introduce the notion of \\emph{multi-input} functional encryption. Here, informally, a user in possession of a token $\\tkf$ for an $n$-ary function $f$ and \\emph{multiple} ciphertexts $\\ct_1=\\enc(x_1)$, \\ldots, $\\ct_n=\\enc(x_n)$ can compute $f(x_1, \\ldots, x_n)$ but nothing else about the~$\\{x_i\\}$.

Besides introducing the notion, we explore the feasibility of multi-input FE in the public-key and symmetric-key settings, with respect to both indistinguishability-based and simulation-based definitions of security.



22:17 [Pub][ePrint] Differential Cryptanalysis and Linear Distinguisher of Full-Round Zorro, by Yanfeng Wang, Wenling Wu, Zhiyuan Guo and Xiaoli Yu

  Zorro is an AES-like lightweight block cipher proposed in CHES 2013, which only uses 4 S-boxes per round. The designers showed the resistance of the cipher against various attacks and concluded the cipher has a large security margin. Recently, Guo et. al have given a key recovery attack on full-round Zorro by using the internal differential characteristics. However, the attack only works for $2^{64}$ out of $2^{128}$ keys. In this paper, the secret key selected randomly from the whole key space can be recovered with a time complexity of $2^{108}$ full-round Zorro encryptions and a data complexity of $2^{112.4}$ chosen plaintexts. We first observe that the fourth power of the MDS matrix used in Zorro equals to the identity matrix. Moveover, several iterated differential characteristics and iterated linear trails are found due to the interesting property. We select three characteristics with the largest probability to give a key recovery attack on Zorro and a linear trail with the largest correlation to show a a linear distinguishing attack with $2^{105.3}$ known plaintexts. The results show that the security of Zorro against linear and differential cryptanalysis evaluated by designers is insufficient and the block cipher Zorro is far from a random permutation.



22:17 [Pub][ePrint] Location Leakage in Distance Bounding: Why Location Privacy does not Work, by Aikaterini Mitrokotsa and Cristina Onete and Serge Vaudenay

  In many cases, we can only have access to a service by proving we are sufficiently close to a particular location (e.g. in automobile or building access control). In these cases, proximity can be guaranteed through signal attenuation. However, by using additional transmitters an attacker can relay signals between the prover and the verifier. Distance-bounding protocols are the main countermeasure against such attacks; however, such protocols may leak information regarding the location of the prover and/or the verifier who run the distance-bounding protocol.

In this paper, we consider a formal model for location privacy in the context of distance-bounding. In particular, our contributions are threefold: we first define a security game for location privacy in distance-bounding; secondly, we define an adversarial model for this game, with two adversary classes; finally, we assess the feasibility of attaining location privacy for distance-bounding protocols. Concretely, we prove that for protocols with a beginning or a termination, it is theoretically impossible to achieve location privacy for either of the two adversary classes, in the sense that there always exists a polynomially bounded adversary that wins the security game. However, for so-called limited adversaries, which cannot see the location of arbitrary provers, carefully chosen parameters do, in practice, enable computational location privacy.



22:17 [Pub][ePrint] Construction of Multiplicative Monotone Span Program, by Yuenai Chen and Chunming Tang

  Multiplicative monotone span program is one of the important tools to realize secure multiparty computation. It is essential to construct multiplicative monotone span programs for secure multiparty computations. For any access structure, Cramer et al. gave a method to construct multiplicative monotone span programs, but its row size became double, and the column size also increased. In this paper, we propose a new construction which can get a multiplicative monotone span program with the row size less than double without changing the column size.