International Association
for Cryptologic Research

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.

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.

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

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.

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.

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.

This paper introduces Multi-Stage Fault Attacks, which allow Differential Fault Analysis of block ciphers having independent subkeys. Besides the specification of an algorithm implementing the technique, we show concrete applications to LED-128 and PRINCE and demonstrate that in both cases approximately 3 to 4 fault-injections are enough to reconstruct the full 128-bit key.

We investigate an application of Radio Frequency Identification (RFID) referred to in the literature as group scanning, in which an RFID reader device interrogates several RFID tags to establish \"simultaneous\" presence of a group of tags. Our goal is to study the group scanning problem in strong adversarial settings and show how group scanning can be used in distributed applications for supply chain management.

We present a security framework for group scanning and give a formal description of the attending security requirements. Our model is based on the Universal Composability framework and supports re-usability

(through modularity of security guarantees). We propose two novel protocols that realize group scanning in this security model, based on off-the-shelf components such as low-cost (highly optimized) pseudorandom functions, and show how these can be integrated into RFID supply-chain management systems

Rabbit stream cipher is one of the finalists of eSTREAM

project which uses 128-bit secret keys. Prior to us, the attacks on Rabbit

has been all focused on the bias analysis and the best result showed the

distinguishing attack with complexity 2136. Our analysis in this paper,

is based on chosen IV analysis on reduced N-S round of Rabbit though

using multi cube tester. For this purpose we show for a mature cube

we could easily identify weak subcubes which increase the probability of

distinguishing for an unknown secret key. We also represent with 225

complexity, using one iteration of next state function the keystream is

completely distinguishable from random.

We define a notion of semantic security of multi-linear

(a.k.a. graded) encoding schemes: roughly speaking, we require that if

an algebraic attacker (obeying the multi-linear restrictions) cannot tell

apart two constant-length sequences $\\vec{m}_0$, $\\vec{m}_1$ in the

presence of some other elements $\\vec{z}$, then

encodings of these sequences should be indistinguishable.

Assuming the existence of semantically secure multi-linear encodings

and the LWE assumption, we demonstrate the existence of

indistinguishability obfuscators for all polynomial-size circuits.

Additionally, if we assume an strengthening of

semantic security, our construction yields extractatability

obfuscators for all polynomial-size circuits.

We rely on the beautiful candidate obfuscation constructions

of Garg et al (FOCS\'13), Brakerski and Rothblum (TCC\'14) and Barak et

al (ePrint\'13) that were proven secure only in idealized generic

multilinear encoding models,

and develop new techniques for demonstrating security in the standard model, based only on

semantical security of multi-linear encoding (which trivially holds in

the generic multilinear encoding model).

The Bitcoin scheme is one of the most popular and talked about alternative payment schemes. It was conceived in 2008 by the mysterious Satoshi Nakamoto, whose real identity remains unknown even

though his bitcoin holdings are believed to be worth several hundred

million dollars. One of the most active parts of the Bitcoin ecosystem was the Silk Road marketplace, in which highly illegal substances and services were traded. It was run by another mysterious person who called himself Dread Pirate Roberts (DPR), whose bitcoin holdings are also estimated to be worth hundreds of millions of dollars at today\'s exchange rate. On October 1-st 2013, the FBI arrested a 29 year old person named Ross William Ulbricht, claiming that he is DPR, and seizing a small fraction of his bitcoin wealth. In this paper we use the publicly available record to trace the evolution of his holdings in order to find how he acquired and how he tried to hide them from the authorities. For example, we show that all his income from the months of May, June and September 2013, along with numerous other amounts, were not seized by the FBI. One of the most surprising discoveries we made during our analysis was the existence of a recent substantial transfer (which was worth more than 60,000 dollars when made on March 20-th 2013, and close to a million dollars at today\'s exchange rate) which may link these two mysterious figures.

In this paper we propose a new approach to code-based signatures that

makes use in particular of rank metric codes. When the classical approach consists in finding the unique

preimage of a syndrome through a decoding algorithm, we propose to introduce the notion

of mixed decoding of erasures and errors for building signature schemes.

In that case the difficult problem becomes, as is the case in lattice-based cryptography,

finding a preimage of weight above the Gilbert-Varshamov bound (case where

many solutions occur) rather than finding a unique preimage of weight below

the Gilbert-Varshamov bound. The paper describes RankSign: a

new signature algorithm for the rank metric

based on a new mixed algorithm for decoding erasures and errors for

the recently introduced Low Rank Parity Check (LRPC) codes.

We explain how it is possible (depending on choices

of parameters) to obtain a full decoding algorithm which is able

to find a preimage of reasonable rank weight for any random syndrome

with a very strong probability. We study the semantic security

of our signature algorithm and show how it is possible to reduce

the unforgeability to direct attacks on the public matrix, so that

no information leaks through signatures. Finally, we give several examples of parameters

for our scheme, some of which with public key of size $5760$ bits and signature of size $1728$ bits.

Moreover the scheme can be very fast for small base fields.

Submission: 15 March 2014
Notification: 15 April 2014
From June 24 to June 26
Location: Putrajaya, Malaysia
More Information: http://einspem.upm.edu.my/cryptology2014/

Elliptic Curve Cryptography can be vulnerable to Side-Channel Attacks, such as the Zero Power Analysis (ZPA).

This attack takes advantage of the occurrence of special points that bring a zero-value when computing a doubling or an addition of points.

This paper consists in analysing this attack.

Some properties of the said special points are explicited.

A novel dynamic countermeasure is described.

The elliptic curve formul\\ae{} are updated depending on the elliptic curve and the provided base point.

While the hybrid public key encryption scheme of Kurosawa and Desmedt (CRYPTO 2004) is provably secure against chosen ciphertext attacks (namely, IND-CCA-secure), its associated key encapsulation mechanism (KEM) is not IND-CCA-secure (Herranz et al. 2006, Choi et al. 2009). In this paper, we show a simple twist, yet neglected in the literature, on the Kurosawa-Desmedt KEM turning it into a scheme with IND-CCA security under the decisional Diffie-Hellman assumption. Our KEM beats the standardized version of Cramer-Shoup KEM in ISO/IEC 18033-2 by margins of around 30% in encapsulation speed, and 20% ~ 60% in decapsulation speed. Moreover, the public and secret key sizes in our schemes are at least 160-bit smaller than those of the Cramer-Shoup KEM. We then generalize the technique into hash proof systems, proposing several KEM schemes with IND-CCA security under decision linear and decisional composite residuosity assumptions respectively. All the KEMs are in the standard model, and use standard, computationally secure symmetric building blocks.

This paper describes software optimization for the stream Cipher ChaCha. We leverage the wide vectorization capabilities of the new AVX2 architecture, to speed up ChaCha encryption (and decryption) on the latest x86_64 processors. In addition, we show how to apply vectorization for the future AVX512 architecture, and get further speedup. This leads to significant performance gains. For example, on the latest Intel Haswell microarchitecture, our AVX2 implementation performs at 1.43 cycles per byte (on a 4KB message), which is ~2x faster than the current implementation in the Chromium project.

We explain the origins of Boolean feedback functions of nonlinear feedback shift registers (NLFSRs) of fixed order n generating de Bruijn binary sequences. They all come into existence by cross joining operations starting from one maximum period feedback shift register, e.g., a linear one which always exists for any order n. The result obtained yields some constructions of NLFSRs generating maximum period $ 2^n-1 $ binary sequences.

In this paper, we investigate the multi-user setting both in public-key and in secret-key cryptanalytic applications. In this setting, the adversary tries to recover keys of many users in parallel more efficiently than with classical attacks, \\textit{i.e.}, the number of recovered keys multiplied by the time complexity to find a single key, by amortizing the cost among several users. One possible scenario is to recover a single key in a large set of users more efficiently than to recover a key in the classical model. Another possibility is, after some shared precomputation, to be able to learn individual keys very efficiently. This latter model is close to traditional time/memory tradeoff attacks with precomputation. With these goals in mind, we introduce two new algorithmic ideas to improve collision-based attacks in the multi-user setting. Both ideas are derived from the parallelizable collision search as proposed by van~Oorschot and Wiener.

We recall that this collision search uses precomputed chains obtained by iterating some basic function. In our cryptanalytic application, each pair of merging chains can be used to correlate the key of two distinct users. The first idea is to construct a graph, whose vertices are keys and whose edges are these correlations. When the graph becomes connected, we simultaneously recover all the keys. Thanks to random graph analysis techniques, we can show that the number of edges that are needed to make this event occurs is small enough to obtain some improved attacks.

The second idea modifies the basic technique of van~Oorschot and Wiener: instead of waiting for two chains to merge, we now require that they become {\\it parallel}.

We first show that, using the first idea alone, we can recover the discrete logs of $L$ users in a group of size $N$ in time $\\widetilde{O}(\\sqrt{NL})$, without any special restriction on the value of $L$. As a first application of these two ideas put together, we show that in the multi-user Even-Mansour scheme, \\textit{all} the keys of $L=N^{1/3}$ users can be found with $N^{1/3+\\epsilon}$ queries for each user (where $N$ is the domain size). Finally, we consider the PRINCE block cipher (with 128-bit keys and 64-bit blocks) and find the keys of $2$ users among a set of $2^{32}$ users in time $2^{65}$. We also describe a new generic attack in the classical model for PRINCE that is better than all published attacks.

Revocation and key evolving paradigms are central issues in cryptography, and in PKI in particular. A novel concern related to these areas was raised in the recent work of Sahai, Seyalioglu, and Waters (Crypto 2012) who noticed that revoking past keys should at times (e.g., the scenario of cloud storage) be accompanied by revocation of past ciphertexts (to prevent unread ciphertexts from being read by revoked users). They introduced revocable-storage attribute-based encryption (RS-ABE) as a good access control mechanism for cloud storage. RS-ABE protects against the revoked users not only the future data by supporting key-revocation but also the past data by supporting ciphertext-update, through which a ciphertext at time $T$ can be updated to a new ciphertext at time $T+1$ using only the public key.

Motivated by this pioneering work, we ask whether it is possible to have a modular approach, which includes a primitive for time managed ciphertext update as a primitive. We call encryption which supports this primitive a ``self-updatable encryption\'\' (SUE). We then suggest a modular cryptosystems design methodology based on three sub-components: a primary encryption scheme, a key-revocation mechanism, and a time-evolution mechanism which controls the ciphertext self-updating via an SUE method, coordinated with the revocation (when needed). Our goal in this is to allow the self-updating ciphertext component to take part in the design of new and improved cryptosystems and protocols in a flexible fashion. Specifically, we achieve the following results:

- We first introduce a new cryptographic primitive called self-updatable encryption (SUE), realizing a time-evolution mechanism. In SUE, a ciphertext and a private key are associated with time. A user can decrypt a ciphertext if its time is earlier than that of his private key. Additionally, anyone (e.g., a cloud server) can update the ciphertext to a ciphertext with a newer time. We also construct an SUE scheme and prove its full security under static assumptions.

- Following our modular approach, we present a new RS-ABE scheme with shorter ciphertexts than that of Sahai et al. and prove its security. The length efficiency is mainly due to our SUE scheme and the underlying modularity.

- We apply our approach to predicate encryption (PE) supporting attribute-hiding property, and obtain a revocable-storage PE (RS-PE) scheme that is selectively-secure.

- We further demonstrate that SUE is of independent interest, by showing it can be used for timed-release encryption (and its applications), and for augmenting key-insulated encryption with forward-secure storage.

In this paper, we propose a reasonable definition of predicate-hiding inner product encryption (IPE) in a public key setting, which we call inner product encryption with ciphertext conversion (IPE-CC), where original ciphertexts are converted to predicate-searchable ones by an helper in possession of a conversion key. We then define a notion of full security for IPE-CC, which comprises three security properties of being adaptively predicate- and attribute-hiding in the public key setting, adaptively (fully-)attribute-hiding against the helper, and usefully secure even against the private-key generator (PKG). We then present the first fully secure IPE-CC scheme, and convert it into the first fully secure symmetric-key IPE (SIPE) scheme, where the security is defined in the sense of Shen, Shi, Waters. All the security properties are proven under the decisional linear assumption in the standard model. The IPE-CC scheme is comparably as efficient as existing attribute-hiding (not predicate-hiding) IPE schemes. We also present a variant of the proposed IPE-CC scheme with the same security that achieves shorter public and secret keys. We

employ two key techniques, trapdoor basis setup, in which a new trapdoor is embedded in a public key, and multi-system proof technique, which further generalizes an extended dual system approach given by Okamoto and Takashima recently.