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

16:17 [Pub][ePrint] Faster Bootstrapping with Polynomial Error, by Jacob Alperin-Sheriff and Chris Peikert

  \\emph{Bootstrapping} is a technique, originally due to Gentry (STOC

2009), for ``refreshing\'\' ciphertexts of a somewhat homomorphic

encryption scheme so that they can support further homomorphic

operations. To date, bootstrapping remains the only known way of

obtaining fully homomorphic encryption for arbitrary unbounded


Over the past few years, several works have dramatically improved the

efficiency of bootstrapping and the hardness assumptions needed to

implement it. Recently, Brakerski and Vaikuntanathan~(ITCS~2014)

reached the major milestone of a bootstrapping algorithm based on

Learning With Errors for \\emph{polynomial} approximation factors.

Their method uses the Gentry-Sahai-Waters~(GSW)

cryptosystem~(CRYPTO~2013) in conjunction with Barrington\'s ``circuit

sequentialization\'\' theorem~(STOC~1986). This approach, however,

results in \\emph{very large} polynomial runtimes and approximation

factors. (The approximation factors can be improved, but at even

greater costs in runtime and space.)

In this work we give a new bootstrapping algorithm whose runtime and

associated approximation factor are both \\emph{small} polynomials.

Unlike most previous methods, ours implements an elementary and

efficient \\emph{arithmetic} procedure, thereby avoiding the

inefficiencies inherent to the use of boolean circuits and

Barrington\'s Theorem. For $2^{\\lambda}$ security under conventional

lattice assumptions, our method requires only a \\emph{quasi-linear}

$\\Otil(\\lambda)$ number of homomorphic operations on GSW ciphertexts,

which is optimal (up to polylogarithmic factors) for schemes that

encrypt just one bit per ciphertext. As a contribution of independent

interest, we also give a technically simpler variant of the GSW system

and a tighter error analysis for its homomorphic operations.

16:17 [Pub][ePrint] RECTANGLE: A Bit-slice Ultra-Lightweight Block Cipher Suitable for Multiple Platforms, by Wentao Zhang and Zhenzhen Bao and Dongdai Lin and Vincent Rijmen and Bohan Yang and Ingrid Verbauwhede

  In this paper, we propose a new lightweight block cipher named RECT-

ANGLE. The main idea of the design of RECTANGLE is to allow lightweight

and fast implementations using bit-slice techniques. RECTANGLE uses an SP-

network. The substitution layer consists of 16 4×4 S-boxes in parallel. The per-

mutation layer is composed of 3 rotations. As shown in this paper, RECTAN-

GLE offers great performance in both hardware and software environment, which

proves enough flexibility for different application scenario. The following are 3

main advantages of RECTANGLE. First, RECTANGLE is extremely hardware-

friendly. For the 80-bit key version, a one-cycle-per-round parallel implementa-

tion only needs 1467 gates for a throughput of 246 Kbits/sec at 100KHz clock

and an energy efficiency of 1.11 pJ/bit. Second, RECTANGLE achieves a very

competitive software speed among the existing lightweight block ciphers due to

its bit-slice style. Using 128-bit SSE instructions, a bit-slice implementation of

RECTANGLE reaches an average encryption speed of about 5.38 cycles/byte for

messages around 1000 bytes. Last but not least. We propose new design criteria

for 4×4 S-boxes. RECTANGLE uses such a new type of S-box. Due to our care-

ful selection of the S-box and the asymmetric design of the permutation layer,

RECTANGLE achieves a very good security-performance tradeoff. Our exten-

sive and deep security analysis finds distinguishers for up to 14 rounds only, and

the highest number of rounds that we can attack, is 18 (out of 25).

16:17 [Pub][ePrint] Multipermutations in Crypto World: Different Faces of the Perfect Diffusion Layer, by Aleksandra Mileva

  Diffusion layers, and specially perfect diffusion layers, are very important subject for cryptographic research. Main quest is a perfect diffusion layer with more optimal hardware and/or software implementations (if possible, the last needs to holds also for its inverse). Different structures can be used for representing these layers, but all are interconnected. We start with multipermutations as a tools for obtaining perfect diffusion, and we summarize the interconnections between them, MDS codes, Latin squares and quasigroups, orthogonal arrays and $m$-arcs. We give a new construction of perfect recursive diffusion layer from $r$-recursive MDS codes, or recursively $r$-differentiable quasigroups.

16:17 [Pub][ePrint] Randomized and Efficient Authentication in Mobile Environments, by Wei Jiang, Dan Lin, Feng Li, Elisa Bertino

  In a mobile environment, a number of users act as a network nodes and communicate with one another to acquire location based information and services. This emerging paradigm has opened up new business opportunities and enables numerous applications such as road safety enhancement, service recommendations and mobile entertainment. A fundamental issue that impacts the success of these applications is the security and privacy concerns raised regarding the mobile users. In that, a malicious user or service provider can track the locations of a user traveled so that other malicious act can be carried out more effectively against the user. Therefore, the challenge becomes how to authenticate mobile users while preserving their actual identity and location privacy. In this work, we propose a novel randomized or privacy-preserving authentication protocol based on homomorphic encryption. The protocol allows individual users to self generate any number of authenticated identities to achieve full anonymity in mobile environment. The proposed protocol prevents users being tracked by any single party including peer users, service providers, authentication servers, and other infrastructure. Meanwhile, our protocol also provides traceability in case of any dispute. We have conducted experimental study which demonstrates

the efficiency of our protocol. Another advantage of the proposed protocol is lightweight computation and storage requirement, particularly suitable for any mobile devices with limited computation power and storage space.

16:17 [Pub][ePrint] AnoA: A Framework For Analyzing Anonymous Communication Protocols, by Michael Backes and Aniket Kate and Praveen Manoharan and Sebastian Meiser and Esfandiar Mohammadi

  Protecting individuals\' privacy in online communications has become a challenge of paramount importance. To this end, anonymous communication (AC) protocols such as the widely used Tor network have been designed to provide anonymity to their participating users. While AC protocols have been the subject of several security and anonymity analyses in the last years, there still does not exist a framework for analyzing complex systems such as Tor and their different anonymity properties in a unified manner.

In this work we present AnoA: a generic framework for defining, analyzing, and quantifying anonymity properties for AC protocols. AnoA relies on a novel relaxation of the notion of (computational) differential privacy, and thereby enables a unified quantitative analysis of well- established anonymity properties, such as sender anonymity, sender unlinkability, and relationship anonymity. While an anonymity analysis in AnoA can be conducted in a purely information theoretical manner, we show that the protocol\'s anonymity properties established in AnoA carry over to secure cryptographic instantiations of the protocol. We exemplify the applicability of AnoA for analyzing real-life systems by conducting a thorough analysis of the anonymity properties provided by the Tor network against passive adversarys. Our analysis significantly improves on known anonymity results from the literature.

05:59 [Event][New] NSPW'14: 2014 New Security Paradigms Workshop

  Submission: 11 April 2014
Notification: 6 June 2014
From September 15 to September 18
Location: Victoria, Canada
More Information:

15:45 [Event][New] MPC14: Workshop on Theory and Practice of Secure Multiparty Computation

  From May 5 to May 9
Location: Aarhus, Denmark
More Information:

15:41 [Event][New] ECTCM 2014: Second International Workshop on Emerging Cyberthreats and Countermeasures

  Submission: 31 March 2014
Notification: 23 May 2014
From September 8 to September 12
Location: Fribourg, Switzerland
More Information:

16:17 [Pub][ePrint] A Full Characterization of Completeness for Two-party Randomized Function Evaluation, by Daniel Kraschewski and Hemanta K. Maji and Manoj Prabhakaran and Amit Sahai

  We settle a long standing open problem which has pursued a full characterization of completeness of (potentially randomized) finite functions for 2-party computation that is secure against active adversaries. Since the first such complete function was discovered [Kilian, FOCS 1988], the question of which finite 2-party functions are complete has been studied extensively, leading to characterization in many special cases. In this work, we completely settle this problem.

We provide a polynomial time algorithm to test whether a 2-party finite secure function evaluation (SFE) functionality (possibly randomized) is complete or not. The main tools in our solution include:

-- A formal linear algebraic notion of {\\em redundancy} in a general 2-party randomized function.

-- A notion of {\\em statistically testable games}. A kind of interactive proof in the information-theoretic setting where {\\em both} parties are computationally unbounded but differ in their knowledge of a secret.

-- An extension of the (weak) {\\em converse of Shannon\'s channel coding theorem}, where an adversary can adaptively choose the channel based on it view.

We show that any function $f$, if complete, can implement any (randomized) circuit $C$ using only $O(|C| + k)$ calls to $f$, where $k$ is the statistical security parameter. In particular, for any two-party functionality $g$, this establishes a universal notion of its quantitative ``cryptographic complexity\'\' independent of the setup and has close connections to circuit complexity.

16:17 [Pub][ePrint] Efficient Round Optimal Blind Signatures, by Sanjam Garg and Divya Gupta

  Known constructions of blind signature schemes suffer from at least one of the following limitations: (1) rely on parties having access to a common reference string or a random oracle, (2) are not round-optimal, or (3) are prohibitively expensive.

In this work, we construct the \\emph{first} blind-signature scheme that does not suffer from any of these limitations. In other words, besides being round optimal and having a standard model proof of security, our scheme is very efficient. Specifically, in our scheme, one signature is of size $6.5$ KB and the communication complexity of the signing protocol is roughly $100$ KB. An amortized variant of our scheme has communication complexity less that $1$ KB.

16:17 [Pub][ePrint] Garbled RAM Revisited, Part I, by Craig Gentry and Shai Halevi and Mariana Raykova and Daniel Wichs

  The notion of *garbled random-access machines* (garbled RAMs) was introduced by Lu and Ostrovsky (Eurocrypt 2013). It can be seen as an analogue of Yao\'s garbled circuits, that allows a user to garble a RAM program directly, without performing the expensive step of converting it into a circuit. In particular, the size of the garbled program and the time it takes to create and evaluate it are only proportional to its running time on a RAM rather than its circuit size. Lu and Ostrovsky gave a candidate construction of this primitive based on pseudo-random functions (PRFs).

The starting point of this work is a subtle yet difficult-to-overcome issue with the Lu-Ostrovsky construction, that prevents a proof of security from going through. Specifically, the construction requires a complex \"circular\" use of Yao garbled circuits and PRFs. As our main result, we show how to remove this circularity and get a provably secure solution using *identity-based encryption* (IBE). We also abstract out, simplify and generalize the main ideas behind the Lu-Ostrovsky construction, making them easier to understand and analyze.

In a companion work to ours (Part II), Lu and Ostrovsky show an alternative approach to solving the circularity problem. Their approach relies only on the existence of one-way functions, at the price of higher overhead. Specifically, our construction has overhead $\\poly(k)\\polylog(n)$ (with $k$ the security parameter and $n$ the data size), while the Lu-Ostrovsky approach can achieve overhead $\\poly(k)n^\\eps$ for any constant $\\eps>0$. It remains as an open problem to achieve an overhead of $\\poly(k)\\polylog(n)$ assuming only the existence of one-way functions.