2015-06-25Key Schedule in Symmetric-Key CryptographyThomas Peyrin (Nanyang Technological University)
In this talk, we will focus on the (still open) problem of designing and analysing key schedules for symmetric-key cryptography. We will first recall basic construction techniques of block ciphers and hash functions and explain why they are very successful at resisting state-of-the-art cryptanalysis in the single-key model. Then, we will identify why related-key attacks are much more complex to protect against and review recent improvement in this domain, both in construction and in cryptanalysis. Finally, we will propose some interesting research topics in this direction.
Cryptanalysis of the multilinear mapsChangmin Lee (Seoul National University)
Multilinear maps are a very useful tool in cryptography. For a long time, however, constructing multilinear maps has been an open problem. Recently, two types of cryptographic (approximate) multilinear maps have been constructed. One is the GGH scheme over the ideal lattice. The other is the CLT scheme over the integers. Unfortunately, in 2015, these schemes have turned out not to be secure. In this presentation, the GGH scheme and the CLT scheme will be briefly explained, followed by how to analyze them.
Revocable Identity-Based Encryption from Multilinear MapsKwangsu Lee (Sejong University)
A revocation mechanism in cryptosystems for a large number of users is absolutely necessary for maintaining the security of whole systems. A revocable identity-based encryption (RIBE) provides an efficient revocation method in IBE in which a trusted authority periodically broadcasts an update key for non-revoked users and a user can decrypt a ciphertext if his private key is not revoked in the update key. Boldyreva, Goyal, and Kumar (CCS 2008) defined RIBE and proposed an RIBE scheme that uses a tree-based revocation encryption scheme to revoke users' private keys. However, this approach has an inherent limitation in that the number of private key elements and update key elements cannot be constant. In this talk, to overcome this limitation, we present a new technique for RIBE and propose RIBE schemes with a constant number of private key elements. Our new technique for RIBE combines a hierarchical IBE (HIBE) scheme and a public-key broadcast encryption (PKBE) scheme by using multilinear maps. Following our new technique, we propose an RIBE scheme in three-leveled multilinear maps that combines the HIBE scheme of Boneh and Boyen (EUROCRYPT 2004) and the PKBE scheme of Boneh, Gentry, and Waters (CRYPTO 2005). Next, we propose another RIBE scheme with reduced public parameters by combining the HIBE scheme of Boneh and Boyen and the PKBE scheme of Boneh, Waters, and Zhandry (CRYPTO 2014), which uses multilinear maps.
2015-06-26Cryptanalysis of the Co-ACD AssumptionMoon Sung Lee (Seoul National University)
At ACM-CCS 2014, Cheon, Lee and Seo introduced a new number-theoretic assumption, the co-approximate common divisor (Co-ACD) assumption, based on which they constructed several cryptographic primitives, including a particularly fast additively homomorphic encryption scheme. For their proposed parameters, they found that their scheme was the ``most efficient of those that support an additive homomorphic property''.
In this talk, we present the security analysis of the Cheon-Lee-Seo (CLS) homomorphic encryption scheme and of the underlying Co-ACD assumption, and present several lattice-based attacks that are effectively devastating for the proposed constructions. First, we prove that a few known plaintexts are sufficient to decrypt any ciphertext in the symmetric-key CLS scheme. This breaks the one-wayness of both the symmetric-key and the public-key variants of CLS encryption as well as the underlying decisional Co-ACD assumption for a wide range of parameters. Then, we show that this attack can be heuristically extended to decrypt small messages without any known plaintext. And finally, we find that Coppersmith's theorem can even be used to solve the search variant of the Co-ACD problem, and mount a full key recovery on the public-key CLS scheme.
This is a joint work with Pierre-Alain Fouque, Tancrède Lepoint, and Mehdi Tibouchi.
Homomorphic Authentication and its Applications to Secure OutsourcingDario Fiore (IMDEA Software Institute)
The emergence of cloud computing motivates the investigation of novel cryptographic primitives that can allow a user Alice to securely outsource her data and computations to remote, untrusted, service providers. One security concern in this setting is related to preserving the privacy of the outsourced data. This question can be elegantly and successfully addressed by the recent work on homomorphic encryption. A second security concern deals with enforcing the integrity of the computations performed on the outsourced data.
In this talk I will mostly focus on the integrity aspect, and I will discuss how this can be solved via the notion of homomorphic authentication. In a nutshell, homomorphic message authenticators allow the holder of a (public) evaluation key to perform computations over previously authenticated data, in such a way that the produced tag can vouch for the correctness of the computation.
The talk will present the notion of homomorphic authenticators, give an overview of the state of the art in this area, and cover some of the recent efficient constructions. Finally, I will also discuss interesting extensions of these results, such as those schemes devoted to solving both privacy and integrity in the outsourcing scenario.
Quantum algorithms on encrypted dataTaewan Kim (Ewha Womans University)
Recently, it has been shown that there can exist cryptographic protocols to perform computations without revealing the data and its computing result. This is called the homomorphic encryption. In this talk, we introduce the quantum version, the quantum fully homomorphic encryption. We consider a situation where we perform quantum algorithms on encrypted data based on the quantum fully homomorphic encryption. We present a problem arising in the situation and its solution.
Image size and non-surjectivity for encodings to elliptic curvesMehdi Tibouchi (NTT Secure Platform Laboratories)
Many cryptographic protocols based on elliptic curves rely on the possibility of representing integer values or bit strings as elliptic curve points, or vice versa, in an invertible way. The most practical approach proposed to achieve this for an elliptic curve $E/\Fq$ has been the use of (piecewise) algebraic maps $f: \Fq\to E(\Fq)$ called ``encoding functions'', for which numerous constructions have been proposed in recent years.
The earliest of those is probably due to Boneh and Franklin (CRYPTO 2001), and has the remarkable property of being almost a bijection between $\Fq$ and $E(\Fq)$, which is very convenient for security proofs and other applications. Unfortunately, it only maps to supersingular curves, which severely limits is usefulness nowadays.
Since then, many other encoding functions have been proposed, and constructions are known for all elliptic curves. So far, however, none of these numerous encodings has replicated the very useful bijectivity property of the Boneh--Franklin encoding in the case of ordinary curves.
In this talk, we show that this is unsurprising: if an elliptic curve admits an encoding whose image contains almost all curve points (and satisfies certain standard technical conditions), then it must be supersingular. The proof is related to a classical theorem in group theory due to Camille Jordan.