International Association
for Cryptologic Research

In a traitor tracing scheme, each user is given a different decryption key. A content distributor can encrypt digital content using a public encryption key and each user in the system can decrypt it using her decryption key. Even if a coalition of users combines their decryption keys and constructs some ``pirate decoder\'\' that is capable of decrypting the content, there is a public tracing algorithm that is guaranteed to recover the identity of at least one of the users in the coalition given black-box access to such decoder.

In prior solutions, the users are indexed by numbers $1,\\ldots,N$ and the tracing algorithm recovers the index $i$ of a user in a coalition. Such solutions implicitly require the content distributor to keep a record that associates each index $i$ with the actual identifying information for the corresponding user (e.g., name, address, etc.) in order to ensure accountability. In this work, we construct traitor tracing schemes where all of the identifying information about the user can be embedded directly into the user\'s key and recovered by the tracing algorithm. In particular, the content distributor does not need to separately store any records about the users of the system, and honest users can even remain anonymous to the content distributor.

The main technical difficulty comes in designing tracing algorithms that can handle an exponentially large universe of possible identities, rather than just a polynomial set of indices $i \\in [N]$. We solve this by abstracting out an interesting algorithmic problem that has surprising connections with seemingly unrelated areas in cryptography. We also extend our solution to a full ``broadcast-trace-and-revoke\'\' scheme in which the traced users can subsequently be revoked from the system. Depending on parameters, some of our schemes can be based only on the existence of public-key encryption while others rely on indistinguishability obfuscation.

Protocols for secure computation enable mutually distrustful parties to jointly compute on their private inputs without revealing anything but the result. Over recent years, secure computation has become practical and considerable effort has been made to make it more and more efficient. A highly important tool in the design of two-party protocols is Yao\'s garbled circuit construction (Yao 1986), and multiple optimizations on this primitive have led to performance improvements of orders of magnitude over the last years. However, many of these improvements come at the price of making very strong assumptions on the underlying cryptographic primitives being used (e.g., that AES is secure for related keys, that it is circular secure, and even that it behaves like a random permutation when keyed with a public fixed key). The justification behind making these strong assumptions has been that otherwise it is not possible to achieve fast garbling and thus fast secure computation. In this paper, we take a step back and examine whether it is really the case that such strong assumptions are needed. We provide new methods for garbling that are secure solely under the assumption that the primitive used (e.g., AES) is a pseudorandom function. Our results show that in many cases, the penalty incurred is not significant, and so a more conservative approach to the assumptions being used can be adopted.

We prove that there is no black-box construction of a one-way permutation family from a one-way function and an indistinguishability obfuscator for the class of all oracle-aided circuits, where the construction is \"domain invariant\" (i.e., where each permutation may have its own domain, but these domains are independent of the underlying building blocks).

Following the framework of Asharov and Segev (FOCS \'15), by considering indistinguishability obfuscation for oracle-aided circuits we capture the common techniques that have been used so far in constructions based on indistinguishability obfuscation. These include, in particular, non-black-box techniques such as the punctured programming approach of Sahai and Waters (STOC \'14) and its variants, as well as sub-exponential security assumptions. For example, we fully capture the construction of a trapdoor permutation family from a one-way function and an indistinguishability obfuscator due to Bitansky, Paneth and Wichs (ePrint \'15). Their construction is not domain invariant and our result shows that this, somewhat undesirable property, is unavoidable using the common techniques.

In fact, we observe that constructions which are not domain invariant circumvent all known negative results for constructing one-way permutations based on one-way functions, starting with Rudich\'s seminal work (PhD thesis \'88). We revisit this classic and fundamental problem, and resolve this somewhat surprising gap by ruling out all such black-box constructions -- even those that are not domain invariant.

Although all current scientific white-box approaches of standardized cryptographic primitives are broken, there is still a large number of companies which sell \"secure\" white-box products. In this paper a new approach to assess the security of white-box implementations is presented which requires neither knowledge about the look-up tables used nor any reverse engineering effort. This differential computation analysis (DCA) attack is the software counterpart of the differential power analysis attack as applied by the cryptographic hardware community.

We developed plugins to widely available dynamic binary instrumentation frameworks to produce software execution traces which contain information about the memory addresses being accessed. We show how DCA can extract the secret key from all publicly (non-commercial) available white-box programs implementing standardized cryptography by analyzing these traces to identify secret-key dependent correlations.

Side-channel cryptanalysis is a very efficient class of attacks that recovers secret information by exploiting the physical leakage of a device executing a cryptographic computation. To adress this type of attack, many countermeasures have been proposed, and some papers adressed the question of constructing an efficient masking scheme for existing ciphers. In their work, G.~Piret, T.~Roche and C.~Carlet took the problem the other way around and specifically designed a cipher that would be easy to mask. Their careful analysis, that started with the design of an adapted Sbox, leads to the construction of a 12-round Feistel cipher named PICARO. In this paper, we present the first full-round cryptanalysis of this cipher and show how to recover the key in the related-key model. Our analysis takes advantage of the low diffusion of the key schedule together with the non-bijectivity of PICARO Sbox. Our best trade-off has a time complexity equivalent to $2^{107.4}$ encryptions, a data complexity of $2^{99}$ plaintexts and requires to store $2^{17}$ (plaintext, ciphertext) pairs.

Generally, lattice-based cryptographic primitives offer good performance and allow for strong security reductions. However, the most efficient current lattice-based signature schemes sacrifice (part of its) security to achieve good performance: first, security is based on ideal lattice problems, that might not be as hard as standard lattice problems. Secondly, the security reductions of the most efficient schemes are non-tight; hence, their choices of parameters offer security merely heuristically.

Moreover, lattice-based signatures are instantiated for classical adversaries, although they are based on presumably quantum hard problems. Yet, it is not known how such schemes perform in a post-quantum world.

We bridge this gap by proving the lattice-based signature scheme TESLA to be tightly secure based on the learning with errors problem over standard lattices in the random oracle model. As such, we improve the security of the original proposal by Bai and Galbraith (CT-RSA\'14) twofold; we tighten the security reduction and we minimize the underlying security assumptions. Remarkably, by enhancing the security we can improve TESLA\'s performance by a factor of two.

Furthermore, we are first to propose parameters providing a security of 128 bits against both classical and quantum adversaries

for a lattice-based signature scheme. Our implementation of TESLA competes well with state-of-the-art lattice-based signatures and

SPHINCS (EUROCRYPT\'15), the only signature scheme instantiated with quantum-hard parameters thus far.

In 2014, Chen et al. proposed a one-way hash self-healing group key distribution scheme for resource-constrained wireless networks in Journal of Sensors (14(14):24358-24380, DOI: 10.3390/ s141224358). They asserted that their scheme 2 has the constant storage overhead, low communication overhead, and is secure, i.e., achieves mt-revocation capability, mt-wise forward secrecy, any-wise backward secrecy and has mt-wise collusion attack resistance capability. Unfortunately, an attack method against Chen et al.\'s scheme 2 is found in this paper, which contributes to some security flaws. More precisely, a revoked user can recover other legitimate users\' personal secrets, which directly breaks the forward security, mt-revocation capability and mt-wise collusion attack resistance capability. Thus, Chen et al.\'s scheme 2 is insecure.

Most stream ciphers used in practice are vulnerable against generic collision attacks, which allow to compute the secret initial state on the basis of O(2^{n/2}) keystream bits in time and space O(2^{n/2}), where n denotes the inner state length of the underlying keystream generator. This implies the well-known rule that for reaching n-bit security, the inner state length should be at least 2n. Corresponding to this, the inner state length of recent proposals for practically used stream ciphers is quite large (e.g., n=288 for Trivium and n=160 for Grain v1).

In this paper, we suggest a simple stream cipher operation mode, respectively a simple way how to modify existing operation modes like that in the Bluetooth system, which provides provable security near 2^{2n/3} against generic collision attacks. Our suggestion refers to stream ciphers (like E0 in Bluetooth) which generate keystreams that are partitioned into packets and where the initial states for each packet are computed from a packet-IV and the secret session key using a resynchronization algorithm.

Our security analysis is based on modeling the resynchronization algorithm in terms of the FP(1)-construction E(x,k)=F(P(x+k)+k), where k denotes an n-bit secret key (corresponding to the symmetric session key), F denotes a publicly known n-bit function (corresponding to the output function of the underlying keystream generator), P denotes a publicly known n-bit permutation (corresponding to the iterated state update function of the generator), and the input x is an n-bit public initial value. Our security bounds follow from the results presented in [Cryptology ePrint Archive: Report 2015/636], where a tight 2n/3 security bound for the FP(1)-construction in the random oracle model was proved.

In this paper, we survey the status of attacks on the ring

and polynomial learning with errors problems (RLWE and PLWE). Recent

work on the security of these problems [EHL, ELOS] gives rise to

interesting questions about number fields. We extend these attacks and

survey related open problems in number theory, including spectral distortion of an algebraic number and its relationship to Mahler measure, the monogenic property for the ring of integers of a number field, and the size of elements of small order modulo q.

In March, 2015 Gu Chunsheng proposed a candidate ideal multilinear

map [eprint 2015/269]. An ideal multilinear map allows to perform

as many multiplications as desired, while in k-multilinear maps like GGH [EC 2013] or CLT [CR2013, CR2015] one we canperform at most a predetermined number k of multiplications. In this note, we show that the extraction Multilinear Computational Diffie-Hellman problem (ext-MCDH) associated to Gu\'s map can be solved in polynomial-time: this candidate ideal multilinear map is insecure. We also give intuition on why we think that the two other ideal multilinear maps proposed by Gu in [eprint 2015/269] are not secure either.

Applications are invited for two fixed-term studentships from suitably qualified candidates who wish to undertake a PhD in Computer Security at University College Cork, Ireland. The positions are within the Insight Centre for Data Analytics, funded by Science Foundation Ireland and industry. The research topics are on confidentiality and user consent in big datasets and on anomaly detection in big datasets.

More information and application details at:

http://www.ucc.ie/en/hr/vacancies/research/full-details-555797-en.html

We will consider applications until the positions are filled.

Name: Dr. Ratna Dutta
Topic: Studies on Pairing-Based and Constant Round Dynamic Group Key Agreement Protocols
Category: (no category)

Name: Dr. Y. Sreenivasa Rao
Topic: Design and Analysis of Attribute-Based Cryptosystems using Bilinear Pairings
Category: public-key cryptography

Description: Cryptosystems based on the attribute-based framework have recently acquired much\r\nimportance due to their enhanced functionality and flexibility, and\r\ntheir promising potential as a cryptographic platform for achieving advanced functionalities.\r\nHowever, attribute-based cryptosystems incur high communication and computation overheads which could impede their practical usage.\r\n%The main goal of this thesis is to design efficient and provably secure attribute-based cryptographic schemes with low communication and computation cost, using bilinear pairings.\r\nThis thesis aims at designing efficient and provably secure attribute-based cryptographic schemes allowing for expressive access policies with significantly low communication and computation cost, using bilinear pairings.\r\n\r\n The contributions of the thesis are manifold. We first propose two Key-Policy Attribute-Based Encryption (KP-ABE) schemes with constant-size ciphertext for Linear Secret-Sharing Scheme (LSSS)-realizable (monotone) access structures, supporting small universes of attributes. Among these, one scheme is Chosen Plaintext Attack (CPA) secure and the other is chosen ciphertext attack secure. We then extend these schemes to support not only the positive but also the negative attributes. Next, a CPA secure KP-ABE for large attribute universes is presented that features linear-size ciphertext and constant-size public parameters.\r\nLater, a dual-policy ABE with short ciphertext and constant-size ciphertext broadcast KP-ABE schemes are constructed.\r\n\r\n\r\n In all the aforementioned schemes, one fully trusted authority manages attributes and issues secret decryption keys to legitimate users.\r\nWe suggest a decentralized multi-authority Ciphertext-Policy ABE (dCP-ABE) for general monotone access structures. We incorporate the ciphertext access control policy in terms of minimal authorized sets in access structure, without using any secret-sharing scheme.\r\n\r\n Further, we present a key[...]

Name: Saqib A. Kakvi
Topic: On the Improvement of Security Proofs: Bridging the Gap between Theory and Practice
Category: foundations

Description:

This Thesis makes a humble attempt to bridge the well-known gap between the use of cryptography in practice and the theory, or lack thereof, behind it. With a concentration on digital signature scheme, we endeavour forth to fill in the gaps and, as far as possible, join the two edges of our chasm. To this end, we start from primitives that lie close to, if not at the very edge, of one side and try to push ourselves closer and closer to the other end of the spectrum. \r\n

\r\n

\r\nFor our first leap, we start from the side of practice. Our starting point is one of the most widely used and implemented signature schemes, RSA-FDH. Despite it\'s wide acceptance, RSA-FDH has a loose security proof and is not as theoretically secure as it is assumed to be in practice. Hence, we have found our first gap to bridge. We present a tight security proof for RSA-FDH which meets the security expectations that have until now, been assumed by practitioners.\r\n

\r\n

\r\nThe next step sees us starting from the side of theory looking towards practice. Despite our satisfactory results vis à vis RSA-FDH, they are in the Random Oracle Model, which is shaky grounds at best. With this in mind, we look towards building tightly secure signatures in the standard model. Such signatures were known previously, but from a limited number of assumptions. We examined these schemes closer and were able to show a generic framework that was implicitly used to construct all of them. Utilising this framework we are able to construct tightly secure signatures from a multitude of assumptions. Sadly, our signatures fall a few hand spans short and are just gripping the edge of practicality.\r\n

\r\n

\r\nThe final hop we make does not take us all the way from theory to practice, but some headway is gained. The last step could be seen not only as a bridge between theory and practice, but also between our first two results. Recent results have shown that using obfuscation, one can prove RSA-FD[...]

Submission: 24 December 2015
Notification: 29 February 2016
From May 30 to June 1
Location: Ghent, Belgium
More Information: http://ifipsec.org/2016/

We show how to construct indistinguishability obfuscation (iO) for circuits from any non-compact functional encryption (FE) scheme with sub-exponential security against unbounded collusions. We accomplish this by giving a generic transformation from any such FE scheme into a compact FE scheme. By composing this with the transformation from sub-exponentially secure compact FE to iO (Ananth and Jain [CRYPTO\'15], Bitansky and Vaikuntanathan [FOCS\'15]), we obtain our main result.

Our result provides a new pathway to iO. For example, by combining our result with the FE scheme of Garg et al. [ePrint 2014/666], we obtain a new construction of iO based on the sub-exponential GGHZ assumption over composite-order multilinear maps.

We also identify a \"simple\" function family for FE that suffices for our general result. We show that the function family F is complete, where every f in F consists of three evaluations of a Weak PRF followed by finite operations. We believe that this may be useful for realizing iO from weaker assumptions in the future.

Recently, several research groups in cryptography have presented new elliptic curve model based on Edwards curves.

These new curves were selected for their good performance and security perspectives.

Cryptosystems based on elliptic curves in embedded devices can be vulnerable to Side-Channel Attacks (SCA), such as the Simple Power Analysis (SPA) or the Differential Power Analysis (DPA).

In this paper, we analyze the existence of special points whose use in SCA is known as Same Value Analysis (SVA), for Edwards curves. These special points show up as internal collisions under power analysis. Our results indicate that no Edwards curve is safe from such an attacks.

In WISA\'13, a novel lightweight block cipher named LEA

was released. This algorithm has certain useful features for hardware

and software implementations, i.e., simple ARX operations, non-S-box

architecture, and 32-bit word size. These features are realized in several

platforms for practical usage with high performance and low overheads.

In this paper, we further improve 128-, 192- and 256-bit LEA encryption

for low-end embedded processors. Firstly we present speed optimization

methods. The methods split a 32-bit word operation into four byte-wise

operations and avoid several rotation operations by taking advantages of

efficient byte-wise rotations. Secondly we reduce the code size to ensure

minimum code size.We nd the minimum inner loops and optimize them

in an instruction set level. After then we construct the whole algorithm

in a partly unrolled fashion with reasonable speed. Finally, we achieved

the fastest LEA implementations, which improves performance by 10.9%

than previous best known results. For size optimization, our implemen-

tation only occupies the 280B to conduct LEA encryption. After scaling,

our implementation achieved the smallest ARX implementations so far,

compared with other state-of-art ARX block ciphers such as SPECK and

SIMON.

In previous work(2015/474 in Cryptology ePrint Archive), I proposed a fully homomorphic encryption without bootstrapping which has the weak point in the enciphering function. In this paper I propose the improved fully homomorphic encryption scheme on non-associative octonion ring over finite field without bootstrapping technique. I improve the previous scheme by (1) adopting the enciphering function such that it is difficult to express simply by using the matrices and (2) constructing the composition of the plaintext p with two sub-plaintexts u and v. The improved scheme is immune from the \"p and -p attack\". The improved scheme is based on multivariate algebraic equations with high degree or too many variables while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. The improved scheme is against the Gröbner basis attack.

The key size of this scheme and complexity for enciphering /deciphering become to be small enough to handle.

In this paper, we analyze the security claims of Extended Generalized Feistel Networks (EGFNs) schemes proposed by Berger et al [1]. We provide impossible differentials for 10 rounds of EGFNs with 16 branches which add up one round to the claim of 9 rounds in the impossible differential trail. Therefore, impossible differential trail covers 10 rounds for the EGFNs scheme, which is the best result on impossible differentials of EGFNs so far. We also provide several 10 round impossible differential trails to attack EGFNs based new cipher proposals. 𝒰-method is also used by authors to assert their claim for maximum number of rounds in impossible differential trails of EGFNs. This analysis indicates that 𝒰-method does not provide optimal results for this scheme.