International Association
for Cryptologic Research

We present Edrax, a general architecture for building cryptocurrencies with stateless transaction validation. In Edrax, all cryptocurrency nodes, such as miners and validating nodes, can validate incoming transactions and subsequently update user balances simply by accessing the last confirmed block. This removes the current need for storing, off-chain and on-disk, order-of-gigabytes large validation state. We present and implement two instantiations of Edrax, one in the UTXO-based model of Bitcoin-like cryptocurrencies, where we use sparse Merkle trees, and one in the account-based model of Ethereum-like cryptocurrencies, where we show that Merkle trees cannot be used and where algebraic vector commitments are needed instead. Towards this goal, we construct, prove secure and implement the first practical algebraic vector commitment with logarithmic asymptotic costs that can scale to millions of accounts, as required by cryptocurrencies today. Our evaluation of Edrax shows that (i) for the current scale of Bitcoin and Ethereum our stateless transaction validation overhead is comparable to stateful transaction validation that requires gigabytes of local index data; (ii) while the scale increases, the performance of stateful validation deteriorates substantially due to expensive I/Os and our stateless validation is faster by up to approximately two orders of magnitude.

Since 2016 and the introduction of the exTNFS (extended Tower Number Field Sieve) algorithm, the security of cryptosystems based on non- prime finite fields, mainly the paring and torus-based one, is being reassessed. The feasibility of the relation collection, a crucial step of the NFS variants, is especially investigated. It usually involves polynomials of degree one, i.e., a search space of dimension two. However, exTNFS uses bivariate polynomials of at least four coefficients. If sieving in dimension two is well described in the literature, sieving in higher dimension received significantly less attention. We describe and analyze three different generic algorithms to sieve in any dimension for the NFS algorithms. Our implementation shows the practicability of dimension four sieving, but the hardness of dimension six sieving.

The Multivariate Ring Learning with Errors ($m$-RLWE) problem was introduced in 2015 by Pedrouzo-Ulloa, Troncoso-Pastoriza and P\'erez-Gonz\'alez. Instead of working over a polynomial residue ring with one variable as in RLWE, it works over a polynomial residue ring in several variables. However, care must be taken when choosing the multivariate rings for use in cryptographic applications as they can be either weak or simply equivalent to univariate RLWE. For example, Pedrouzo-Ulloa et al.\ suggest using tensor products of cyclotomic rings, in particular power-of-two cyclotomic rings. They claim incorrectly that the security increases with the product of the individual degrees. In this paper, we present simple methods to solve the search $m$-RLWE problem far more efficiently than is stated in the current literature by reducing the problem to the RLWE problem in dimension equal to the maximal degree of its components (and not the product) and where the noise increases with the square-root of the degree of the other components. Our methods utilise the fact that the defining cyclotomic polynomials share algebraically related roots. We use these methods to successfully attack the search variant of the $m$-RLWE problem for a set of parameters estimated to offer more than 2600 bits of security, and being equivalent to solving the bounded distance decoding problem in a highly structured lattice of dimension 16384, in less than two weeks of computation time or just a few hours if parallelized on 128 cores.

Finally, we also show that optimizing module-LWE cryptosystems by introducing an extra ring structure as is common practice to optimize LWE, often results in a total breakdown of security.

We present attacks that use only the volume of responses to range queries to reconstruct databases. Our focus is on practical attacks that work for large-scale databases with many values and records, without requiring assumptions on the data or query distributions. Our work improves on the previous state-of-the-art due to Kellaris \emph{et al.} (CCS 2016) in all of these dimensions.

Our main attack targets reconstruction of database counts and involves a novel graph-theoretic approach. It generally succeeds when $R$, the number of records, exceeds $N^2/2$, where $N$ is the number of possible values in the database. For a uniform query distribution, we show that it requires volume leakage from only $O(N^2 \log N)$ queries (cf.\ $O(N^4 \log N)$ in prior work).

We present two ancillary attacks. The first identifies the value of a new item added to a database using the volume leakage from fresh queries, in the setting where the adversary knows or has previously recovered the database counts. The second shows how to efficiently recover the ranges involved in queries in an online fashion, given an auxiliary distribution describing the database.

Our attacks are all backed with mathematical analyses and extensive simulations using real data.

This paper addresses fast scalar multiplication for elliptic curves over finite fields. In the first part of the paper, we obtain several efficiently computable formulas for basic elliptic curves arithmetic in the family of twisted Edwards curves over prime fields. Our $2Q+P$ formula saves about $2.8$ field multiplications, and our $5P$ formula saves about $4.2$ field multiplications in standard projective coordinate systems, compared to the latest existing results. In the second part of the paper, we formulate bucket methods for the DAG-based and the tree-based abstract ideas. We propose systematically finding a near optimal chain for multi-base number systems (MBNS). These proposed bucket methods take significantly less time to find a near optimal chain, compared to an optimal chain. We conducted extensive experiments to compare the performance of the MBNS methods (e.g., greedy, ternary/binary, multi-base NAF, tree-based, rDAG-based, and bucket). Our proposed formulas were integrated in these methods. Our results show our work had an important role in advancing the efficiency of scalar multiplication.

Attribute-Based Encryption (ABE) is a versatile one-to-many encryption primitive which enables fine-grained access control over encrypted data. Due to its promising applications in practice, ABE has been attracting much attention in the community and schemes with better security, access policy expressivity, and efficiency have been continuously emerging. On the other hand, due to the nature of ABE, namely, different users may share some common decryption privileges and a malicious user may leak some common decryption privileges for financial gain or other incentives, being able to identify such malicious users (i.e. traitor tracing) is crucial towards the practicality of an ABE system. For some existing ABE schemes with appealing properties (e.g. full security, large universe), the corresponding traceable counterparts have been proposed. However, these works are proceeded case by case, and there are still many appealing ABE schemes not having the traceable counterparts. Furthermore, when any new ABE scheme emerges and we want to apply it in practice, it will take significant workload to investigate and propose its traceable counterpart.

In this paper, we propose a framework to transform existing and (possibly) future ABE schemes to their traceable counterparts in a generic manner. In particular, by specifying some requirements on the structure of the ABE constructions, we propose an ABE template, and show that any ABE scheme satisfying this template can be transformed to a fully collusion-resistant blackbox traceable ABE scheme in a generic manner, at the cost of sublinear overhead, while keeping the appealing properties, such as fine-grained access control on encrypted data, highly expressive access policy, short ciphertext, and so on. We prove the security in the framework all in the standard model, and we present a couple of existing ABE schemes with appealing properties as examples that do satisfy our ABE template.

Ledger-based systems that enable rich applications often suffer from two limitations. First, validating a transaction requires re-executing the state transition that it attests to. Second, transactions not only reveal which application had a state transition but also reveal the application's internal state. Unfortunately, expensive re-execution and lack of privacy rule out many use cases.

We design, implement, and evaluate ZEXE, a ledger-based system where users can execute offline computations and subsequently produce transactions, attesting to the correctness of these computations, that satisfy two main properties. First, transactions hide all information about the offline computations. Second, transactions can be validated by anyone in constant time, regardless of the offline computation.

The core of ZEXE is a protocol for a new cryptographic primitive that we introduce, *decentralized private computation* (DPC). The security guarantees of DPC are concisely expressed via an ideal functionality, which our protocol provably achieves. In order to achieve an efficient implementation of our protocol, we leverage tools in the area of cryptographic proofs, including succinct zero knowledge proofs and recursive proof composition. Overall, transactions in ZEXE are 968 bytes *regardless of the offline computation*, and generating them takes less than 2 minutes plus a time that grows with the offline computation.

To facilitate real-world deployments, ZEXE also provides support for delegating the process of producing a transaction to an untrusted worker, and support for threshold transactions and blind transactions.

Ring oscillator-based true random number generators (RO-based TRNGs) are widely used to provide unpredictable random numbers for cryptographic systems. The unpredictability of the output numbers, which can be measured by entropy, is extracted from the jitter of the oscillatory signal. To quantitatively evaluate the entropy, several stochastic models have been proposed, all of which take the jitter as a key input parameter. So it is crucial to accurately estimate the jitter in the process of entropy evaluation. However, several previous methods have estimated the jitter with non-negligible error, which would cause the overestimation of the entropy. In this paper, we propose a jitter estimation method with high accuracy. Our method aims at eliminating the quantization error in previous counter-based jitter estimation methods and finally can estimate the jitter with the error smaller than $1\%$. Furthermore, for the first time, we give a theoretical error bound for our jitter estimation. The error bound confirms the $1\%$ error level of our method. As a consequence, our method will signicantly help to evaluate the entropy of RO-based TRNGs accurately. Finally, we present the application of our jitter estimation method on a practical FPGA device and provide a circuit module diagram for on-chip implementation.

A central tenet of theoretical cryptography is the study of the minimal assumptions re- quired to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings.

Here, we propose a scheme for using quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver, against a linear number of adaptive queries to the token, in the quantum universal composability framework. We prove stand-alone security against a malicious sender, but leave open the question of composable security against a malicious sender, as well as security against a malicious receiver making a polynomial number of adaptive queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the “prepare-and-measure” type. We also show our scheme is “tight” according to two scenarios.

Videos from talks at Crypto 2018 are now available on the IACR Youtube Channel. This includes the rump session and the affiliated workshop titled "Beyond Crypto: A TCS Perspective". See https://youtube.com/TheIACR

The Department of Information Technology and Electrical Engineering (www.ee.ethz.ch) at ETH Zurich invites applications for Professor or Assistant Professor (Tenure Track) of Hardware Security position.

The successful candidate will build a leading research programme in the area of computing architectures that addresses security concerns (data integrity, user authentication, and privacy) from a hardware perspective. Topics of interest include, but are not limited to, the development of architectures designed with both performance and security in mind, such as specific hardware implementations for computing on encrypted data, efficient post-quantum cryptography and novel hardware solutions to prevent side-channel (power, timing) attacks. He or she is expected to collaborate and interact with colleagues in the department and at ETH Zurich, benefiting from strong activities on integrated circuits (e.g. the Microelectronic Design Center) and on security and privacy (e.g. the Zurich Information Security and Privacy Center).

Closing date for applications: 15 January 2019

Contact: Applications through online forms from the URL below:

More information: https://bit.ly/2CGCTXg

The School of Engineering & Technology at the University of Washington Tacoma is seeking applications from qualified candidates for a full-time lecturer position for the Master of Cybersecurity & Leadership Program (MCL) program, with an emphasis on Cyber Risk Management, Cloud Computing/Cloud Security, IoT Security, Mobile Security, and Blockchains. This is a full-time, renewable position with an initial appointment of one to three years based on experience, beginning September 2019. Reappointments are up to five years. The successful candidate(s) will teach master and undergraduate courses in Cybersecurity and Leadership and Information Technology in one or more of the following areas:

Network and Internet Security

Principles of Cybersecurity

Information Assurance, Risk Management and Security Strategies

Cybersecurity Management

Server-Side Web Programming

Database Systems Design & Administration

Network and System Administration

Course description can be found at: https://www.washington.edu/students/crscatt/tcsl.html, and

https://www.washington.edu/students/crscatt/tinfo.html

Screening of applications will begin on December 15, 2018, and will continue until the position is filled. Salary is competitive and will be commensurate with experience and qualifications. For additional information, please contact MCL/IT Lecturer Search Committee at mcl (at) uw.edu.

Required Education:

This position requires a minimum of an MS or foreign equivalent in Cybersecurity, Information Technology, or a related field at the time of appointment.

Required Work Experience:

This position requires at least 1 year of teaching experience in Cybersecurity/ Information Technology-related areas.

Application Instructions

Curriculum Vitae

A cover letter including:

A list of courses in which you feel qualified for teaching

Evidence of prior teaching success

Statement about demonstrated commitment to diversity in teaching, mentoring, and/or service

Contact information for three references

Closing date for applications: 31 March 2019

More information: http://apply.interfolio.com/53684

For the DFG Collaborative Research Center CRC 1119 CROSSING (Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments) the University Duisburg-Essen, Faculty of Business Administration and Economics, Department Computer Science, Working Group Computer Science with focus on Secure Software Systems at Campus Essen seeks to hire one Research Assistant / PhD Student (full position, salary based on E-13 TV-L, federal state salary rate)

Description of Position:

Conducting research in computer security, especially in the areas of Trusted Computing technologies (remote attestation), system and software security, mobile security, hardware security, IoT security. Opportunity for further qualification (doctoral dissertation) is given.

The desired qualifications include

• very good programming skills, especially in system-level programming (C, C++, Assembler)
• very good background in system and software security
• additional background in one of the following areas: hardware programming, side channel attacks, reverse-engineering

All candidates must have an excellent M.Sc./Diploma degree in computer science, computer security, or related fields, and must show high motivation and interest in creative conceptual and practical work.

More information on how to apply can be found at the website of the Secure Software Systems research group.

Closing date for applications: 30 November 2018

Contact: Prof. Lucas Davi

More information: https://www.syssec.wiwi.uni-due.de/en/team/open-positions/

Project

We are looking for a Ph.D. student to work on the FWO research project ESCALATE (Efficient and Scalable Algorithms for Large Flow Detection) in cooperation with and coordinated by ETH Zurich. The project starts on February 1 and has a duration of 4 years. The objectives of the project are two-fold:

1. To develop novel algorithms for efficient in-network large-flow detection. This is important for QoS (Quality of Service) schemes and DDoS (Distributed Denial of Service) defense mechanisms.
2. To decrease the detection overhead through FPGA acceleration, and to enable dynamic adaptation to ?ow distribution at run-time.

The applicant will mainly work on objective 2 in collaboration with the Ph.D. student at ETH Zurich that will be working on objective 1.

Research group

This project will be carried out as a Ph.D. project within the group of Associate Professor dr. Nele Mentens. The applicant will be a member of the ES&S (Embedded Systems & Security) group on Campus Diepenbeek and the COSIC (Computer Security and Industrial Cryptography) group in Leuven. This is the perfect setting to benefit from the decades of experience in data security and hardware design in both groups.

Profile

Candidates must hold a master’s degree in electronics engineering or computer engineering, have good grades, experience in FPGA design and a keen interest in security. We prefer candidates who can demonstrate that they have developed their research skills during their master’s studies. Adequate English (written and verbal communication) for scientific interactions is required.

Closing date for applications: 9 November 2018

Contact: Nele Mentens, Associate Professor, nele.mentens (at) kuleuven.be

More information: https://www.kuleuven.be/personeel/jobsite/jobs/54883962?hl=en&lang=en

Simula UiB (simula-uib.com) has six three-year PhD positions available in the field of cryptography. More information about the positions, Simula UiB, and how to submit the application can be found at https://www.simula.no/about/job/call-phd-students-cryptography-simula-uib.

Closing date for applications: 30 November 2018

Contact: Håvard Raddum

email: haavardr (at) simula.no

More information: https://www.simula.no/about/job/call-phd-students-cryptography-simula-uib

The Department of Mathematics & Statistics of the University of South Florida seeks to fill a 9 month, full-time and tenure-earning, Assistant Professor position in Cryptography/Cybersecurity to begin August 7, 2019.

Ph.D. in Mathematics or a closely-related field is required, with preference in disciplines related to Cryptography/Cybersecurity (e.g., Algebra, Number Theory, Algebraic Geometry, Combinatorics, etc.). Applications from individuals who are ABD will be accepted, but the degree must be conferred by appointment start date.

Closing date for applications: 15 November 2018

Contact: Denise Marks: denise (at) usf.edu

More information: http://www.math.usf.edu/about/18548/

Side-channel attacks and evaluations typically utilize leakage models to extract sensitive information from measurements of cryptographic implementations. Efforts to establish a true leakage model is still an active area of research since Kocher proposed Differential Power Analysis (DPA) in 1999. Leakage certification plays an important role in this aspect to address the following question: "how good is my leakage model?". However, existing leakage certification methods still need to tolerate assumption error and estimation error of unknown leakage models. There are many probability density distributions satisfying given moment constraints. As such, finding the most unbiased and most reasonable model still remains an unresolved problem. In this paper, we address a more fundamental question: "what's the true leakage model of a chip?". In particular, we propose Maximum Entropy Distribution (MED) to estimate the leakage model as MED is the most unbiased, objective and theoretically the most reasonable probability density distribution conditioned upon the available information. MED can theoretically use information on arbitrary higher-order moments to infinitely approximate the true leakage model. It well compensates the theory vacancy of model profiling and evaluation. Experimental results demonstrate the superiority of our proposed method for approximating the leakage model using MED estimation.

Event date: 7 December to 8 December 2018
Submission deadline: 26 October 2018
Notification: 5 November 2018

Event date: 4 June to 6 June 2019
Submission deadline: 10 February 2019
Notification: 8 April 2019

A key-dependent message (KDM) secure encryption scheme is secure even if an adversary obtains encryptions of messages that depend on the secret key. Such key-dependent encryptions naturally occur in scenarios such as harddisk encryption, formal cryptography, or in specific protocols. However, there are not many provably secure constructions of KDM-secure encryption schemes. Moreover, only one construction, due to Camenisch, Chandran, and Shoup (Eurocrypt 2009) is known to be secure against active (i.e., CCA) attacks.

In this work, we construct the first public-key encryption scheme that is KDM-secure against active adversaries and has compact ciphertexts. As usual, we allow only circular key dependencies, meaning that encryptions of arbitrary *entire* secret keys under arbitrary public keys are considered in a multi-user setting.

Technically, we follow the approach of Boneh, Halevi, Hamburg, and Ostrovsky (Crypto 2008) to KDM security, which however only achieves security against passive adversaries. We explain an inherent problem in adapting their techniques to active security, and resolve this problem using a new technical tool called ``lossy algebraic filters'' (LAFs). We stress that we significantly deviate from the approach of Camenisch, Chandran, and Shoup to obtain KDM security against active adversaries. This allows us to develop a scheme with compact ciphertexts that consist only of a constant number of group elements.