International Association
for Cryptologic Research

In this work, we study the fascinating notion of output-compressing randomized encodings for Turing Machines, in a shared randomness model. In this model, the encoder and decoder have access to a shared random string, and the efficiency requirement is, the size of the encoding must be independent of the running time and output length of the Turing Machine on the given input, while the length of the shared random string is allowed to grow with the length of the output. We show how to construct output- compressing randomized encodings for Turing machines in the shared randomness model, assuming iO for circuits and any assumption in the set {LWE, DDH, Nth Residuosity}.

We then show interesting implications of the above result to basic feasibility questions in the areas of secure multiparty computation (MPC) and indistinguishability obfuscation (iO):

1. Compact MPC for Turing Machines in the Random Oracle Model: In the context of MPC, we consider the following basic feasibility question: does there exist a malicious-secure MPC protocol for Turing Machines whose communication complexity is independent of the running time and output length of the Turing Machine when executed on the combined inputs of all parties? We call such a protocol as a compact MPC protocol. Hubacek and Wichs [HW15] showed via an incompressibility argument, that, even for the restricted setting of circuits, it is impossible to construct a malicious secure two party computation protocol in the plain model where the communication complexity is independent of the output length. In this work, we show how to evade this impossibility by compiling any (non-compact) MPC protocol in the plain model to a compact MPC protocol for Turing Machines in the Random Oracle Model, assuming output-compressing randomized encodings in the shared randomness model.

2. Succinct iO for Turing Machines in the Shared Randomness Model: In all existing constructions of iO for Turing Machines, the size of the obfuscated program grows with a bound on the input length. In this work, we show how to construct an iO scheme for Turing Machines in the shared randomness model where the size of the obfuscated program is independent of a bound on the input length, assuming iO for circuits and any assumption in the set {LWE, DDH, Nth Residuosity}.

Hardware masked AES designs usually rely on Boolean masking and perform the computation of the S-box using the tower-field decomposition. On the other hand, splitting sensitive variables in a multiplicative way is more amenable for the computation of the AES S-box, as noted by Akkar and Giraud. However, multiplicative masking needs to be implemented carefully not to be vulnerable to first-order DPA with a zero-value power model. Up to now, sound higher-order multiplicative masking schemes have been implemented only in software. In this work, we demonstrate the first hardware implementation of AES using multiplicative masks. The method is tailored to be secure even if the underlying gates are not ideal and glitches occur in the circuit. We detail the design process of first- and second-order secure AES-128 cores, which result in the smallest die area to date among previous state-of-the-art masked AES implementations with comparable randomness cost and latency. The first- and second-order masked implementations improve resp. 29% and 18% over these designs. We deploy our construction on a Spartan-6 FPGA and perform a side-channel evaluation. No leakage is detected with up to 50 million traces for both our first- and second-order implementation. For the latter, this holds both for univariate and bivariate analysis.

Mixing Networks are protocols that allow a set of senders to send messages anonymously. Such protocols are fundamental building blocks to achieve privacy in a variety of applications, such as anonymous e-mail, anonymous payments, and electronic voting.

Back in 2002, Golle et al. proposed a new concept of mixing network, called optimistic mixing, that allows for fast mixing when all the parties execute the protocol honestly. If, on the other hand, one or more mix-servers cheat, then the attack is recognized and one can back up to a different, slow mix-net.

Unfortunately, Abe and Imai (ACISP'03) and independently Wikström (SAC'03) showed several major flaws in the optimistic protocol of Golle et al. In this work, we give another look at optimistic mixing networks. Our contribution is mainly threefold. First, we give formal definitions for optimistic mixing in the UC model. Second, we propose a compiler for obtaining a UC-secure mixing network by combining an optimistic mixing with a traditional mixing protocol as backup mixing. Third, we propose an efficient UC-secure realization of optimistic mixing based on the DDH assumption in the non-programmable random oracle model. As a key ingredient of our construction, we give a new randomizable replayable-CCA secure public key encryption (PKE) that outperforms in efficiency all previous schemes. We believe this result is of independent interest.

We present Helix, a Byzantine fault tolerant and scalable consensus algorithm for fair ordering of transactions among nodes in a distributed network. In Helix, one among the network nodes proposes a potential set of successive transactions (block). The known PBFT protocol is then run within a bounded-size committee in order to achieve agreement and commit the block to the blockchain indefinitely. In Helix, transactions are encrypted via a threshold encryption scheme in order to hide information from the ordering nodes, limiting censorship and front-running. The encryption is further used to realize a verifiable source of randomness, which in turn is used to elect the committees in an unpredictable way, as well as to introduce a correlated sampling scheme of transactions included in a proposed block. The correlated sampling scheme restricts nodes from promoting their own transactions over those of others. Nodes are elected to participate in committees in proportion to their relative reputation. Reputation, attributed to each node, serves as a measure of obedience to the protocol's instructions. Committees are thus chosen in a way that is beneficial to the protocol.

This paper studies the security of Ring Oscillator Physically Unclonable Function (PUF) with Enhanced Challenge-Response Pairs as proposed by Delavar et al. We present an attack that can predict all PUF responses after querying the PUF with n+2 attacker-chosen queries. This result renders the proposed RO-PUF with Enhanced Challenge-Response Pairs inapt for most typical PUF use cases, including but not limited to all cases where an attacker has query access.

The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as a central problem in cryptography, with a flurry of recent activity in both theory and practice. In all of these works, the main bottleneck is the overhead incurred by the server, both in time and in space.

Assuming (sub-exponential) LWE, we construct a one-round argument-system for proving the correctness of any time $T$ and space $S$ RAM computation, in which both the verifier and prover are highly efficient. The verifier runs in time $n \cdot polylog(T)$ and space $polylog(T)$, where $n$ is the input length. Assuming $S \geq \max(n,polylog(T))$, the prover runs in time $\tilde{O}(T)$ and space $S + o(S)$, and in many natural cases even $S+polylog(T)$. Our solution uses somewhat homomorphic encryption but, surprisingly, only requires homomorphic evaluation of arithmetic circuits having multiplicative depth (which is a main bottleneck in homomorphic encryption) $\log_2\log(T)+O(1)$.

Prior works based on standard assumptions had a $T^c$ time prover, where $c \geq 3$ (at the very least). As for the space usage, we are unaware of any work, even based on non-standard assumptions, that has space usage $S+polylog(T)$.

Along the way to constructing our delegation scheme, we introduce several technical tools that we believe may be useful for future work.

The problem of privatizing statistical databases is a well-studied topic that has culminated with the notion of differential privacy. The complementary problem of securing these databases, however, has---as far as we know---not been considered in the past. While the security of private databases is in theory orthogonal to the problem of private statistical analysis (e.g., in the central model of differential privacy the curator is trusted) the recent real-world deployments of differentially-private systems suggest that it will become a problem of increasing importance. In this work, we consider the problem of designing encrypted databases (EDB) that support differentially-private statistical queries. More precisely, these EDBs should support a set of encrypted operations with which a curator can securely query and manage its data, and a set of private operations with which an analyst can privately analyze the data. Using such an EDB, a curator can securely outsource its database to an untrusted server (e.g., on-premise or in the cloud) while still allowing an analyst to privately query it.

We show how to design an EDB that supports private histogram queries. As a building block, we introduce a differentially-private encrypted counter based on the binary mechanism of Chan et al. (ICALP, 2010). We then carefully combine multiple instances of this counter with a standard encrypted database scheme to support differentially-private histogram queries.

LowMC is a family of block ciphers designed for a low multiplicative complexity. The specification allows a large variety of instantiations, differing in block size, key size, number of S-boxes applied per round and allowed data complexity. The number of rounds deemed secure is determined by evaluating a number of attack vectors and taking the number of rounds still secure against the best of these.

In this paper, we demonstrate that the attacks considered by the designers of LowMC in the version 2 of the round-formular were not sufficient to fend off all possible attacks. In the case of instantiations of LowMC with one of the most useful settings, namely with few applied S-boxes per round and only low allowable data complexities, efficient attacks based on difference enumeration techniques can be constructed. We show that it is most effective to consider tuples of differences instead of simple differences, both to increase the range of the distinguishers and to enable key recovery attacks. All applications for LowMC we are aware of, including signature schemes like Picnic and more recent (ring/group) signature schemes have used version 3 of the round formular for LowMC, which takes our attack already into account.

Sanitizable signature schemes (SSS) enable a designated party (called the sanitizer) to alter admissible blocks of a signed message. This primitive can be used to remove or alter sensitive data from already signed messages without involvement of the original signer. Current state-of-the-art security definitions of SSSs only define a "weak" form of security. Namely, the unforgeability, accountability and transparency definitions are not strong enough to be meaningful in certain use-cases. We identify some of these use-cases, close this gap by introducing stronger definitions, and show how to alter an existing construction to meet our desired security level. Moreover, we clarify a small yet important detail in the state-of-the-art privacy definition. Our work allows to deploy this primitive in more and different scenarios.

Event date: 31 March to 5 April 2019
Submission deadline: 14 December 2018
Notification: 8 February 2019

Event date: 10 December to 11 December 2018
Submission deadline: 1 October 2018
Notification: 5 November 2018

Cryptographic Engineering Research Group (CERG) at George Mason University, U.S.A., is seeking qualified candidates for multiple Ph.D. students / Graduate Research Assistants in the area of efficient implementations of Post-Quantum Cryptosystems, side-channel attacks targeting these cryptosystems, and countermeasures against such attacks.

The desired qualifications include

• strong mathematical background in algebra and number theory,
• experience in hardware design using hardware description languages, and
• knowledge of C and scripting languages, such as Python.

Additional experience in

• Magma or SageMath,
• ASIC or FPGA design,
• software/hardware codesign,
• High-Level Synthesis,
• embedded software development, and/or
• Linux operating system

is a plus.

The position is open starting in January 2019. Qualified candidates should apply to the ECE Ph.D. program at George Mason University by October 15, 2018. In parallel, an earlier e-mail contact with Dr. Gaj and/or Dr. Kaps is highly recommended.

Closing date for applications: 15 October 2018

Contact: Dr. Kris Gaj, Professor, kgaj (at) gmu.edu, and/or Dr. Jens-Peter Kaps, Associate Professor, jkaps (at) gmu.edu, ECE Department, George Mason University, 4400 University Drive, Fairfax, VA, U.S.A.

More information: https://cryptography.gmu.edu

Cryptographic Engineering Research Group (CERG) at George Mason University, U.S.A., is seeking qualified candidates for a Ph.D. student / Graduate Research Assistant in the area of efficient and secure implementations of Lightweight Cryptography.

The desired qualifications include experience in

• embedded systems,
• knowledge of C, assembly, and scripting languages,
• hardware design using hardware description languages,
• Linux operating system, and
• strong experimental skills.

Additional experience in

• side-channel and/or fault attacks,
• countermeasures against these attacks,
• ASIC or FPGA design,
• software/hardware codesign,
• embedded software development, and/or
• circuit/PCB design

is a plus.

Closing date for applications: 15 October 2018

Contact: Dr. Jens-Peter Kaps, Associate Professor, jkaps (at) gmu.edu and/or Dr. Kris Gaj, Professor, kgaj (at) gmu.edu, ECE Department, George Mason University, 4400 University Drive, Fairfax, VA, U.S.A.

More information: https://cryptography.gmu.edu

The Institute of Cybersecurity and Cryptology (iC2) at University of Wollongong, Australia is searching for highly motivated PhD candidates to conduct research in the area of applied cryptography in the topic of dynamic access control in the cloud.

This PhD studentship is partly funded by the Australian Research Council (ARC) Discovery project. The successful candidate will be awarded a PhD scholarship and stipend for the duration of 3 years, with a possible extension for an additional 6 months to complete the PhD thesis.

A successful candidate will be supervised by the Chief Investigators of this project: Prof. Willy Susilo and Dr. Joonsang Baek.

Interested candidates should provide a complete CV highlighting research experience, complete transcript (in English) for Bachelor and Master degrees and a research proposal. The successful candidate is expected to start in March 2019.

Application should be submitted to Dr. Joonsang Baek via email: baek (at) uow.edu.au

More Information on ic2 can be obtained from: https://eis.uow.edu.au/scit/institute-cybersecurity-cryptology/index.html

Closing date for applications: 20 October 2018

The AriC team at ENS de Lyon is seeking to recruit a post-doc in the area of cryptography. The position is available now and the term is two years.

The post-doc will work with the cryptography researchers of ENS de Lyon on topics in lattice-based cryptography. This post is part of the EU H2020 PROMETHEUS project for building quantum-safe privacy-preserving systems. Our focus within this project is on primitive/protocol design. Applicants with a background in other areas are also welcome to apply but some familiarity with zero-knowledge proofs is expected.

Applicants should have already completed a PhD in a relevant area. They should have an outstanding research track record in cryptography. They should demonstrate scientific creativity and research independence.

This is a full-time, fixed-term position based in Lyon.

Applications should be sent by email to benoit[dot]libert[at]ens-lyon[dot]fr, damien[dot]stehle[at]gmail[dot]com and fabien[dot]laguillaumie[at]ens-lyon[dot]fr. They should include a CV, a list of publications (with the top 3 ones highlighted) and contact information of two persons who are willing to give references.

Closing date for applications: 28 February 2019

Contact: Benoît Libert (benoit[dot]libert[at]ens-lyon[dot]fr)

More information: http://prometheuscrypt.gforge.inria.fr/

QUADRAC is serving job opportunities of software engineer, technical lead and technical manager for those who are enthusiastic about application technology with cryptographic communication and security protocol.

Their roles include own products’ R&D, technical lead, support et al., with the followings: implementation of security protocol with cryptography and authentication, its evaluation and tests, and software developments of security management technologies.

If you are interested in work in Japan with us in our office (in Nogizaka, Tokyo), please contact.

Japanese fluency (incl. your target) is welcome.

Step forward to work together with our skillful colleagues to new innovative product development.

QUADRAC’s business includes self-development and sales of retail transaction server, and R&D about closed-coupled communication technology.

FeliCa(NFC) core developer and skillful colleagues started a business together in 2009.

We are eager to serve people globally a happy, pleasant, convenient new life style with technology innovation, as it has been, from now on.

http://www.quadrac.co.jp/en-index

Closing date for applications: 18 March 2019

Contact: Please contact: send CV to hirohisa.iijima [at] quadrac.co.jp

We are looking for an outstanding candidate with a research focus on cryptography. The position is open for all aspects of cryptography ranging from the design and analysis of cryptographic primitives/protocols to application and implementation aspects. We offer an interesting research environment, research questions with practical relevance, and integration in a motivated team of researchers and developers.

To increase the proportion of female academic personnel in the position of professor at Graz University of Technology, the Faculty of Computer Science and Biomedical Engineering is seeking to fill a tenure track professorship for the field of Cryptography for women.

The position, is initially restricted to six years as a University Assistant with Doctorate, 40 hours per week and the successful candidate is expected to start on 01.04.2019, at the Institute of Applied Information Processing and Communications.

Upon agreement on a qualification agreement, the candidate will be appointed as assistant professor. As soon as the qualification agreement has been fulfilled, the position will be converted into a tenured position as associate professor.

Closing date for applications: 3 December 2018

Contact: Stefan Mangard, Email: Stefan.Mangard (at) iaik.tugraz.at

More information: https://www.tugraz.at/fakultaeten/infbio/news/vacancies/tenure-track-professor-in-cryptography-women-only/

We present (linkable) Raptor, the first lattice-based (link- able) ring signature that is practical. Our scheme is as fast as classical solutions; while the size of the signature is roughly 1.3 KB per user. Our designs are based on a completely new generic construction that is provable secure in random oracle model. Prior to our work, all existing lattice-based solutions are analogues of their discrete-log or pairing-based counterparts. We give instantiations to both standard lattice setting, as a proof of concept, and NTRU lattice, as an efficient instantiation. Our main building block is a so called Chameleon Hash Plus (CH+) function, which may be of independent research interest.

The Blockwise-Korkine-Zolotarev (BKZ) lattice reduction algorithm is central in cryptanalysis, in particular for lattice-based cryptography. A precise understanding of its practical behavior in terms of run-time and output quality is necessary for parameter selection in cryptographic design. As the provable worst-case bounds poorly reflect the practical behavior, cryptanalysts rely instead on the heuristic BKZ simulator of Chen and Nguyen (Asiacrypt'11). It fits better with practical experiments, but not entirely. In particular, it over-estimates the norm of the first few vectors in the output basis. Put differently, BKZ performs better than its Chen-Nguyen simulation.

In this work, we first report experiments providing more insight on this shorter-than-expected phenomenon. We then propose a refined BKZ simulator by taking the distribution of short vectors in random lattices into consideration. We report experiments suggesting that this refined simulator more accurately predicts the concrete behavior of BKZ. Furthermore, we design a new BKZ variant that exploits the shorter-than-expected phenomenon. For the same cost assigned to the underlying SVP-solver, the new BKZ variant produces bases of better quality. We further illustrate its potential impact by testing it on the SVP-120 instance of the Darmstadt lattice challenge.

The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital signature scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures is significantly faster than for DSA or ECDSA. Despite the huge practical importance of RSA PKCS#1 v1.5 signatures, providing formal evidence for their security based on plausible cryptographic hardness assumptions has turned out to be very difficult. Therefore the most recent version of PKCS#1 (RFC 8017) even recommends a replacement the more complex and less efficient scheme RSA-PSS, as it is provably secure and therefore considered more robust. The main obstacle is that RSA PKCS#1 v1.5 signatures use a deterministic padding scheme, which makes standard proof techniques not applicable.

We introduce a new technique that enables the first security proof for RSA-PKCS#1 v1.5 signatures. We prove full existential unforgeability against adaptive chosen-message attacks (EUF-CMA) under the standard RSA assumption. Furthermore, we give a tight proof under the Phi-Hiding assumption. These proofs are in the random oracle model and the parameters deviate slightly from the standard use, because we require a larger output length of the hash function. However, we also show how RSA-PKCS#1 v1.5 signatures can be instantiated in practice such that our security proofs apply.

In order to draw a more complete picture of the precise security of RSA PKCS#1 v1.5 signatures, we also give security proofs in the standard model, but with respect to weaker attacker models (key-only attacks) and based on known complexity assumptions. The main conclusion of our work is that from a provable security perspective RSA PKCS#1 v1.5 can be safely used, if the output length of the hash function is chosen appropriately.