International Association
for Cryptologic Research

We put forward the concept of a reconfigurable cryptosystem.

Intuitively, a reconfigurable cryptosystem allows to increase the security of the system at runtime, by changing a single central parameter we call common reference string (CRS). In particular, e.g., a cryptanalytic advance does not necessarily entail a full update of a large public-key infrastructure; only the CRS needs to be updated. In this paper we focus on the reconfigurability of encryption and signature schemes, but we believe that this concept and the

developed techniques can also be applied to other kind of cryptosystems.

Besides a security definition, we offer two reconfigurable encryption schemes, and one reconfigurable signature scheme. Our first reconfigurable encryption scheme uses indistinguishability obfuscation (however only in the CRS) to adaptively derive short-term keys from long-term keys. The security of long-term keys can be based on a one-way function, and the security of both the indistinguishability obfuscation and the actual encryption scheme can be increased on-the-fly, by changing the CRS. We stress that our scheme remains secure even if previous short-term secret keys are leaked.

Our second reconfigurable encryption scheme has a similar structure (and similar security properties), but relies on a pairing-friendly group instead of obfuscation. Its security is based on the recently introduced hierarchy of \\(k\\)-SCasc assumptions. Similar to the \\(k\\)-Linear assumption, it is known that \\(k\\)-SCasc implies \\((k+1)\\)-SCasc, and that this implication is proper in the generic group model. Our system allows to increase \\(k\\) on-the-fly, just by changing the CRS. In that sense, security can be increased without changing any long-term keys.

We also offer a reconfigurable signature scheme based on the same hierarchy of assumptions.

The question whether there exist verifiable random functions with exponential-sized input space and full adaptive security based on a non-interactive, constant-size assumption is a long-standing open problem. We construct the first verifiable random functions which simultaneously achieve all these properties.

Our construction can securely be instantiated in symmetric bilinear groups, based on any member of the (n-1)-linear assumption family with n >= 3. This includes, for example, the 2-linear assumption, which is also known as the decision linear (DLIN) assumption.

We propose the Synthetic Counter-in-Tweak (SCT) mode, which turns a tweakable block cipher into a nonce-based authenticated encryption scheme (with associated data). The SCT mode combines in a SIV-like manner a Wegman-Carter MAC inspired from PMAC for the authentication part and a new counter-like mode for the encryption part, with the unusual property that the counter is applied on the tweak input of the underlying tweakable block cipher rather than on the plaintext input. Unlike many previous authenticated encryption modes, SCT enjoys provable security beyond the birthday bound (and even up to roughly $2^n$ tweakable block cipher calls, where $n$ is the block length, when the tweak length is sufficiently large) in the nonce-respecting scenario where nonces are never repeated. In addition, SCT ensures security up to the birthday bound even when nonces are reused, in the strong nonce-misuse resistance sense (MRAE) of Rogaway and Shrimpton (EUROCRYPT 2006). To the best of our knowledge, this is the first authenticated encryption mode that provides at the same time close-to-optimal security in the nonce-respecting scenario and birthday-bound security for the nonce-misuse scenario. While two passes are necessary to achieve MRAE-security, our mode enjoys a number of desirable features: it is simple, parallelizable, it requires the encryption direction only, it is particularly efficient for small messages (no precomputation is required) and it allows incremental update of associated data.

We are looking for excellent applicants with a strong international standing from all theoretical and practical areas of IT-security and privacy, in particular in the area of Usable Security.

The position is part of the German IT-security center CISPA - Center for IT-Security, Privacy, and Accountability.

It addresses a broad range of research problems, from fundamental research questions to the development of new technologies and prototypic systems.

The close connection of the CISPA to the department of Computer Science (CS), the Max-Planck-Institute (MPI) for Informatics, the MPI for Software Systems, the German Research Center for Artificial Intelligence (DFKI), the Excellence Cluster Multimodal Computing and Interaction (MMCI), and the Graduate School for CS is of crucial importance for its success.

Collaboration with partners in the cross-border region SaarLorLux is explicitly supported by the “University of the Greater Region” project (http://www.uni-gr.eu).

Requirements:

• Outstanding scientific skills (publications in the leading international IT-security conferences),
• management skills and
• excellent teaching skills & strong dedication towards teaching (teaching language for Master studies and the graduate school is English).

Participation towards establishing the CISPA and the acquisition of projects is expected.

Aside from requirements by public sector employment law, necessary qualifications for hiring include a tertiary education, pedagogical suitability, the ability for scientific work, generally proven by the doctoral degree and additional scientific achievements.

In accordance with the promotion of women act, Saarland University aims to increase the proportion of women in this type of employment and actively encourages applications from women. For candidates with equal qualifications, preference will be given to p

The Chair for Information Security and Cryptography at University of Trier, Germany, offers a full-time Post-Doc position in the area of e-voting, with a focus on cryptographic aspects.

The position is available immediately and is fully funded with an internationally competitive salary.

Contracts are initially offered for one year.

The deadline for applications is November 30th, 2015. Late applications will be considered until the position is filled.

See http://infsec.uni-trier.de/jobopenings for the official job announcement.

We are looking for excellent applicants from all applied areas of IT-security and privacy, in particular in the area of Network Security.

The position is part of the German IT-security center CISPA - Center for IT-Security, Privacy, and Accountability.

It addresses a broad range of research problems, from fundamental research questions to the development of new technologies and prototypic systems.

The close connection of the CISPA to the department of Computer Science (CS), the Max-Planck-Institute (MPI) for Informatics, the MPI for Software Systems, the German Research Center for Artificial Intelligence (DFKI), the Excellence Cluster Multimodal Computing and Interaction (MMCI), and the Graduate School for CS is of crucial importance for its success.

Collaboration with partners in the cross-border region SaarLorLux is explicitly supported by the “University of the Greater Region” project (http://www.uni-gr.eu).

Requirements:

• Outstanding scientific skills (publications in the leading international IT-security conferences),
• management skills and
• excellent teaching skills & strong dedication towards teaching (teaching language for Master studies and the graduate school is English).

Participation towards establishing the CISPA and especially the acquisition of projects is expected.

Aside from requirements by public sector employment law, necessary qualifications for hiring include a tertiary education, pedagogical suitability, the ability for scientific work, generally proven by the doctoral degree, and additional scientific achievements (e.g., an excellent publication record).

In accordance with the promotion of women act, Saarland University aims to increase the proportion of women in this type of employment and actively encourages applications from women. For candidates with equal qualifications, preference will be given to peo

Secure computation research has gained traction internationally in the last five years. In the United States, the DARPA PROCEED program (2011-2015) focused on development of multiple SC paradigms and improving their performance. In the European Union, the PRACTICE program (2013-2016) focuses on its use to secure cloud computing. Both programs have demonstrated exceptional prototypes and performance improvements. In this paper, we collect the results from both programs and other published literature to present the state of the art in what can be achieved with today\'s secure computing technology. We consider linear secret sharing based computations, garbled circuits and fully homomorphic encryption. We describe theoretical and practical criteria that can be used to characterize secure computation paradigms and provide an overview of common benchmarks such as AES evaluation.

Gentry\'s bootstrapping technique is the most famous method of obtaining fully homomorphic encryption. In previous work I proposed a fully homomorphic encryption without bootstrapping which has the weak point in the plaintext. In this paper I propose the improved fully homomorphic encryption scheme on non-associative octonion ring over finite ring with composite number modulus where the plaintext p consists of three numbers u,v,w. The proposed fully homomorphic encryption scheme is immune from the \"p and -p attack\". As the scheme is based on computational difficulty to solve the multivariate algebraic equations of high degree while the almost all multivariate cryptosystems proposed until now are based on the quadratic equations avoiding the explosion of the coefficients. Because proposed fully homomorphic encryption scheme is based on multivariate algebraic equations with high degree or too many variables, it is against the Gröbner basis attack, the differential attack, rank attack and so on.

It is proved that if there exists the PPT algorithm that decrypts the plaintext from the ciphertexts of the proposed scheme, there exists the PPT algorithm that factors the given composite number modulus.

Multiplicative complexity is a complexity measure defined

as the minimum number of AND gates required to implement a given primitive by a circuit over the basis (AND, XOR, NOT). Implementations of ciphers with a small number of AND gates are preferred in protocols for fully homomorphic encryption, multi-party computation and zero-knowledge proofs. In 2002, Fischer and Peralta showed that the number of $n$-variable Boolean functions with multiplicative complexity one equals $2\\binom{2^n}{3}$. In this paper, we study Boolean functions with multiplicative complexity 2. By characterizing the structure of these functions in terms of affine equivalence relations, we provide a closed form formula for the number of Boolean functions with multiplicative complexity 2.

This paper shows that it is feasible to implement the stateless hash-based signature scheme SPHINCS-256 on a \"very small device\" with memory even smaller than a signature and limited computing power. We demonstrate that it is possible to generate and verify the 41\\,KB signature on an ARM Cortex M3 that only has 16\\,KB of memory available.

We provide benchmarks for our implementation which show that this can be used in practice. To analyze the costs of using the stateless SPHINCS scheme instead of its stateful alternatives, we also implement XMSS^{MT} on this platform and give a comparison.

In this very short note we prove that the pseudo-random index j of RC4 is indeed not pseudo-random. This is a simple result that missed our attention for quite a long time. We show that in long term Pr(j = i+1) = 1/N - 1/N^2, instead of the random association 1/N and this happens for the non-existence of the condition S[i] = 1 and j = i+1 that is mandatory for the non-existence of the Finney cycle.

We show that homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure homomorphic encryption scheme cannot be implemented by circuits of polynomial size and constant depth, i.e., in the class $\\ac^0$. In contrast, we observe that there exist ordinary public-key encryption schemes of quasipolynomial security in $\\ac^0$ assuming noisy parities are exponentially hard to learn. We view this as evidence that homomorphic evaluation is inherently more complex than basic operations in encryption schemes.

Current issues with mass surveillance and a lack of end-user encryption, coupled with a growing demand for key escrow under legal oversight and certificate authority security concerns, raises the question of the appropriateness of continued general dependency on PKI. Under this context, we examine Identity-Based Encryption (IBE) as an alternative to public-key encryption, contrasting the two in light of present interests. Balancing goals of encryption and (limited) key escrow, we compare IBE schemes involving multiple private-key generators (PKGs) where trust is not placed in a single entity, but spread evenly amongst many. Finally, we present CARIBE, a cascaded IBE scheme, and prove the security of it in the computational model. CARIBE combines the ease-of-use of IBE with key escrow, limited to the case when the entire set of participating PKGs collaborate. As a focal point, due to its construction, CARIBE also allows for maximum flexibility and user-side control of which PKGs should be allowed into the web of trust.

Nonlinearity is one of the most challenging combinatorial property in the domain of Boolean function research. Obtaining nonlinearity greater than the bent concatenation bound for odd number of variables continues to be one of the most sought after combinatorial research problems. The pioneering result in this direction has been discovered by Patterson and Wiedemann in 1983 (IEEE-IT), which considered Boolean functions on $5 \\times 3 = 15$ variables that are invariant under the actions of the cyclic group

${GF(2^5)}^\\ast \\cdot {GF(2^3)}^\\ast$ as well as the group of Frobenius authomorphisms. Such Boolean functions posses nonlinearity greater than the bent concatenation bound, namely $2^{n-1} - 2^{\\frac{n-1}{2}}$. The next possible option for obtaining such functions is on $7 \\times 3 = 21$ variables. However, obtaining such functions remained elusive for more than three decades even after substantial efforts as evident in the literature. In this paper, we exploit combinatorial arguments together with heuristic search to demonstrate such functions for

the first time.

We describe a cryptanalysis of the GGH15 multilinear maps. Our attack breaks the multipartite key-agreement protocol by generating an equivalent user private key.

The Cut-and-choose paradigm gives by far the most popular and efficient secure two-party computation protocols in the standard malicious model, able to offer s bits of security with only s copies of garbled circuits in the one-time execution scenario. Nielsen and Orlandi et al. have even proposed the seminal idea of LEGO-style cut-and-choose to further reduce the number of circuit copies to less than s while still keep constant round complexity. However, a substantial gap still exists between the theoretical idea of LEGO cut-and-choose and a practical implementation, e.g., LEGO is not compatible with free-XOR and uses expensive asymmetric key operations for soldering, while MiniLEGO leaves the important building-block of soldering unspecified.

In this work, we introduce XOR-Homomorphic Interactive Hash and propose an efficient implementation of this primitive by combining Reed-Solomon encoding and k-out-of-n oblivious transfers. We show how to apply this primitive to solve the performance-critical wire-soldering problem and propose a new LEGO-style cut-and-choose protocol. Comparing to previous LEGO-style protocols, ours only requires a single (as opposed to \"a majority of\") correctly garbled gate in each bucket to guarantee security against malicious adversaries. Plus, through integrating Half-Gates garbling, we double the chance a \"bad\" gate being detected in the check stage (compared to MiniLEGO). Our construction is more bandwidth-efficient than Lindell (CRYPTO, 2013) either when the circuit size N is sufficiently large, or when N is larger than a threshold solely determined by the ratio between the input and circuit sizes. E.g., we use less bandwidth for computing most linear and sub-linear functions.

Deploying a LEGO-style cut-and-choose protocol involves convoluted protocol parameter selection. To this end, we give a thorough analysis of the relations among all protocol parameters and propose efficient algorithms that automate the search for the optimal parameter configuration based on a requirement specification (i.e., the security parameters s,k and application parameter N) with provable accuracy.

Last, we formally prove a tight bound on the benefit of LEGO-style secure computation protocols, in the sense that the circuit duplication factor $\\kappa$ has to be larger than 2 and any $\\kappa > 2$ is indeed achievable. This corrects a common mistake of claiming LEGO cut-and-choose can reduce $\\kappa$ to $O(sk/ \\log N)$ since $2 \\not\\in O(sk/\\log N)$.

An Ultimate Transposition Cipher (UTC) is defined as a cipher that transposes any permutation of some n elements to any other permutation of the same elements. Hence, by listing together the protected message and plausible alternatives to it, and then mixing it, one secures a ciphertext which the intended reader will readily \"un-mix\" (using the shared key), but the cryptanalyst will find proper keys for all the \'decoy messages\' and will not be able to go further. The UTC transposed permutation (the ciphertext) projects mathematical parity towards these plausible candidates for the actual message sent. We show that in real life situations when both sides can reasonably prepare a list of plausible plaintexts, the UTC equals the mathematical security offered by Vernam\'s One-Time-Pad, albeit, without Vernam\'s key size inconvenience. UTC decoys may be constructed manually or with AI. Applying a UTC protection before further encrypting with any common cipher will add a new dimension of equivocation (a clear entropic advantage) to the prevailing intractability-only protection. An example for an actual UTC is referenced and described.

In this paper we analyze three methods to detect cache-based side-channel attacks in real time, preventing or limiting the amount of leaked information. Two of the three methods are based on machine learning techniques and all the three of them can successfully detect an attacker in about one fifth of the time required to complete the attack. There were no false positives in our test environment. Moreover we could not measure a change in the execution time of the processes involved in the attack, meaning there is no perceivable overhead. We also analyze how the detection systems behave with a modified version of one of the spy processes. With some optimization we are confident these systems can be used in real world scenarios.

We investigate a well-known way to construct pseudo-random sequences by separation p-adic coordinate sequences of linear recurrences over Galois ring. Commonly

it is necessary to know rank estimations of separated sequences.

In this article we describe divisors of the minimal polynomial of the second p-adic

coordinate sequence of the linear recurrent sequence of maximal period/MP-LRS

over non-trivial Galois ring of odd characteristic in dependence of the initial vector

of this LRS.

Also we describe polynomials divisible by that minimal polynomial in dependence of the initial vector of this LRS.

As a corollary we get non-trivial upper and lower estimations for the rank of the

second coordinate sequence of such MP-LRS which provides us by possibility to use

it in pseudo-random generation.

We say that the Galois ring is non-trivial, if it differs from Galois field and from

quotient ring too.

These results were worked out with participation of V.L.Kurakin as a supervisor.

Author is very grateful to V.L.Kurakin for his participation in this work

In Cornell\'s \"CS4830: Introduction to Cryptography\" offered Fall 2015, students are asked to devise a physical secure two-party protocol for computing AND, using 4 cards or fewer. An elegant 5-card scheme was first proposed by Boer et al. Recently, in Asiacrypt 2012, Mizuki et al. were the first to improve the scheme to 4 cards. Although they mention that 4 cards is the minimum -- the minimum only holds when users must encode their input each with two cards.

Given the collective wisdom of our Cornell CS4830 students, we demonstrate an array of creative schemes using from 1 to 4 cards. Our students documented these solutions in a homework assignment, many of which are unanticipated by the instructor and the TAs. We had fun with students\' solutions and therefore would like to share them. Several of the students solutions are simpler than the standard textbook version by Boer et al., and we imagine that they could be useful for pedagogical purposes.