International Association
for Cryptologic Research

In this paper, we describe a new protocol for secure three-party computation of any functionality, with an honest majority and a \textit{malicious} adversary. Our protocol has both an information-theoretic and computational variant, and is distinguished by extremely low communication complexity and very simple computation. We start from the recent semi-honest protocol of Araki et al. (ACM CCS 2016) in which the parties communicate only a single bit per AND gate, and modify it to be secure in the presence of malicious adversaries. Our protocol follows the paradigm of first constructing Beaver multiplication triples and then using them to verify that circuit gates are correctly computed. As in previous work (e.g., the so-called TinyOT and SPDZ protocols), we rely on the cut-and-choose paradigm to verify that triples are correctly constructed. We are able to utilize the fact that at most one of three parties is corrupted in order to construct an extremely simple and efficient method of constructing such triples. We also present an improved combinatorial analysis for this cut-and-choose which can be used to achieve improvements in other protocols using this approach.

Private communication over the Internet continues to be a challenging problem. Even if messages are encrypted, it is hard to deliver them without revealing metadata about which pairs of users are communicating. Scalable systems, such as Tor, are susceptible to traffic analysis. In contrast, the largest-scale systems with metadata privacy require passing all messages through each server, capping their throughput and scalability.

This paper presents Stadium, the first system to provide metadata and data privacy while being able to scale its work efficiently across many servers. Much like Vuvuzela, the current largest-scale system, Stadium is based on differential privacy. However, providing privacy in Stadium is more challenging because distributing users' traffic across servers creates opportunities for adversaries to observe it in fine granularity. To solve this challenge, Stadium uses a collaborative noise generation approach combined with a novel verifiable parallel mixnet design where servers collaboratively check that others follow the protocol. We show that Stadium can scale to use hundreds of servers, support over an order of magnitude more users than Vuvuzela, and cut the costs of operating each server.

Secure multiparty computation platforms are often provided with a programming language that allows to write privacy-preserving applications without thinking of the underlying cryptography. The control flow of these programs is expensive to hide, hence they typically disallow branching on private values. The application programmers have to specify their programs in terms of allowed constructions, either using ad-hoc methods to avoid such branchings, or the general methodology of executing all branches and obliviously selecting the effects of one at the end. There may be compiler support for the latter.

The execution of all branches introduces significant computational overhead. If the branches perform similar private operations, then it may make sense to compute repeating patterns only once, even though the necessary bookkeeping also has overheads. In this paper, we propose a program optimization doing exactly that, allowing the overhead of private conditionals to be reduced. The optimization is quite general, and can be applied to various privacy-preserving platforms.

Differentially 4-uniform permutations on $\mathbb{F}_{2^{2k}}$ with high nonlinearity and algebraic degree are often used in block ciphers and some stream ciphers as Substitution boxes. Recently,Chen et al.(An equivalent condition on the switching construction of differentially 4-uniform permutations on from the inverse function, International Journal of Computer Mathematics, DOI:10.1080/00207160.2016.1167884) presented a n equivalent condition on the switching construction. More precisely,they presented a sufficient and necessary condition on differentially 4-uniform permutations on $\mathbb{F}_{2^{2k}}$ of the form $G(x)=x^{-1}+f(x^{-1})$, where $f$ is a Boolean function. However, the number of the satisfied functions is so enormous that it is difficult to find all the functions. In this paper,a new class of such functions are constructed. These functions may provide more options for the design of Substitute boxes.

The Secure Systems group of the Department of Computer Science at University of Helsinki is looking for an excellent postdoctoral researcher or doctoral student in cryptography. The topics of this position are related to cryptographic solutions that ensure security and privacy of positioning services. The exact topic will be decided together with the candidate based on his/her background and research interests.

Candidates for the doctoral student position should have completed a Master (or equivalent) degree in computer science, electrical engineering, mathematics, or other related field. We expect at least some experience and prior knowledge on cryptography, cryptographic protocols, or systems security. Candidates for the postdoctoral position should have completed their doctoral degree from a topic related to cryptography or information security and they are expected to have a good publication record. A candidate must be motivated, capable to take initiative, work independently, and be fluent in both written and spoken English.

Applications should be sent via email and should include a motivation letter, a full CV, a copy of the diploma with the grade transcript, a list of publications (for the postdoctoral position), and contact information for one or two persons who are willing to give references.

The applications will be reviewed immediately and the position will be filled when a suitable candidate is found.

Closing date for applications: 31 October 2016

Contact: Kimmo Järvinen, kimmo.jarvinen.crypto (at) gmail.com

Oblivious Transfer (OT) is one of the most fundamental cryptographic primitives with wide-spread application in general secure multi-party computation (MPC) as well as in a number of tailored and special-purpose problems of interest such as private set intersection (PSI), private information retrieval (PIR), contract signing to name a few. Often the instantiations of OT require prohibitive communication and computation complexity. OT extension protocols are introduced to compute a very large number of OTs referred as extended OTs at the cost of a small number of OTs referred as seed OTs.

We present a fast OT extension protocol for small secrets in active setting. Our protocol when used to produce $1$-out-of-$n$ OTs outperforms all the known actively secure OT extensions. Our protocol is built on the semi-honest secure extension protocol of Kolesnikov and Kumaresan of CRYPTO'13 (referred as KK13 protocol henceforth) which is the best known OT extension for short secrets. At the heart of our protocol lies an efficient consistency checking mechanism that relies on the linearity of Walsh-Hadamard (WH) codes. Asymptotically, our protocol adds a communication overhead of $O(\mu \log{\kappa})$ bits over KK13 protocol irrespective of the number of extended OTs, where $\kappa$ and $\mu$ refer to computational and statistical security parameter respectively. Concretely, our protocol when used to generate a large enough number of OTs adds only $0.011-0.028\%$ communication overhead and $4-6\%$ runtime overhead both in LAN and WAN over KK13 extension. The runtime overheads drop below $2\%$ when in addition the number of inputs of the sender in the extended OTs is large enough.

As an application of our proposed extension protocol, we show that it can be used to obtain the most efficient PSI protocol secure against a malicious receiver and a semi-honest sender.

Physical Unclonable Functions (PUFs) are promising primitives for lightweight integrated circuit authentication. Indeed, by extracting an identifier from random process variations, they allow each instance of a design to be uniquely identified. However, the extracted identifiers are not stable enough to be used as is, but need to be corrected first. This is currently achieved using error correcting codes, which generate helper data through a one-time process. As an alternative, we propose key reconciliation protocols. This interactive method, originating from quantum key distribution, allows two entities to correct errors in their respective correlated keys by discussing over a public channel. We believe this can also be used by a device and a remote server to agree on two different responses to the same challenge from the same PUF obtained at different times. This approach has the advantage of requiring few logic resources on the device side, at least three times fewer than existing error correcting codes. The leakage caused by the key reconciliation process is limited and easily computable. Results of implementation on various FPGA targets are presented.

This work considers the problem of fast and secure scalar multiplication using curves of genus one defined over a field of prime order. Previous work by Gaudry and Lubicz had suggested the use of the associated Kummer line to speed up scalar multiplication. In this work, we explore this idea in details. The first task is to obtain an elliptic curve in the Legendre form which satisfies necessary security conditions such that the associated Kummer line has small parameters and a base point with small coordinates. It turns out that the Kummer ladder supports parallelism and can be implemented very efficiently in constant time using the single-instruction multiple-data (SIMD) operations available in modern processors. We report implementation using Intel intrinsics and the code is publicly available. The timing results show that the performance of the Kummer line based approach compare favourably with previously proposed genus one curves over prime order fields.

General Lucas sequences are practically useful in cryptography. In the past quarter century, factoring large RSA modulo into its primes is one of the most important and most challenging problems in computational number theory. A factoring technique on RSA modulo is mainly hindered by the strong prime properties. The success of factoring few large RSA modulo within the last few decades has been due to computing prowess overcoming one strong prime of RSA modulo. In this paper, some useful properties of Lucas sequences shall be explored in factoring RSA modulo. This paper introduces the S-index formation in solving quadratic equation modulo N. The S-index pattern is very useful in designing an algorithm to factor RSA modulo. At any instance in the factoring algorithm, the accumulative result stands independently. In effect, there is no clear direction to maneuver whether to go left or right. The S-index will add another comparative tool to better maneuver in a factoring process. On one hand, it shall remain a theoretical challenge to overcome the strong prime properties. On the other hand, it shall remain a computational challenge to achieve a running time within polynomial time to factor RSA modulo. This paper will propose an avenue to do both using general Lucas sequences.

This article continues investigation of ways to obtain pseudo-random sequences over Galois field via generating LRS over Galois ring and complication it.

Previous work is available at http://eprint.iacr.org/2016/212

In this work we provide low rank estimations for sequences generated by two different designs based on coordinate sequences of linear recurrent sequences (LRS) of maximal period (MP) over Galois ring $R=GR(p^n,r)$, $p\ge 5$, $r\ge2$, with numbers $s$ such that $s=kr+2$, $k\in \mathbb{N}_0$, and based on digital sequences of coordinate sequences of matrix/skew MP LRS over such Galois rings.

Side-channel analysis (SCA) attacks pose a serious threat to embedded systems. So far, the research on masking as a countermeasure against SCA focuses merely on cryptographic algorithms, and has either been implemented for particular hardware or software implementations. However, the drawbacks of protecting specific implementations are the lack of flexibility in terms of used algorithms, the impossibility to update protected hardware implementations, and long development cycles for protecting new algorithms. Furthermore, cryptographic algorithms are usually just one part of an embedded system that operates on informational assets. Protecting only this part of a system is thus not sufficient for most security critical embedded applications. In this work, we introduce a flexible, SCA-protected processor design based on the open-source V-scale RISC-V processor. The introduced processor design can be synthesized to defeat SCA attacks of arbitrary attack order. Once synthesized, the processor protects the computation on security-sensitive data against side-channel leakage. The benefits of our approach are (1) flexibility and updatability, (2) faster development of SCA-protected systems, (3) transparency for software developers, (4) arbitrary SCA protection level, (5) protection not only for cryptographic algorithms, but against leakage in general caused by processing sensitive data.

Starting with the work of Bellare, Goldreich and Goldwasser [CRYPTO'94], a rich line of work has studied the design of updatable cryptographic primitives. For example, in an updatable signature scheme, it is possible to efficiently transform a signature over a message into a signature over a related message without recomputing a fresh signature.

In this work, we continue this line of research, and perform a systematic study of updatable cryptography. We take a unified approach towards adding updatability features to recently studied cryptographic objects such as attribute-based encryption, functional encryption, witness encryption, indistinguishability obfuscation, and many others that support non-interactive computation over inputs. We, in fact, go further and extend our approach to classical protocols such as zero-knowledge proofs and secure multiparty computation.

To accomplish this goal, we introduce a new notion of updatable randomized encodings that extends the standard notion of randomized encodings to incorporate updatability features. We show that updatable randomized encodings can be used to generically transform cryptographic primitives to their updatable counterparts.

We provide various definitions and constructions of updatable randomized encodings based on varying assumptions, ranging from one-way functions to compact functional encryption.

This paper describes a 1-out-of-N oblivious transfer (OT) extension protocol with active security, which achieves very low overhead compared with the passively secure protocol of Kolesnikov and Kumaresan (Crypto 2011). Our protocol obtains active security using a consistency check which requires only simple computation and has a communication overhead that is independent of the total number of OTs to be produced. We prove its security in both the random oracle model and the standard model, assuming a variant of correlation robustness. We describe an implementation, which demonstrates our protocol only incurs an overhead of around 5–30% on top of the passively secure protocol. Random 1-out-of-N OT is a key building block in recent, very efficient, passively secure private set intersection (PSI) protocols. Our random OT extension protocol has the interesting feature that it even works when N is exponentially large in the security parameter, provided that the sender only needs to obtain polynomially many outputs. We show that this can be directly applied to improve the performance of PSI, allowing the core private equality test and private set inclusion subprotocols to be carried out using just a single OT each. This leads to a reduction in communication of up to 3 times for the main component of PSI.

Software encoding countermeasures are becoming increasingly popular among researchers proposing code-level prevention against data-dependent leakage allowing an attacker to mount a side-channel attack. Recent trends show that it is possible to design a solution that does not require excessive overhead and yet provides a reasonable security level. However, if the device leakage is hard to be observed, attacker can simply switch to a different class of physical attacks, such as fault injection attack. Instead of stacking several layers of countermeasures, it is always more convenient to choose one that provides decent protection against several attack methods. Therefore, in our paper we use our custom designed code analyzer to formally inspect a recently proposed software encoding countermeasure based on device-specific encoding function, and compare it with other solutions, either based on balanced look-up tables or balanced encoding. We also provide an experimental validation, using the laser fault injection setup. Our results show that the device-specific encoding scheme provides a good protection against fault injection attacks, being capable of preventing majority of faults using different fault models.

When it comes to side-channel countermeasures, software encoding schemes are becoming more popular and provide a good level of security for general-purpose microcontrollers. However, these schemes are not designed to be fault resistant, and this property is discussed very rarely. Therefore, implementers have to pile up two different countermeasures in order to protect the algorithm against these two popular classes of attacks. In our paper, we discuss the fault resistance properties of encoding schemes in general. We define theoretical bounds that clearly show the possibilities and limitations of encoding-based countermeasures, together with trade-offs between side-channel and fault resistance. Moreover, we simulate several codes with respect to most popular fault models, using a general-purpose microcontroller assembly implementation. Our algorithm shows how to implement fault resistance to an encoding scheme that currently has the best side-channel resistant capabilities. As a result, we are able to design a code by using automated methods, that can provide the optimal trade-off between side-channel and fault resistance.

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 compared in the same setting. In addition, existing PSI protocols are several orders of magnitude slower than an insecure naive hashing solution which is used in practice. In this work, we review the progress made on PSI protocols and give an overview of existing protocols in various security models. We then focus on PSI protocols that are secure against semi-honest adversaries and take advantage of the most recent efficiency improvements in OT extension and propose significant optimizations to previous PSI protocols and to suggest a new PSI protocol whose run-time 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, give recommendations on which protocol to use in a particular setting, and evaluate the progress on PSI protocols by comparing them to the currently employed insecure naive hashing protocol. We demonstrate the feasibility of our new PSI protocol by processing two sets with a billion elements each.

Sharing a secret efficiently amongst a group of participants is not easy since there is always an adversary / eavesdropper trying to retrieve the secret. In secret sharing schemes, every participant is given a unique share. When the desired group of participants come together and provide their shares, the secret is obtained. For other combinations of shares, a garbage value is returned. A threshold secret sharing scheme was proposed by Shamir and Blakeley independently. In this (n,t) threshold secret sharing scheme, the secret can be obtained when at least t out of n participants contribute their shares. This paper proposes a novel algorithm to reveal the secret only to the subsets of participants belonging to the access structure. This scheme implements totally generalized ideal secret sharing. Unlike threshold secret sharing schemes, this scheme reveals the secret only to the authorized sets of participants, not any arbitrary set of users with cardinality more than or equal to t. Since any access structure can be realized with this scheme, this scheme can be exploited to implement various access priorities and access control mechanisms. A major advantage of this scheme over the existing ones is that the shares being distributed to the participants is totally independent of the secret being shared. Hence, no restrictions are imposed on the scheme and it finds a wider use in real world applications.

In this paper, we study an important problem in secret sharing that determines the exact value or bound for the complexity. First, we used induced subgraph complexity of the graph G with access structure, Gama, to obtain a lower bound on the complexity of the graph G. Secondly, by applying decomposition techniques we obtain an upper bound on the complexity of the graph G. We determine the exact values of the complexity for each of the ten graph access structures on seven participants. Also, we improve the value bound of the complexity of the six graph access structures with seven participants.

Videos from CHES 2016 are now available online at the IACR youtube page.

Videos from Crypto 2016 are now available online at the IACR youtube page.