International Association
for Cryptologic Research

We construct a succinct non-interactive publicly-verifiable delegation scheme for any log-space uniform circuit under the sub-exponential Learning With Errors ($\mathsf{LWE}$) assumption. For a circuit $C:\{0,1\}^N\rightarrow\{0,1\}$ of size $S$ and depth $D$, the prover runs in time $\mathsf{poly}(S)$, the communication complexity is $D \cdot \mathsf{polylog} (S)$, and the verifier runs in time $(D+N) \cdot \mathsf{polylog} (S)$.

To obtain this result, we introduce a new cryptographic primitive: lossy correlation-intractable hash functions. We use this primitive to soundly instantiate the Fiat-Shamir transform for a large class of interactive proofs, including the interactive sum-check protocol and the $\mathsf{GKR}$ protocol, assuming the sub-exponential hardness of $\mathsf{LWE}$.

By relying on the result of Choudhuri et al. (STOC 2019), we also establish the sub-exponential average-case hardness of $\mathsf{PPAD}$, assuming the sub-exponential hardness of $\mathsf{LWE}$.

Mercurial signatures are a useful building block for privacy-preserving schemes, such as anonymous credentials, delegatable anonymous credentials, and related applications. They allow a signature $\sigma$ on a message $m$ under a public key $\mathsf{pk}$ to be transformed into a signature $\sigma'$ on an equivalent message $m'$ under an equivalent public key $\mathsf{pk}'$ for an appropriate notion of equivalence. For example, $\mathsf{pk}$ and $\mathsf{pk}'$ may be unlinkable pseudonyms of the same user, and $m$ and $m'$ may be unlinkable pseudonyms of a user to whom some capability is delegated.

The only previously known construction of mercurial signatures suffers a severe limitation: in order to sign messages of length $n$, the signer's public key must also be of length $n$. In this paper, we eliminate this restriction and provide a signing protocol that admits messages of any length. This significantly improves the applicability of mercurial signatures to chains of anonymous credentials.

We propose a new cryptanalytic technique and key recovery attack for the Sparx cipher, Partly-Pseudo-Linear Cryptanalysis, a meet-in-the-middle attack combining linear and pseudo-linear approximations. We observe improvements over the linear hull attacks in the literature for Sparx 128/128 and 128/256. Additionally, we generate another attack for comparison purposes, using the Cho-Pieprzyk property for a fully-linear approximation and a corresponding key recovery attack. We observe improvements on the data complexity, bias, and number of recovered key bits, over all variants of Sparx, when compared to the use of only the Cho-Pieprzyk approximation.

The deep learning-based side-channel analysis represents a powerful and easy to deploy option for profiled side-channel attacks. A detailed tuning phase is often required to reach a good performance where one first needs to select relevant hyperparameters and then tune them. A common selection for the tuning phase are hyperparameters connected with the neural network architecture, while those influencing the training process are less explored. In this work, we concentrate on the optimizer hyperparameter, and we show that this hyperparameter has a significant role in the attack performance. Our results show that common choices of optimizers (Adam and RMSprop) indeed work well, but they easily overfit, which means that we must use short training phases, small profiled models, and explicit regularization. On the other hand, SGD type of optimizers works well on average (slower convergence and less overfit), but only if momentum is used. Finally, our results show that Adagrad represents a strong option to use in scenarios with longer training phases or larger profiled models.

Fitzi, Garay, Maurer, and Ostrovsky (Journal of Cryptology 2005) showed that in the presence of a dishonest majority, no primitive of cardinality $n - 1$ is complete for realizing an arbitrary $n$-party functionality with guaranteed output delivery. In this work, we introduce a new $2$-party primitive $\mathcal{F}_{\mathsf{SyX}}$ (``synchronizable fair exchange'') and show that it is complete for realizing any $n$-party functionality with fairness in a setting where all $n$ parties are pairwise connected by independent instances of $\mathcal{F}_{\mathsf{SyX}}$.

In the $\mathcal{F}_{\mathsf{SyX}}$-hybrid model, the two parties load $\mathcal{F}_{\mathsf{SyX}}$ with some input, and following this, either party can trigger $\mathcal{F}_{\mathsf{SyX}}$ with a suitable ``witness'' at a later time to receive the output from $\mathcal{F}_{\mathsf{SyX}}$. Crucially the other party also receives output from $\mathcal{F}_{\mathsf{SyX}}$ when $\mathcal{F}_{\mathsf{SyX}}$ is triggered. The trigger witnesses allow us to synchronize the trigger phases of multiple instances of $\mathcal{F}_{\mathsf{SyX}}$, thereby aiding in the design of fair multiparty protocols. Additionally, a pair of parties may reuse a single a priori loaded instance of $\mathcal{F}_{\mathsf{SyX}}$ in any number of multiparty protocols (possibly involving different sets of parties).

We design Aardvark, a novel authenticated dictionary backed by vector commitments with short proofs. Aardvark guarantees the integrity of outsourced data by providing proofs for lookups and modifications, even when the servers storing the data are untrusted. To support high-throughput, highly-parallel applications, Aardvark includes a versioning mechanism that allows the dictionary to accept stale proofs for a limited time.

We apply Aardvark to the problem of decoupling storage from transaction verification in cryptocurrencies. Here networking resources are at a premium and transmission of long proofs can easily become the dominant cost, with multiple users reading and writing concurrently.

We implement Aardvark and evaluate it as a standalone authenticated dictionary. We show that Aardvark saves substantial storage resources while incurring limited extra bandwidth and processing costs.

Modern public key encryption relies on various hardness assumptions for its security. Hardness assumptions may cause security uncertainty, for instance, when a hardness problem is no longer hard or the best solution to a hard problem might not be publicly released.

In this paper, we propose a public key encryption scheme Compact-LWE-MQ^{H} to demonstrate the feasibility of designing public key encryption without relying on hardness assumptions. Instead, its security is based on problems that are called factually hard.The two factually hard problems we proposed in this work are stratified system of linear and quadratic equations, and learning with relatively big errors. Such factually hard problems have the structures to ensure that they can only be solved by exhaustively searching their solution spaces, even when the problem size is very small.

Based on the structure of factually hard problems, we prove that without brute-force search the adversary cannot recover plaintexts or private key components, and then discuss CPA-security and CCA-security of Compact-LWE-MQ^{H}. We have implemented Compact-LWE-MQ^{H} in SageMath. In a configuration for 128-bit security level, the public key has 3708 bytes and a ciphertext is around 574 bytes.

Secure two party computation (2PC) of arbitrary programs can be efficiently achieved using garbled circuits (GC). The bottleneck of GC efficiency is communication. It is widely believed that it is necessary to transmit the entire GC during 2PC, even for conditional branches that are not taken.

This folklore belief is false.

We propose a novel GC technique, stacked garbling, that eliminates the communication cost of inactive conditional branches. We extend the ideas of conditional GC evaluation explored in (Kolesnikov, Asiacrypt 18) and (Heath and Kolesnikov, Eurocrypt 20). Unlike these works, ours is for general 2PC where no player knows which conditional branch is taken.

Our garbling scheme, Stack, requires communication proportional to the longest execution path rather than to the entire circuit. Stack is compatible with state-of-the-art techniques, such as free XOR and half-gates.

Stack is a garbling scheme. As such, it can be plugged into a variety of existing protocols, and the resulting round complexity is the same as that of standard GC. The approach does incur computation cost quadratic in the conditional branching factor vs linear in standard schemes, but the tradeoff is beneficial for most programs: GC computation even on weak hardware is faster than GC transmission on fast channels.

We implemented Stack in C++. Stack reduces communication cost by approximately the branching factor: for 16 branches, communication is reduced by 10.5x. In terms of wall-clock time for circuits with branching factor 16 over a 50 Mbps WAN on a laptop, Stack outperforms state-of- the-art half-gates-based 2PC by more than 4x.

In this short note, we describe a practical optimization of the well-known extended binary GCD algorithm, for the purpose of computing modular inverses. The method is conceptually simple and is applicable to all odd moduli (including non-prime moduli). When implemented for inversion in the field of integers modulo the prime $2^{255}-19$, on a recent x86 CPU (Coffee Lake core), we compute the inverse in 7490 cycles, with a fully constant-time implementation.

Post-quantum schemes are expected to replace existing public-key schemes within a decade in billions of devices. To facilitate the transition, the US National Institute for Standards and Technology (NIST) is running a standardization process. Multivariate signatures is one of the main categories in NIST's post-quantum cryptography competition. Among the four candidates in this category, the LUOV and Rainbow schemes are based on the Oil and Vinegar scheme, first introduced in 1997 which has withstood over two decades of cryptanalysis. Beyond mathematical security and efficiency, security against side-channel attacks is a major concern in the competition. The current sentiment is that post-quantum schemes may be more resistant to fault-injection attacks due to their large key sizes and the lack of algebraic structure. We show that this is not true.

We introduce a novel hybrid attack, QuantumHammer, and demonstrate it on the constant-time implementation of LUOV currently in Round 2 of the NIST post-quantum competition. The QuantumHammer attack is a combination of two attacks, a bit-tracing attack enabled via Rowhammer fault injection and a divide and conquer attack that uses bit-tracing as an oracle. Using bit-tracing, an attacker with access to faulty signatures collected using Rowhammer attack, can recover secret key bits albeit slowly. We employ a divide and conquer attack which exploits the structure in the key generation part of LUOV and solves the system of equations for the secret key more efficiently with few key bits recovered via bit-tracing.

We have demonstrated the first successful in-the-wild attack on LUOV recovering all 11K key bits with less than 4 hours of an active Rowhammer attack. The post-processing part is highly parallel and thus can be trivially sped up using modest resources. QuantumHammer does not make any unrealistic assumptions, only requires software co-location (no physical access), and therefore can be used to target shared cloud servers or in other sandboxed environments.

An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function $f(x) = ax + b$, where a sender inputs the field elements $a,b$, and a receiver inputs $x$ and learns $f(x)$. OLE can be used to build secret-shared multiplication, and is an essential component of many secure computation applications including general-purpose multi-party computation, private set intersection and more.

In this work, we present several efficient OLE protocols from the ring learning with errors (RLWE) assumption. Technically, we build two new passively secure protocols, which build upon recent advances in homomorphic secret sharing from (R)LWE (Boyle et al., Eurocrypt 2019), with optimizations tailored to the setting of OLE. We upgrade these to active security using efficient amortized zero-knowledge techniques for lattice relations (Baum et al., Crypto 2018), and design new variants of zero-knowledge arguments that are necessary for some of our constructions.

Our protocols offer several advantages over existing constructions. Firstly, they have the lowest communication complexity amongst previous, practical protocols from RLWE and other assumptions; secondly, they are conceptually very simple, and have just one round of interaction for the case of OLE where $b$ is randomly chosen. We demonstrate this with an implementation of one of our passively secure protocols, which can perform more than 1 million OLEs per second over the ring $\mathbb{Z}_m$, for a 120-bit modulus $m$, on standard hardware.

Let $\mathbb{F}_{\!p}$ be a prime finite field ($p > 5$) and $E_b\!: y_0^2 = x_0^3 + b$ be an elliptic $\mathbb{F}_{\!p}$-curve of $j$-invariant $0$. In this article we produce the simplified SWU hashing to curves $E_b$ having an $\mathbb{F}_{\!p^2}$-isogeny of degree $5$. This condition is fulfilled for some Barreto--Naehrig curves, including BN512 from the standard ISO/IEC 15946-5. Moreover, we show how to implement the simplified SWU hashing in constant time (for any $j$-invariant), namely without quadratic residuosity tests and inversions in $\mathbb{F}_{\!p}$. Thus in addition to the protection against timing attacks, the new hashing $h\!: \mathbb{F}_{\!p} \to E_b(\mathbb{F}_{\!p})$ turns out to be much more efficient than the (universal) SWU hashing, which generally requires to perform $2$ quadratic residuosity tests.

Presenting a new technology to fit quantum-randomness into a lump of matter where the randomness is held through the molecular bonds of seeded macro-molecules, and reliably measured in two or more sufficiently exact duplicates, serving as a large reservoir for quantum-grade randomness to support cryptographic protocols.

We have (fully funded) multiple PhD positions in the areas of applied cryptography beginning from Fall 2021 (August 2021) or Spring 2021 (January 2021) at University of South Florida (USF). USF is a Rank-1 Research University (rank 31 of CS departments at US public universities per according Academic Analytics on Scholarly Research Index) and offers a competitive salary with an excellent working environment, all within close proximity of high-tech industry and beautiful beaches of Sunny Florida. Tampa/Orlando area is a key part of the Florida High Technology Corridor and harbors major tech and research companies. The qualified candidate will have opportunities for research internship and joint-projects with lead-industrial companies. Topics include:

Trustworthy and Scalable Blockchains

• New cryptographic schemes for consensus and distributed transactions in Blockchains
• Practical quantum-safe cryptographic deployments for Blockchains

Secure and Reliable Internet of Things and Systems (IoT)

• Lightweight cryptography for IoT
• Efficient cryptography for vehicular and unmanned aerial systems
• Efficient digital signatures

Privacy-Enhancing Technologies

• Searchable encryption, Oblivious RAM, and multi-party computation

Trustworthy Machine Learning (TML)

• Privacy-Preserving Machine Learning
• Adversarial Machine Learning

Requirements:

• A BS degree in ECE/CS with a high-GPA
• Very good programming skills (e.g., C, C++), familiarity with Linux
• MS degree in ECE/CS/Math is a big plus. Publications in security and privacy are highly desirable

Please send (by e-mail) to below contact information:

• Transcripts
• Curriculum vitae
• Three reference letters (send by referees)
• Research statement
• GRE and TOEFL

Closing date for applications:

Contact: Dr. Attila A. Yavuz
Email: attilaayavuz@usf.edu
Webpage : http://www.csee.usf.edu/~attilaayavuz/

More information: http://www.csee.usf.edu/~attilaayavuz/article/PositionDescrption_at_USF.pdf

The Cryptography and Privacy Engineering Group (ENCRYPTO) @Department of Computer Science @Technical University of Darmstadt offers a full position for a Postdoctoral Researcher in Cryptography & Privacy Engineering, available immediately and for initially up to 2.5 years.

Our mission is to demonstrate that privacy can be efficiently protected in real-world applications via cryptographic protocols.

TU Darmstadt is a top research university for IT security, cryptography and computer science in Europe. The position is based in the City of Science Darmstadt, which is very international, livable and well-connected in the Rhine-Main area around Frankfurt. Initially, no knowledge of German is necessary and TU Darmstadt offers corresponding support.

Job description

As postdoc @ENCRYPTO, you conduct research, build prototype implementations, and publish and present the results at top venues. You are involved in project management, teaching, co-advise PhD students and supervise thesis students & student research assistants. The position is co-funded by the ERC Starting Grant “Privacy-preserving Services on the Internet” (PSOTI), where we build privacy-preserving services on the Internet, which includes designing protocols for privately processing data among untrusted service providers using secure multi-party computation and implementing a scalable framework.

Your profile

• Completed PhD degree (or equivalent) at a top university in IT security, computer science, applied mathematics, electrical engineering, or a similar area
• Publications at top venues (CORE rank A*/A) for IT security/applied cryptography (e.g., S&P, CCS, NDSS, USENIX SEC, EUROCRYPT), ideally on cryptographic protocols and secure computation
• Experience in software development, project management and supervising students
• Self-motivated, reliable, creative, can work in a team, and want to do excellent research on challenging scientific problems with practical relevance
• The working language at ENCRYPTO is English, so you must be able to discuss/write/present scientific results in English, whereas German is not required.

Closing date for applications:

Contact: Thomas Schneider (schneider@encrypto.cs.tu-darmstadt.de)

More information: https://encrypto.de/POSTDOC

The Department of Computer Science and Engineering at National Sun Yat-sen University invites applications for tenure-track positions from February 2021 or August 2021. Applicants in areas of information security and artificial intelligence are sought. Applicants for assistant professorship must demonstrate strong research potential, in addition to good teaching ability. Applicants for associate professorship and professorship must have an exceptional record of research achievement. All successful candidates are expected to conduct both research and teaching activities. The department offers BS, MS and Ph. D. degrees in Computer Science and Engineering. The official language of teaching is Chinese, and English teaching is encouraged by the university. For more information, please visit our website: https://cse.nsysu.edu.tw/index.php?Lang=en Applications should include a curriculum vitae, recent publications, and reference letters from at least three people who can comment on the applicant's professional qualification. Other supporting material is welcome. Applications should be sent to: Faculty Recruiting Committee Department of Computer Science and Engineering National Sun Yat-sen University Kaohsiung, Taiwan 80424 Email:srkuang@cse.nsysu.edu.tw TEL:+886-7-5252000 ext. 4340 FAX:+886-7-5254301 The deadline for applications is October 31, 2020, and will continue to receive documents as appropriate until February 28, 2021.

Closing date for applications:

Contact: Email: srkuang@cse.nsysu.edu.tw TEL:+886-7-5252000 ext. 4340 FAX:+886-7-5254301

More information: https://cse.nsysu.edu.tw/index.php?Lang=en

Event date: 4 November to 6 November 2020
Submission deadline: 30 September 2020
Notification: 19 October 2020

Event date: 7 June to 11 June 2021
Submission deadline: 21 August 2020
Notification: 24 October 2020

Event date: 14 December to 16 December 2020
Submission deadline: 20 September 2020
Notification: 30 September 2020

The program chairs and the program committee of Crypto 2020 are pleased to announce the Best Paper and Best Paper by Early Career Researchers Awards to be presented at Crypto next week:

Best Paper Awards

• "Chosen Ciphertext Security from Injective Trapdoor Functions", by Susan Hohenberger, Venkata Koppula, and Brent Waters
• "Breaking the Decisional Diffie-Hellman Problem for Class Group Actions using Genus Theory", by Wouter Castryck, Jana Sotáková, and Frederik Vercauteren
• "Improved Differential-Linear Attacks with Applications to ARX Ciphers", by Christof Beierle, Gregor Leander, and Yosuke Todo

Best Paper by Early Career Researchers Award

• "Handling Adaptive Compromise for Practical Encryption Schemes", by Joseph Jaeger and Nirvan Tyagi

Congratulations to all authors!

The Best Paper Awards will be presented during a special session on Tuesday 18 Aug at 16:25 UTC, and the Best Paper by Early Career Researchers Award will be presented on Monday 17 Aug at 15:15 UTC.

To register and for more information about the Crypto 2020 technical program and attendance details, please visit: https://crypto.iacr.org/2020/