International Association
for Cryptologic Research

Secret sharing is a mechanism by which a trusted dealer holding a secret ``splits\'\' the secret into many ``shares\'\' and distributes the shares to a collections of parties. Associated with the sharing is a monotone access structure, that specifies which parties are ``qualified\'\' and which are not: any qualified subset of parties can (efficiently) reconstruct the secret, but no unqualified subset can learn anything about the secret. In the most general form of secret sharing, the access structure can be any monotone NP language.

In this work, we consider two very natural extensions of secret sharing. In the first, which we call distributed secret sharing, there is no trusted dealer at all, and instead the role of the dealer is distributed amongst the parties themselves. Distributed secret sharing can be thought of as combining the features of multiparty non-interactive key exchange and standard secret sharing, and may be useful in settings where the secret is so sensitive that no one individual dealer can be trusted with the secret. Our second notion is called functional secret sharing, which incorporates some of the features of functional encryption into secret sharing by providing more fine-grained access to the secret. Qualified subsets of parties do not learn the secret, but instead learn some function applied to the secret, with each set of parties potentially learning a different function.

Our main result is that both of the extensions above are equivalent to several recent cutting-edge primitives. In particular, general-purpose distributed secret sharing is equivalent to witness PRFs, and general-purpose functional secret sharing is equivalent to indistinguishability obfuscation. Thus, our work shows that it is possible to view some of the recent developments in cryptography through a secret sharing lens, yielding new insights about both these cutting-edge primitives and secret sharing.

Learning with errors (LWE) was introduced by Regev in 2005, which enjoys attractive worst-case hardness properties. It has served as the foundation for a variety of cryptographic schemes. There are two main types of attacks against LWE: one for the decision version of LWE, the other for the search version of LWE.

In this paper, we apply the list decoding method to solve search version of LWE. Our algorithm runs in probabilistic polynomial time and results in specific security estimates for a large range of parameters. To our knowledge, it is the first time to apply the list decoding method to recover the key of LWE.

Our algorithm improves Laine and Lauter\'s result.

Recently, Hu and Jia presented an efficient attack on the GGH map. They show that the MPKE and WE based on GGH with public tools of encoding are not secure. Currently, an open problem is to fix GGH with functionality-preserving. We present a new construction of multilinear map using ideal lattices, which maintains functionality of GGH with public tools of encoding, such as applications of GGH-based MPKE and WE. The security of our construction depends upon new hardness assumption.

Standard form of authenticated encryption (AE) requires the ciphertext to be expanded by

the nonce and the authentication tag. These expansions can be problematic

when messages are relatively short and communication cost is high.

This paper studies a form of AE scheme whose ciphertext is only expanded by

nonce, with the help of stateful receiver which also enables detection of replays.

While there is a scheme having this feature, called AERO, proposed by McGrew and Foley,

there is no formal treatment based on the provable security framework.

We propose a provable security framework for such AE schemes, which we call MiniAE, and

show several secure schemes using standard symmetric crypto primitives.

Most notably, one of our schemes

has a similar structure as OCB mode of operation and uses only one blockcipher call

to process one input block, thus the computation cost is comparable to the

nonce-based encryption-only schemes.

We consider scenarios in sensor network where the sensed samples are each encrypted with a different key and streamed to a cloud storage. The large number of samples poses technical challenge in fine-grained sharing. For instance, if the data owner wants to grant a user access to a large subset of the samples, the straightforward solution of sending all corresponding keys to the user would overwhelm the data owner\'s network resources. Although existing solution such as Attribute-Based Encryption (ABE) and Key Aggregation Cryptosystem (KAC) can aggregate a number of keys into a single key of small size, each of the techniques has limitations in certain aspects, which render them impractical in our applications. In particular, ABE generally incurs large overhead in ciphertext size, while KAC, though attaining constant ciphertext size and aggregated key size, requires quadratic reconstruction time with respect to the number of keys to be reconstructed. In this paper, we made an observation that for a large class of queries, specifically the combination of range and down-sampling queries, there is a algorithmic enhancement for KAC that reduces its reconstruction time from quadratic to linear. Such improvement addresses the main hurdle in adopting KAC for large datasets. Experimental studies show that on those class of queries, the proposed algorithm outperforms the original KAC by at least $90$ times when reconstructing $2^{15}$ keys. We also give a Minimum Spanning Tree (MST)-based algorithm for general queries and a clustering algorithm to trade-off the reconstruction time with the size of aggregated key. Experimental studies show that these algorithms can reduce the reconstruction time for keys that are dense in small range.

We initiate a formal investigation on the power of predictability for argument of knowledge systems for NP.

Specifically, we consider private-coin argument systems where the answers of the prover can be predicted, given the private randomness of the verifier.

We show that predictable arguments of knowledge (PAoK) can be made extremely laconic, with the prover sending a single bit, and assumed to have only one round (two messages) without loss of generality. We then explore constructs of PAoK. For specific relations we obtain PAoK from Extractable Hash Proof systems (Wee, Crypto \'10); we also show that PAoK are equivalent to Extractable Witness Encryption. Unfortunately, the latter poses serious doubts on the existence of PAoK for all NP. However, we show that for the class of random self-reducible problems in NP we can avoid the problem relying on the assumption of public-coin differing-inputs obfuscation (Ishai et al., TCC \'15).

Finally, we apply PAoK in the context of leakage-tolerant PKE protocols.

At PKC \'13 Nielsen et al. have shown that any leakage-tolerant PKE protocol requires long keys already when it tolerates super-logarithmic leakage.

We strengthen their result proving a more fine-grained lower bound for any constant numbers bits of leakage.

Abstract. We propose generic constructions of public-key encryption schemes, satisfying key- dependent message (KDM) security for projections and different forms of key-leakage resilience, from CPA-secure private key encryption schemes with two main abstract properties: (1) additive homomorphism with respect to both messages and randomness, and (2) reproducibility, providing a means for reusing encryption randomness across independent secret keys. More precisely, our construction transforms a private-key scheme with the stated properties (and one more mild condition) into a public-key one, providing:

- n-KDM-projection security, an extension of circular security, where the adversary may also ask for encryptions of negated secret key bits;

- a (1-o(1)) resilience rate in the bounded-memory leakage model of Akavia et al. (TCC 2009); and

- Auxiliary-input security against subexponentially-hard functions.

We introduce homomorphic weak pseudorandom functions, a homomorphic version of the weak PRFs proposed by Naor and Reingold (FOCS \'95) and use them to realize our base encryption scheme. We obtain homomorphic weak PRFs under assumptions including subgroup indistinguishability (implied, in particular, by QR and DCR) and homomorphic hash-proof systems (HHPS). As corollaries of our results, we obtain (1) a projection-secure encryption scheme (as well as a scheme with a (1-o(1)) resilience rate) based solely on the HHPS assumption, and (2) a unifying approach explaining the results of Boneh et al (CRYPTO \'08) and Brakerski and Goldwasser (CRYPTO \'10). Finally, by observing that Applebaum\'s KDM amplification method (EUROCRYPT \'11) preserves both types of leakage resilience, we obtain schemes providing at the same time high leakage resilience and KDM security against any fixed polynomial-sized circuit family.

We introduce a matrix decomposition method and prove

that multiplication in GF$(2^k)$ with a Type 1 optimal normal

basis for can be performed using $k^2-1$ XOR gates irrespective

of the choice of the irreducible polynomial generating the field.

The previous results achieved this bound only with special

irreducible polynomials. Furthermore, the decomposition method

performs the multiplication operation using $1.5k(k-1)$ XOR gates

for Type 2a and 2b optimal normal bases, which matches previous

bounds.

Group signatures are a central cryptographic primitive which allows users to sign messages while hiding their identity within a crowd of group members. In the standard model (without the random oracle idealization), the most efficient constructions rely on the Groth-Sahai proof systems (Eurocrypt\'08). The structure-preserving signatures of Abe et al. (Asiacrypt\'12) make it possible to design group signatures based on well-established, constant-size number theoretic assumptions (a.k.a. ``simple assumptions\'\') like the Symmetric eXternal Diffie-Hellman or Decision Linear assumptions. While much more efficient than group signatures built on general assumptions, these constructions incur a significant overhead w.r.t.

constructions secure in the idealized random oracle model. Indeed, the best known solution based on simple assumptions requires 2.8 kB per signature for currently recommended parameters. Reducing this size and presenting techniques for shorter signatures are thus natural questions. In this paper, our first contribution is to significantly reduce this overhead. Namely, we obtain the first fully anonymous group signatures based on simple assumptions with signatures shorter than 2 kB at the 128-bit security level. In dynamic (resp. static) groups, our signature length drops to 1.8 kB (resp. 1 kB). This improvement is enabled by two technical tools. As a result of independent interest, we first construct a new structure-preserving signature based on simple assumptions which shortens the best previous scheme by 25%. Our second tool is a new method for attaining anonymity in the strongest sense using a new CCA2-secure encryption scheme which is simultaneously a Groth-Sahai commitment.

There is a significant effort in building lightweight cryptographic operations, yet the proposed solutions are typically single-purpose modules that can implement a single functionality. In contrast, we propose BitCryptor, a multi-purpose, bit-serialized compact processor for cryptographic applications on reconfigurable hardware. The proposed crypto engine can perform pseudo-random number generation, strong collision-resistant hashing and variable-key block cipher encryption. The hardware architecture utilizes SIMON, a recent lightweight block cipher, as its core. The complete engine uses a bit-serial design methodology to minimize the area. Implementation results on the Xilinx Spartan-3 s50 FPGA show that the proposed architecture occupies 95 slices (187 LUTs, 102 registers), which is 10$\\times$ smaller than the nearest comparable multi-purpose design. BitCryptor is also smaller than the majority of recently proposed lightweight single-purpose designs. Therefore, it is a very efficient cryptographic IP block for resource-constrained domains, providing a good performance at a minimal area overhead.

In this paper, we show efficient implementations of K-571 over ARMv8. We exploit an advanced 64-bit polynomial multiplication (PMULL) supported by ARMv8 for high speed multiplication and squaring operations. Particularly, multiplication is conducted with three terms of asymptotically faster Karatsuba multiplication. Inversion is constructed by using constant time Fermat-based inversion method. For high speed scalar multiplication, 4TNAF method is exploited which takes an advantage of simple doubling method. Finally, our method conducts ECDH over K-571 within 783,705 clock cycles. Our proposed method on ARMv8 improves the performance by a factor of 4.6 times than previous techniques on ARMv7.

The Cryptology Group at Ruhr-University Bochum (Horst-Goertz Institute) is seeking to recruit one Marie Sklodowska-Curie Research Fellows in Cryptography to start in October 2015, as part of the ECRYPT-NET project.

ECRYPT-NET is a research network of six universities and two companies that intends to develop advanced cryptographic techniques for the Internet of Things and the Cloud, and to create efficient and secure implementations of those techniques on a broad range of platforms. ECRYPT-NET is funded by a prestigious Marie Sklodowska-Curie ITN (Integrated Training Network) grant. The network will educate a group of 15 PhD students with a set of interdisciplinary skills in the areas of mathematics, computer science and electrical engineering. The training will be provided in an international context that includes Summer Schools, workshops and internships. Participants are expected to spend at least six months abroad with a network partner, or in one of the seven associated companies. We are looking for highly motivated candidates, ideally with background on cryptology and with proven research abilities.

One of the ECRYPT-NET ESR (Early Stage Researcher) positions will be based at Ruhr-University Bochum, to work on the project Fully Homomorphic Encryption - Design and Analysis.

We are looking for a candidate with a strong background in algorithmics and with a passion for cryptanalysis.

Marie Curie ITN eligibility criteria apply to this position.

Founded in 2001, the Horst-Görtz Institute at Ruhr-University Bochum is a world-leading interdisciplinary research center dedicated to research and education covering all aspects of IT security, with an excellent record of research in cryptography. The Horst-Görtz Institute has 15 professors and over 80 PhD students. It hosts the only German Research Training Group for Doctoral students in Cryptology.

The group for Cryptography and Network Security at Hangzhou Normal University, China chaired by Prof. Dr. Qi Xie is looking for two faculty members with strong crypto/security background. Candidates should have a PhD degree in mathematics, computer science, or related disciplines, be highly motivated with strong R&D capability and also a good team player, have good presentation and communication skills, be able to perform deep system-level investigations of security mechanisms. The candidates are expected to publish high-quality papers OR develop security-related projects. Any prior experience in cloud computing, e-health or WSN/VANETs security is certainly an asset..

Interested candidates please send CV to Qi Xie {qixie68 (at) 126.com}. The positions offer a competitive salary. All candidates will be contacted for further infomation.

We present new frameworks for constructing public-key encryption schemes satisfying key-dependent message (KDM) security and that yield efficient, universally composable oblivious transfer (OT) protocols via the dual-mode cryptosystem framework of Peikert, Waters and Vaikuntanathan (Crypto 2008).

- Our first framework yields a conceptually simple and unified treatment of the KDM-secure schemes of Boneh et al. (Crypto 2008), Brakerski and Goldwasser (Crypto 2010) and Brakerski, Goldwasser and Kalai (TCC 2011) in the single-key setting.

- Using our second framework, we obtain new dual-mode cryptosystems based on the d-linear, quadratic residuocity and decisional composite residuocity assumptions.

Both of these frameworks build on the notion of smooth projective hashing introduced by Cramer and Shoup (Eurocrypt 2002), with the additional requirement that the hash function is homomorphic, as is the case for all known instantiations.

We are the first to address the problem of efficient oblivious substring search over encrypted data supporting updates. Our two new protocols SA-ORAM and ST-ORAM obliviously search for substrings in an outsourced set of n encrypted strings. Both protocols are efficient, requiring communication complexity that is only poly-logarithmic in n. Compared to a straightforward solution for substring search using recent \"oblivious data structures\" [30], we demonstrate that our tailored solutions improve communication complexity by a factor of logn. The idea behind SA-ORAM and ST-ORAM is to employ a new, hierarchical ORAM tree structure that takes advantage of data dependency and optimizes the size of ORAM blocks and tree height. Based on oblivious suffix arrays, SA-ORAM targets efficiency, yet does not allow updates to the outsourced set of strings. ST-ORAM, based on oblivious suffix trees, allows updates at the additional communications cost of a factor of loglogn. We implement and benchmark SA-ORAM to show its feasibility for practical deployments: even for huge datasets of 2^40 strings, an oblivious substring search can be performed with only hundreds of KBytes communication cost.

Generic distinguishers against Feistel Network with up to 5 rounds exist in the regular setting and up to 6 rounds in a multi-key setting. We present new cryptanalyses against Feistel Networks with 5, 6 and 7 rounds which are not simply distinguishers but actually recover completely the unknown Feistel functions.

When an exclusive-or is used to combine the output of the round function with the other branch, we use the so-called \\textit{yoyo game} which we improved using a heuristic based on particular cycle structures. The complexity of a complete recovery is equivalent to $O(2^{2n})$ encryptions where $n$ is the branch size. This attack can be used against 6- and 7-round Feistel Networks in time respectively $O(2^{n2^{n-1}+2n})$ and $O(2^{n2^{n}+2n})$. However when modular addition is used, this attack does not work. In this case, we use an optimized guess-and-determine strategy to attack 5 rounds with complexity $O(2^{n2^{3n/4}})$.

Our results are, to the best of our knowledge, the first recovery attacks against generic 5-, 6- and 7-round Feistel Networks.

Lattice-based cryptography has been proposed as a postquantum public-key cryptosystem. In this paper, we present a masked ring-LWE decryption implementation resistant to first-order side-channel attacks. Our solution has the peculiarity that the entire computation is performed in the masked domain. This is achieved thanks to a new, bespoke masked decoder implementation. The output of the ring-LWE decryption are Boolean shares suitable for derivation of a symmetric key. We have implemented a hardware architecture of the masked ring-LWE processor on a Virtex-II FPGA, and have performed side channel analysis to confirm the soundness of our approach. The area of the protected architecture is around $2000$ LUTs, a $20\\%$ increase with respect to the unprotected architecture. The protected implementation takes $7478$ cycles to compute, which is only a factor $\\times2.6$ larger than the unprotected implementation.

In \"A Short Paper on How to Improve U-Prove Using Self-Blindable Certificates\" by L. Hanzlik and K. Kluczniak (FC\'2014), an unlinkable version of the U-Prove attribute-based credential scheme is proposed. Unfortunately, the new scheme is forgeable: if sufficiently many users work together then they can construct new credentials, containing any set of attributes of their choice, without any involvement of the issuer. In this short paper we show how they can achieve this and we point out the error in the unforgeability proof.

Cayley hash functions are based on a simple idea of using a pair of

(semi)group elements, A and B, to hash the 0 and 1 bit, respectively, and then to hash an arbitrary bit string in the natural way, by using multiplication of elements in the (semi)group. In this paper, we focus on hashing with linear functions of one variable over F_p. The corresponding hash functions are very efficient, in particular, due to the fact that a linear function is determined by its values at two points. Thus, we show that hashing a bit string of length $n$ with our method requires just 2n multiplications in F_p, but with particular pairs of linear functions that we suggest, one does not need to perform any multiplications at all. We also give explicit lower bounds on the

length of collisions for hash functions corresponding to these particular pairs of linear functions over F_p.

We present DPA attacks on an ARM Cortex-A8 processor running at 1 GHz. This high-end processor is typically found in portable devices such as phones and tablets. In our case, the processor sits in a single board computer and runs a full-fledged Linux operating system. The targeted AES implementation is bitsliced and runs in constant time and constant flow. We show that, despite the complex hardware and software, high clock frequencies and practical measurement issues, the implementation can be broken with DPA starting from a few thousand measurements of the electromagnetic emanation of a decoupling capacitor near the processor. To harden the bitsliced implementation against DPA attacks, we mask it using principles of hardware gate-level masking. We evaluate the security of our masked implementation against first-order and second-order attacks. Our experiments show that successful attacks require roughly two orders of magnitude more measurements.