Here you can see all recent updates to the IACR webpage. These updates are also available:

23
February
2019

Event Calendar
ICISS 2019: 15th International Conference on Information Systems Security
Hyderabad, INDIA, 16 December - 20 December 2019

Event date: 16 December to 20 December 2019

Submission deadline: 12 July 2019

Notification: 25 September 2019

Submission deadline: 12 July 2019

Notification: 25 September 2019

Event Calendar
CANS 2019: The 18th International Conference on Cryptology And Network Security
Fuhou, China, 25 October - 27 October 2019

Event date: 25 October to 27 October 2019

Submission deadline: 6 May 2019

Notification: 8 July 2019

Submission deadline: 6 May 2019

Notification: 8 July 2019

21
February
2019

Applications are invited for a PhD fellowship/scholarship at the Department of Engineering, Aarhus University, Denmark. The position is available from 1 August 2019 or later.

**Title**: Verifiable cryptographic software

Zero-knowledge proofs are integral for deploying privacy-preserving cryptocurrencies and other blockchain applications, as they represent a fundamental building block for proving statements about confidential data. The most popular framework for such proofs is based on cryptographic pairings defined over elliptic curves, where pairing-based zero-knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs) underlie private transactions.

The PhD candidate will investigate techniques to develop a formally verified efficient software library for pairing-based cryptography, as means to support current blockchain projects relying on zero-knowledge proofs. The PhD candidate will also be involved in other educational activities, such as serving as teaching assistant in courses related to his/her expertise.

The project is a collaboration between researchers from the Departments of Engineering and Computer Science; the DIGIT Centre for Digitalisation, Big Data and Data Analytics; and the recently opened Concordium Blockchain Research Center.

**Qualifications**:

We are looking for dedicated and enthusiastic applicants, preferably with a Master’s degree in Computer Science/Engineering, Mathematics or related discipline. A theoretical background with cryptography or formal verification will be important for the project. Practical experience with software development and the Coq proof assistant will be seen as a plus. Analytical and critical thinking are naturally essential to pursuing a PhD degree. Further requirements are fluency in English, good reporting/organization skills and being able to work independently.

**Closing date for applications:** 1 May 2019

**Contact:** Diego F. Aranha, Assistant Professor, *dfaranha (at) eng.au.dk*; or Bas Spitters, Associate Professor, *spitters (at) cs.au.dk*

**More information:** https://phd.scitech.au.dk/for-applicants/apply-here/may-2019/verifiable-cryptographic-software/

Excellent candidates interested in pursuing a PhD in security/cryptography are invited to apply for this PhD studentship in the Department of Computer Science at the University of Warwick. This scholarship covers full UK/EU fees and a stipend payable at current UK Research Council rates for 3.5 years. Outstanding overseas students are also encouraged to apply, however a gap in the tuition fee will need to be filled. There is no formal closing date for this scholarship as it will be closed when it\'s filled. Therefore, candidates are advised to apply as early as possible.

For informal inquiries, please contact Professor Feng Hao, *feng.hao (at) warwick.ac.uk*, enclosing a CV and a short description of your relevant background and interests.

The Computer Science Department at Warwick is a leading department in the UK. In the 2014 Research Evaluation Framework (REF) which all UK universities participated in, Warwick computer science was ranked the 1st in terms of research output, 2nd in terms of impact and 2nd overall. It is also highly regarded for its research culture, informal environment, excellent students, and beautiful campus.

**Closing date for applications:** 1 August 2019

**More information:** https://warwick.ac.uk/fac/sci/dcs/admissions/postgraduateresearch/researchstudentships/?newsItem=8a1785d769003af00169015

Job Posting
PhD position in Statistical Disclosure Control -- Data Privacy
Norwegian University of Science and Technology (NTNU)

The NTNU Applied Cryptology Lab at NTNU has an open PhD position (4 years) in statistical disclosure control. Of particular interest are development of differentially private response mechanisms for distributed data, longitudinal data, and theory around privacy as an only partially renewable resource.

**Closing date for applications:** 1 May 2019

**Contact:** Staal A. Vinterbo, Staal.V*interbo (at) ntnu.no*

**More information:** https://www.jobbnorge.no/en/available-jobs/job/163521/

Job Posting
Professor (full, tenured) of Construction and Analysis of Secure Software Systems
Ulm University, Germany

We search a candidate who is internationally highly recognized for research on the foundations and methods of software engineering, specifically, the construction and analysis of large-scale software systems with a focus on security and privacy properties. This includes topics like static and dynamic program analysis for programming languages and their ecosystems, test-based quality assurance techniques to identify security vulnerabilities, e.g., test case generation, test optimization, fuzzing, program transformations, e.g., automatic program repair, constructive or interactive approaches to support developers in the engineering of secure systems.

For more details and application portal, see URL below

**Closing date for applications:** 14 March 2019

**Contact:** Prof. Dr. Frank Kargl, https://www.uni-ulm.de/in/vs/inst/team/frank-kargl/

**More information:** https://stellenangebote.uni-ulm.de/jobposting/95503659d66923316e3b202e35ce7405db5365d1

We are looking for highly-skilled, motivated, and driven students for multiple research internships at the HP Inc. Security Lab in Bristol, UK. As an intern you will help us advance the state-of-the-art in system security. We’re looking for people to work on a range of topics: from researching cyber-resilient hardware and software security architectures, designing security for next generation cyber-physical infrastructures, to security analytics, machine learning for security, and emerging 3D printing ecosystems.

Our industrial research lab is a unique environment at the intersection between academic research and real-world innovation in partnership with HP global business units. We provide interns with a unique opportunity to learn about the realities of both worlds, and to contribute research that may eventually impact the HP products and solutions used by millions of people across the globe.

Internships will start between February and July 2019, for a preferred duration of 5-6 months.

We welcome applications from full time students with the relevant skills and experience at Masters and PhD level.

**Closing date for applications:** 31 March 2019

**Contact:** Philippa Bayley

Security Lab Operations Manager

*philippa.bayley (at) hp.com*

**More information:** https://h30631.www3.hp.com/job/bristol/hp-security-lab-intern/3544/10307305

ePrint Report
XONN: XNOR-based Oblivious Deep Neural Network Inference
M. Sadegh Riazi, Mohammad Samragh, Hao Chen, Kim Laine, Kristin Lauter, Farinaz Koushanfar

Advancements in deep learning enable cloud servers to provide inference-as-a-service for clients. In this scenario, clients send their raw data to the server to run the deep learning model and send back the results. One standing challenge in this setting is to ensure the privacy of the clients' sensitive data. Oblivious inference is the task of running the neural network on the client's input without disclosing the input or the result to the server. This paper introduces XONN, a novel end-to-end framework based on Yao's Garbled Circuits (GC) protocol, that provides a paradigm shift in the conceptual and practical realization of oblivious inference. In XONN, the costly matrix-multiplication operations of the deep learning model are replaced with XNOR operations that are essentially free in GC. We further provide a novel algorithm that customizes the neural network such that the runtime of the GC protocol is minimized without sacrificing the inference accuracy.

We design a user-friendly high-level API for XONN, allowing expression of the deep learning model architecture in an unprecedented level of abstraction. We further provide a compiler to translate the model description from high-level Python (i.e., Keras) to that of XONN. Extensive proof-of-concept evaluation on various neural network architectures demonstrates that XONN outperforms prior art such as Gazelle (USENIX Security'18) by up to 7×, MiniONN (ACM CCS'17) by 93×, and SecureML (IEEE S&P'17) by 37×. State-of-the-art frameworks require one round of interaction between the client and the server for each layer of the neural network, whereas, XONN requires a constant round of interactions for any number of layers in the model. XONN is first to perform oblivious inference on Fitnet architectures with up to 21 layers, suggesting a new level of scalability compared with state-of-the-art. Moreover, we evaluate XONN on four datasets to perform privacy-preserving medical diagnosis. The datasets include breast cancer, diabetes, liver disease, and Malaria.

We design a user-friendly high-level API for XONN, allowing expression of the deep learning model architecture in an unprecedented level of abstraction. We further provide a compiler to translate the model description from high-level Python (i.e., Keras) to that of XONN. Extensive proof-of-concept evaluation on various neural network architectures demonstrates that XONN outperforms prior art such as Gazelle (USENIX Security'18) by up to 7×, MiniONN (ACM CCS'17) by 93×, and SecureML (IEEE S&P'17) by 37×. State-of-the-art frameworks require one round of interaction between the client and the server for each layer of the neural network, whereas, XONN requires a constant round of interactions for any number of layers in the model. XONN is first to perform oblivious inference on Fitnet architectures with up to 21 layers, suggesting a new level of scalability compared with state-of-the-art. Moreover, we evaluate XONN on four datasets to perform privacy-preserving medical diagnosis. The datasets include breast cancer, diabetes, liver disease, and Malaria.

20
February
2019

The early registration deadline for FSE 2019 is approaching soon (February 26). After that date, registration prices will increase!

You can register online at https://secure.iacr.org/conferences/fse2019/register/.

FSE 2019 will take place in Paris, France during March 25-28, 2019. For more information on the conference please visit https://fse.iacr.org/2019.

You can register online at https://secure.iacr.org/conferences/fse2019/register/.

FSE 2019 will take place in Paris, France during March 25-28, 2019. For more information on the conference please visit https://fse.iacr.org/2019.

ePrint Report
Key-dependent cube attack on reduced Frit permutation in Duplex-AE modes
Lingyue Qin, Xiaoyang Dong, Keting Jia, Rui Zong

Frit is a new lightweight 384-bit cryptographic permutation proposed by Simon et al., which is designed for resisting fault injection and performs competitively in both hardware and software. Dobraunig et al. first studied Frit in EM construction, and left an open problem to explore the security of Frit in a sponge or duplex modes. In this paper, by introducing a new key-dependent cube attack method, we partially answer the open question by Dobraunig et al. and give some key-recovery attacks on the rounded-reduced Frit used in duplex authenticated encryption mode (Frit-AE). Our results cover all the versions of Frit-AE and include some practical key-recovery attacks that could recover the key within several minutes.

ePrint Report
Updatable Anonymous Credentials and Applications to Incentive Systems
Johannes Blömer, Jan Bobolz, Denis Diemert, Fabian Eidens

In this paper, we introduce updatable anonymous credential systems (UACS) and use them to construct a new privacy-preserving incentive system.
In a UACS, a user holding a credential certifying some attributes can interact with the corresponding issuer to update his attributes. During this, the issuer knows which update function is run, but does not learn the user's previous attributes. Hence the update process preserves anonymity of the user.
One example for a class of update functions are additive updates of integer attributes, where the issuer increments an unknown integer attribute value $v$ by some known value $k$. This kind of update is motivated by an application of UACS to incentive systems. Users in an incentive system can anonymously accumulate points, e.g. in a shop at checkout, and spend them later, e.g. for a discount.

In this paper, we (1) formally define UACS and their security, (2) give a generic construction for UACS supporting arbitrary update functions, and (3) construct a practically efficient incentive system using UACS.

In this paper, we (1) formally define UACS and their security, (2) give a generic construction for UACS supporting arbitrary update functions, and (3) construct a practically efficient incentive system using UACS.

ePrint Report
Profiling Side-channel Analysis in the Restricted Attacker Framework
Stjepan Picek, Annelie Heuser, Sylvain Guilley

Profiling side-channel attacks represent the most powerful category of side-channel attacks. There, we assume that the attacker has access to a clone device in order to profile the device. Additionally, we assume the attacker to be unbounded in power in an effort to give the worst-case security analysis.
In this paper, we start from a different premise and consider an attacker in a restricted setting where he is able to profile only a limited number of measurements. To that end, we propose a new framework for profiling side-channel analysis that we call the Restricted Attacker framework. With it, we enforce the attackers to really conduct the most powerful attack possible but also we provide a setting that inherently allows a more fair analysis among attacks.
Next, we discuss the ramifications of having the attacker with unbounded power when considering neural network-based attacks.
There, we are able to prove that the Universal Approximation Theorem can result in neural network-based attacks being able to break implementations with only a single measurement. Those considerations further strengthen the need for the Restricted Attacker framework.

ePrint Report
Analysis of Secure Caches and Timing-Based Side-Channel Attacks
Shuwen Deng, Wenjie Xiong, Jakub Szefer

Many secure cache designs have been proposed in literature with the aim of mitigating different types of cache timing-based side-channel attacks. However, there has so far been no systematic analysis of how these secure cache designs can, or cannot, protect against different types of the timing-based attacks. To provide a means of analyzing the caches, this paper first presents a novel three-step modeling approach to exhaustively enumerate all the possible cache timing-based side-channel vulnerabilities. The model covers not only attacks that leverage cache accesses or flushes from the local processor core, but also attacks that leverage changes in the cache state due to the cache coherence protocol actions from remote cores. Moreover, both conventional attacks and speculative execution attacks are considered. With the list of all possible cache timing side-channel vulnerabilities derived from the three-step model, this work further analyzes each of the existing secure cache designs to show which types of timing-based side-channel vulnerabilities each secure cache can mitigate. Based on the security analysis of the existing secure cache designs, this paper further summaries different techniques gleaned from the secure cache designs and the technique’s ability help mitigate different types of cache timing-based side-channel vulnerabilities.

ePrint Report
Verifiable Delay Functions from Supersingular Isogenies and Pairings
Luca De Feo, Simon Masson, Christophe Petit, Antonio Sanso

We present two new Verifiable Delay Functions (VDF) based on assumptions from elliptic curve cryptography. We discuss both the advantages and some drawbacks of our constructions, we study their security and we demonstrate their practicality with a proof-of-concept implementation.

ePrint Report
libInterMAC: Beyond Confidentiality and Integrity in Practice
Martin R. Albrecht, Torben Brandt Hansen, Kenneth G. Paterson

Boldyreva et al. (Eurocrypt 2012) defined a fine-grained security model capturing ciphertext fragmentation attacks against symmetric encryption schemes. The model was extended by Albrecht et al. (CCS 2016) to include an integrity notion.
The extended security model encompasses important security goals of SSH that go beyond confidentiality and integrity to include length hiding and denial-of-service resistance properties. Boldyreva et al. also defined and analysed the InterMAC scheme, while Albrecht et al. showed that InterMAC satisfies stronger security notions than all currently available SSH encryption schemes. In this work, we take the InterMAC scheme and make it fully ready for use in practice. This involves several steps. First, we modify the InterMAC scheme to support encryption of arbitrary length plaintexts and we replace the use of Encrypt-then-MAC in InterMAC with modern nonce-based authenticated encryption. Second, we describe a reference implementation of the modified InterMAC scheme in the form of the library libInterMAC. We give a performance analysis of libInterMAC. Third, to test the practical performance of libInterMAC, we implement several InterMAC-based encryption schemes in OpenSSH and carry out a performance analysis for the use-case of file transfer using SCP. We measure the data throughput and the data overhead of using InterMAC-based schemes compared to existing schemes in OpenSSH. Our analysis shows that, for some network set-ups, using InterMAC-based schemes in OpenSSH only moderately affects performance whilst providing stronger security guarantees compared to existing schemes.

ePrint Report
Use your Brain! Arithmetic 3PC For Any Modulus with Active Security
Hendrik Eerikson, Claudio Orlandi, Pille Pullonen, Joonas Puura, Mark Simkin

Secure multiparty computation (MPC) allows a set of mutually distrustful parties to compute a public function on their private inputs without revealing anything beyond the output of the computation.
In recent years, a large effort has undergone into designing and implementing MPC protocols that can be used in practice.
This paper focuses on the specific case of three-party computation with an honest majority, which is among the most popular models for real-world applications of MPC.
Somewhat surprisingly, despite its significant popularity, there are currently no practical solutions for evaluating arithmetic circuits over real-world CPU word sizes, like 32- and 64-bit words, that are secure against active adversaries that may arbitrarily deviate from the protocol description.
Existing solutions are either only passively secure or require the computations to be performed over prime fields, which do not match real-world system architectures.
This is unfortunate, since it requires application developers to redesign their applications for the models of computation that are provided by existing MPC frameworks, rather than the MPC frameworks matching the needs of the developers.

In this paper we present the first fully-fledged implementation of an MPC framework that can evaluate arithmetic circuits with arbitrary word sizes. Our framework is based on a new protocol, which improves the communication overhead of the best known previous solutions by a factor of two. We provide extensive benchmarks of our framework in a LAN and in different WAN settings, showing that the online overhead for achieving active security is less than two, when compared to the best solutions for the same setting with passive security. Concretely, for the case of 32- and 64-bit words, we show that our framework can evaluate $10^6$ multiplication gates per second.

In this paper we present the first fully-fledged implementation of an MPC framework that can evaluate arithmetic circuits with arbitrary word sizes. Our framework is based on a new protocol, which improves the communication overhead of the best known previous solutions by a factor of two. We provide extensive benchmarks of our framework in a LAN and in different WAN settings, showing that the online overhead for achieving active security is less than two, when compared to the best solutions for the same setting with passive security. Concretely, for the case of 32- and 64-bit words, we show that our framework can evaluate $10^6$ multiplication gates per second.

ePrint Report
Fast Side-Channel Security Evaluation of ECC Implementations: Shortcut Formulas for Horizontal Side-channel Attacks against ECSM with the Montgomery ladder
Melissa Azouaoui, Romain Poussier, François-Xavier Standaert

Horizontal attacks are a suitable tool to evaluate the (nearly) worst-case side-channel security level of ECC implementations, due to the fact that they allow extracting a large amount of information from physical observations. Motivated by the difficulty of mounting such attacks and inspired by evaluation strategies for the security of symmetric cryptography implementations, we derive shortcut formulas to estimate the success rate of horizontal differential power analysis attacks against ECSM implementations, for efficient side-channel security evaluations. We then discuss the additional leakage assumptions that we exploit for this purpose, and provide experimental confirmation that the proposed tools lead to good predictions of the attacks' success.

We introduce a new variant of decentralised, trustless, permissionless proof-of-work blockchain. The main novelty of the new variant is a multi-stage proof of work which is analogous to multi-stage pipelining used in hardware architectures. Among the possible advantages
of using a multi-stage proof-of-work blockchain are the following.

Reduction of the time for confirmation of a transaction and speeding up the overall rate of transactions processing without reducing the time for mining a block.

Encourage cooperative behaviour among the miners so that the reward for mining a block is shared by a number of miners.

Use of hardware incompatible hash functions for various stages so that it becomes very difficult for a single entity to attain major computational advantage over all the stages of the block mining.

Improve security by making 51\% attacks more difficult to achieve and by providing resilience to selfish mining attacks.

We believe that the new blockchain structure mitigates the problem of scalability without compromising security. By enforcing cooperative behaviour among the miners, reward for mining a block is more equitably distributed. This, in turn, will help in ensuring participation by a greater number of entities in the overall mining activity.

Reduction of the time for confirmation of a transaction and speeding up the overall rate of transactions processing without reducing the time for mining a block.

Encourage cooperative behaviour among the miners so that the reward for mining a block is shared by a number of miners.

Use of hardware incompatible hash functions for various stages so that it becomes very difficult for a single entity to attain major computational advantage over all the stages of the block mining.

Improve security by making 51\% attacks more difficult to achieve and by providing resilience to selfish mining attacks.

We believe that the new blockchain structure mitigates the problem of scalability without compromising security. By enforcing cooperative behaviour among the miners, reward for mining a block is more equitably distributed. This, in turn, will help in ensuring participation by a greater number of entities in the overall mining activity.

ePrint Report
Understanding Optimizations and Measuring Performances of PBKDF2
Andrea Francesco Iuorio, Andrea Visconti

Password-based Key Derivation Functions (KDFs) are used to generate secure keys of arbitrary length implemented in many security-related systems.
The strength of these KDFs is the ability to provide countermeasures against brute-force/dictionary attacks.
One of the most implemented KDF is PBKDF2. In order to slow attackers down,
PBKDF2 uses a salt and introduces computational intensive operations based on an iterated pseudo-random function.
Since passwords are widely used to protect personal data and to authenticate users to access specific resources,
if an application uses a small iteration count value, the strength of PBKDF2 against attacks performed
on low-cost commodity hardware may be reduced.
In this paper we introduce the cryptographic algorithms involved in the key derivation process,
describing the optimization techniques used to speed up PBKDF2-HMAC-SHA1 in a GPU/CPU context.
Finally, a testing activities has been executed on consumer-grade hardware and experimental results are reported.

ePrint Report
FPGA-based High-Performance Parallel Architecture for Homomorphic Computing on Encrypted Data
Sujoy Sinha Roy, Furkan Turan, Kimmo Jarvinen, Frederik Vercauteren, Ingrid Verbauwhede

Homomorphic encryption is a tool that enables computation on encrypted data and thus has applications in privacy-preserving cloud computing. Though conceptually amazing, implementation of homomorphic encryption is very challenging and typically software implementations on general purpose computers are extremely slow. In this paper we present our year long effort to design a domain specific architecture in a heterogeneous Arm+FPGA platform to accelerate homomorphic computing on encrypted data. We design a custom co-processor for the computationally expensive operations of the well-known Fan-Vercauteren (FV) homomorphic encryption scheme on the FPGA, and make the Arm processor a server for executing different homomorphic applications in the cloud, using this FPGA-based co-processor. We use the most recent arithmetic and algorithmic optimization techniques and perform designspace exploration on different levels of the implementation hierarchy. In particular we apply circuit-level and block-level pipeline strategies to boost the clock frequency and increase the throughput respectively. To reduce computation latency, we use parallel processing at all levels. Starting from the highly optimized building blocks, we gradually build our multi-core multi-processor architecture for computing. We implemented and tested our optimized domain specific programmable architecture on a single Xilinx Zynq UltraScale+ MPSoC ZCU102 Evaluation Kit. At 200 MHz FPGA-clock, our implementation achieves over 13x speedup with respect to a highly optimized software implementation of the FV homomorphic encryption scheme on an Intel i5 processor running at 1.8 GHz.

ePrint Report
Robust MPC: Asynchronous Responsiveness yet Synchronous Security
Chen-Da Liu-Zhang, Julian Loss, Ueli Maurer, Tal Moran, Daniel Tschudi

Two paradigms for secure MPC are synchronous and asynchronous
protocols, which differ substantially in terms of the guarantees they
provide. While synchronous protocols tolerate more corruptions and
allow every party to give its input, they are very slow because the
speed depends on the conservatively assumed worst-case delay $\Delta$
of the network. In contrast, asynchronous protocols are as fast as
the actual network allows, i.e., run in time proportional to the
actual maximal network delay $\delta$, but unavoidably parties with
slow network connections cannot give input.

This paper proposes a new, composable model (of UC functionalities) capturing the best of both worlds. Each party obtains the output as fast as the network allows (a property called responsiveness), and it is guaranteed that all parties obtain the same output. We consider different corruption thresholds: correctness, privacy, and responsiveness are guaranteed for less than $T_C$, $T_P$, and $T_R$ corruptions, respectively, while termination is always guaranteed. We achieve a trade-off between correctness, privacy and responsiveness: For any $T_R\leq\frac{1}{3}n$, one can achieve $T_C = T_P=\min\{\frac{1}{2}n,n-2T_R\}$. In particular, setting $T_R = \frac{1}{4}n$ allows us to obtain $T_C = T_P = \frac{1}{2}n$, hence achieving substantial responsiveness, yet correctness and privacy much better than in an asynchronous protocol and as good as for a purely synchronous (slow) protocol.

This result is achieved by a black-box compiler for combining an asynchronous and a synchronous protocol, involving new protocol techniques that may have applications in other contexts, and by devising an asynchronous protocol with $T_C = T_P = n-2T_R$, improving the correctness and privacy of known protocols achieving $T_C=T_P=\frac{1}{3}n$.

This paper proposes a new, composable model (of UC functionalities) capturing the best of both worlds. Each party obtains the output as fast as the network allows (a property called responsiveness), and it is guaranteed that all parties obtain the same output. We consider different corruption thresholds: correctness, privacy, and responsiveness are guaranteed for less than $T_C$, $T_P$, and $T_R$ corruptions, respectively, while termination is always guaranteed. We achieve a trade-off between correctness, privacy and responsiveness: For any $T_R\leq\frac{1}{3}n$, one can achieve $T_C = T_P=\min\{\frac{1}{2}n,n-2T_R\}$. In particular, setting $T_R = \frac{1}{4}n$ allows us to obtain $T_C = T_P = \frac{1}{2}n$, hence achieving substantial responsiveness, yet correctness and privacy much better than in an asynchronous protocol and as good as for a purely synchronous (slow) protocol.

This result is achieved by a black-box compiler for combining an asynchronous and a synchronous protocol, involving new protocol techniques that may have applications in other contexts, and by devising an asynchronous protocol with $T_C = T_P = n-2T_R$, improving the correctness and privacy of known protocols achieving $T_C=T_P=\frac{1}{3}n$.

ePrint Report
Noninteractive Zero Knowledge for NP from (Plain) Learning With Errors
Chris Peikert, Sina Shiehian

We finally close the long-standing problem of constructing a
noninteractive zero-knowledge (NIZK) proof system for any NP language
with security based on the plain Learning With Errors (LWE)
problem, and thereby on worst-case lattice problems. Our proof system
instantiates the framework recently developed by Canetti
et al. [EUROCRYPT'18], Holmgren and Lombardi [FOCS'18], and Canetti
et al. [STOC'19] for soundly applying the Fiat--Shamir transform using
a hash function family that is correlation intractable for a
suitable class of relations. Previously, such hash families were based
either on ``exotic'' assumptions (e.g., indistinguishability
obfuscation or optimal hardness of certain LWE variants) or, more
recently, on the existence of circularly secure fully homomorphic
encryption (FHE). However, none of these assumptions are known to be
implied by plain LWE or worst-case hardness.

Our main technical contribution is a hash family that is correlation intractable for arbitrary size-$S$ circuits, for any polynomially bounded $S$, based on plain LWE (with small polynomial approximation factors). The construction combines two novel ingredients: a correlation-intractable hash family for log-depth circuits based on LWE (or even the potentially harder Short Integer Solution problem), and a ``bootstrapping'' transform that uses (leveled) FHE to promote correlation intractability for the FHE decryption circuit to arbitrary (bounded) circuits. Our construction can be instantiated in two possible ``modes,'' yielding a NIZK that is either computationally sound and statistically zero knowledge in the common random string model, or vice-versa in the common reference string model.

Our main technical contribution is a hash family that is correlation intractable for arbitrary size-$S$ circuits, for any polynomially bounded $S$, based on plain LWE (with small polynomial approximation factors). The construction combines two novel ingredients: a correlation-intractable hash family for log-depth circuits based on LWE (or even the potentially harder Short Integer Solution problem), and a ``bootstrapping'' transform that uses (leveled) FHE to promote correlation intractability for the FHE decryption circuit to arbitrary (bounded) circuits. Our construction can be instantiated in two possible ``modes,'' yielding a NIZK that is either computationally sound and statistically zero knowledge in the common random string model, or vice-versa in the common reference string model.

ePrint Report
Schnorr-based implicit certification: improving the security and efficiency of V2X communications
Paulo S. L. M. Barreto, Marcos A. Simplicio Jr., Jefferson E. Ricardini, Harsh Kupwade Patil

In the implicit certification model, the process of verifying the validity of the signer's public key is combined with the verification of the signature itself. When compared to traditional, explicit certificates, the main advantage of the implicit approach lies in the shorter public key validation data. This property is particularly important in resource-constrained scenarios where public key validation is performed very often, which is common in vehicular communications (V2X) that employ pseudonym certificates. In this article, we propose a Schnorr-based implicit certification procedure that is more efficient than the state of the art. We then integrate the proposed solution with a popular V2X-oriented pseudonym certificate provisioning approach, the (unified) butterfly key expansion, showing the corresponding performance gains. As an additional contribution, we show that butterfly keys are vulnerable to existential forgery attacks under certain conditions, and also discuss how this issue can be fixed in an effective and efficient manner.

ePrint Report
Efficient Constructions for Almost-everywhere Secure Computation
Siddhartha Jayanti, Srinivasan Raghuraman, Nikhil Vyas

The importance of efficient MPC in today's world needs no retelling. An obvious barebones requirement to execute protocols for MPC is the ability of parties to communicate with each other. Traditionally, we solve this problem by assuming that every pair of parties in the network share a dedicated secure link that enables reliable message transmission. This assumption is clearly impractical as the number of nodes in the network grows, as it has today. In their seminal work, Dwork, Peleg, Pippenger and Upfal introduced the notion of almost-everywhere secure primitives in an effort to model the reality of large scale global networks and study the impact of limited connectivity on the properties of fundamental fault-tolerant distributed tasks. In this model, the underlying communication network is sparse and hence some nodes may not even be in a position to participate in the protocol (all their neighbors may be corrupt, for instance). A protocol for almost everywhere reliable message transmission, which would guarantee that a large subset of the network can transmit messages to each other reliably, implies a protocol for almost-everywhere agreement where nodes are required to agree on a value despite malicious or byzantine behavior of some subset of nodes, and an almost-everywhere agreement protocol implies a protocol almost-everywhere secure MPC that is unconditionally or information-theoretically secure. The parameters of interest are the degree $d$ of the network, the number $t$ of corrupted nodes that can be tolerated and the number $x$ of nodes that the protocol may give up. Prior work achieves $d = O(1)$ for $t = O(n/\log n)$ and $d = O(\log^{q}n)$ for $t = O(n)$ for some fixed constant $q > 1$.

In this work, we first derive message protocols which are efficient with respect to the total number of computations done across the network. We use this result to show an abundance of networks with $d = O(1)$ that are resilient to $t = O(n)$ random corruptions. This randomized result helps us build networks which are resistant to worst-case adversaries. In particular, we improve the state of the art in the almost everywhere reliable message transmission problem in the worst-case adversary model by showing the existence of an abundance of networks that satisfy $d = O(\log n)$ for $t = O(n)$, thus making progress on this question after nearly a decade. Finally, we define a new adversarial model of corruptions that is suitable for networks shared amongst a large group of corporations that: (1) do not trust each other, and (2) may collude, and construct optimal networks achieving $d = O(1)$ for $t = O(n)$ in this model.

In this work, we first derive message protocols which are efficient with respect to the total number of computations done across the network. We use this result to show an abundance of networks with $d = O(1)$ that are resilient to $t = O(n)$ random corruptions. This randomized result helps us build networks which are resistant to worst-case adversaries. In particular, we improve the state of the art in the almost everywhere reliable message transmission problem in the worst-case adversary model by showing the existence of an abundance of networks that satisfy $d = O(\log n)$ for $t = O(n)$, thus making progress on this question after nearly a decade. Finally, we define a new adversarial model of corruptions that is suitable for networks shared amongst a large group of corporations that: (1) do not trust each other, and (2) may collude, and construct optimal networks achieving $d = O(1)$ for $t = O(n)$ in this model.

Decryption failure is a common phenomenon in most lattice-based public-key schemes. To reduce the rate of decryption failure, application of error correction code can be helpful. However, the literature of error correcting codes typically addresses computational performances and error correcting capabilities of the codes; their security properties are yet to be investigated. Hence, direct porting of an error correcting code in a cryptographic scheme could open new avenues to the attacks. For example, a recent work has exploited non-constant-time execution of the BCH error correcting code to reduce the security of the lattice-based public-key scheme LAC.

In this work we analyze the decoding algorithm of the BCH code and design a constanttime version of the BCH decoding algorithm. To study the computational overhead of the countermeasures, we integrated our constant-time BCH code in the reference and optimized implementations of the LAC scheme and observed nearly 1.1 and 3.0 factor slowdown respectively for the CCA-secure primitives.

In this work we analyze the decoding algorithm of the BCH code and design a constanttime version of the BCH decoding algorithm. To study the computational overhead of the countermeasures, we integrated our constant-time BCH code in the reference and optimized implementations of the LAC scheme and observed nearly 1.1 and 3.0 factor slowdown respectively for the CCA-secure primitives.

ePrint Report
FastKitten: Practical Smart Contracts on Bitcoin
Poulami Das, Lisa Eckey, Tommaso Frassetto, David Gens, Kristina Hostáková, Patrick Jauernig, Sebastian Faust, Ahmad-Reza Sadeghi

Smart contracts are envisioned to be one of the killer applications of decentralized cryptocurrencies. They enable self-enforcing payments between users depending on complex program logic. Unfortunately, Bitcoin – the largest and by far most widely used cryptocurrency – does not offer support for complex smart contracts. Moreover, simple contracts that can be executed on Bitcoin are often cumbersome to design and very costly to execute. In this work we present FastKitten, a practical framework for executing arbitrarily complex smart contracts at low costs over decentralized cryptocurrencies which are designed to only support simple transactions. To this end, FastKitten leverages the power of trusted computing environments (TEEs), in which contracts are run off-chain to enable efficient contract execution at low cost. We formally prove that FastKitten satisfies strong security properties when all but one party are malicious. Finally, we report on a prototype implementation which supports arbitrary contracts through a scripting engine, and evaluate performance through benchmarking a provably fair online poker game. Our implementation illustrates that FastKitten is practical for complex multi-round applications with a very small latency. Combining these features, FastKitten is the first truly practical framework for complex smart contract execution over Bitcoin.

ePrint Report
Overdrive2k: Efficient Secure MPC over $Z_{2^k}$ from Somewhat Homomorphic Encryption
Emmanuela Orsini, Nigel P. Smart, Frederik Vercauteren

Recently, Cramer et al. (CRYPTO 2018) presented a protocol, SPDZ2k, for actively secure multiparty computation for dishonest majority in the pre-processing model over the ring $Z_{2^k}$, instead of over a prime field $F_p$. Their technique used oblivious transfer for the pre-processing phase, more specifically the MASCOT protocol (Keller et al. CCS 2016). In this paper we describe a more efficient technique for secure multiparty computation over $Z_{2^k}$ based on somewhat homomorphic encryption. In particular we adapt the Overdrive approach (Keller et al. EUROCRYPT 2018) to obtain a protocol which is more like the original SPDZ protocol (Damg{\aa}rd et al. CRYPTO 2012).

To accomplish this we introduce a special packing technique for the BGV encryption scheme operating on the plaintext space defined by the SPDZ2k protocol, extending the ciphertext packing method used in SPDZ to the case of $Z_{2^k}$. We also present a more complete pre-processing phase for secure computation modulo $2^k$ by adding a new technique to produce shared random bits. These are needed in a number of online protocols and are quite expensive to generate using the MASCOT-based method given in the original SPDZ2k paper.

Our approach can be applied to both the Low-Gear and High-Gear variant of Overdrive, and it leads to a protocol whose overall efficiency is three to six times better than the OT-based methodology.

To accomplish this we introduce a special packing technique for the BGV encryption scheme operating on the plaintext space defined by the SPDZ2k protocol, extending the ciphertext packing method used in SPDZ to the case of $Z_{2^k}$. We also present a more complete pre-processing phase for secure computation modulo $2^k$ by adding a new technique to produce shared random bits. These are needed in a number of online protocols and are quite expensive to generate using the MASCOT-based method given in the original SPDZ2k paper.

Our approach can be applied to both the Low-Gear and High-Gear variant of Overdrive, and it leads to a protocol whose overall efficiency is three to six times better than the OT-based methodology.

ePrint Report
Privacy-preserving Approximate GWAS computation based on Homomorphic Encryption
Duhyeong Kim, Yongha Son, Dongwoo Kim, Andrey Kim, Seungwan Hong, Jung Hee Cheon

One of three tasks in a secure genome analysis competition called IDASH 2018 was to develop a solution for privacy-preserving GWAS computation based on homomorphic encryption. The scenario is that a data holder encrypts a number of individual records, each of which consists of several phenotype and genotype data, and provide the encrypted data to an untrusted server. Then, the server performs a GWAS algorithm based on homomorphic encryption without the decryption key and outputs the result in encrypted state so that there is no information leakage on the sensitive data to the server.
We develop a privacy-preserving semi-parallel GWAS algorithm by applying an approximate homomorphic encryption scheme HEAAN. Fisher scoring and semi-parallel GWAS algorithms are modified to be efficiently computed over homomorphically encrypted data with several optimization methodologies; substitute matrix inversion by an adjoint matrix, avoid computing a superfluous matrix of super-large size, and transform the algorithm into an approximate version.
Our modified semi-parallel GWAS algorithm based on homomorphic encryption which achieves 128-bit security takes $30$--$40$ minutes for $245$ samples containing $10,000$--$15,000$ SNPs. Compared to the true $p$-value from the original semi-parallel GWAS algorithm, the $F_1$ score of our $p$-value result is over $0.99$.

The problem of solving a system of quadratic equations in multiple variables---known as multivariate-quadratic or MQ problem---is the underlying hard problem of various cryptosystems. For efficiency reasons, a common instantiation is to consider quadratic equations over $\F_2$. The current state of the art in solving the \MQ problem over $\F_2$ for sizes commonly used in cryptosystems is enumeration, which runs in time $\Theta(2^n)$ for a system of $n$ variables. Grover's algorithm running on a large quantum computer is expected to reduce the time to $\Theta(2^{n/2})$. As a building block, Grover's algorithm requires an "oracle", which is used to evaluate the quadratic equations at a superposition of all possible inputs. In this paper, we describe two different quantum circuits that provide this oracle functionality. As a corollary, we show that even a relatively small quantum computer with as little as 92 logical qubits is sufficient to break MQ instances that have been proposed for 80-bit pre-quantum security.

This paper introduces a constant-time implementation for a quasi-cyclic moderate-density-parity-check (QC-MDPC) code based encryption scheme. At a $2^{80}$ security level, the software takes 14679937 Cortex-M4 and 1560072 Haswell cycles to decrypt a short message, while the previous records were 18416012 and 3104624 (non-constant-time) cycles. Such speed is achieved by combining two techniques: 1) performing each polynomial multiplication in $\mathbb{F}_2[x]/(x^r-1)$ and $\mathbb{Z}[x]/(x^r-1)$ using a sequence of ``constant-time rotations'' and 2) bitslicing.