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

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-21
19:17 [Pub][ePrint]

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.

19:17 [Pub][ePrint]

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.

19:17 [Pub][ePrint]

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.

19:17 [Pub][ePrint]

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.

2013-11-20
19:17 [Forum]

I wanted to give my perspective to this discussion as someone from the early to mid career range and who just went through the tenure process. Like everyone else, I had a certain amount of anxiety attached to tenure evaluation. During the process, I discovered that it was very helpful that the IACR conferences of CRYPTO, Eurocrypt, and Asiacrypt were well recognized and had established strong reputations in the broader community. I was pleasantly surprised to find that the reputation of our conferences and workshops had reached colleagues that worked in very different areas. Clearly, the credit for the excellent standing of our conferences and workshops belongs to the foundations built by researchers and IACR members over many years. I appreciate the efforts by people to continue to improve our publication process and I think that there are multiple good ideas out there. However, I have a significant amount of concern about the most far reaching proposals to remove (and replace) our established conferences. While I understand many of the thoughts behind this, I believe it is very important to not undervalue what we already have. In practice, the reputation of publication venues is what people in other areas depend upon in tenure and other evaluations. Having conferences of the stature of ours is not easy to come by and requires a long investment of time. I believe that there would be significant downsides to abandoning them, especially to young researchers. On a more personal note, I have enjoyed each of the experiences of submission, review, and attending attached to our conferences. While nothing is perfect, I found our conference culture to be very helpful and welcoming when I began as a researcher. -Brent From: 2013-20-11 17:31:53 (UTC)

2013-11-18
10:57 [Election]

The official results for the IACR 2012 election is now available at /elections/2013/.

10:09 [Event][New]

Submission: 7 March 2014
From June 23 to June 25
Location: Heraklion, Greece

2013-11-17
04:17 [Pub][ePrint]

This paper presents an efficient and side channel protected software implementation of point multiplication for the standard NIST and SECG binary elliptic curves. The enhanced performance is achieved by improving the L\\`{o}pez-Dahab/Montgomery method at the algorithmic level, and by leveraging Intel\'s AVX architecture and the pclmulqdq processor instruction at the coding level.

The fast carry-less multiplication is further used to speed up the reduction on the newest Haswell platforms.

For the five NIST curves over $GF(2^m)$ with $m$ $\\in$ $\\{163,233,283,409,571\\}$, the resulting point multiplication implementation is about 6 to 12 times faster than that of OpenSSL-1.0.1e, enhancing the ECDHE and ECDSA algorithms significantly.

04:17 [Pub][ePrint]

{\\begin{tabbing}

\\hspace{0,3 cm}\\=\\hspace{0,7 cm}\\=\\hspace{8 cm}\\=\\kill

Kernel of the symmetric block ciphering methods presented here is the coupling of XOR operations\\\\

and of invertible substitution tables S with all possible 256$^{t}$ byte groups (with t=1, 2, 3, ... bytes,\\\\

fixed at the beginning) being derived from keys:\\\\

\\>\\>\\textbf{K}(block) := S(S(block) $\\otimes$ E$_{o}$) $\\otimes$ E$_{u}$ with\\\\

-\\> E$_{o}$ upper and E$_{u}$ lower triangular (byte-group-)matrix with (byte-block-length/t)$^{2}$ values,\\\\

\\> value 1 at all non-zero positions,\\\\

-\\> $\\oplus$ the byte-group-wise addition without carry (\'xor\'; \'not xor\' is possible too),\\\\

-\\> $\\otimes$ the (vector) multiplication which belongs to $\\oplus$.\\\\

Variable block lengths (v$\\cdot$t or (mod t)$>$0) are possible. This kernel can be applied n-times:\\\\

\\>\\>\\textbf{K}$_{\\textbf{n}}$(block) := K(...K(block)...) with n K-operations, in which n can be variable.\\\\

Because XOR operations and S-tables only operate in a useful manner if \'block\' is not to\\\\

\"{}homogeneous\"{} and for safety, two further components are determined from keys\\\\

\\>\\>- parameters of 2 pseudo random processes,\\>- operation key\\\\

used at beginning and at end to get a ciphered block:\\\\

\\>\\>\\textbf{cblock} := S(ZZ$_{2}$ $\\oplus$ S(Op$_{E}$ $\\oplus$ S(K$_{n}$(Op$_{A}$ $\\oplus$ S(ZZ$_{1}$ $\\oplus$ S(block)))))) with\\\\

-\\> ZZ$_{1}$ and ZZ$_{2}$ are the bytes of the 1. and 2. pseudo random number process in block length,\\\\

-\\> Op$_{A}$ and Op$_{E}$ is the (1./front and 2./back part of the or multiple of the) operation key.

\\end{tabbing}

An initial key is first expanded to t$\\cdot$256$^{t}$ bytes (all further keys have this size too) and can be modified so the result key does not statistically differ from a random key.

Using an invertible S-table, the value (modulo n) of only as much consecutive bits of a key as to represent the number n-1 is determined to shift the last n S-table elements cyclically in accordance with this value, n=2 to 256$^{t}$. So all such 256$^{t}$! tables can be generated by the top bits of all possible keys and have length of t$\\cdot$256$^{t}$ bytes.

The byte-group-value +1 at a position of a S-table determines the byte-group in the key from which up 2$\\cdot$7 bytes are used to initialize two floating point numbers (IEEE 754) for a pseudo random process. Floating point numbers are initialized again if a process will be cyclic.\\\\

\\\\

Idea is, to modify (operation) keys similar to data blocks to generate and use more or less continual new S-tables, new pseudo random processes, and new operation keys during ciphering data.

Inspections show that in spite of knowledge of 2 of the 3 components S-table, pseudo random parameters, and operation key as well as the knowledge of original and ciphered data it can not infer the missing 3. component if component modifications are carried out \"{}some time\"{}.

As well it is shown that by knowledge of the 3 components generated by a key the key itself can not be inferred (because of usage of interim operation keys). That is compromising of data and with that of components does not concern data ciphered before component-changing to the compromised components. By add-on usage of separate components only for the modifications of keys, it will be guaranteed that data sections ciphered after a component-changing started from compromised components are not compromised automatically.

Because of that a safety stream ciphering should be possible as already constructed for t=1,2,3.

}

04:17 [Pub][ePrint]

Smart meters are widely deployed to provide fine-grained data

that correspond to tenant power consumption. These data are analyzed by suppliers for personalized billing, more accurate statistics and energy consumption predictions.

Indirectly this aggregation of data can reveal personal information of tenants such as number of persons in a house, vacation periods and appliance preferences.

To date, work in the area has focused mainly on privacy preserving aggregate statistical functions as the computation of sum.

In this paper we propose a novel solution for privacy preserving unique data collection per smart meter. We consider the operation of identifying the maximum consumption

of a smart meter as an interesting property for energy suppliers, as it can be employed for energy forecasting to allocate in advance electricity. In our solution we employ an order preserving encryption scheme in which the order of numerical

data is preserved in the ciphertext space. We enhance the accuracy of maximum consumption by utilizing a delta encoding scheme.

04:17 [Pub][ePrint]

This work furthers the exploration of meaningful definitions for security of Functional Encryption. We propose new simulation based definitions for function privacy in addition to data privacy and study their achievability. In addition, we improve efficiency/ underlying assumptions/ security achieved by existing inner product Functional Encryption and Property Preserving Encryption schemes, in both the private and public key setting. Our results can be summarized as follows:

o We present a new simulation based definition, which we call Relax-AD-SIM, that lies between simulation based (SIM) and indistinguishability based (IND) definitions for data privacy, and implies the function privacy definition of [BRS13a]. Our definition relaxes the requirements on the simulator to bypass impossibility of SIM in the standard model. We show that the inner product FE scheme of [KSW08] enjoys Relax-AD-SIM security for function hiding and the inner product FE scheme of [LOS+10] enjoys Relax-AD-SIM security for data hiding.

o We study whether known impossibilities for achieving strong SIM based security imply actual real world attacks. For this, we present a new UC-style SIM based definition of security that captures both data and function hiding, both public key and symmetric key settings and represents the \"dream\" security of FE. While known impossibilities rule out its achievability in the standard model, we show, surprisingly, that it can be achieved in the generic group model for Inner Product FE ([KSW08]). This provides evidence that FE implementations may enjoy extremely strong security against a large class of real world attacks, namely generic attacks. It also implies a program obfuscator for the inner product functionality in the generic group model, which is related to the hyperplane-membership obfuscator of [CRV10].

o We provide several improvements to known constructions of Inner Product FE. In the private key setting, the construction by Shen et al. was based on non-standard assumptions, used composite order groups, and only achieved selective security. We give the first construction of a symmetric key inner product FE which is built using prime order groups, and is fully secure under the standard DLIN assumption. Our scheme is more efficient in the size of key and ciphertext than [SSW09], when the latter is converted to prime-order groups. We also port the public key inner product scheme of [KSW08] to prime order groups.

o We give the first standard model construction of a property preserving encryption (PPE) scheme [PR12] for inner-products. Our scheme is secure under the DLIN assumption and satisfies the strongest definition of security - Left-or-Right security. Note that previously known constructions were only known to be secure in the generic group model.