International Association
for Cryptologic Research

The complexity class TFNP consists of all NP search problems that are total in the sense that a solution is guaranteed to exist for all instances. Over the years, this class has proved to illuminate surprising connections among several diverse subfields of mathematics like combinatorics, computational topology, and algorithmic game theory. More recently, we are starting to better understand its interplay with cryptography. We know that certain cryptographic primitives (e.g. one-way permutations, collision-resistant hash functions, or indistinguishability obfuscation) imply average-case hardness in TFNP and its important subclasses. However, its relationship with the most basic cryptographic primitive. i.e., one-way functions (OWFs), still remains unresolved. Under an additional complexity theoretic assumption, OWFs imply hardness in TFNP (Hubacek, Naor, and Yogev, ITCS 2017). It is also known that average-case hardness in most structured subclasses of TFNP does not imply any form of cryptographic hardness in a black-box way (Rosen, Segev, and Shahaf, TCC 2017), and, thus, one-way functions might be sufficient. Specifically, no negative result which would rule out basing average-case hardness in TFNP solely on OWFs is currently known. In this work, we further explore the interplay between TFNP and OWFs and give the first negative results. As our main result, we show that there cannot exist constructions of average-case (and, in fact, even worst-case) hardness in TFNP from OWFs with a certain type of simple black-box security reductions. The class of reductions we rule out is, however, rich enough to capture many of the currently known cryptographic hardness results for TFNP. Our results are established using the framework of black-box separations (Impagliazzo and Rudich, STOC 1989) and involve a novel application of the reconstruction paradigm (Gennaro and Trevisan, FOCS 2000).

As blockchains grow in size, validating new transactions becomes more and more resource intensive. To deal with this, there is a need to discover compact encodings of the (effective) state of a blockchain -- an encoding that allows for efficient proofs of membership and updates. In the case of account-based cryptocurrencies, the state can be represented by a key-value map, where keys are the account addresses and values consist of account balance, nonce, etc.

We propose a new commitment scheme for key-value maps whose size does not grow with the number of keys, yet proofs of membership are of constant-size. In fact, both the encoding and the proofs consist of just two and three group elements respectively (in groups of unknown order like class groups). Verifying and updating proofs involves just a few group exponentiations. Additive updates to key values enjoy the same level of efficiency too.

Key-value commitments can be used to build dynamic accumulators and vector commitments, which find applications in group signatures, anonymous credentials, verifiable databases, interactive oracle proofs, etc. Using our new key-value commitment, we provide the most efficient constructions of (sub)vector commitments to date.

Randomness is typically thought to be essential for zero knowledge protocols. Following this intuition, Goldreich and Oren (Journal of Cryptology 94) proved that auxiliary-input zero knowledge cannot be achieved with a deterministic prover. On the other hand, positive results are only known in the honest-verifier setting, or when the prover is given at least a restricted source of entropy.

We prove that removing (or just bounding) the verifier's auxiliary input, deterministic-prover zero knowledge becomes feasible:

- Assuming non-interactive witness-indistinguishable proofs and subexponential indistinguishability obfuscation and one-way functions, we construct deterministic-prover zero-knowledge arguments for $\mathsf{NP}\cap \mathsf{coNP}$ against verifiers with bounded non-uniform auxiliary input.

- Assuming also keyless hash functions that are collision-resistant against bounded-auxiliary-input quasipolynomial-time attackers, we construct similar arguments for all of $\mathsf{NP}$.

Together with the result of Goldreich and Oren, this characterizes when deterministic-prover zero knowledge is feasible. We also demonstrate the necessity of strong assumptions, by showing that deterministic prover zero knowledge arguments for a given language imply witness encryption for that language. We further prove that such arguments can always be collapsed to two messages and be made laconic. These implications rely on a more general connection with the notion of predictable arguments by Faonio, Nielsen, and Venturi (PKC 17).

We present malleability attacks against encrypted binary executable files when they are encrypted by CBC mode of operation. While the CBC malleability is classic and has been used to attack on various real-world applications, the risk of encrypting binary executable via CBC mode on common OSs has not been widely recognized. We showed that, with a certain non-negligible probability, it is possible to manipulate the CBC-encrypted binary files so that the decryption result allows an arbitrary code execution (ACE), which is one of the most powerful exploits, even without the knowledge of plaintext binary. More specifically, for both 32- and 64-bit Linux and Windows OS, we performed a thorough analysis on the binary executable format to evaluate the practical impact of ACE on CBC encryption, and showed that the attack is possible if the adversary is able to correctly guess 13 to 25 bits of the address to inject code. In principle, our attack affects a wide range of storage/file encryption systems that adopt CBC encryption. In addition, a manual file encryption using OpenSSL API (AES-256-CBC) is affected, which is presumed to be frequently used in practice for file encryption. We provide Proof-of-Concept implementations for Linux and Windows. We have communicated our findings to the appropriate institution and have informed to vendors as an act of responsible disclosure.

We suggest a small change to the Dilithium signature scheme, that allows reusing computation between aborted attempts for a speed-up in signing time.

This work concerns secure protocols in the massively parallel computation (MPC) model, which is one of the most widely-accepted models for capturing the challenges of writing protocols for the types of parallel computing clusters which have become commonplace today (MapReduce, Hadoop, Spark, etc.). Recently, the work of Chan et al. (ITCS '20) initiated this study, giving a way to compile any MPC protocol into a secure one in the common random string model, achieving the standard secure multi-party computation definition of security with up to 1/3 of the parties being corrupt.

We are interested in achieving security for much more than 1/3 corruptions. To that end, we give two compilers for MPC protocols, which assume a simple public-key infrastructure, and achieve semi-honest security for all-but-one corruptions. Our first compiler assumes hardness of the learning-with-errors (LWE) problem, and works for any MPC protocol with ``short'' output---that is, where the output of the protocol can fit into the storage space of one machine, for instance protocols that output a trained machine learning model. Our second compiler works for any MPC protocol (even ones with a long output, such as sorting) but assumes, in addition to LWE, indistinguishability obfuscation and a circular secure variant of threshold FHE. Both protocols allow the attacker to choose corrupted parties based on the trusted setup, an improvement over Chan et al., whose protocol requires that the CRS is chosen independently of the attacker's choices.

A hierarchical key assignment scheme (HKAS) is a method to assign some private information and encryption keys to a set of classes in a partially ordered hierarchy, so that the private information of a higher class together with some public information can be used to derive the keys of all classes lower down in the hierarchy. Historically, HKAS have been introduced to enforce multi-level access control, where it can be safely assumed that the public information is made available in some authenticated form. Subsequently, HKAS have found application in several other contexts where, instead, it would be convenient to certify the trustworthiness of public information. Such application contexts include key management for IoT and for emerging distributed data acquisition systems such as wireless sensor networks. In this paper, motivated by the need of accommodating this additional security requirement, we first introduce a new cryptographic primitive: Verifiable Hierarchical Key Assignment Scheme (VHKAS). A VHKAS is a key assignment scheme with a verification procedure that allows honest users to verify whether public information has been maliciously modified so as to induce an honest user to obtain an incorrect key. Then, we design and analyse verifiable hierarchical key assignment schemes which are provably secure. Our solutions support key update for compromised encryption keys by making a limited number of changes to public and private information.

As cloud computing becomes more popular, research has focused on usable solutions to the problem of verifiable computation (VC), where a computationally weak device (Verifier) outsources a program execution to a powerful server (Prover) and receives guarantees that the execution was performed faithfully. A Prover can further demonstrate knowledge of a secret input that causes the Verifier’s program to satisfy certain assertions, without ever revealing which input was used. State-of-the-art Zero-Knowledge Proofs of Knowledge (ZKPK) methods encode a computation using arithmetic circuits and preserve the privacy of Prover’s inputs while attesting the integrity of program execution. Nevertheless, developing, debugging and optimizing programs as circuits remains a daunting task, as most users are unfamiliar with this programming paradigm.

In this work we present Zilch, a framework that accelerates and simplifies the deployment of VC and ZKPK for any application transparently, i.e., without the need of trusted setup. Zilch uses traditional instruction sequences rather than static arithmetic circuits that would need to be regenerated for each different computation. Towards that end we have implemented ZMIPS: a MIPS-like processor model that allows verifying each instruction independently and compose a proof for the execution of the target application. To foster usability, Zilch incorporates a novel cross-compiler from an object-oriented Java- like language tailored to ZKPK and optimized our ZMIPS model, as well as a powerful API that enables integration of ZKPK within existing C/C++ programs. In our experiments, we demonstrate the flexibility of Zilch using two real-life applications, and evaluate Prover and Verifier performance on a variety of benchmarks.

Functional encryption for set intersection (FE-SI) in the multi-client environment is that each client $i$ encrypts a set $X_i$ associated with time $T$ by using its own encryption key and uploads it to a cloud server, and then the cloud server which receives a function key of the client indexes $i, j$ from a trusted center can compute the intersection $X_i \cap X_j$ of the two client ciphertexts. In this paper, we first newly define the concept of FE-SI suitable for the multi-client setting. Then, we propose an efficient FE-SI scheme in asymmetric bilinear groups and prove the static security of our scheme under newly introduced assumptions. In our FE-SI scheme, a ciphertext consists of $O(\ell)$ group elements, a function key consists of a single group element, and the decryption algorithm has $O(\ell^2)$ complexity where $\ell$ is the size of a set in the ciphertext. Next, we propose another FE-SI scheme with time-constrained keys that limits the ability of function keys to be valid only for a specified time period $T$, and proves the static security of our scheme. Finally, we prove that the two assumptions hold in the general group model to provide confidence in the two newly introduced assumptions.

This note describes some methods for adding a key commitment property to a generic (nonce-based) AEAD scheme. We analyze the the privacy bounds and key commitment guarantee of the resulting constructions, by expressing them in terms of the properties of the underlying AEAD scheme and the added key commitment primitive. We also offer concrete constructions for a key committing version of AES-GCM.

The design and cryptanalysis are the both sides from which we look at symmetric-key primitives. If a symmetric-key primitive is broken by a kind of cryptanalysis, it's definitely insecure. If a designer claims a symmetric-key primitive to be secure, one should demonstrate that the primitive resists against all known attacks. Differential and linear cryptanalysis are two of the most important kinds of cryptanalysis. To conduct a successful differential (linear) cryptanalysis, a differential (linear) distinguisher with significant differential probability (linear correlation) is needed.

We observe that, for some lightweight symmetric-key primitives, their significant trails usually contain iterative trails. In this work, We propose an automatic tool for searching iterative trails. We model the problem of searching itrative trails as a problem of finding elementry ciucuits in a graph. Based on the iterative trails found, we further propose a method to estimate the probability (correlation) of a differential (linear hull).

We apply our methods to the 256-bit KNOT permutation, PRESENT, GIFT-64 and RECTANGLE. Iterative trails are found and visualized. If iterative trails are found, we show our method can efficiently find good differentials and linear hulls. What's more, the results imply that for the primitives we test with bit permutations as their linear layers, the good differentials and linear hulls are dominated by iterative trails.

Diffie-Hellman key exchange (DHKE) is a widely adopted method for exchanging cryptographic key material in realworld protocols like TLS-DH(E). Past attacks on TLS-DH(E) focused on weak parameter choices or missing parameter validation. The confidentiality of the computed DH share, the premaster secret, was never questioned; DHKE is used as a generic method to avoid the security pitfalls of TLS-RSA. We show that due to a subtle issue in the key derivation of all TLS-DH(E) cipher suites in versions up to TLS 1.2, the premaster secret of a TLS-DH(E) session may, under certain circumstances, be leaked to an adversary. Our main result is a novel side-channel attack, named Raccoon attack, which exploits a timing vulnerability in TLS-DH(E), leaking the most significant bits of the shared Diffie-Hellman secret. The root cause for this side channel is that the TLS standard encourages non-constant-time processing of the DH secret. If the server reuses ephemeral keys, this side channel may allow an attacker to recover the premaster secret by solving an instance of the Hidden Number Problem. The Raccoon attack takes advantage of uncommon DH modulus sizes, which depend on the properties of the used hash functions. We describe a fully feasible remote attack against an otherwisesecure TLS configuration: OpenSSL with a 1032-bit DH modulus. Fortunately, such moduli are not commonly used on the Internet. Furthermore, with our large-scale scans we have identified implementation-level issues in production-grade TLS implementations that allow for executing the same attack by directly observing the contents of server responses, without resorting to timing measurements.

In this work we show that an adversary can leverage blockchain technology to attack the integrity of contact tracing systems based on Google-Apple Exposure Notifications (GAEN). We design a suite of smart contracts named TEnK-U allowing an on-line market where infected individuals interested in monetizing their status will then upload to the servers of the GAEN-based systems some keys (i.e., TEKs) chosen by an adversary. As a consequence, there will be fake exposure notifications of at-risk contacts arbitrarily decided by the adversary and allowed by infected individuals looking for money.

Such vulnerability can be exploited to anonymously and digitally trade valuable contact tracing data without a mediator and without risks of being cheated. This makes infected individuals prone to get bribed by adversaries willing to compromise the integrity of the contact tracing system for any malicious purpose. For instance, large-scale attacks with catastrophic consequences (e.g., jeopardizing the health system, compromising the result of elections) are easy to mount and attacks to specific targets are completely straight-forward (e.g., schools, shops, hotels, factories).

We show as main contribution a smart contract with two collateral deposits that works, in general, on GAEN-based systems and concretely with Immuni and SwissCovid. In addition, we show smart contracts with one collateral deposit that work with SwissCovid. Finally, we also suggest the design of a more sophisticated smart contract that could potentially be used to attack GAEN-based system even in case those systems are repaired to make the previous attacks ineffective. This last smart contract crucially uses DECO to connect blockchains with TLS sessions.

Our work shows that risks envisioned by Anderson and Vaudenay are absolutely concrete, in particular TEnK-U shows how to realize with Immuni and SwissCovid the terrorist attack to decentralized systems discussed by Vaudenay.

Most blockchain solutions are susceptible to quantum attackers as they rely on cryptography that is known to be insecure in the presence of quantum adversaries. In this work we advance the study of quantum-resistant blockchain solutions by giving a quantum-resistant construction of a deterministic wallet scheme. Deterministic wallets are frequently used in practice in order to secure funds by storing the sensitive secret key on a so-called cold wallet that is not connected to the Internet. Recently, Das et al. (CCS'19) developed a formal model for the security analysis of deterministic wallets and proposed a generic construction from certain types of signature schemes that exhibit key rerandomization properties. We revisit the proposed classical construction in the presence of quantum adversaries and obtain the following results.

First, we give a generic wallet construction with security in the quantum random oracle model (QROM) if the underlying signature scheme is secure in the QROM. We next design the first post-quantum secure signature scheme with rerandomizable public keys by giving a construction from generic lattice-based Fiat-Shamir signature schemes. Finally, we show and evaluate the practicality by analyzing an instantiation of the wallet scheme based on the signature scheme qTESLA (ACNS'20).

This work presents a hardware accelerator, for the optimization of latency and area at the same time, to improve the performance of point multiplication process in Elliptic Curve Cryptography. In order to reduce the overall computation time in the proposed 2-stage pipelined architecture, a rescheduling of point addition and point doubling instructions is performed along with an efficient use of required memory locations. Furthermore, a 41-bit multiplier is also proposed. Consequently, the FPGA and ASIC implementation results have been provided. The performance comparison with state-of-the-art implementations, in terms of latency and area, proves the significance of the proposed accelerator.

Along with the rapid development of cloud computing technology, containerization technology has drawn much attention from both industry and academia. In this paper, we perform a comparative measurement analysis of Docker-sec, which is a Linux Security Module proposed in 2018, and a new AppArmor profile generator called Lic-Sec, which combines Docker-sec with a modified version of LiCShield, which is also a Linux Security Module proposed in 2015. Docker-sec and LiCShield can be used to enhance Docker container security based on mandatory access control and allows protection of the container without manually configurations. Lic-Sec brings together their strengths and provides stronger protection. We evaluate the effectiveness and performance of Docker-sec and Lic-Sec by testing them with real-world attacks. We generate an exploit database with 42 exploits effective on Docker containers selected from the latest 400 exploits on Exploit-db. We launch these exploits on containers spawned with Docker-sec and Lic-Sec separately. Our evaluations show that for demanding images, Lic Sec gives protection for all privilege escalation attacks for which Docker-sec failed to give protection.

Event date: 10 May to 13 May 2021
Submission deadline: 13 November 2020

Technology Innovation Institute (TII) is a publicly funded research institute, based in Abu Dhabi, United Arab Emirates. It is home to a diverse community of leading scientists, engineers, mathematicians, and researchers from across the globe, transforming problems and roadblocks into pioneering research and technology prototypes that help move society ahead.

Responsibilities

• Specify, design, implement and deploy cryptographic IP cores (including quantum-secure solutions)
• Conduct research on (but not limited to) efficient cryptographic implementations, implementation attacks and countermeasures, design methodologies and tools
• Perform security reviews of hardware designs and implementations
• Work closely with the integration team and other teams in the organization to design and prototype secure systems and communication protocols

  Minimum qualifications:

• BSc, MSc or PhD degree in Cryptography, Computer Science, Engineering or similar degree with 3+ years of relevant work or research
• Thorough knowledge of computer architecture and digital design principles Relevant hardware development experience with a focus on hardware security
• Extensive experience developing for FPGA and/or ASIC platforms in Verilog/VHDL
• Experience writing testbenches and using waveform-based debugging tools
• Solid understanding of cryptography, side-channel analysis attacks and countermeasures

  
  Preferred qualifications:

• Knowledge of UVM and assertion-based formal tools
• Understanding of low-power and high-performance techniques
• Understanding of micro-architectural attacks (e.g., Spectre, Meltdown, MDS)
• Hands-on experience integrating IP blocks in complex systems (SoCs)
• Programming skills in C/C++, Python, and/or Tcl
• Hands-on experience with lab equipment (e.g., oscilloscopes, function generators)

  Closing date for applications:

  Contact: Mehdi Messaoudi
  Talent Acquisition Manager
  mehdi.messaoudi@tii.ae

We are looking for candidates for a free Post-Doc position in the field of design and modeling of self-timed rings (STR) as a source of randomness in logic devices, implementation of true random number generators (TRNG) based on STRs in FPGAs and ASICs, analysis of statistical properties of the generated numbers, statistical modeling of the proposed TRNGs and construction of efficient embedded tests dedicated to the proposed generators and based on their stochastic models. Desired profile: Ph.D. degree is required. Required skills: a) good knowledge of digital electronics and embedded systems; b) knowledge of CAD tools and FPGA design (Intel, Xilinx or Microsemi) as well as simulation tools (Modelsim); c) ASIC design using Cadence tools (design, simulation, verification); d) good level of English. Other useful skills: e) data acquisition and data analysis (use of tcl and python languages in particular); f) signal processing, mathematical modeling, statistics; g) basic knowledge in information security.

Closing date for applications:

Contact: fischer(at)univ-st-etienne.fr

More information: https://laboratoirehubertcurien.univ-st-etienne.fr/en/teams/secure-embedded-systems-hardware-architectures/job-opportunities-2.html

We are looking for a Postdoctoral Cryptography Researcher to join our Team. This is an opportunity for someone who is genuinely excited by new technologies to influence the design and implementation of bleeding edge advanced cryptographic systems and protocols. Functioning somewhat independently and working within the larger Research Team, the Postdoctoral Cryptography Researcher will research and design cryptographic protocols and concepts, partnering with the team to develop prototypes. Our Researchers are also internal subject matter experts, providing guidance and learning opportunities to our extended staff. Researchers are also responsible for publishing meaningful research, independently and with other members of staff.

You will be working on a fast-paced, rapidly growing, high-profile project with a significant opportunity for industry-level impact on emerging blockchain and cryptocurrency technologies.

Overseen by Silvio Micali, this opportunity is for one (1) year with the possibility for extension.

Full role description (including responsibilities and qualifications) and application link is available at the further information link.

Interested candidates should submit their application at the further information link along with their CV (including list of publications), one (1) recently published paper relevant to the position responsibilities, and two (2) reference letters. You can share your paper and reference letter via the "Portfolio" link when applying, or upload the files with you CV. This position is available immediately and thus candidates who are already in the US are preferred.

Closing date for applications:

Contact: Regnia O'Brien, Head of People & Talent

More information: https://jobapply.page.link/TNVg