International Association
for Cryptologic Research

We initiate a study of garbled circuits that contain both Boolean and arithmetic gates in secure multiparty computation. In particular, we incorporate the garbling gadgets for arithmetic circuits recently presented by Ball, Malkin, and Rosulek (ACM CCS 2016) into the multiparty garbling paradigm initially introduced by Beaver, Micali, and Rogaway (STOC '90). This is the first work that studies arithmetic garbled circuits in the multiparty setting. Our garbled circuits are secure in the semi-honest model, under the same hardness assumptions as Ball et al., and can be efficiently and securely computed in constant rounds assuming an honest majority.

We first extend free addition and multiplication by a constant to the multiparty setting. We further extend to the multiparty setting efficient garbled multiplication gates. The garbled multiplication gate construction we show was previously achieved only in the two-party setting and assuming a random oracle.

Our main technical contribution is in garbling selector gates. Selector gates compute a simple ``if statement" in the arithmetic setting: the gate selects the output value from two input values in $\mathbb{F}_p$, according to a Boolean selector bit; if the bit is $0$ the output equals the value on the first wire, and if the bit is $1$ the output equals the value on the second wire. We show a new and designated garbled selector gate that reduces by approximately $33\%$ the evaluation time from the best previously known constructions that use existing techniques.

On the downside, we find that testing equality and computing exponentiation by a constant are significantly more complex to garble in the multiparty setting than in the two-party setting.

Key Exchange (KE) from RLWE (Ring-Learning with Errors) is a potential alternative to Diffie-Hellman (DH) in a post quantum setting. Key leakage with RLWE key exchange protocols in the context of key reuse has already been pointed out in previous work. The Signal leakage attack relies on changes in the signal sent by the responder reusing his key, in a sequence of key exchange sessions initiated by an attacker with a malformed key. A possible defense against this attack would be by requiring the initiator of the key exchange to send the signal, which is the one pass case of the KE protocol. The initial attack described bu Fluhrer is designed in such a way that it only works on Peikert’s KE protocol and its variants that derives the shared secret from the most significant bits of the approximately equal keys computed by both parties. It does not work on the Ding’s key exchange that uses the least significant bits to derive a shared key. In this work, we describe a new attack on Ding’s one pass case without relying on the signal function output but using only the information of whether the final key of both parties agree. We also use LLL reduction to make the adversary’s keys random looking to the party being compromised. This completes the series of attacks on RLWE key exchange with key reuse for all variants in both cases of the initiator and responder sending the signal. This work shows that when a party fixes their public key for a long term, the protocol can always be broken by a malicious user. Moreover, we show that the previous Signal leakage attack can be made more efficient with fewer queries and how it can be extended to Peikert’s key exchange, which was used in the BCNS implementation and integrated with TLS and a variant used in the New Hope implementation.

Applications are invited for two Post-Doctoral Research Associate posts, hosted in the Cryptography and Information Security group [1] set within the University of Bristol; the group is recognised by EPSRC/NCSC as a UK Academic Centre of Excellence in Cyber Security Research (ACE-CSR).

These posts represent an exciting opportunity to join the group as part of the 5-year SCARV [2] project, in turn part of the recently announced, EPSRC/NCSC-supported Research Institute in Hardware Security & Embedded Systems (RISE) [3]. SCARV is a project focused on challenges in cryptographic engineering, at the intersection of computer architecture and cryptography: alongside both industrial (i.e., Cerberus Security Labs. and Thales) and academic partners, it aims to deliver more efficient, more secure platforms based on and around RISC-V. Given the project goals, a strong background in micro-processor design and implementation, and/or implementation (e.g., side-channel) attacks on cryptography is therefore desirable.

Although you will have at least a first degree and preferably a PhD in Computer Science, Electrical Engineering, or closely related discipline, we view relevant industrial experience as extremely valuable and therefore equally encourage applicants of this type.

[1] http://www.bris.ac.uk/engineering/research/cryptography

[2] http://gow.epsrc.ac.uk/NGBOViewGrant.aspx?GrantRef=EP/R012288/1

[3] http://www.ukrise.org

Closing date for applications: 21 January 2018

Contact: Dr. Daniel Page (Daniel.Page (at) bristol.ac.uk)

More information: http://www.bris.ac.uk/jobs/find/details.html?nPostingID=6948&nPostingTargetID=42514&JobNum=ACAD103055

The deadline for proposing an IACR Cryptology School is December 31. There are two deadlines annually, and this is the last chance to apply for IACR Schools taking place during May-October 2018. Information about proposing an IACR School can be found at https://www.iacr.org/schools/propose.php

The IACR sponsors a small number of Cryptology Schools providing intensive training on clearly identified topics in cryptology. The aim is to develop awareness and increased capacity for research in cryptology. A list of past and upcoming schools can be found at https://www.iacr.org/schools

Event date: 4 April to 5 April 2018
Submission deadline: 15 January 2018
Notification: 1 February 2018

Event date: 28 May to 31 May 2018
Submission deadline: 1 February 2018
Notification: 1 March 2018

The University of Luxembourg invites applications for a Ph.D. position at the Applied Security and Information Assurance (APSIA) group of the Interdisciplinary Centre for Security, Reliability and Trust (SnT).

The successful candidate will join the APSIA group led by Prof. Peter Y. A. Ryan. The candidate will be part of the Luxembourg National Research Fund (FNR) project “Stateful Zero-Knowledge”, which will start on 1st March 2018 and will conduct pioneering research on zero-knowledge proofs. The candidate will be supervised by Prof. Peter Y. A. Ryan and by Dr. Alfredo Rial. The candidate’s tasks include the following:

- Conducting research on the following topics: zero-knowledge proofs and zero-knowledge data structures, privacy-preserving cryptographic protocols, universal composability and related security frameworks, design and implementation of a zero-knowledge compiler

- Providing guidance to M.Sc. students

- Disseminating results through scientific publications and talks at conferences

Your Profile:

- M.Sc. degree in Computer Science, Applied Mathematics, Electrical Engineering, or a related field

- Strong mathematical and/or algorithmic CS background

- Good skills in programming

- Fluent written and verbal communication skills in English are mandatory

- Background in cryptography and information security (a plus)

The duration of a Ph.D is typically 3-4 years. The University offers highly competitive salaries and is an equal opportunity employer. You will work in an exciting international environment.

Applications, written in English, should include:

- Curriculum Vitae (including your contact address and email address, education, work experience, publications if any)

- Transcript of all modules and results from university-level courses taken

- A research statement indicating your interest, prior research (if any) and your motivation (max 1 page)

- Contact information for 2-3 referees

Closing date for applications: 15 January 2018

Contact: Dr. Alfredo Rial (e-mail: alfredo.rial (at) uni.lu)

More information: https://wwwen.uni.lu/snt/research/apsia

Post-doc positions are available immediately at the Electrical Engineering Department in USF. The research is inter-disciplinary, and we focus on building innovative secure and privacy-enhancing technologies in research areas such as: Machine learning, Big Data Analytics, IoT and Edge Computing. Our projects are mainly funded by DARPA. Candidates with strong hands-on experience and strong publication record in relevant areas are encouraged to apply.

Minimum Qualifications:

• A PhD in Computer Science, Electrical Engineering, Statistics, or related field completed within the past three years or soon to be completed.

• Research-level expertise in one (or more) of the following areas: – Privacy-enhancing technologies, – Machine Learning – Security and Applied Cryptography – IoT Security and Privacy – Big Data Analytics – Edge Computing

Preferred Qualifications:

• Candidates should have publications in high impact journals and conferences.

• The candidate should have strong programming skills including experience with Java, MATLAB, Pyton, and/or R.

Additional Information for Applicants:

A curriculum vitae, publication list, a cover letter/research statement outlining your research experience and interests, your research plans (not exceeding 2 pages), and the names of three academic/professional references.

Send the required documents to the email: brandeis.iastate_at_gmail_dot_com. To facilitate conveying the best image of your research, we recommend you attach to your application the two publications that you are most proud of.

Review of applications starts immediately and will continue until positions are filled.

Closing date for applications: 31 March 2018

Multivariate Public Key Cryptography is a leading option for security in a post quantum society. In this paper we propose a new encryption scheme, EFLASH, and analyze its efficiency and security.

Cryptographic primitives that are secure against quantum computing are receiving growing attention with recent, steady advances in quantum computing and standardization initiatives in post-quantum cryptography by NIST and ETSI. Lattice-based cryptography is one of the families in post-quantum cryptography, demonstrating desirable features such as well-understood security, efficient performance, and versatility.

In this work, we present Round2 that consists of a key-encapsulation mechanism and a public-key encryption scheme. Round2 is based on the General Learning with Rounding problem, that unifies the Learning with Rounding and Ring Learning with Rounding problems. Round2's construction using the above problem allows for a unified description and implementation. The key-encapsulation mechanism and public-key encryption scheme furthermore share common building blocks, simplifying (security and operational) analysis and code review. Round2's reliance on prime cyclotomic rings offers a large design space that allows fine-tuning of parameters to required security levels. The use of rounding reduces bandwidth requirements and the use of sparse-trinary secrets improves CPU performance and decryption success rates. Finally, Round2 includes various approaches of refreshing the system public parameter A, allowing efficient ways of preventing precomputation and back-door attacks.

In the area of distributed graph algorithms a number of network's entities with local views solve some computational task by exchanging messages with their neighbors. Quite unfortunately, an inherent property of most existing distributed algorithms is that throughout the course of their execution, the nodes get to learn not only their own output but rather learn quite a lot on the inputs or outputs of many other entities. This leakage of information might be a major obstacle in settings where the output (or input) of network's individual is a private information (e.g., distributed networks of selfish agents, decentralized digital currency such as Bitcoin, voting systems).

While being quite an unfamiliar notion in the classical distributed setting, the notion of secure multi-party computation (MPC) is one of the main themes in the Cryptography community. Yet despite all extensive work in the area, no existing algorithm fits the framework of classical distributed models in which there are no assumptions on the graph topologies and only messages of bounded size are sent on the edges in each round.

In this paper, we introduce a new framework for \emph{secure distributed graph algorithms} and provide the first \emph{general compiler} that takes any "natural" non-secure distributed algorithm that runs in $r$ rounds, and turns it into a secure algorithm that runs in $\widetilde{O}(r \cdot D \cdot poly(\Delta))$ rounds where $\Delta$ is the maximum degree in the graph and $D$ is its diameter. We also show that this is nearly (existentially) optimal for any round-by-round compiler for bounded degree graphs.

The main technical part of our compiler is based on a new cycle cover theorem: We show that the edges of every bridgeless graph $G$ of diameter $D$ can be covered by a collection of cycles such that each cycle is of length $\widetilde{O}(D)$ and each edge of the graph $G$ appears in $\widetilde{O}(1)$ many cycles. In fact, our construction can be made instance optimal with respect to each single edge. Letting $C_e$ be the shortest cycle containing $e$ in $G$, our cycle collection contains a cycle of length $\widetilde{O}(|C_e|)$ that covers $e$ for every $e \in G$, and in addition, each edge appears on $\widetilde{O}(1)$ many cycles. As a result, our compiler becomes instance optimal for bounded degree graphs.

The hardness of solving multivariate quadratic (MQ) systems is the underlying problem for multivariate-based schemes in the field of post-quantum cryptography. The concrete, practical hardness of this problem needs to be measured by state-of-the-art algorithms and high-performance implementations. We describe, implement, and evaluate an adaption of the Crossbred algorithm by Joux and Vitse for solving MQ systems over GF(2). Our adapted algorithm is highly parallelizable and is suitable for solving MQ systems on GPU architectures. Our implementation is able to solve an MQ system of 134 equations in 67 variables in 98.39 hours using one single commercial Nvidia GTX 980 graphics card, while the original Joux-Vitse algorithm requires 6200 CPU-hours for the same problem size. We used our implementation to solve all the Fukuoka Type-I MQ challenges for n = 55,...,74. Based on our implementation, we estimate that the expected computation time for solving an MQ system of 80 equations in 84 variables is about one year using a cluster of 3647 GTX 980 graphics cards. These parameters have been proposed for 80-bit security by, e.g., Sakumoto, Shirai, and Hiwatari in 2011.

This paper presents an FPGA implementation of the Niederreiter cryptosystem using binary Goppa codes, including modules for encryption, decryption, and key generation. We improve over previous implementations in terms of efficiency (time-area product and raw performance) and security level. Our implementation is constant time in order to protect against timing side-channel analysis. The design is fully parameterized, using code-generation scripts, in order to support a wide range of parameter choices for security, including binary field size, the degree of the Goppa polynomial, and the code length. The parameterized design allows us to choose design parameters for time-area trade-offs in order to support a wide variety of applications ranging from smart cards to server accelerators. For parameters that are considered to provide 128-bit ‘’post-quantum security'', our time-optimized implementation requires 966,400 cycles for the generation of both public and private portions of a key and 14,291 cycles to decrypt a ciphertext. The time-optimized design uses only 121,806 ALMs (52% of the available logic) and 961 RAM blocks (38% of the available memory), and results in a design that runs at about 250 MHz on a medium-size Stratix V FPGA.

We derive necessary conditions related to the notions, in additive combinatorics, of Sidon sets and sum-free sets, on those exponents $d\in {\mathbb Z}/(2^n-1){\mathbb Z}$ which are such that $F(x)=x^d$ is an APN function over ${\mathbb F}_{2^n}$ (which is an important cryptographic property). We study to which extent these new conditions may speed up the search for new APN exponents $d$. We also show a new connection between APN exponents and Dickson polynomials: $F(x)=x^d$ is APN if and only if the reciprocal polynomial of the Dickson polynomial of index $d$ is an injective function from $\{y\in {\Bbb F}_{2^n}^*; tr_n(y)=0\}$ to ${\Bbb F}_{2^n}\setminus \{1\}$. This also leads to a new and simple connection between Reversed Dickson polynomials and reciprocals of Dickson polynomials in characteristic 2 (which generalizes to every characteristic thanks to a small modification): the squared Reversed Dickson polynomial of some index and the reciprocal of the Dickson polynomial of the same index are equal.

Error reconciliation is an important technique for Learning With Error (LWE) and Ring-LWE (RLWE)-based constructions. In this paper, we present a comparison analysis on two error reconciliation-based RLWE key exchange protocols: Ding et al. in 2012 (DING12) and Bos et al. in 2015 (BCNS15). We take them as examples to explain core idea of error reconciliation, building key exchange over RLWE problem, implementation, real-world performance and compare them comprehensively. We also analyse a LWE key exchange “Frodo” that uses an improved error reconciliation mechanism in BCNS15. To the best of our knowledge, our work is the first to present at least 128-bit classic (80-bit quantum) and 256-bit classic (>200-bit quantum) secure parameter choices for DING12 with efficient portable C/C++ implementations. Benchmark shows that our efficient implementation is 11x faster than BCNS15 and one key exchange execution only costs 0.07ms on a 4-year-old middle range CPU. Error reconciliation is 1.57x faster than BCNS15.

Mobile platforms use biometrics for authentication. Unfortunately, biometrics exhibit noise between repeated readings. Due to the noise, biometrics are stored in plaintext, so device compromise completely reveals the user's biometric value.

To limit privacy violations, one can use fuzzy extractors to derive a stable cryptographic key from biometrics (Dodis et al., Eurocrypt 2004). Unfortunately, fuzzy extractors have not seen wide deployment due to insufficient security guarantees. Current fuzzy extractors provide no security for real biometric sources and no security if a user enrolls the same biometric with multiple devices or providers.

Previous work claims key derivation systems from the iris but only under weak adversary models. In particular, no known construction securely handles the case of multiple enrollments. Canetti et al. (Eurocrypt 2016) proposed a new fuzzy extractor called sample-then-lock.

We construct biometric key derivation for the iris starting from sample-then-lock. Achieving satisfactory parameters requires modifying and coupling of the image processing and the cryptography. Our construction is implemented in Python and being open-sourced. Our system has the following novel features:

-- 45 bits of security. This bound is pessimistic, assuming the adversary can sample strings distributed according to the iris in constant time. Such an algorithm is not known.

-- Secure enrollment with multiple services.

-- Natural incorporation of a password, enabling multifactor authentication. The structure of the construction allows the overall security to be sum of the security of each factor (increasing security to 79 bits).

The high cost of IC design has made chip protection one of the first priorities of the semiconductor industry. Although there is a common impression that combinational circuits must be designed without any cycles, circuits with cycles can be combinational as well. Such cyclic circuits can be used to reliably lock ICs. Moreover, since memristor is compatible with CMOS structure, it is possible to efficiently obfuscate cyclic circuits using polymorphic memristor-CMOS gates. In this case, the layouts of the circuits with different functionalities look exactly identical, making it impossible even for an inside foundry attacker to distinguish the defined functionality of an IC by looking at its layout. In this paper, we propose a comprehensive chip protection method based on cyclic locking and polymorphic memristor-CMOS obfuscation. The robustness against state-of-the-art key-pruning attacks is demonstrated and the overhead of the polymorphic gates is investigated.

We consider generic Garbled Circuit (GC)-based techniques for Secure Function Evaluation (SFE) in the semi-honest model.

We describe efficient GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits for subtraction and comparison are approximately two times smaller (in terms of garbled tables) than previous constructions. This implies corresponding computation and communication improvements in SFE of functions using our efficient building blocks. The techniques rely on recently proposed ``free XOR'' GC technique.

Further, we present concrete and detailed improved GC protocols for the problem of secure integer comparison, and related problems of auctions, minimum selection, and minimal distance. Performance improvement comes both from building on our efficient basic blocks and several problem-specific GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.

Event date: 1 December to 1 September 2018
Submission deadline: 1 February 2018
Notification: 1 April 2018

Event date: 9 September to 12 September 2018
Submission deadline: 16 April 2018
Notification: 18 June 2018