International Association
for Cryptologic Research

Secure two-party computation allows two mutually distrusting parties to jointly compute an arbitrary function on their private inputs without revealing anything but the result. An interesting target for deploying secure computation protocols are mobile devices as they contain a lot of sensitive user data. However, their resource restrictions make this a challenging task.

In this work, we optimize and implement the secure computation protocol by Goldreich-Micali-Wigderson~(GMW) on mobile phones. To increase performance, we extend the protocol by a trusted hardware token (i.e., a smartcard). The trusted hardware token allows to pre-compute most of the workload in an initialization phase, which is executed locally on one device and can be pre-computed independently of the later communication partner. We develop and analyze a proof-of-concept implementation of generic secure two-party computation on Android smart phones making use of a microSD smartcard. Our use cases include private set intersection for finding shared contacts and private scheduling of a meeting with location preferences. For private set intersection, our token-aided implementation on mobile phones is up to two orders of magnitude faster than previous generic secure two-party computation protocols on mobile phones and even as fast as previous work on desktop computers.

Certificateless public key cryptography eliminates inherent key escrow problem in identity-based cryptography, and does not yet requires certificates as in the traditional public key infrastructure. However, most of certificateless signature schemes without random oracles have been demonstrated to be insecure. In this paper, we propose a new certificateless signature scheme and prove that our new scheme is existentially unforgeable against adaptively chosen message attack in the standard model. Performance analysis shows that our new scheme has shorter system parameters, shorter length of signature, and higher computational efficiency than the previous schemes in the standard model.

We propose an efficient Key-policy Attribute-based Encryption (KP-ABE)

scheme for general (monotone) Boolean circuits based on secret sharing and on a very particular and simple form of leveled multilinear maps,

called chained multilinear maps. The number of decryption key components is substantially reduced in comparison with the current scheme based on leveled multilinear maps, and the size of the multilinear map (in terms of bilinear map components) is less than the Boolean circuit depth, while it is quadratic in the Boolean circuit depth for the current scheme based on leveled multilinear map. Moreover, it is much easier to find chained multilinear maps than leveled multilinear maps. Selective security of the proposed schemes in the standard model is proved, under the decisional multilinear Diffie-Hellman assumption.

In a homomorphic signature scheme, given a vector of signatures $\\vec{\\sigma}$ corresponding to a dataset of messages $\\vec{\\mu}$, there is a {\\it public} algorithm that allows to derive a signature $\\sigma\'$ for message $\\mu\'=f(\\vec{\\mu})$ for any function $f$.

Given the tuple $(\\sigma\', \\mu\', f)$ anyone can {\\it publicly}

verify the result of the computation of function $f$.

Along with the standard notion of unforgeability

for signatures, the security of homomorphic signatures guarantees that no adversary is able to make a forgery $\\sigma^*$ for $\\mu^* \\neq f(\\vec{\\mu})$.

We construct the first homomorphic signature scheme for evaluating arbitrary functions. In our scheme, the public parameters and the size of the resulting signature grows linearly

with the depth of the circuit representation of $f$. Our scheme is secure in the standard model assuming hardness of

finding {\\it Small Integer Solutions} in hard lattices.

Furthermore, our construction has asymptotically fast verification

which immediately leads to a new solution for verifiable outsourcing with pre-processing phase. Previous state of the art constructions were limited to evaluating polynomials of constant degree, secure in random oracle model

without asymptotically fast verification.

We present the design, implementation and evaluation of the root of trust for the Trusted Execution Environment (TEE) provided by ARM TrustZone based on SRAM Physical Unclonable Functions (PUFs). We first implement a building block which provides the foundations for the root of trust: secure key storage and truly random source. The building block doesn\'t require on or off-chip secure non-volatile memory to store secrets, but provides a high-level security: resistance to physical attackers capable of controlling all external interfaces of the system on chip (SoC). Based on the building block, we build the root of trust consisting of seal/unseal primitives for secure services running in the TEE, and a software-only TPM service running in the TEE which provides rich TPM functionalities for the rich OS running in the normal world of TrustZone. The root of trust resists software attackers capable of compromising the entire rich OS. Besides, both the building block and the root of trust run on the powerful ARM processor. In one word, we leverage the SRAM PUF, commonly available on mobile devices, to achieve a low-cost, secure, and efficient design of the root of trust.

We consider *semi-adaptive* security for attribute-based encryption,

where the adversary specifies the challenge attribute vector after

it sees the public parameters but before it makes any secret key

queries. We present two constructions of semi-adaptive

attribute-based encryption under static assumptions with *short*

ciphertexts. Previous constructions with short ciphertexts either

achieve the weaker notion of selective security, or require

parameterized assumptions.

As an application, we obtain improved delegation schemes for Boolean

formula with *semi-adaptive* soundness, where correctness of the

computation is guaranteed even if the client\'s input is chosen

adaptively depending on its public key. Previous delegation schemes

for formula achieve one of adaptive soundness, constant

communication complexity, or security under static assumptions; we

show how to achieve semi-adaptive soundness and the last two

simultaneously.

In this paper, we introduce the concept of the derivative of sequence of numbers and define new statistical indices by which we discoverd new properties of randomly generated number sequences.

We also build a test for pseudo random generators based on these properties and use it to confirm the weakness of RC4 key scheduling algorithm that has been reported in the litterature.

In this rescpect we publish a new RC4\'s key scheduling algorithm that don\'t have this weakness.

One-time memories (OTM\'s) are simple, tamper-resistant cryptographic devices, which can be used to implement sophisticated functionalities such as one-time programs. Can one construct OTM\'s whose security follows from some physical principle? This is not possible in a fully-classical world, or in a fully-quantum world, but there is evidence that OTM\'s can be built using \"isolated qubits\" -- qubits that cannot be entangled, but can be accessed using adaptive sequences of single-qubit measurements.

Here we present new constructions for OTM\'s using isolated qubits, which improve on previous work in several respects: they achieve a stronger \"single-shot\" security guarantee, which is stated in terms of the (smoothed) min-entropy; they are proven secure against adversaries who can perform arbitrary local operations and classical communication (LOCC); and they are efficiently implementable.

These results use Wiesner\'s idea of conjugate coding, combined with error-correcting codes that approach the capacity of the q-ary symmetric channel, and a high-order entropic uncertainty relation, which was originally developed for cryptography in the bounded quantum storage model.

Formal verification of the security of software systems is gradually moving from the traditional focus on idealized models, to the more ambitious goal of producing verified implementations. This trend is also present in recent work targeting the verification of cryptographic software, but the reach of existing tools has so far been limited to cryptographic primitives, such as RSA-OAEP encryption, or standalone protocols, such as SSH. This paper presents a scalable

approach to formally verifying implementations of higher-level cryptographic systems, directly in the computational model.

We consider circuit-based cloud-oriented cryptographic protocols for secure and verifiable computation over encrypted data. Our examples share as central component Yao\'s celebrated transformation of a boolean circuit into an equivalent garbled form that can be evaluated securely in an untrusted environment. We leverage the foundations of garbled circuits set forth by Bellare, Hoang, and Rogaway (CCS 2012, ASIACRYPT 2012) to build verified implementations of garbling schemes, a verified implementation of Yao\'s secure

function evaluation protocol, and a verified (albeit partial) implementation of the verifiable computation protocol by Gennaro, Gentry, and Parno (CRYPTO 2010). The implementations are formally verified using EasyCrypt, a tool-assisted framework for building high-confidence cryptographic proofs, and critically rely on two novel features: a module and theory system that supports compositional reasoning, and a code extraction mechanism for generating

implementations from formalizations.

We introduce the notion of a class of lattice-based digital signature schemes based on modular properties of the coordinates of lattice vectors. We also suggest a method of making such schemes transcript secure via a rejection sampling technique of Lyubashevsky (2009). A particular instantiation of this approach is given, using NTRU lattices. Although the scheme is not supported by a formal security reduction, we present arguments for its security and derive concrete parameters based on the performance of state-of-the-art lattice reduction and enumeration techniques.

We initiate the study of principled, automated, methods for analyzing hardness assumptions in generic group models, following the approach of symbolic cryptography. We start by defining a broad class of generic and symbolic group models for different

settings---symmetric or asymmetric (leveled) k-linear groups---and by

proving \"computational soundness\" theorems for the symbolic models.

Based on this result, we formulate a very general master theorem that formally relates the hardness of a (possibly interactive) assumption in these models to solving problems in polynomial algebra. Then, we systematically analyze these problems. We identify different classes of assumptions and obtain decidability and undecidability results.

Then, we develop and implement automated procedures for verifying the conditions of master theorems, and thus the validity of hardness assumptions in generic group models. The concrete outcome of this work is an automated tool which takes as input the statement of an assumption, and outputs either a proof of its

generic hardness or shows an algebraic attack against the assumption.

Template attacks remain a most powerful side-channel technique to

eavesdrop on tamper-resistant hardware. They use a profiling step to

compute the parameters of a multivariate normal distribution from a

training device and an attack step in which the parameters obtained

during profiling are used to infer some secret value (e.g.

cryptographic key) on a target device. Evaluations using the same

device for both profiling and attack can miss practical problems

that appear when using different devices. Recent

studies showed that variability caused by the use of either

different devices or different acquisition campaigns on the same

device can have a strong impact on the performance of template

attacks. In this paper, we explore further the effects that lead to

this decrease of performance, using four different Atmel XMEGA 256

A3U 8-bit devices. We show that a main difference between devices is

a DC offset and we show that this appears even if we use the same

device in different acquisition campaigns. We then explore several

variants of the template attack to compensate for these differences.

Our results show that a careful choice of compression method and

parameters is the key to improving the performance of these attacks

across different devices. In particular we show how to maximise the

performance of template attacks when using Fisher\'s Linear

Discriminant Analysis or Principal Component Analysis. Overall, we

can reduce the entropy of an unknown 8-bit value below 1.5 bits even

when using different devices.

Most implementations of Yao\'s garbled circuit approach for 2-party secure computation use the {\\em free-XOR} optimization of Kolesnikov \\& Schneider (ICALP 2008). We introduce an alternative technique called {\\em flexible-XOR} (fleXOR) that generalizes free-XOR and offers several advantages. First, fleXOR can be instantiated under a weaker hardness assumption on the underlying cipher/hash function (related-key security only, compared to related-key and circular security required for free-XOR) while maintaining most of the performance improvements that free-XOR offers. Alternatively, even though XOR gates are not always ``free\'\' in our approach, we show that the other (non-XOR) gates can be optimized more heavily than what is possible when using free-XOR. For many circuits of cryptographic interest, this can yield a significantly (over 30\\%) smaller garbled circuit than any other known techniques (including free-XOR) or their combinations.

In a homomorphic signature scheme, a user Alice signs some large data $x$ using her secret signing key and stores the signed data on a server. The server can then run some computation $y=g(x)$ on the signed data and homomorphically produce a short signature $\\sigma$. Anybody can verify the signature using Alice\'s public verification key and become convinced that $y$ is the correct output of the computation $g$ over Alice\'s data, without needing to have the underlying data itself.

In this work, we construct the first leveled fully homomorphic signature schemes that can evaluate arbitrary circuits over signed data, where only the maximal depth $d$ of the circuit needs to be fixed a priori. The size of the evaluated signature grows polynomially in $d$, but is otherwise independent of the circuit size or the data size. Our solutions are based on the hardness of the small integer solution (SIS) problem, which is in turn implied by the worst-case hardness of problems in standard lattices. We get a scheme in the standard model, albeit with large public parameters whose size must exceed the total size of all signed data. In the random-oracle model, we get a scheme with short public parameters. These results offer a significant improvement in capabilities and assumptions over the best prior homomorphic signature scheme due to Boneh and Freeman (Eurocrypt \'11).

As a building block of independent interest, we introduce a new notion called homomorphic trapdoor functions (HTDF). We show to how construct homomorphic signatures using HTDFs as a black box. We construct HTDFs based on the SIS problem by relying on a recent technique developed by Boneh et al. (Eurocrypt \'14) in the context of attribute based encryption.

We propose a new protocol for a cryptocurrency, that builds upon the Bitcoin protocol by combining its Proof of Work component with a Proof of Stake type of system. Our Proof of Activity (PoA) protocol offers good security against possibly practical future attacks on Bitcoin, and has a relatively low penalty in terms of network communication and storage space. We explore various attack scenarios and suggest remedies to potential vulnerabilities of the PoA protocol, as well as evaluate the performance of its core subroutine.

The linear layer is a core component in any substitution-permutation network block cipher. Its design significantly influences both the security and the efficiency of the resulting block cipher. Surprisingly, not many general constructions are known that allow to choose trade-offs between security and efficiency. Especially, when compared to Sboxes, it seems that the linear layer is crucially understudied. In this paper, we propose a general methodology to construct good, sometimes optimal, linear layers allowing for a large variety of trade-offs. We give several instances of our construction and on top underline its value by presenting a new block cipher. PRIDE is optimized for 8-bit micro-controllers and significantly outperforms all academic solutions both in terms of code size and cycle count.

This work deals with DPA-resistant logic styles, i.e., cell-level countermeasures against power analysis attacks that are known as a serious threat to cryptographic devices. Early propagation and imbalanced routings are amongst the well-known issues of such countermeasures, that - if not considered during the design process - can cause the underlying cryptographic device to be vulnerable to certain attacks. Although most of the DPA-resistant logic styles target an ASIC design process, there are a few attempts to apply them in an FPGA platform. This is due to the missing freedom in FPGA design tools required to deal with the aforementioned problems. Our contribution in this work is to provide solutions for both early propagation and imbalanced routings considering a modern Xilinx FPGA as the target platform. Foremost, based on the WDDL concept we design a new FPGA-based logic style without early propagation in both precharge and evaluation phases. Additionally, with respect to the limited routing resources within an FPGA we develop a customized router to nd the best appropriate dual-rail routes for a given dual-rail circuit. Based on practical experiments on a Virtex-5 FPGA our evaluations verify the efficiency of each of our proposed approaches. They significantly improve the resistance of the design compared to cases not benefiting from our schemes.

Secret sharing (SS) is one of the most important cryptographic primitives used for data outsourcing. The (t, n) SS was introduced by Shamir and Blakley separately in 1979. The secret sharing policy of the (t, n) threshold SS is far too simple for many applications because it assumes that every shareholder has equal privilege to the secret or every share-holder is equally trusted. Ito et al. introduced the concept of a general secret sharing scheme (GSS). In a GSS, a secret is divided among a set of shareholders in such a way that any \"qualified\" subset of shareholders can access the secret, but any \"unqualified\" subset of shareholders cannot access the secret. The secret access structure of GSS is far more flexible than threshold SS. In this paper, we propose an optimized implementation of GSS. Our proposed scheme first uses Boolean logic to derive two important subsets, one is called which is the minimal positive access subset and the other is called which is the maximal negative access subset, of a given general secret sharing structure. Then, condi-tions of parameters of a GSS are established based on these two important subsets. Fur-thermore, integer linear/non-linear programming is used to optimize the size of shares of a GSS. The complexity of linear/non-linear programming is where is the number of shares generated by the dealer. This proposed design can be applied to implement GSS based on any classical SS. We use two GSSs, one is based on Shamir\'s weighted SS (WSS) using linear polynomial and the other is based on Asmuth-Bloom\'s SS using Chinese Re-mainder Theorem (CRT), to demonstrate our design. In comparing with existing GSSs, our proposed scheme is more efficient and can be applied to all classical SSs.

Private set intersection (PSI) allows two parties to compute the intersection of their sets without revealing any information about items that are not in the intersection. It is one of the best studied applications of secure computation and many PSI protocols have been proposed. However, the variety of existing PSI protocols makes it

difficult to identify the solution that performs best in a respective scenario, especially since they were not all implemented and compared in the same setting.

In this work, we give an overview on existing PSI protocols that are secure against semi-honest adversaries. We take advantage of the most recent efficiency improvements in OT extension to propose significant optimizations to previous PSI protocols and to suggest a new PSI protocol whose runtime is superior to that of existing protocols. We compare the performance of the protocols both theoretically and experimentally, by implementing all protocols on the same platform, and give recommendations on which protocol to use in a particular setting.

SIMON is a family of lightweight block ciphers which are designed by the U.S National Security Agency in 2013. In this paper, we improve the previous differential attacks on SIMON family of block ciphers by considering some bit-difference equations. Combining with some new observations on key guess policies of SIMON family, we mount differential attacks on 21-round SIMON32/64, 22-round SIMON$48/72$, 22-round SIMON48/96, 28-round SIMON$64/96$ and SIMON$64/128$ with time complexity about $2^{46}$, $2^{63}$, $2^{71}$, $2^{60}$ and $2^{60}$ encryptions respectively. As far as we know, these results are the best attacks on reduced-round SIMON versions.