International Association
for Cryptologic Research

From August 16 to August 18
Location: Ottawa, Canada
More Information: http://sacconference.org/

In this paper, we describe a variant of the cube attack with much better-understood Preprocessing Phase, where complexity can be calculated without running the actual experiments and random-like search for the cubes. We apply our method to a few different cryptographic algorithms, showing that the method can be used against a wide range of cryptographic primitives, including hash functions and authenticated encryption schemes. We also show that our key-recovery approach could be a framework for side-channel attacks, where the attacker has to deal with random errors in measurements.

We present TWORAM, the first efficient round-optimal oblivious RAM (ORAM) scheme. TWORAM provides oblivious access of a memory index $y$ in exactly two rounds: The client prepares an encrypted query encapsulating $y$ and sends it to the server. The server accesses memory obliviously and returns encrypted information containing the desired value $\\mathsf{M}[y]$. The cost of TWORAM is only a multiplicative factor of security parameter higher than the tree-based ORAM schemes such as the path ORAM of Stefanov et al. (CCS, 2013). TWORAM gives rise to interesting applications, and in particular to the first fully-secure searchable symmetric encryption scheme where search is sublinear and search pattern is not leaked---access pattern can also be concealed if we assume the documents are stored in the obliviously accessed memory $\\mathsf{M}$.

Functional encryption provides fine-grained access control for encrypted data, allowing each user to learn only specific functions of the encrypted data. We study the notion of \\emph{hierarchical} functional encryption, which augments functional encryption with \\emph{delegation} capabilities, offering significantly more expressive access control.

We present a {\\em generic transformation} that converts any general-purpose public-key functional encryption scheme into a hierarchical one without relying on any additional assumptions. This significantly refines our understanding of the power of functional encryption, showing (somewhat surprisingly) that the existence of functional encryption is equivalent to that of its hierarchical generalization.

Instantiating our transformation with the existing functional encryption schemes yields a variety of hierarchical schemes offering various trade-offs between their delegation capabilities (i.e., the depth and width of their hierarchical structures) and underlying assumptions. When starting with a scheme secure against an unbounded number of collusions, we can support \\emph{arbitrary} hierarchical structures. In addition, even when starting with schemes that are secure against a bounded number of collusions (which are known to exist under rather minimal assumptions such as the existence of public-key encryption and shallow pseudorandom generators), we can support hierarchical structures of bounded depth and width.

In this paper we propose an efficient single-round, two-party identity based authenticated key agreement protocol in the setting of multiple Private Key Generators (PKGs). One of the major advantages of our construction is that it does not involve any pairing operations. To date, existing protocols in the Identity Based Key Agreement domain revolves around a single PKG environment. Efforts to exploit the multiple PKGs paradigm have placed excessive reliance on Elliptic Curve Cryptography and bilinear pairings. These are computationally intensive and cannot be used when computation is premium, such as in a Vehicular Ad-Hoc Network (VANET), specially when the vehicles in a VANET need to perform a large of key agreement. Previous attempts to model identity based key agreement in multiple PKG scenario by Chen and Kundla, McCullagh have very limited scope and provide weak security guarantees. We propose a new security model for identity based key agreement protocols involving multiple PKGs based on the eCK security model which is much more stronger than the existing models and captures additional properties like Key Compromise Impersonation and forward secrecy that were not captured by the previous models. Our protocol is proven secure in this new security model under the Gap Diffie Hellman (GDH) assumption in the Random Oracle (RO) model.

Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs~\\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. NMCs have emerged as a fundamental object at the intersection of coding theory and cryptography.

A large body of the recent work has focused on various constructions of non-malleable codes in the split-state model.

Many variants of NMCs have been introduced in the literature i.e. strong NMCs, super strong NMCs and continuous NMCs. Perhaps the most useful notion among these is that of continuous non-malleable codes, that allows for continuous tampering by the adversary.

In this paper we give the first efficient, information-theoretic secure construction of continuous non-malleable codes in $2$-split-state model. Enroute to our main result, we obtain constructions for almost all possible notion of non-malleable codes that have been considered in the split-state model, and for which such a construction is possible. Our result is obtained by a series of black-box reductions starting from the non-malleable codes from~\\cite{ADL14}.

One of the main technical ingredient of our result is a new concept that we call \\emph{inception coding}. We believe it may be of independent interest.

The classical Fast Fourier Transform (FFT) allows to compute in quasi-linear time the product of two polynomials, in the circular convolution ring $\\mathbb R[x]/(x^d -1)$ --- a task that naively requires quadratic time. Equivalently, it allows to accelerate matrix-vector products when the matrix is circulant.

In this work, we discover that the ideas of the FFT can be applied to speed up the orthogonalization process of a circulant matrix. We show that, when $n$ is composite, it is possible to proceed to the orthogonalization in an inductive way, leading to a structured Gram-Schmidt decomposition. In turn, this structured Gram-Schmidt decomposition accelerates a cornerstone lattice algorithm: the Nearest Plane algorithm.

The results easily extend to cyclotomic rings, and can be adapted to Gaussian Samplers. This finds applications in lattice-based cryptography, improving the performances of

trapdoor functions.

We formalize the use of Bitcoin as a source of publicly-verifiable randomness. As a side-effect of Bitcoin\'s proof-of-work-based consensus system, random values are broadcast every time new blocks are mined.

We can derive strong lower bounds on the computational min-entropy in each block: currently, at least 68 bits of min-entropy are produced every 10 minutes, from which one can derive over 32 near-uniform bits using standard extractor techniques. We show that any attack on this beacon would form an attack on Bitcoin itself and hence have a monetary cost that we can bound, unlike any other construction for a public randomness beacon in the literature. In our simplest construction, we show that a lottery producing a single unbiased bit is manipulation-resistant against an attacker with a stake of less than 50 bitcoins in the output, or about US$12,000 today. Finally, we propose making the beacon output available to smart contracts and demonstrate that this simple tool enables a number of interesting applications.

Bitcoin exchanges function like banks, securely holding their customers\' bitcoins on their behalf. Several exchanges have suffered catastrophic losses with customers permanently losing their savings. A proof of solvency demonstrates that the exchange controls sufficient reserves to settle each customer\'s account. We introduce Provisions, a privacy-preserving proof of solvency whereby an exchange does not have to disclose its Bitcoin addresses; total holdings or liabilities; or any information about its customers. We also propose an extension which prevents exchanges from colluding to cover for each other\'s losses. We have implemented Provisions and show that it offers practical computation times and proof sizes even for a large Bitcoin exchange with millions of customers.

The Cryptography Research Group seeks qualified PhD students for an immediate internship opening working on applied MPC projects. Successful candidate will have experience with implementing optimized garbled circuits and oblivious transfer protocols and a strong desire to have real-world impact. Projects in collaboration with industry partners will have an interdisciplinary focus. Start date for suitable candidate will be as soon as possible and last for 3 months.

http://privacyus.cs.ucl.ac.uk/

Funded by the EU H2020 Marie Sk?odowska-Curie program, the Privacy & Us Innovative Training Network will train thirteen creative, entrepreneurial and innovative early stage researchers (ESRs) to be able to reason, design and develop innovative solutions to questions related to the protection of citizens’ privacy, considering the multidisciplinary and intersectoral aspects of the issue. ESRs will be trained to face both current and future challenges in the area of privacy and usability.

The studentships have a duration of 36 months, starting August 2016. Students will be recruited and primarily based at the host institutions but will spend a minimum of six months in secondment to another member of the consortium or a partner organization.

All details (including consortium, positions, and application details) are available from the project website at

http://privacyus.cs.ucl.ac.uk/

KIWI is a young hardware startup based in Berlin, developing a keyless entry system “KIWI” which allows users to open doors securely using their cellphones or active RFID tokens. We are building a city-scale wireless sensor network to enable our vision of completely hands-free access for everyone. We build our own technology, from hardware, firmware through to our infrastructure and applications. At the moment, we need a great EMBEDDED ENGINEER to augment our existing team of embedded and RF specialists.

YOUR TASKS

* Design and implement firmware on embedded devices (ARM Cortex M0-M3-M4)

* Design, develop, code, test, verify and debug system software

* Review code and design

* Provide production and post-production support

YOUR QUALIFICATIONS

We are looking for an experienced engineer with

* Degree in Computer Science/Engineering/Electrical Engineering or equivalent work experience-surprise us!

* Experience in hands-on development and troubleshooting with embedded devices, including design and manufacture verification and board bring-up

* Solid programming experience with C

* Familiarity with ticket tracking tools, code review, unit testing, continuous integration, source control, and other tools for modern software development (except for GCC and GNU Make).

NICE TO HAVES

* Experience with ISM band communications/networking

* Bare-metal microcontroller development, including ARM Assembly

* Strong background in Cryptography

* Desire for strong coffee and stronger discussions

Come be a part of our diverse team! English and German are the main languages spoken in the office, however you will also be exposed to Spanish, French, and Polish.

WE OFFER

Our startup has a young international team, and you will be working with them in the heart of Berlin (no remotes, please). You

Motivated by a recently introduced HIMMO key predistribution scheme, we investigate the limits of various attacks on the polynomial interpolation problem with mixedmodular operations and hidden moduli. We firstly review the classical attack and consider itin a quantum-setting. Then, we introduce new techniques for finding out the secret moduli and consider quantum speed-ups.

In this paper, we analyze the security of cryptosystems using short generators over ideal lattices such as candidate multilinear maps

by Garg, Gentry and Halevi and fully homomorphic encryption by Smart

and Vercauteren. Our approach is based on a recent work by Cramer,

Ducas, Peikert and Regev on analysis of recovering a short generator of

an ideal of the q-th cyclotomic field from any generator of the ideal for

a prime power q. Unfortunately, the main result of Cramer et al. has

some flaws since they use an incorrect lower bound of the special values

of Dirichlet L-functions at 1.

Our main contribution is to correct Cramer et al.\'s main result by estimating explicit lower and upper bounds of the special values of Dirichlet L-functions at 1 for any non-trivial Dirichlet characters modulo a prime power. Moreover, we give various experimental evidence that recovering a short generator is succeeded with high probability. As a consequence, our analysis suggests that the security of the above cryptosystems based on the difficulty of recovering a short generator is reduced to solving the principal ideal problem under the number theoretical conjecture so-called Weber\'s class number problem.

In PQCrypto 2013 Yasuda, Takagi and Sakurai proposed an interesting signature scheme of efficiency $O(n^2)$ with parameter $(q=6781, n=121)$ claimed to have 140-bit security level. Later on almost at the same time two independent and different attacks were then proposed by Y. Hashimoto in PQCrypto 2014 and by the authors in ICISC 2014. Hashimoto\'s attack has complexity $O(n^4)$ and breaks $(q=6781, n=121)$ in several minutes. In this paper, we make an essential extension of our work in ICISC 2014. We develop for the our previous method a thorough and rigorous mathematical theory by applying intensively the theory of invariant subspaces, then work out a much better attack with complexity $O(n^4)$, and especially implement it successfully. Our new attack efficiently recovers equivalent private keys of many randomly generated instances, especially breaking $(q=6781, n=121)$ in only about 14.77 seconds, much faster than Y. Hashimoto\'s attack. The approach developed here might have further applications.

We report on the design and implementation of a system that uses multiparty computation to enable banks to benchmark their customers\' confidential performance data against a large representative set of confidential performance data from a consultancy house. The system ensures that both the banks\' and the consultancy house\'s data stays confidential, the banks as clients learn nothing but the computed benchmarking score. In the concrete business application, the developed prototype help Danish banks to find the most efficient customers among a large and challenging group of agricultural customers with too much debt. We propose a model based on linear programming for doing the benchmarking and implement it using the SPDZ protocol by Damg{\\aa}rd et al., which we modify using a new idea that allows clients to supply data and get output without having to participate in the preprocessing phase and without keeping state during the computation.

We ran the system with two servers doing the secure computation using a database with information on about 2500 users. Answers arrived in about 25 seconds.

Bitcoin is the first decentralized crypto-currency that is currently by far the most popular one in use. The bitcoin transaction syntax is

expressive enough to setup digital contracts whose fund transfer can be enforced automatically.

In this paper, we design protocols for the bitcoin

voting problem, in which there are n voters, each of which wishes to fund exactly one of two candidates A and B. The winning candidate is determined by majority voting, while the privacy of individual vote is preserved. Moreover, the decision is irrevocable in the sense

that once the outcome is revealed, the winning candidate is guaranteed to have the funding from all n voters.

As in previous works, each voter is incentivized to follow the protocol by being required to put a deposit in the system, which will be used as compensation if he deviates from the protocol. Our solution is similar to previous protocols used for lottery, but needs

an additional phase to distribute secret random numbers via zero-knowledge-proofs. Moreover, we have resolved a security issue in previous protocols that could prevent compensation from being paid.

The difficulty of integer factorization is fundamental to modern cryptographic security using RSA encryption and signatures. Although a 512-bit RSA modulus was first factored in 1999, 512-bit RSA remains surprisingly common in practice across many cryptographic protocols. Popular understanding of the difficulty of 512-bit factorization does not seem to have kept pace with developments in computing power. In this paper, we optimize the CADO-NFS and Msieve implementations of the number field sieve for use on the Amazon Elastic Compute Cloud platform, allowing a non-expert to factor 512-bit RSA public keys in under four hours for \\$75. We go on to survey the RSA key sizes used in popular protocols, finding hundreds or thousands of deployed 512-bit RSA keys in DNSSEC, HTTPS, IMAP, POP3, SMTP, DKIM, SSH, and PGP.

Recent side-channel attacks on elliptic curve algorithms have shown that the security of these cryptosystems is a matter of serious concern.

The development of techniques in the area of Template Attacks makes it feasible to extract a 256-bit secret key with only 257 traces.

This paper enhances the applicability of this attack by exploiting both the horizontal leakage of the carry propagation during the finite field multiplication, and the vertical leakage of the input data. As a further contribution, our method provides detection and auto-correction of possible errors that may occur during the key recovery. These enhancements come at the cost of extra traces, while still providing a practical attack. Finally, we show that the elliptic curve technology developed in PolarSSL running on a ARM STM32F4 platform is completely vulnerable, when used without any modifications or countermeasures.

Self encrypting devices (SEDs) doing full disk encryption are getting more and more widespread. Hardware implemented AES encryption provides fast and transparent encryption of all user data on the storage medium, at all times. In this paper we will look into some models in a self encrypting external hard drive series; the Western Digital My Passport series. We will describe the security model

of these devices and show several security weaknesses like RAM leakage, weak key attacks and even backdoors on some of these devices, resulting in decrypted user data, without the knowledge of any user credentials.