International Association
for Cryptologic Research

Protocols for secure computation enable parties to compute a joint function on their private inputs without revealing anything but the result. A foundation for secure computation is oblivious transfer (OT), which traditionally requires expensive public key cryptography. A more efficient way to perform many OTs is to extend a small number of base OTs using OT extensions based on symmetric cryptography.

In this work we present optimizations and efficient implementations of OT and OT extensions in the semi-honest model. We propose a novel OT protocol with security in the standard model and improve OT extensions with respect to communication complexity, computation complexity, and scalability. We also provide specific optimizations of OT extensions that are tailored to the secure computation protocols of Yao and Goldreich-Micali-Wigderson and reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations. By applying our implementation to current secure computation frameworks, we can securely compute a Levenshtein distance circuit with 1.29 billion AND gates at a rate of 1.2 million AND gates per second. Moreover, we demonstrate the importance of correctly implementing OT within secure computation protocols by presenting an attack on the FastGC framework.

All known protocols implementing broadcast from synchronous point-to-point channels tolerating any $t < n$ Byzantine corruptions have communication complexity at least $\\Omega(\\ell n^2)$. We give cryptographically secure and information-theoretically secure protocols for $t < n$ that communicate $O(\\ell n)$ bits in order to broadcast sufficiently long $\\ell$ bit messages. This matches the optimal communication complexity bound for any protocol allowing to broadcast $\\ell$ bit messages. While broadcast protocols with the optimal communication complexity exist in cases where $t < n/3$ (by Liang and Vaidya in PODC \'11) or $t < n/2$ (by Fitzi and Hirt in PODC \'06), this paper is the first to present such protocols for $t < n$.

In his keynote speech at CHES 2004, Kocher advocated that side-channel attacks were an illustration that formal cryptography was not as secure as it was believed because some assumptions (e.g., no auxiliary information is available during the computation) were not modeled.

This failure is due to the fact that formal methods work with models rather than implementations.

Of course, we can use formal methods to prove non-functional security properties such as the absence of side-channel leakages.

But a common obstacle is that those properties are very low-level and appear incompatible with formalization.

To avoid the discrepancy between the model and the implementation, we apply formal methods directly on the implementation.

Doing so, we can formally prove that an assembly code is leak-free, provided that the hardware it runs on satisfies a finite (and limited) set of properties that we show are realistic.

We apply this technique to prove that a PRESENT implementation in 8~bit AVR assembly code is leak-free.

Key exchange with unilateral authentication (short: unilateral key exchange)

is an important primitive in practical security protocols; a prime example is

the widely deployed TLS protocol, which is usually run in this mode.

Unilateral key-exchange protocols are employed in a client-server setting

where only the server has a certified public key. The client is then

authenticated by sending credentials via a connection that is secured with the

key obtained from the protocol. Somewhat surprisingly and despite its

importance in practical scenarios, this type of key exchange has received

relatively little attention in the cryptographic literature compared to the

type with mutual authentication.

In this work, we follow the constructive cryptography paradigm of Maurer and

Renner (ICS 2011) to obtain a (composable) security definition for

key-exchange protocols with unilateral authentication: We describe a

\"unilateral key\" resource and require from a key-exchange protocol that it

constructs this resource in a scenario where only the server is authenticated.

One main advantage of this approach is that it comes with strong composition

guarantees: Any higher-level protocol proven secure with respect to the

unilateral key resource remains secure if the key is obtained using a secure

unilateral key-exchange protocol.

We then describe a simple protocol based on any CPA-secure KEM and prove that

it constructs a unilateral key (previous protocols in this setting relied on a

CCA-secure KEM). The protocol design and our security analysis are fully

modular and allow to replace a sub-protocol $\\pi$ by a different sub-protocol

$\\pi\'$ by only proving security of the sub-protocol $\\pi\'$; the composition

theorem immediately guarantees that the security of the modified full protocol

is maintained. In particular, one can replace the KEM by a sub-protocol based

on Diffie-Hellman, obtaining a protocol that is similar to the A-DHKE protocol

proposed by Shoup. Moreover, our analysis is simpler because the actual

key-exchange part of the protocol can be analyzed in a simple three-party

setting; we show that the extension to the multi-party setting follows

generically.

Compared to the TLS handshake protocol, the \"de facto\" standard for unilateral

key exchange on the Internet, our protocol is more efficient (only two

messages) and is based on weaker assumptions.

New GOST R 34.11-2012 standard has been recently selected by the Russian government to replace the old one. The algorithm is based on the hash function Stribog introduced in 2010. The high-level structure of the new hash function is similar to GOST R 34.11-94 with minor modifications. However, the compression function was changed significantly. Such a choice of the compression algorithm has been motivated by the Rjndael due to simplicity and understandable algebraic structure.

In this paper we consider a number of algebraic aspects of the GOST R 34.11. We show how one can express the cipher in AES-like form over the finite field $\\F_{2^8}$, and consider some approaches that can be used for the fast software implementation.

We show how to securely obfuscate a new class of functions: {\\em conjunctions of $NC0_d$ circuits}. These are functions of the form $C(x) = \\bigwedge_{i=1}^m C_i(x)$, where each $C_i$ is a boolean $NC0_d$ circuit, whose output bit is only a function of $d = O(1)$ bits of the input $x$. For example, $d$-CNFs, where each clause is a disjunction of at most $d$ variables, are in this class. Given such a function, we produce an obfuscated program that preserves the input-output functionality of the given function, but reveals nothing else. Our construction is based on multilinear maps, and can be instantiated using the recent candidates proposed by Garg, Gentry and Halevi (EUROCRYPT 2013) and by Coron, Lepoint and Tibouchi (CRYPTO 2013).

We prove that the construction is a secure obfuscation in a generic multilinear group model, under the black-box definition of Barak et al.\\ (CRYPTO 2001). Security is based on a new {\\em worst-case} hardness assumption about exponential hardness of the NP-complete problem 3-SAT, the {\\em Bounded Speedup Hypothesis}.

One of the new techniques we introduce is a method for enforcing input consistency, which we call {\\em randomizing sub-assignments}. We hope that this technique can find further application in constructing secure obfuscators.

The family of functions we obfuscate is considerably richer than previous works that consider black-box obfuscation. As one application, we show how to achieve {\\em obfuscated functional point testing}: namely, to construct a circuit that checks whether $f(x)=y$, where $f$ is an arbitrary ``public\'\' polynomial-time computable function, but $y$ is a ``secret\'\' point that is hidden in the obfuscation.

Combinatorial key predistribution schemes can provide a practical solution to the problem of distributing symmetric keys to the nodes of a wireless sensor network. Such schemes often inherently suit networks in which the number of nodes belongs to some restricted set of values (such as powers of primes). In a recent paper, Bose, Dey and Mukerjee have suggested that this might pose a problem, since discarding keyrings to suit a smaller network might adversely affect the properties of the scheme.

In this paper we explore this issue, with specific reference to classes of key predistribution schemes based on transversal designs. We demonstrate through experiments that, for a wide range of parameters, randomly removing keyrings in fact has a negligible and largely predictable effect on the parameters of the scheme. In order to facilitate these computations, we provide a new, efficient, generally applicable approach to computing important properties of combinatorial key predistribution schemes.

We also show that the structure of a resolvable transversal design can be exploited to give a deterministic method of removing keyrings to adjust the network size, in such a way that the properties of the resulting scheme are easy to analyse. We show that these schemes have the same asymptotic properties as the transversal design schemes on which they are based, and that for most parameter choices their behaviour is very similar.

Functional encryption is an important generalization of several types of encryption such as public-key, identity-based, and attribute-based encryption. Numerous different security definitions for functional encryption have been proposed, most of them being rather complex and involving several algorithms. Many of these definitions differ in details such as which algorithm has oracle access to which oracle, while the consequences of specific choices are often unclear. This spans a large space of possible definitions without a consensus on the adequacy of specific points in this space. What a particular definition means and for which applications it is suitable remains unsettled.

To remedy this situation, we propose a novel interpretation of functional encryption, based on the Constructive Cryptography framework, in which a protocol is seen as a construction of an ideal resource with desired properties from a real resource, which is assumed to be available. The resulting ideal resource can then be used as a real resource in other protocols to construct more advanced resources. The real resource we consider here corresponds to a public repository that allows everyone to read its contents. Such repositories are indeed widely available on the internet. Using functional encryption, we construct, as the ideal resource, a repository with fine-grained access control.

Based on this constructive viewpoint, we propose a new security definition, called FA-security, for functional encryption by adequately modifying an established definition, and prove the equivalence to our notion of construction. This gives evidence that FA-security is an appropriate definition. We further consider known impossibility results and examine a weaker security definition. We show that this weaker definition, for which secure schemes exist, is sufficient to construct a repository that restricts the number and order of interactions. This makes explicit how such schemes can be used.

We describe a security-preserving construction of a random permutation of domain size N from a random function, the construction tolerating adversaries asking all N plaintexts, yet employing just \\Theta(lg N) calls, on average, to the one-bit-output random function. The approach is based on card shuffling. The basic idea is to use the \\textit{sometimes-recurse} transformation: lightly shuffle the deck (with some other shuffle), cut the deck, and then recursively shuffle one of the two halves. Our work builds on a recent paper of Ristenpart and Yilek.

In this paper we use differential cryptanalysis to attack the winner of the SHA-3 competition, namely Keccak hash function. Despite more than 6 years of intensive cryptanalysis there have been known only two preimage attacks which reach 3 (or slightly more) rounds. Our 3-round preimage attack improves the complexity of those two existing attacks and it is obtained with a different technique. We also show the partial preimage attack on the 4-round Keccak, exploiting two properties of the linear step of the Keccak-f permutation.

From August 17 to August 21
Location: Santa Barbara, USA
More Information: http://www.iacr.org/conferences/crypto2014/

The Faculty of Electrical Engineering and Information Technology at the Ruhr-Universität Bochum invites applications for the position of a Junior Professorship for Mobile Security.

The future occupant of the position Mobile Security represents the department in this field in research and teaching. The appointment will be at the rank of an assistant professor.

His/her scientific work should focus on one or more of the following key research areas:

- Security of mobile systems at the hard- or software level

- Security aspects of new application domains (especially cyber-physical systems)

- Reverse engineering of hardware and software systems

- Security aspects of distributed systems

- Secure and dependable software systems

A doctoral degree of outstanding quality and evidence of special aptitude in teaching are just as much required as the willingness to participate in the self-governing bodies of the RUB. Furthermore, we expect the candidate to generally get involved in university processes according to RUB’s mission statement. Beside the specific skills the candidate should have a profound didactical qualification to develop new learning environments such as research oriented teaching.

We expect furthermore readiness to participate in interdisciplinary academic work, willingness and ability to attract external funding, ability to work in teams, and the will to participate in collaborative research.

The Ruhr-Universität Bochum is an equal opportunity employer.

Submission: 27 October 2013
Notification: 29 November 2013
From January 20 to January 20
Location: Vienna, Austria
More Information: http://www.cs2.deib.polimi.it/

UTRCI seeks candidates with expertise in cyber-physical security, wireless sensor networks and embedded systems to join their Networks & Embedded Systems group in Cork, Ireland. The successful candidates are expected to coordinate and primarily execute R&D activities within international projects on cyber-physical systems security. UTRC is developing capability in cyber-physical security to apply to the full range of UTC (http://www.utc.com) products and programs.

The candidate should have a solid background in vulnerability assessment and thorough knowledge of best practices in countermeasures and design processes for secure systems, for example, encryption, authentication and anomaly detection. A successful candidate would also have a solid background in embedded systems and cyber-physical systems with past experience in applying cyber-physical security concepts to the particular constraints of embedded systems, including scalability of countermeasures. Practical experience in identifying and demonstrating both vulnerabilities and countermeasures is highly desirable for this position.

Candidates should have a proven track record of research (top journals and conferences) in cyber-security or cyber-physical security.

The ideal candidate is a self-starter who works well in an international teaming environment, is extremely well-organized and has excellent interpersonal, leadership and communication skills. Besides technical excellence, an entrepreneurial attitude towards innovation is essential.

The candidate should have a PhD in Computer Science, Electrical and Computer Engineering or related fields, with particular expertise in Cyber-Physical Systems and Wireless Sensor Networks. The candidate should also have a strong international publication record and demonstrated ability to do independent research. Fluency in written and spoken English is required.

Hochschule Furtwangen University, Germany, Two Full-time Ph.D. Positions

* The Chair for Security in Distributed Systems, computer science Hochschule Furtwangen, Germany, offers two full-time PhD positions

* The position involves research in the area of IT-security within the BMBF project

ProSeCCo \\\'Promotionsvorhaben zur Erarbeitung von Sicherheitserweiterungen für das

Cloud Computing\\\' in cooperation with the Albert-Ludwig University of Freiburg at the \\\'Institut für Informatik und Gesellschaft (IIG) - Telematik\\\' (Prof. Dr.

Günter Müller) and the university of Karlsruhe (KIT) at the \\\'Institut for Kryptographie und Sicherheit (IKS) (Prof. Dr. Jörn Müller-Quade).

The successful candidate is expected to contribute to research in IT-Security and applied cryptography for Cloud Security.

Besides other cloud security related aspects topics of interest for the two open positions are

- application of homomorphic cryptographic primitives for secure cloud storage,

- monitoring- and attestation mechanisms to control information flow between VMs.

* The position is available from November on and is fully funded. The salary scale for both positions is TV-L E13.

The gross income depends on the candidate\\\'s experience level. At the lowest level it corresponds to approx. 40,000 EUR per year.

* Contracts are initially offered for two years. An extension is possible.

* She or he is given the possiblity to carry out a Ph.D.

* The successful candidate should have a Master\\\'s degree in Computer Science, Mathematics, Information Security, or a related field.

Deep Knowledge in cryptography is not a must but an asset.

* The deadline for applications is September 20, 2013. However, late applications will be considered until the position is filled.

Please send your application with reference number 11

Submission: 12 April 2014
Notification: 13 June 2014
From August 22 to August 23
Location: Santa Barbara, California, USA
More Information: http://csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/SHA3-aug2014-call-for-papers.pdf

This note reports major previously unpublished security vulnerabilities in the password-only authenticated three-party key exchange protocol due to Lee and Hwang (Information Sciences, 180, 1702-1714, 2010): (1) the Lee-Hwang protocol is susceptible to a man-in-the-middle attack and thus fails to achieve implicit key authentication; (2) the protocol cannot protect clients\' passwords against an offline dictionary attack; and (3) the indistinguishability-based security of the protocol can be easily broken even in the presence of a passive adversary.

We show that (leveled) fully homomorphic encryption (FHE) can be based on the hardness of $\\otild(n^{1.5+\\epsilon})$-approximation for lattice problems (such as GapSVP) under quantum reductions for any $\\epsilon>0$ (or $\\otild(n^{2+\\epsilon})$-approximation under classical reductions). This matches the best known hardness for ``regular\'\' (non-homomorphic) lattice based public-key encryption up to the $\\epsilon$ factor. A number of previous methods had hit a roadblock at quasipolynomial approximation. (As usual, a circular security assumption can be used to achieve a non-leveled FHE scheme.)

Our approach consists of three main ideas: Noise-bounded sequential evaluation of

high fan-in operations; Circuit sequentialization using Barrington\'s Theorem; and finally,

successive dimension-modulus reduction.

Nonlinear feedback shift registers (NLFSRs) are used to construct pseudorandom generators for stream ciphers. Their theory is not so complete as that of linear feedback shift registers (LFSRs). In general, it is not known how to construct all NLFSRs with maximum period. The direct method is to search for such registers with suitable properties. Advanced technology of parallel computing has been applied both in software and hardware to search for maximum period NLFSRs having a fairly simple algebraic normal form.

Recently, the U.S National Security Agency has published the specifications of two families of lightweight block ciphers, SIMON and SPECK, in ePrint report 2013/404. The ciphers are developed with optimization towards both hardware and software in mind. While the specification paper discusses design requirements and performance of the presented lightweight ciphers thoroughly, no security assessment is given. This paper is a move towards filling that cryptanalysis gap for the SIMON family of ciphers. We present a series of observations on the presented construction that, in some cases, yield attacks, while in other cases may provide basis of further analysis by the cryptographic community. Specifically, we obtain attacks using classical- as well as truncated differentials. In the former case, we show how the smallest version of SIMON, Simon32/64, exhibits a strong differential effect.