International Association
for Cryptologic Research

In Crypto'05, Bellare et al. proved $O(\ell q^2 /2^n)$ bound for the PRF (pseudorandom function) security of the CBC-MAC based on an $n$-bit random permutation $\Pi$, provided $\ell < 2^{n/3}$. Here an adversary can make at most $q$ prefix-free queries each having at most $\ell$ ``{\em blocks}'' (elements of $\s^n$). In the same paper $O(\ell^{o(1)} q^2 /2^n)$ bound for EMAC (or encrypted CBC-MAC) was proved, provided $\ell < 2^{n/4}$. Both proofs are based on {\bf structure graphs} representing all collisions among ``{\em intermediate inputs}'' to $\Pi$ during the computation of CBC. The problem of bounding PRF-advantage is shown to be reduced to bounding the number of structure graphs satisfying certain collision patterns. Unfortunately, we have shown here that {\em the Lemma 10 in the Crypto'05 paper, stating an important result on structure graphs, is incorrect}. This is due to the fact that the authors {\bf overlooked certain structure graphs}. This invalidates the proofs of the PRF bounds. In ICALP'06, Pietrzak improved the bound for EMAC by showing a {\em tight bound} $O(q^2/2^n)$ under the restriction that $\ell < 2^{n/8}$. As he used the same flawed lemma, this proof also becomes invalid. In this paper, we have revised and sometimes simplified these proofs. We revisit structure graphs in a slightly different mathematical language and provide a complete characterization of certain types of structure graphs. Using this characterization, we show that PRF security of CBC-MAC is about $\sigma q /2^n$ provided $\ell < 2^{n/3}$ where $\sigma$ is the total number of blocks in all queries. We also recovered the tight bound of EMAC with a much relaxed constraint $\ell < 2^{n/4}$ than the original.

Standard differential cryptanalysis uses statistical dependencies between the difference of two plaintexts and the difference of the respective two ciphertexts to attack a cipher. Here we introduce polytopic cryptanalysis which considers interdependencies between larger sets of texts as they traverse through the cipher. We prove that the methodology of standard differential cryptanalysis can unambiguously be extended and transferred to the polytopic case including impossible differentials. We show that impossible polytopic transitions have generic advantages over impossible differentials. To demonstrate the practical relevance of the generalization, we present new low-data attacks on round-reduced DES and AES using impossible polytopic transitions that are able to compete with existing attacks, partially outperforming these.

Computational notions of entropy have recently found many applications, including leakage-resilient cryptography, deterministic encryption or memory delegation. The two main types of results which make computational notions so useful are (1) Chain rules, which quantify by how much the computational entropy of a variable decreases if conditioned on some other variable (2) Transformations, which quantify to which extend one type of entropy implies another.

Such chain rules and transformations typically lose a significant amount in quality of the entropy, and are the reason why applying these results one gets rather weak quantitative security bounds. In this paper we for the first time prove lower bounds in this context, showing that existing results for transformations are, unfortunately, basically optimal for non-adaptive black-box reductions (and it's hard to imagine how non black-box reductions or adaptivity could be useful here.)

A variable $X$ has $k$ bits of HILL entropy of quality $(\epsilon,s)$ if there exists a variable $Y$ with $k$ bits min-entropy which cannot be distinguished from $X$ with advantage $\epsilon$ by distinguishing circuits of size $s$. A weaker notion is Metric entropy, where we switch quantifiers, and only require that for every distinguisher of size $s$, such a $Y$ exists. %For Metric entropy, we further distinguish between a notion that considers probabilistic or only weaker deterministic distinguishers.

We first describe our result concerning transformations. By definition, HILL implies Metric without any loss in quality. Metric entropy often comes up in applications, but must be transformed to HILL for meaningful security guarantees. The best known result states that if a variable $X$ has $k$ bits of Metric entropy of quality $(\epsilon,s)$, then it has $k$ bits of HILL with quality $(2\epsilon,s\cdot\epsilon^2)$. We show that this loss of a factor $\Omega(\epsilon^{-2})$ in circuit size is necessary. In fact, we show the stronger result that this loss is already necessary when transforming so called deterministic real valued Metric entropy to randomised boolean Metric (both these variants of Metric entropy are implied by HILL without loss in quality).

The chain rule for HILL entropy states that if $X$ has $k$ bits of HILL entropy of quality $(\epsilon,s)$, then for any variable $Z$ of length $m$, $X$ conditioned on $Z$ has $k-m$ bits of HILL entropy with quality $(\epsilon,s\cdot \epsilon^2/ 2^{m})$. We show that a loss of $\Omega(2^m/\epsilon)$ in circuit size necessary here. Note that this still leaves a gap of $\epsilon$ between the known bound and our lower bound.

The task of finding a constructive approximation in the computational distance, while simultaneously preserving additional constrains (referred to as "simulators"), appears as the key difficulty in problems related to complexity theory, cryptography and combinatorics.

In this paper we develop a general framework to \emph{efficiently} prove results of this sort, based on \emph{subgradient-based optimization applied to computational distances}. This approach is simpler and natural than KL-projections already studied in this context (for example the uniform min-max theorem from CRYPTO'13), while simultaneously may lead to quantitatively better results.

Some applications of our algorithm include: \begin{itemize} \item Fixing an erroneous boosting proof for simulating auxiliary inputs from TCC'13 and much better bounds for the EUROCRYPT'09 leakage-resilient stream cipher \item Deriving the unified proof for Impagliazzo Hardcore Lemma, Dense Model Theorem, Weak Szemeredi Theorem (CCC'09) \item Showing that "dense" leakages can be efficiently simulated, with significantly improved bounds \end{itemize} Interestingly, our algorithm can take advantage of small-variance assumptions imposed on distinguishers, that have been studied recently in the context of key derivation.

Security of a cryptographic application is typically defined by a security game. The adversary, within certain resources, cannot win with probability much better than $0$ (for unpredictability applications, like one-way functions) or much better than $\frac{1}{2}$ (indistinguishability applications for instance encryption schemes). In so called \emph{squared-friendly applications} the winning probability of the adversary, for different values of the application secret randomness, is not only close to $0$ or $\frac{1}{2}$ on average, but also concentrated in the sense that it's second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important in the context of key derivation. Barak et al. observed that for square-friendly applications one can beat the ``RT-bound'', extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a ``weak'' key, which has only high entropy, as a secure key.

In this paper we give sharp lower bounds on square security assuming security for ``weak'' keys. We show that \emph{any} application which is either (a) secure with weak keys or (b) allows for saving entropy in a key derived by hashing, \emph{must} be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC'13, CRYPTO'11) Hence, they can be understood as a general characterization of squared-friendly applications.

Whereas the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices.

We present a multi-party computation protocol in the case of dishonest majority which has very low round complexity. Our protocol sits philosophically between Gentry's Fully Homomorphic Encryption based protocol and the SPDZ-BMR protocol of Lindell et al (CRYPTO 2015). Our protocol avoids various inefficiencies of the previous two protocols. Compared to Gentry's protocol we only require Somewhat Homomorphic Encryption (SHE). Whilst in comparison to the SPDZ-BMR protocol we require only a quadratic complexity in the number of players (as opposed to cubic), we have fewer rounds, and we require less proofs of correctness of ciphertexts. In addition we present a variant of our protocol which trades the depth of the required SHE scheme for more homomorphic multiplications.

In Crypto 2010, Kiltz, O'Neill and Smith used $m$-prime RSA modulus $N$ with $m\geq 3$ for constructing lossy RSA. The security of the proposal is based on the Multi-Prime $\Phi$-Hiding Assumption. In this paper, we propose a heuristic algorithm based on the Herrmann-May lattice method (Asiacrypt 2008) to solve the Multi-Prime $\Phi$-Hiding Problem when prime $e>N^{\frac{2}{3m}}$. Further, by combining with mixed lattice techniques, we give an improved heuristic algorithm to solve this problem when prime $e>N^{\frac{2}{3m}-\frac{1}{4m^2}}$. These two results are verified by our experiments. Our bounds are better than the existing works.

Group signatures are an important privacy-enhancing tool which allow members of a group to anonymously produce signatures on behalf of the group. Ideally, group signatures are dynamic and thus allow to dynamically enroll new members to a group. For such schemes Bellare et al. (CT-RSA'05) proposed a strong security model (BSZ model) that preserves anonymity of a group signature even if an adversary can see arbitrary key exposures or arbitrary openings of other group signatures. All previous constructions achieving this strong security notion follow the so called sign-encrypt-prove (SEP) paradigm. In contrast, all known constructions which avoid this paradigm and follow the alternative "without encryption" paradigm introduced by Bichsel et al. (SCN'10), only provide a weaker notion of anonymity (which can be problematic in practice). Until now, it was not clear if constructions following this paradigm, while also being secure in the strong BSZ model, even exist. In this paper we positively answer this question by providing a novel approach to dynamic group signature schemes following this paradigm, which is a composition of structure preserving signatures on equivalence classes (Asiacrypt'14) and other standard primitives. Our results are interesting for various reasons: We can prove our construction following this "without encryption" paradigm secure in the strong BSZ model without requiring random oracles. Moreover, when opting for an instantiation in the ROM, the so obtained scheme is extremely efficient. It outperforms existing constructions following the SEP paradigm and being secure in the BSZ model regarding computational efficiency by some orders of magnitude and even yields shorter signatures. Regarding constructions providing a weaker anonymity notion than BSZ, we surprisingly outperform the popular short BBS group signature scheme (Crypto'04) and even obtain shorter signatures.

Given a dataset of user-chosen passwords, the frequency list reveals the frequency of each unique password. We present a novel mechanism for releasing perturbed password frequency lists with rigorous security, efficiency, and distortion guarantees. Specifically, our mechanism is based on a novel algorithm for sampling that enables an efficient implementation of the exponential mechanism for differential privacy (naïve sampling is exponential time). It provides the security guarantee that an adversary will not be able to use this perturbed frequency list to learn anything of significance about any individual user's password even if the adversary already possesses a wealth of background knowledge about the users in the dataset. We prove that our mechanism introduces minimal distortion, thus ensuring that the released frequency list is close to the actual list. Further, we empirically demonstrate, using the now-canonical password dataset leaked from RockYou, that the mechanism works well in practice: as the differential privacy parameter $\epsilon$ varies from $8$ to $0.002$ (smaller $\epsilon$ implies higher security), the normalized distortion coefficient (representing the distance between the released and actual password frequency list divided by the number of users $N$) varies from $8.8\times10^{-7}$ to $1.9\times 10^{-3}$. Given this appealing combination of security and distortion guarantees, our mechanism enables organizations to publish perturbed password frequency lists. This can facilitate new research comparing password security between populations and evaluating password improvement approaches. To this end, we have collaborated with Yahoo! to use our differentially private mechanism to publicly release a corpus of 50 password frequency lists representing approximately 70 million Yahoo! users. This dataset is now the largest password frequency corpus available. Using our perturbed dataset we are able to closely replicate the original published analysis of this data.

The HIMMO scheme has been introduced as a lightweight collusion-resistant key pre-distribution scheme, with excellent efficiency in terms of bandwidth, energy consumption and computation time. As its cryptanalysis relies on lattice techniques, HIMMO is also an interesting quantum-safe candidate. Unlike the schemes by Blom, by Matsumoto and Imai, and by Blundo {\em et al}, which break down once the number of colluding nodes exceeds a given threshold, it aims at tolerating any number of colluding nodes.

In 2015, a contest for the verification of the scheme was held. During the contest, a method was developed to guess a key by finding an approximate solution of one of the problems underlying the scheme. This attack involves finding a short vector in a lattice of dimension linear in a system parameter $\alpha$ and allowed key recovery for several challenges. Thwarting this attack by increasing $\alpha$ would lead to a significant performance degradation, as CPU and memory requirements for the implementation of the scheme scale quadratically in $\alpha$.

This paper describes a generalization of HIMMO parameters that allows configuring the scheme such that both its performance and the dimension of the lattice involved in the attack grow linearly in $\alpha$. Two attacks inspired by the one developed in the contest are described, and the impact of those attacks for different parameter choices is discussed. Parameters choices are described that thwart existing attacks while enabling high performance implementations of the scheme.

Pseudorandom functions (PRFs) play a central role in symmetric cryptography. While in principle they can be built from any one-way functions by going through the generic HILL (SICOMP 1999) and GGM (JACM 1986) transforms, some of these steps are inherently sequential and far from practical. Naor, Reingold (FOCS 1997) and Rosen (SICOMP 2002) gave parallelizable constructions of PRFs in NC^2 and TC^0 based on concrete number-theoretic assumptions such as DDH, RSA, and factoring. Banerjee, Peikert, and Rosen (Eurocrypt 2012) constructed relatively more efficient PRFs in NC^1 and TC^0 based on ``learning with errors'' (LWE) for certain range of parameters. It remains an open problem whether parallelizable PRFs can be based on the ``learning parity with noise'' (LPN) problem for both theoretical interests and efficiency reasons (as the many modular multiplications and additions in LWE would then be simplified to AND and XOR operations under LPN).

In this paper, we give more efficient and parallelizable constructions of randomized PRFs from LPN under noise rate $n^{-c}$ (for any constant $0<c<1)$ and they can be implemented with a family of polynomial-size circuits with unbounded fan-in AND, OR and XOR gates of depth $\omega(1)$, where $\omega(1)$ can any small super-constant (e.g., $\log\log\log{n}$ or even less). Our work complements the lower bound results by Razborov and Rudich (STOC 1994) that PRFs of beyond quasi-polynomial security are not contained in AC0(MOD_2), i.e., the class of polynomial-size, constant-depth circuit families with unbounded fan-in AND, OR, and XOR gates.

Furthermore, our constructions are security-lifting by exploiting the redundancy of low-noise LPN. We show that in addition to parallelizability (in almost constant depth) the PRF enjoys either of (or any tradeoff between) the following:

\begin{itemize} \item A PRF on a weak key of sublinear entropy (or equivalently, a uniform key that leaks any $(1 - o(1))$-fraction) has comparable security to the underlying LPN on a linear size secret. \item A PRF with key length $\lambda$ can have security up to $2^{O(\lambda/\log\lambda)}$, which goes much beyond the security level of the underlying low-noise LPN. \end{itemize} where adversary makes up to certain super-polynomial amount of queries.

In recent years, a lot of progress has been made on speeding up Actively-secure Two-party Function Evaluation (SFE) using Garbled Circuits. For a given level of security, the amount of information that has to be sent and evaluated has been drastically reduced due to approaches that optimize the garbling method for the gates (such as Free-XOR, Flex-OR and Half-Gates). Moreover, the total number of garbled circuits sent to the evaluator dropped by a factor of 3, mostly due to the Forge-and-Lose-technique. In another line of work, Frederiksen et al. introduced the first special purpose garbling technique, namely a garbling scheme without privacy guarantees.

In this note, we present an approach to combine such a privacy-free garbling scheme with an arbitrary SFE protocol for a certain class of circuits, such that the overall protocol is actively secure. This then yields a SFE protocol that has a smaller overhead in total. We instantiate our approach with the SFE protocol by and show that the combination of both allows saving substantial amounts of network bandwidth for certain classes of circuits.

CLEFIA is a block cipher developed by Sony Corporation in 2007. It is a recommended cipher of CRYPTREC, and has been adopted as ISO/IEC international standard in lightweight cryptography. In this paper, some new 9-round zero-correlation linear distinguishers of CLEFIA are constructed with the input masks and output masks being independent, which allow multiple zero-correlation linear attacks on 14/15-rounds CLEAIA-192/256 with the partial sum technique. Furthermore, the relations between integral distinguishers and zero-correlation linear approximations are improved, and some new integral distinguishers over 9-round are deduced from zero-correlation linear approximations. By using these integral distinguishers and the partial sum technique, the previous integral results on CLEFIA are improved. The two results have either one more rounds or lower time complexity than previous attack results by means of integral and zero-correlation linear cryptanalysis.

In this paper, we propose an Undeniable Blind Signature scheme (UBSS) based on isogenies between supersingular elliptic curves. The proposed UBSS is an extension of the Jao-Soukharev undeniable signature scheme. We formalize the notion of a UBSS by giving the formal definition. We then study its properties along with the pros and cons. Based on this, we provide a couple of its applcations. We then state the isogeny problems in a more general form and discuss their computational hardnesses. Finally, we prove that the proposed scheme is secure in the presence of a quantum adversary under certain assumptions.

In this work, we put forward a new class of polynomial-time attacks on the original multilinear maps of Garg, Gentry, and Halevi (2013). Previous polynomial-time attacks on GGH13 were ``zeroizing'' attacks that generally required the availability of low-level encodings of zero. Most significantly, such zeroizing attacks were not applicable to candidate indistinguishability obfuscation (iO) schemes. iO has been the subject of intense study.

To address this gap, we introduce \emph{annihilation attacks}, which attack multilinear maps using non-linear polynomials. Annihilation attacks can work in situations where there are no low-level encodings of zero. Using annihilation attacks, we give the first polynomial-time cryptanalysis of candidate iO schemes over GGH13. More specifically, we exhibit two simple programs that are functionally equivalent, and show how to efficiently distinguish between the obfuscations of these two programs.

Given the enormous applicability of iO, it is important to devise iO schemes that can avoid attack.

In this paper, we investigate a variant of the BKZ algorithm, called progressive BKZ, which performs BKZ reductions by starting with a small blocksize and gradually switching to larger blocks as the process continues. We discuss techniques to accelerate the speed of the progressive BKZ algorithm by optimizing the following parameters: blocksize, searching radius and probability for pruning of the local enumeration algorithm, and the constant in the geometric series assumption (GSA). We then propose a simulator for predicting the length of the Gram-Schmidt basis obtained from the BKZ reduction. We also present a model for estimating the computational cost of the proposed progressive BKZ by considering the efficient implementation of the local enumeration algorithm and the LLL algorithm. Finally, we compare the cost of the proposed progressive BKZ with that of other algorithms using instances from the Darmstadt SVP Challenge. The proposed algorithm is approximately 50 times faster than BKZ 2.0 (proposed by Chen-Nguyen) for solving the SVP Challenge up to 160 dimensions.

Event date: 8 May 2016
Submission deadline: 1 May 2016

The Cryptographic Security Team Leader is responsible for developing and maintaining the internal expertise in cryptography and more particularly in the security of algorithms executed on embedded systems. You will help organise and manage cryptographic tasks in order to meet the schemes and customers’ expectations.

This will include the analysis of cryptographic codes embedded in products under evaluation, the development and the realisation of high level of cryptographic side-channel attacks, and the support and the training of engineers for evaluation projects. You will also provide technical expertise in embedded cryptography and related attacks and help each team member to develop their own skills and expertise.

The position includes the representation of the Company in industry forums and the management of complex projects. As a team leader, responsibilities also include managing the performance of direct reports by developing accountabilities, establishing performance objectives, providing career counselling, feedback and guidance and ensuring that all policies are understood and adhered to.

Closing date for applications: 28 April 2016

Contact: Dom Gooch / 02032067564 / dominic.gooch (at) solagroup.com

Event date: 10 October to 12 October 2016
Submission deadline: 15 June 2016
Notification: 1 August 2016

Job description: The research group Cryptography and IT Security of the Institute of Theoretical Informatics (ITI) at KIT has an opening for a PhD position in the scope of the project "CyPhyCrypt: Advanced Crypto for New and Next-Generation Cyber-Physical Systems" (PIs: Andy Rupp at KIT and Christof Paar at RUB). This project is fully funded by the German Research Foundation (DFG). It deals with the development of novel CPS security mechanisms with provable security guarantees and computational requirements that can be met in practical settings, based on sound advanced cryptographic constructions (e-cash, anonymous reputation systems, optimistic fair-exchange, etc.). The PhD candidate will be working on security models for the considered CPS as well as on cryptographic constructions which can be shown secure in these models.

Qualification:

• Very good university degree (Master or equivalent) in Computer Science or Mathematics.
• Solid background in provable security, e.g., demonstrated by excellent grades in corresponding postgraduate courses or by publications.
• Self-motivation, team spirit, and willingness to work in interdisciplinary projects.

Application:Please send your application (CV, transcripts and certificates, names of references) by e-Mail to: andy.rupp (at) kit.edu

KIT is an equal opportunity employer. Women are especially encouraged to apply. Applicants with disabilities will be preferentially considered if equally qualified.

Closing date for applications: 4 March 2016

Contact: Andy Rupp, Karlsruhe Institute of Technology, Institute of Theoretical Informatics, email: andy.rupp (at) kit.edu, phone: +49 721/608-41862.

More information: http://www.pse.kit.edu/downloads/stellenangebote/PhD-Theoretische%20Informatik-engl.pdf