International Association
for Cryptologic Research

Event date: 25 August to 28 August 2019

Event date: 2 October to 4 October 2019
Submission deadline: 4 May 2019
Notification: 22 June 2019

Event date: 27 May to 29 May 2019

Anonymous credential (AC) schemes are protocols which allow for authentication of authorized users without compromising their privacy. Of particular interest are non-interactive anonymous credential (NIAC) schemes, where the authentication process only requires the user to send a single message that still conceals its identity. Unfortunately, all known NIAC schemes in the standard model require pairing based cryptography, which limits them to a restricted set of specific assumptions and requires expensive pairing computations. The notion of keyed-verification anonymous credential (KVAC) was introduced in (Chase et al., CCS'14) as an alternative to standard anonymous credential schemes allowing for more efficient instantiations; yet, making existing KVAC non-interactive either requires pairing-based cryptography, or the Fiat-Shamir heuristic.

In this work, we construct the first non-interactive keyed-verification anonymous credential (NIKVAC) system in the standard model, without pairings. Our scheme is efficient, attribute-based, supports multi-show unlinkability, and anonymity revocation. We achieve this by building upon a combination of algebraic \MAC with the recent designated-verifier non-interactive zero-knowledge (DVNIZK) proof of knowledge of (Couteau and Chaidos, Eurocrypt'18). Toward our goal of building NIKVAC, we revisit the security analysis of a MAC scheme introduced in (Chase et al., CCS'14), strengthening its guarantees, and we introduce the notion of oblivious non-interactive zero-knowledge proof system, where the prover can generate non-interactive proofs for statements that he cannot check by himself, having only a part of the corresponding witness, and where the proof can be checked efficiently given the missing part of the witness. We provide an efficient construction of an oblivious DVNIZK, building upon the specific properties of the DVNIZK proof system of (Couteau and Chaidos, Eurocrypt'18).

In this paper, we propose a Multi-Key Homomorphic Encryption (MKHE) which allows homomorphic evaluation of a binary gate (with bootstrapping) on ciphertexts encrypted under different keys. We generalize a low-latency homomorphic encryption scheme of Chillotti et al. (ASIACRYPT 2016) by exploiting a key-extension approach of Brakerski and Perlman (CRYPTO 2016).

All the prior works on MKHE were too inefficient to be used in practice. Our construction improved the performance in terms of both asymptotic and concrete complexity: the length of ciphertexts and the computational costs of a binary gate grow linearly and quadratically on the number of parties, respectively. Furthermore, our scheme is fully-dynamic so that no information about the involved parties needs to be known before the computation and the resulting ciphertext can be reused in further computation with newly joined parties.

To the best of our knowledge, this is the first work to implement an MKHE scheme. Our implementation takes about 0.15 (resp. 0.72) seconds to perform the gate bootstrapping when the number of involved parties is 2 (resp. 4).

Distributional collision resistance is a relaxation of collision resistance that only requires that it is hard to sample a collision (x,y) where x is uniformly random and y is uniformly random conditioned on colliding with x. The notion lies between one-wayness and collision resistance, but its exact power is still not well-understood. On one hand, distributional collision resistant hash functions cannot be built from one-way functions in a black-box way, which may suggest that they are stronger. On the other hand, so far, they have not yielded any applications beyond one-way functions.

Assuming distributional collision resistant hash functions, we construct constant-round statistically hiding commitment scheme. Such commitments are not known based on one-way functions and are impossible to obtain from one-way functions in a black-box way. Our construction relies on the reduction from inaccessible entropy generators to statistically hiding commitments by Haitner et al. (STOC '09). In the converse direction, we show that two-message statistically hiding commitments imply distributional collision resistance, thereby establishing a loose equivalence between the two notions.

A corollary of the first result is that constant-round statistically hiding commitments are implied by average-case hardness in the class SZK (which is known to imply distributional collision resistance). This implication seems to be folklore, but to the best of our knowledge has not been proven explicitly. We provide yet another proof of this implication, which is arguably more direct than the one going through distributional collision resistance.

A threshold signature scheme enables distributed signing among $n$ players such that any subgroup of size $t+1$ can sign, whereas any group with $t$ or fewer players cannot. While there exist previous threshold schemes for the ECDSA signature scheme, we present the first protocol that supports multiparty signatures for any $t \leq n$ with efficient, dealerless key generation. Our protocol is faster than previous solutions and significantly reduces the communication complexity as well. We prove our scheme secure against malicious adversaries with a dishonest majority. We implemented our protocol, demonstrating its efficiency and suitability to be deployed in practice.

Privacy and mutual authentication under corruption with temporary state disclosure are two significant requirements for real-life applications of RFID schemes. No RFID scheme is known so far to meet these two requirements. In this paper we propose two practical RFID schemes that fill this gap. The first one achieves destructive privacy, while the second one narrow destructive privacy, in Vaudenay's model with temporary state disclosure. Both of them provide mutual (reader-first) authentication. In order to achieve these privacy levels we use Physically Unclonable Functions (PUFs) to assure that the internal secret of the tag remains hidden against an adversary with invasive capabilities. Our first RFID scheme cannot be desynchronized for more than one step, while the second one avoids the use of random generators on tags. Detailed security and privacy proofs are provided.

Techniques for eliminating variables from a system of nonlinear equations are used to find solutions of the system. We discuss how these methods can be used to attack certain types of symmetric block ciphers, by solving sets of equations arising from known plain text attacks. The systems of equations corresponding to these block ciphers have the characteristics that the solution is determined by a small subset of the variables (i.e., the secret key), and also that it is known that there always exists at least one solution (again corresponding to the key which is actually used in the encryption). It turns out that some toy ciphers can be solved simpler than anticipated by this method, and that the method can take advantage of overdetermined systems.

In this paper, we continue the study of bit-parallel multiplier using a $n$-term Karatsuba algorithm (KA), recently introduced by Li et al. (IEEE Access 2018). Such a $n$-term KA is a generalization of the classic KA, which can multiply two $n$-term polynomials using $O(n^2/2)$ scalar multiplications. Based on this observation, Li et al. developed an efficient bit-parallel multiplier scheme for a new special class of irreducible trinomial $x^{m}+x^{k}+1, m=nk$. The lower bound of the space complexity of their proposal is about $O(\frac{m^2}{2}+m^{3/2})$. However, such a special type of trinomial does not always exist. In this contribution, we investigate the space and time complexity of Karatsuba multiplier for general trinomials, i.e., $x^m+x^k+1$ where $m>2k$. We use a new decomposition that $m=n\ell+r$, where $r<n, r<\ell$. Combined with shifted polynomial basis (SPB), a new approach other than Mastrovito approach is proposed to exploit the spatial correlation between different subexpressions. Explicit space and time complexity formulations are given to indicate the optimal choice of the decomposition. As a result, the optimal multiplier achieves nearly the same space complexity as $x^{m}+x^{k}+1, m=nk$, but it is suitable to more general trinomials. Meanwhile, its time complexity matches or is at most $1T_X$ higher than the similar KA multipliers, where $T_X$ is the delay of one 2-input XOR gate.

In this paper, we present an efficient method to compute arbitrary odd-degree isogenies on Edwards curves. By using the $w$-coordinate, we optimized the isogeny formula on Edwards curves by Moody \textit{et al}.. The state-of-the-art implementation of isogeny-based cryptosystems works entirely with Montgomery curves since they provide efficient isogeny computation and elliptic curve arithmetic. However, we demonstrated that the same computational costs of elliptic curve arithmetic and isogeny evaluation could be achieved by using the $w$-coordinate on Edwards curves, with additional benefit when computing isogenous curves. For $\ell$-degree isogeny where $\ell=2s+1$, our isogeny formula on Edwards curves outperforms Montgomery curves when $s \geq 2$. The result of our work opens the door for the usage of Edwards curves in isogeny-based cryptography, especially in CSIDH which requires higher degree isogenies.

In this paper, we present an optimized FPGA implementation of a novel, fast and highly parallelized NTT-based polynomial multiplier architecture, which proves to be effective as an accelerator for lattice-based homomorphic cryptographic schemes. As input-output (I/O) operations are as time-consuming as NTT operations during homomorphic computations in a host processor/accelerator setting, instead of achieving the fastest NTT implementation possible on the target FPGA, we focus on a balanced time performance between the NTT and I/O operations. Even with this goal, we achieved the fastest NTT implementation in literature, to the best of our knowledge. For proof of concept, we utilize our architecture in a framework for Fan-Vercauteren (FV) homomorphic encryption scheme, utilizing a hardware/software co-design approach, in which NTT operations are offloaded to the accelerator while the rest of operations in the FV scheme are executed in software running on an off-the-shelf desktop computer. Specifically, our framework is optimized to accelerate Simple Encrypted Arithmetic Library (SEAL), developed by the Cryptography Research Group at Microsoft Research, for the FV encryption scheme, where forward and inverse NTT operations are utilized extensively for large degree polynomial multiplications. The hardware part of the proposed framework targets XILINX VIRTEX-7 FPGA device, which communicates with its software part via a PCIe connection. Offloading forward/inverse NTT and coefficient multiplication operations on FPGA, taking into account the time expended on I/O operations, the proposed framework achieves almost x11 latency speedup for the offloaded operations compared to their pure software implementations. With careful pipelining, overlapping I/O operations with actual polynomial multiplication computations, and assuming one of the operands for the polynomial multiplication operation is already inside the FPGA (valid assumption for encrypt/decrypt operations for homomorphic applications), we achieved a throughput of almost 800k polynomial multiplications per second, for polynomials of degree 1024 with 32-bit coefficients.

Algebraic structure lies at the heart of much of Cryptomania as we know it. An interesting question is the following: instead of building (Cryptomania) primitives from concrete assumptions, can we build them from simple Minicrypt primitives endowed with additional algebraic structure? In this work, we affirmatively answer this question by adding algebraic structure to the following Minicrypt primitives:

• One-Way Function (OWF) • Weak Unpredictable Function (wUF) • Weak Pseudorandom Function (wPRF)

The algebraic structure that we consider is group homomorphism over the input/output spaces of these primitives. We also consider a “bounded” notion of homomorphism where the primitive only supports an a priori bounded number of homomorphic operations in order to capture lattice-based and other “noisy” assumptions. We show that these structured primitives can be used to construct many cryptographic protocols. In particular, we prove that:

• (Bounded) Homomorphic OWFs (HOWFs) imply collision-resistant hash functions, Schnorr-style signatures, and chameleon hash functions. • (Bounded) Input-Homomorphic weak UFs (IHwUFs) imply CPA-secure PKE, non-interactive key exchange, trapdoor functions, blind batch encryption (which implies anonymous IBE, KDM-secure and leakage-resilient PKE), CCA2 deterministic PKE, and hinting PRGs (which in turn imply transformation of CPA to CCA security for ABE/1-sided PE). • (Bounded) Input-Homomorphic weak PRFs (IHwPRFs) imply PIR, lossy trapdoor functions, OT and MPC (in the plain model).

In addition, we show how to realize any CDH/DDH-based protocol with certain properties in a generic manner using IHwUFs/IHwPRFs, and how to instantiate such a protocol from many concrete assumptions. We also consider primitives with substantially richer structure, namely Ring IHwPRFs and L-composable IHwPRFs. In particular, we show the following:

• Ring IHwPRFs with certain properties imply FHE. • 2-composable IHwPRFs imply (black-box) IBE, and $L$-composable IHwPRFs imply non-interactive $(L + 1)$-party key exchange.

Our framework allows us to categorize many cryptographic protocols based on which structured Minicrypt primitive implies them. In addition, it potentially makes showing the existence of many cryptosystems from novel assumptions substantially easier in the future.

MDS matrices are important building blocks providing diffusion functionality for the design of many symmetric-key primitives. In recent years, continuous efforts are made on the construction of MDS matrices with small area footprints in the context of lightweight cryptography. Just recently, Duval and Leurent (ToSC 2018/FSE 2019) reported some $32 \times 32$ binary MDS matrices with branch number 5, which can be implemented with only 67 XOR gates, whereas the previously known lightest ones of the same size cost 72 XOR gates. In this article, we focus on the construction of lightweight {\it involutory} MDS matrices, which are even more desirable than ordinary MDS matrices, since the same circuit can be reused when the inverse is required. In particular, we identify some involutory MDS matrices which can be realized with only 78 XOR gates with depth 4, whereas the previously known lightest involutory MDS matrices cost 84 XOR gates with the same depth. Notably, the involutory MDS matrix we find is much smaller than the AES MixColumns operation, which requires 97 XOR gates with depth 8 when implemented as a block of combinatorial logic that can be computed in one clock cycle. However, with respect to latency, the AES MixColumns operation is superior to our 78-XOR involutory matrices, since the AES MixColumns can be implemented with depth 3 by using more XOR gates. We prove that the depth of a $32\times 32$ MDS matrix with branch number 5 ({e.g.}, the AES MixColumns operation) is at least 3. Then, we enhance Boyar's SLP-heuristic algorithm with circuit depth awareness, such that the depth of its output circuit is limited. Along the way, we give a formula for computing the minimum achievable depth of a circuit implementing the summation of a set of signals with given depths, which is of independent interest. We apply the new SLP heuristic to a large set of lightweight involutory MDS matrices, and we identify a depth 3 involutory MDS matrix whose implementation costs 88 \XOR gates, which is superior to the AES MixColumns operation with respect to both lightweightness and latency, and enjoys the extra involution property.

After two decades of research on signcryption, recently a new cryptographic primitive, named higncryption, was proposed at ACM CCS'16. Higncryption can be viewed as privacy-enhanced signcryption, which integrates public key encryption, digital signature and identity concealment (which is not achieved in signcryption) into a monolithic primitive. Here, identity concealment means that the transcript of protocol run should not leak participants' identity information.

In this work, we propose the first identity-based higncryption(IBHigncryption, for short). We present formal security model for IBHigncryption, under which security proof of the proposed scheme is conducted. The most impressive feature of IBHigncryption, besides other desirable properties it offers, is its simplicity and efficiency, which might be somewhat surprising in retrospect. Our IBHigncryption has a much simpler setup stage with smaller public parameters and particularly no need of computing master public key. It is essentially as efficient as (if not more than) the fundamental CCA-secure Boneh-Franklin identity-based encryption scheme, and has significant efficiency advantage over the IEEE 1363.3 standard of identity-based signcryption.

We revisit the concept of *non-malleable* secret sharing (Goyal and Kumar, STOC 2018) in the computational setting. In particular, under the assumption of one-to-one one-way functions, we exhibit a *computationally* private, *threshold* secret sharing scheme satisfying all of the following properties.

-) Continuous non-malleability: No computationally-bounded adversary tampering independently with all the shares can produce mauled shares that reconstruct to a value related to the original secret. This holds even in case the adversary can tamper *continuously*, for an *unbounded* polynomial number of times, with the same target secret sharing, where the next sequence of tampering functions, as well as the subset of shares used for reconstruction, can be chosen *adaptively* based on the outcome of previous reconstructions. -) Resilience to noisy leakage: Non-malleability holds even if the adversary can additionally leak information independently from all the shares. There is no bound on the length of leaked information, as long as the overall leakage does not decrease the min-entropy of each share by too much. -) Improved rate: The information rate of our final scheme, defined as the ratio between the size of the message and the maximal size of a share, asymptotically approaches 1 when the message length goes to infinity.

Previous constructions achieved information-theoretic security, sometimes even for arbitrary access structures, at the price of *at least one* of the following limitations: (i) Non-malleability only holds against one-time tampering attacks; (ii) Non-malleability holds against a bounded number of tampering attacks, but both the choice of the tampering functions and of the sets used for reconstruction is non-adaptive; (iii) Information rate asymptotically approaching zero; (iv) No security guarantee in the presence of leakage.

Migration of security applications to the cloud poses unique challenges in key management and protection: asymmetric keys which would previously have resided in tamper-resistant, on-premise Hardware Security Modules (HSM) now must either continue to reside in non-cloud HSMs (with attendant communication and integration issues) or must be removed from HSMs and exposed to cloud-based threats beyond an organization's control, e.g. accidental loss, warranted seizure, theft etc.

Threshold schemes offer a halfway house between traditional HSM-based key protection and native cloud-based usage. Threshold signature schemes allow a set of actors to share a common public key, generate fragments of the private key and to collaboratively sign messages, such that as long as a sufficient quorum of actors sign a message, the partial signatures can be combined into a valid signature.

However, threshold schemes, while being a mature idea, suffer from large protocol transcripts and complex communication-based requirements. This consequently makes it a more difficult task for a user to verify that a public key is, in fact, a genuine product of the protocol and that the protocol has been executed validly. In this work, we propose a solution to these auditability and verication problems, reporting on a prototype cloud-based implementation of a threshold RSA key generation and signing system tightly integrated with modern distributed ledger and consensus techniques.

Event date: 4 June to 6 June 2019
Submission deadline: 15 February 2019
Notification: 15 March 2019

We introduce models of computation that enable direct comparisons between classical and quantum algorithms. Incorporating previous work on quantum computation and error correction, we justify the use of the gate-count and depth-times-width cost metrics for quantum circuits. We demonstrate the relevance of these models to cryptanalysis by revisiting, and increasing, the security estimates for the Supersingular Isogeny Diffie--Hellman (SIDH) and Supersingular Isogeny Key Encapsulation (SIKE) schemes. Our models, analyses, and physical justifications have applications to a number of memory intensive quantum algorithms.

The Security & Privacy group at TU Wien (https://secpriv.tuwien.ac.at) in Vienna, Austria, is currently looking for outstanding PhD students in the area of applied security. The successful applicant should have recently completed (or is close to complete) a Master or Bachelor with Honors degree, and should have a strong background and interest in at least one of the following areas:

• systems security and privacy

• distributed systems

• malware and mobile app analysis

Research topics may cover (but are not limited to):

• detection and prevention of novel attacks against smartphones and users’ privacy

• large-scale static and dynamic analysis of mobile apps

For our previous research in this area see https://martina.lindorfer.in.

The employment is a full-time position (40 hrs/week) with an internationally competitive salary. The working language is English, knowledge of German is not required.

Interested candidates should provide:

• a motivation letter

• a transcript of records

• a curriculum vitae

• a publication list (if applicable)

• contact information for two referees

TU Wien offers an outstanding research environment and numerous professional development opportunities. The Faculty of Informatics is the largest of its kind in Austria and is consistently ranked among the best in Europe. The city of Vienna features a vibrant and excellence-driven research landscape. The candidate will have the opportunity to collaborate with several other leading research institutes (e.g., IST, AIT, SBA Research, ABC). Finally, Vienna has been consistently ranked by Mercer over the last years as the best city for quality of life worldwide.

Review of expressions of interest will start immediately and continue until the position is filled.

Closing date for applications: 31 March 2019

Contact: Martina Lindorfer (martina.lindorfer (at) tuwien.ac.at)

More information: https://secpriv.tuwien.ac.at/thesis_and_job_opportunities