International Association
for Cryptologic Research

We construct a structure-preserving signature scheme that is selectively randomizable and works in all types of bilinear groups. We give matching lower bounds showing that our structure-preserving signature scheme is optimal with respect to both signature size and public verification key size.

State of the art structure-preserving signatures in the asymmetric setting consist of 3 group elements, which is known to be optimal. Our construction preserves the signature size of 3 group elements and also at the same time minimizes the verification key size to 1 group element.

Depending on the application, it is sometimes desirable to have strong unforgeability and in other situations desirable to have randomizable signatures. To get the best of both worlds, we introduce the notion of selective randomizability where the signer may for specific signatures provide randomization tokens that enable randomization.

Our structure-preserving signature scheme unifies the different pairing-based settings since it can be instantiated in both symmetric and asymmetric groups. Since previously optimal structure-preserving signatures had only been constructed in asymmetric bilinear groups this closes an important gap in our knowledge. Having a unified signature scheme that works in all types of bilinear groups is not just conceptually nice but also gives a hedge against future cryptanalytic attacks. An instantiation of our signature scheme in an asymmetric bilinear group may remain secure even if cryptanalysts later discover an efficiently computable homomorphism between the source groups.

Multiple encryption---the practice of composing a blockcipher several

times with itself under independent keys---has received considerable

attention of late from the standpoint of provable security. Despite

these efforts proving definitive security bounds (i.e., with matching

attacks) has remained elusive even for the special case of triple

encryption. In this paper we close the gap by improving both the best

known attacks and best known provable security, so that both bounds

match. Our results apply for arbitrary number of rounds and show that

the security of $\\ell$-round multiple encryption is precisely

$\\exp(\\kappa + \\min\\{\\kappa (\\ell\'-2)/2), n (\\ell\'-2)/\\ell\'\\})$ where

$\\exp(t) = 2^t$ and where $\\ell\' = 2\\lceil \\ell/2\\rceil$ is the even

integer closest to $\\ell$ and greater than or equal to $\\ell$, for all

$\\ell \\geq 1$. Our technique is based on Patarin\'s H-coefficient

method and reuses a combinatorial result of Chen and Steinberger

originally required in the context of key-alternating ciphers.

We propose a new and simple framework for constructing fully homomorphic encryption (FHE) which is completely different from the previous work. We use finite non-commutative (a.k.a., non-abelian) groups which are \"highly non-commutative\" (e.g., the special linear groups of size two) as the underlying structure. We show that, on such groups, the AND and NOT operations on plaintext bits (which are sufficient to realize an arbitrary operation by composing them) can be emulated by a \"randomized commutator\" (which essentially requires the non-commutativity) and division operations on ciphertext elements, respectively. Then we aim at concealing the \"core structure\" of ciphertexts by taking conjugation by a secret element (where the non-commutativity is again essential), rather than adding noise to the ciphertext as in the previous FHE schemes. The \"noise-freeness\" of our framework yields the fully-homomorphic property directly, without the bootstrapping technique used in the previous schemes to remove the noise amplified by the homomorphic operations. This makes the overall structure of the FHE schemes significantly simpler and easier to understand. Although a secure instantiation based on the framework has not been found, we hope that the proposed framework itself is of theoretical value, and that the framework is flexible enough to allow a secure instantiation in the future.

Random oracles are powerful cryptographic objects. They facilitate the security proofs of an impressive number of practical cryptosystems ranging from KDM-secure and deterministic encryption to point-function obfuscation and many more. However, due to an uninstantiability result of Canetti, Goldreich, and Halevi (STOC 1998) random oracles have become somewhat controversial. Recently, Bellare, Hoang, and Keelveedhi (BHK; CRYPTO 2013 and ePrint 2013/424, August 2013) introduced a new abstraction called Universal Computational Extractors (UCEs), and showed that they suffice to securely replace random oracles in a number of prominent applications, including all those mentioned above, without suffering from the aforementioned uninstantiability result. This, however, leaves open the question of constructing UCEs in the standard model.

We show that the existence of indistinguishability obfuscation (iO) implies (non-black-box) attacks on all the definitions that BHK proposed within their UCE framework in the original version of their paper, in the sense that no concrete hash function can satisfy them. We also show that this limitation can be overcome, to some extent, by restraining the class of admissible adversaries via a statistical notion of unpredictability. Following our attack, BHK (ePrint 2013/424, September 2013), independently adopted this approach in their work.

In the updated version of their paper, BHK (ePrint 2013/424, September 2013) also introduce two other novel source classes, called bounded parallel sources and split sources, which aim at recovering the computational applications of UCEs that fall outside the statistical fix. These notions keep to a computational notion of unpredictability, but impose structural restrictions on the adversary so that our original iO attack no longer applies. We extend our attack to show that indistinguishability obfuscation is sufficient to also break the UCE security of any hash function against bounded parallel sources. Towards this goal, we use the randomized encodings paradigm of Applebaum, Ishai, and Kushilevitz (STOC 2004) to parallelize the obfuscated circuit used in our attack, so that it can be computed by a bounded parallel source whose second stage consists of constant-depth circuits. We conclude by discussing the composability and feasibility of hash functions secure against split sources.

Name: Nizamuddin
Topic: On the Design of signcryption Schemes
Category: public-key cryptography

We consider secret key agreement by multiple parties observing correlated data and communicating interactively over an insecure communication channel. Our main contribution is a single-shot upper bound on the length of the secret keys that can be generated, without making any assumptions on the distribution of the underlying data. Heuristically, we bound the secret key length in terms of ``how far\" is the joint distribution of the initial observations of the parties and the eavesdropper from a distribution that renders the observations of the parties conditionally independent across some partition, when conditioned on the eavesdropper\'s side information.

The closeness of the two distributions is measured in terms of the exponent of the probability of error of type II for a binary hypothesis testing problem, thus bringing out a structural connection between secret key agreement and binary hypothesis testing. When the underlying data consists of an independent and identically distributed sequence, an application of our bound recovers several known upper bounds for the asymptotic rate of a secret key that can be generated, without requiring the agreement error probability or the security index to vanish to 0 asymptotically.

Also, we consider the following problem of secure function computation with trusted parties: Multiple parties observing correlated data seek to compute a function of their collective data. To this end, they communicate interactively over an insecure communication channel. It is required that the value of the function be concealed from an eavesdropper with access to the communication. When is such a secure computation of a given function feasible? Using the aforementioned upper bound, we derive a necessary condition for the existence of a communication protocol that allows the parties to reliably recover the value of a given function, while keeping this value concealed from an eavesdropper with access to (only) the communication.

PRINCE is a lightweight block cipher proposed by Borghoff et al. at Asiacrypt 2012. Due to its originality, novel design and low number of rounds, it has already attracted the attention of a large number of

cryptanalysts. Several results on reduced versions have been published

to date; the best one is an attack on 8 rounds out of the total number

of 12. In this paper we improve this result by two rounds: we provide

an attack on 10 rounds of the cipher with a data complexity of $2^{57.94}$ and a time complexity of $2^{60.62}$, corresponding to 118.56 security bits, instead of 126 for the generic attacks. Our attack uses multiple differentials and exploits some properties of PRINCE for recovering the whole key. PRINCE is defined as a member of a family of ciphers, differing by the choice of an Sbox among a distinguished set. We also show that the security offered by all the members of the family is not equivalent, by identifying an Sbox for which our attack can be extended up to 11 rounds with a data complexity of $2^{59.81}$ and a time complexity of $2^{62.43}$.

Due to the recent emergence of resource-constrained devices, cryptographers are facing the problem of designing dedicated lightweight ciphers. KLEIN is one of the resulting primitives, proposed at RFIDSec in 2011 by Gong et al. This family of software-oriented block ciphers has an innovative structure, as it combines 4-bit Sboxes with the AES MixColumn transformation, and has woken up the attention of cryptanalysts. Several security analyses have been published, in particular on the 64-bit key version. The best of these results could attack up to 8 rounds out of the total number of 12. In this paper we propose a new family of attacks that can cryptanalyze for the first time all the 12 rounds of the complete version of KLEIN-64. Our attacks use truncated differential paths and are based both on some of the notions developed in previous attacks and on our new ideas that allow to considerably improve the performance. To prove the validity of our attacks, we have implemented reduced-round versions of them. In particular we were able to reproduce a practical attack that recovers the whole key on 10 rounds, which also corresponds to the best practical attack against KLEIN-64.

In this paper, we investigate matrices acting on finite commutative groups and rings; in fact, we study modules on ring of matrices over Z_N and also modules over the ring (F_2^t,\\oplus,\\land); these new algebraic constructions are a generalization of some of the constructions which were previously presented by the authors of this paper. We present new linearized and nonlinear MDS diffusion layers, based on this mathematical investigation. Then, we study some types of nonlinear number generators over Z_(2^n ) and we present a lower bound on the period of these new nonlinear number generators. As a consequence, we present nonlinear recurrent sequences over Z_(2^n ) with periods which are multiples of the period of the corresponding

sigma-LFSR\'s.

In this paper, we present a new type of PKC, system-oriented PKC,referred to as K(I)SOPKC that can be well adapted to a secure and a high speed communication between various systems and organizations of the present day network society.

K(I)SOPKC is constructed on the basis of K(XIV)SE(1)PKC, a modified version of K(XII)SE(1)PKC, K(XIII)SE(1)PKC and ${\\rm K_p(XIII)SE(1)PKC}$.

It is well known that the classical three- and four-round Feistel constructions are provably secure under chosen-plaintext and chosen-ciphertext attacks, respectively. However, irrespective of the number of rounds, no Feistel construction can resist related-key attacks where the keys can be offset by a constant. In this paper we show that, under suitable reuse of round keys, security under related-key attacks can be provably attained. Our modification is substantially simpler and more efficient than alternatives obtained using generic transforms, namely the PRG transform of Bellare and Cash (CRYPTO 2010) and its random-oracle analogue outlined by Lucks (FSE 2004).

Additionally we formalize Luck\'s transform and show that it does not always work if related keys are derived in an oracle-dependent way, and then prove it sound under appropriate restrictions.

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

computations.

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.

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

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.

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.

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.

Submission: 11 April 2014
Notification: 6 June 2014
From September 15 to September 18
Location: Victoria, Canada
More Information: http://www.nspw.org/2014/cfp

From May 5 to May 9
Location: Aarhus, Denmark
More Information: http://ctic.au.dk/workshops-conferences/mpc-2014/

Submission: 31 March 2014
Notification: 23 May 2014
From September 8 to September 12
Location: Fribourg, Switzerland
More Information: http://www.ectcm.net

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.