International Association
for Cryptologic Research

Witness encryption (WE) allows us to use an arbitrary NP statement $x$ as a public key to encrypt a message, and the witness $w$ serves as a decryption key. Security ensures that, when the statement $x$ is false, the encrypted message remains computationally hidden. WE appears to be significantly weaker than indistinguishability obfuscation (iO). Indeed, WE is closely related to a highly restricted form of iO that only guarantees security for null circuits (null iO). However, all current approaches towards constructing WE under nice assumptions go through iO. Such constructions are quite complex and are unlikely to lead to practically instantiable schemes. In this work, we revisit a very simple WE and null iO candidate of Chen, Vaikuntanathan and Wee (CRYPTO 2018). We show how to prove its security under a nice and easy-to-state assumption that we refer to as "evasive LWE" following Wee (EUROCRYPT 2022). Roughly speaking, the evasive LWE assumption says the following: assume we have some joint distributions over matrices $\mathbf{P}$, $\mathbf{S}$ and auxiliary information $\mathsf{aux}$ such that $$({\mathbf{S}\mathbf{B} + \mathbf{E}},{\mathbf{S} \mathbf{P} + \mathbf{E}'}, \mathsf{aux}) \approx_c ({\mathbf{U}},{\mathbf{U'}}, \mathsf{aux}),$$ for a uniformly random (and secret) matrix $\mathbf{B}$, where $\mathbf{U}, \mathbf{U}'$ are uniformly random matrices, and $\mathbf{E},\mathbf{E}'$ are chosen from the LWE error distribution with appropriate parameters. Then it must also be the case that: $$\mathbf{S}\mathbf{B} + \mathbf{E}, \mathbf{B}^{-1}(\mathbf{P}),\mathsf{aux}) \approx_c (\mathbf{U}, \mathbf{B}^{-1}(\mathbf{P}),\mathsf{aux}).$$ Essentially the above says that given $\mathbf{S}\mathbf{B} + \mathbf{E}$, getting the additional component $\mathbf{B}^{-1}(\mathbf{P})$ is no more useful than just getting the product $({\mathbf{S}\mathbf{B} + \mathbf{E}})\cdot \mathbf{B}^{-1}(\mathbf{P}) \approx \mathbf{S} \mathbf{P} + \mathbf{E}'$.

We present a novel, complete definition of metadata-private messaging (MPM) and show that our definition is achievable and non-trivially more general than previous attempts that we are aware of. Our main contributions are:

1) We describe a vulnerability in existing MPM implementations through a variation of the compromised-friend (CF) attack proposed by Angel et al. Our attack can compromise the exact metadata of any conversations between honest users.

2) We present a security definition for MPM systems assuming that some friends may be compromised.

3) We present a protocol satisfying our security definition based on Anysphere, an MPM system we deployed in practice.

We propose Designated-Verifier Linkable Ring Signatures with unconditional anonymity, a cryptographic primitive that protects the privacy of signers in two ways: Firstly, it allows them to hide inside a ring (i.e. an anonymity set) they can create by collecting a set of public keys all of which must be used for verification. Secondly, it allows a designated entity to simulate signatures thus making it difficult for an adversary to deduce their identity from the content of the exchanged messages. Our scheme differs from similar proposals since the anonymity guarantees are unconditional.

In this paper, we propose a new protocol for private computation on set intersection (PCI) which is an extension of private set intersection (PSI). In PSI, each party has a private set and both want to securely compute the intersection of their sets such that only the result is revealed and nothing else. In PCI, we want to additionally apply a private computation on the result. The goal is to reveal only the result of such a secure evaluation on the intersection and nothing else. We particularly focus on a client-server setting where the server's set is significantly larger than the client's set and the result of the computation should be revealed only to the client. The protocol aims at a low communication overhead which is sublinear in the server's set size. Such PSI protocols have already been realized using fully homomorphic encryption (FHE). However, they do not allow for private post-processing to enable PCI. There are also protocols enabling PCI which are in addition very fast with respect to the computational overhead. Their drawback is that they have a communication overhead which is at least linear in the larger set. We present a PSI protocol which can be used for arbitrary post-processing without creating a new protocol for every special-purpose PCI functionality. Our construction relies on the evaluation of a branching program using an FHE scheme. Using the properties of an FHE scheme, we build a non-interactive protocol with extendable functionalities. That means, we can not only securely compute the intersection but use the encrypted result to apply further computations without revealing the intersection itself. To the best of our knowledge, this results in the first PCI protocol with communication cost sublinear in the larger set. Compared to previous work, we can reduce the communication by factor 47.

In this paper, we consider the new version of tropical cryptography protocol, i.e the tropical version of ElGamal encryption. We follow the ideas and modify the classical El Gamal encryption using tropical matrices and matrix power in tropical algebra. Then we also provide a toy example for the reader’s understanding.

Cryptographic group actions are a relaxation of standard cryptographic groups that have less structure. This lack of structure allows them to be plausibly quantum resistant despite Shor's algorithm, while still having a number of applications. The most famous example of group actions are built from isogenies on elliptic curves.

Our main result is that CDH for abelian group actions is quantumly *equivalent* to discrete log. Galbraith et al. (Mathematical Cryptology) previously showed *perfectly* solving CDH to be equivalent to discrete log quantumly; our result works for any non-negligible advantage. We also explore several other questions about group action and isogeny protocols.

Event date: 15 December to 17 December 2022
Notification: 31 October 2022

Applications are invited for the MS and PhD positions in Information Security at the Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung, Taiwan. The successful candidate will work under the guidance of Dr. Arijit Karati on the diverse topics in Applied Cryptology. Candidates must comprehend formal security analysis, secure coding, and effective security integration in the application domains.

Responsibilities: Apart from academic work, student must involve in several activities in a group or individually, such as (not limited to):

Design and implementation of security protocol.

Assesment of the security and performance metric.

Research meeting with the supervisor.

Requirements: Apart from the university's basic admission policies (https://cse.nsysu.edu.tw/?Lang=en), students are desired to have following key requirements:

Strong motivation on information security.

Knowledge of modern technology.

Knowledge of basic mathematics for cryptography.

Knowledge of at least two programming languages, such as Python/Java/C/C++.

Scholarship:

Under the university policy.

Project funding (based on availability for master's Ph.D. students).

What students can expect:

Cooperation from the supervisor and labmates.

The rich culture in research and related activities.

Flexibility in communication, e.g., English.

What the supervisor can expect: Apart from academic and research works, students are expected to have

Good moral character.

Hardworking and dedication.

Deadline: Until September 2022 (for spring semester) and March 2023 (for fall semester)

Closing date for applications:

Contact: Arijit Karati (arijit.karati@mail.cse.nsysu.edu.tw)

Devices and Services Trust and Security (DSTS) group at Amazon is looking for a senior cryptographer with cryptography implementation experience. Candidate is expected to be a primary contributor to the development and execution of a post-quantum transition strategy within DSTS with impacts Amazon wide. In addition, candidate will identify security and cryptography concerns in devices/web services/applications at all stages of development (from concept to in-production). Candidate will lead or participate in the development of proof-of-concept implementations and guidance/training material regarding secure/proper use of cryptography. Key job responsibilities * Develop strategy, plans, and collateral to transition to PQ cryptographic algorithms * Develop and productize software implementations for PQ algorithms capable of running on Amazon devices and low-cost MCUs * Write collateral and training material to aid development teams in use of cryptography and transition to PQ algorithms * Perform trade-offs between cryptography, business-needs and security requirements to recommend best algorithm solutions and timings for algorithm transitions, taking into account software, hardware, backend services and market acceptance * Participate in development of requirements and hardware/software implementations for performant implementations of new cryptographic algorithms * Asses and resolve trouble tickets from development teams regarding use of crypto in design, implementation and/or production * Develop tools to assess use of cryptography across DSTS teams

Closing date for applications:

Contact: Apply through link above

More information: https://www.amazon.jobs/en/jobs/2033486/sr-applied-cryptographer-ds-crypto

The Cryptanalysis Taskforce at Nanyang Technological University in Singapore led by Prof. Jian Guo is seeking for candidates to fill some positions of post-doctoral research fellows and PhD students with full scholarship support on symmetric-key cryptography. Topics include but are not limited to the following sub-areas:

• tool aided cryptanalysis, such as MILP, CP, STP, and SAT
• machine learning aided cryptanalysis and designs
• privacy-preserving friendly symmetric-key designs
• quantum cryptanalysis
• theory and proof
• threshold cryptography
• cryptanalysis against SHA-2, SHA-3 and AES

Established in 2014, the Cryptanalysis Taskforce is a group dedicated for research in symmetric-key cryptography, it currently comprises more than 15 members of Postdocs, (exchange) PhD students, and visiting professors. Since establishment, the team has been active in both publications in and services for IACR. It has done quite some cryptanalysis work on various important targets such as SHA-3 and AES, and is expanding its interests to the areas mentioned above, with strong funding support from the university and government agencies in Singapore. We offer competitive salary package with extremely low tax (around 5%), as well as excellent environment dedicating for top-venues publication orientated research in Singapore. The contract for postdocs will be initially for one and half years, and has the possibility to be extended. Candidates are expected to have proven record of publications in IACR conferences. Interested candidates are to send their CV and 2 reference letters to Jian Guo. Review of applicants will start immediately until the positions are filled. Details on requirements of PhD admission to NTU and financial supports provided by the scholarships can be found here: https://guo.crypto.sg/students More information about the Cryptanalysis Taskforce research group can be found via https://team.crypto.sg

Closing date for applications:

Contact: Jian Guo, guojian@ntu.edu.sg, with subject [IACR-CATF]

More information: https://team.crypto.sg

The group of Prof. Dr. Cas Cremers at CISPA has multiple open positions. CISPA is one of the leading research institutions in Information Security worldwide, and is situated in Saarbrücken, Germany.

Positions are fully funded and we offer at least two year contracts with optional extension.

We have several ongoing projects in the areas of:

• Provable security : methodologies and automation (e.g., (manual) computational proofs, our work on the Tamarin Prover, or other tools),
• Protocol design, and
• Secure messaging.

We highly welcome new directions, and appreciate applicants with a passion for projects that are different from, but possibly connected to, our ongoing research.

Positions are fully funded and full-time.

Application deadline: September 22, 2022.

For more information, please click the link (title) of this job posting.

Closing date for applications:

Contact: Cas Cremers

More information: https://cispa.saarland/group/cremers/positions/index.html

The group of Prof. Dr. Cas Cremers at CISPA has open positions. CISPA is one of the leading research institutions in Information Security worldwide, and is situated in Saarbrücken, Germany.

We have several open projects in the areas of:

• Provable security : methodologies and automation (e.g., (manual) computational proofs, our work on the Tamarin Prover, or other tools),
• Protocol design, and
• Secure messaging.

Positions are fully funded and full-time.
Application deadline: September 22, 2022.

For more information, please click the link (title) of this job posting.

Closing date for applications:

Contact: Cas Cremers

More information: https://cispa.saarland/group/cremers/positions/index.html

Multiple recursive generators are an important class of pseudorandom number generators which are widely used in cryptography. The predictability of truncated sequences that predict the whole sequences by the truncated high-order bits of the sequences is not only a crucial aspect of evaluating the security of pseudorandom number generators but also serves an important role in the design of pseudorandom number generators. This paper improves the work of Sun et al on the predictability of truncated multiple recursive generators with unknown parameters. Given a few truncated digits of high-order bits output by a multiple recursive generator, we adopt the resultant, the Chinese Remainder Theorem and the idea of recovering $p$-adic coordinates of the coefficients layer by layer, and Kannan's embedding technique to recover the modulus, the coefficients and the initial state, respectively. Experimental results show that our new method is superior to that of the work of Sun et al, no matter in terms of the running time or the number of truncated digits required.

Cloud storage provides highly available and low cost resources to users. However, as massive amounts of outsourced data grow rapidly, an effective data deduplication scheme is necessary. This is a hot and challenging field, in which there are quite a few researches. However, most of previous works require dual-server fashion to be against brute-force attacks and do not support batch checking. It is not practicable for the massive data stored in the cloud. In this paper, we present a secure batch deduplication scheme for backup system. Besides, our scheme resists the brute-force attacks without the aid of other servers. The core idea of the batch deduplication is to separate users into different groups by using short hashes. Within each group, we leverage group key agreement and symmetric encryption to achieve secure batch checking and semantically secure storage. We also extensively evaluate its performance and overhead based on different datasets. We show that our scheme saves the data storage by up to 89.84%. These results show that our scheme is efficient and scalable for cloud backup system and can also ensure data confidentiality.

Elections are an important corner stone of democratic processes. In addition to publishing the final result (e.g., the overall winner), elections typically publish the full tally consisting of all (aggregated) individual votes. This causes several issues, including loss of privacy for both voters and election candidates as well as so-called Italian attacks that allow for easily coercing voters.

Several e-voting systems have been proposed to address these issues by hiding (parts of) the tally. This property is called tally-hiding. Existing tally-hiding e-voting systems in the literature aim at hiding (part of) the tally from everyone, including voting authorities, while at the same time offering verifiability, an important and standard feature of modern e-voting systems which allows voters and external observers to check that the published election result indeed corresponds to how voters actually voted. In contrast, real elections often follow a different common practice for hiding the tally: the voting authorities internally compute (and learn) the full tally but publish only the final result (e.g., the winner). This practice, which we coin publicly tally-hiding, indeed solves the aforementioned issues for the public, but currently has to sacrifice verifiability due to a lack of practical systems.

In this paper, we close this gap. We formalize the common notion of publicly tally-hiding and propose the first provably secure verifiable e-voting system, called Kryvos, which directly targets publicly tally-hiding elections. We instantiate our system for a wide range of both simple and complex voting methods and various result functions. We provide an extensive evaluation which shows that Kryvos is practical and able to handle a large number of candidates, complex voting methods and result functions. Altogether, Kryvos shows that the concept of publicly tally-hiding offers a new trade-off between privacy and efficiency that is different from all previous tally-hiding systems and which allows for a radically new protocol design resulting in a practical e-voting system.

Observation and manipulation of physical characteristics are well-known and powerful threats to cryptographic devices. While countermeasures against passive side-channel and active fault-injection attacks are well understood individually, combined attacks, i.e., the combination of fault injection and side-channel analysis, is a mostly unexplored area. Naturally, the complexity of analysis and secure construction increases with the sophistication of the adversary, making the combined scenario especially challenging. To tackle complexity, the side-channel community has converged on the construction of small building blocks, which maintain security properties even when composed. In this regard, Probe-Isolating Non-Interference (PINI) is a widely used notion for secure composition in the presence of side-channel attacks due to its efficiency and elegance. In this work, we transfer the core ideas behind PINI to the context of fault and combined security and, from that, construct the first trivially composable gadgets in the presence of a combined adversary.

During the last decades, many advances in the field of automated security protocol analysis have seen the field mature and grow from being applicable to toy examples, to modeling intricate protocol standards and finding real-world vulnerabilities that extensive manual analysis had missed.

However, modern security protocols often contain elements for which such tools were not originally designed, such as protocols that construct, by design, terms of unbounded size, such as counters, trees, and blockchains. Protocol analysis tools such as Tamarin and ProVerif have some very restricted support, but typically lack the ability to effectively reason about dynamically growing unbounded-depth terms.

In this work, we introduce subterm-based proof techniques that are tailored for automated protocol analysis in the Tamarin prover. In several case studies, we show that these techniques improve automation (allow for analyzing more protocols, or remove the need for manually specified invariants), efficiency (reduce proof size for existing analyses), and expressive power (enable new kinds of properties). In particular, we provide the first automated proofs for TreeKEM, S/Key, and Tesla Scheme~2; and we show substantial benefits, most notably in WPA2 and 5G-AKA, two of the largest automated protocol proofs.

Microarchitectural attacks utilize the performance optimization constructs that have been studied over decades in computer architecture research and show the vulnerability of such optimizations in a realistic framework. One such highly performance driven vulnerable construct is speculative execution. In this paper, we focus on the problem of breaking the kernel address-space layout randomization (KASLR) on modern mobile devices without using cache memory as a medium of observation. However, there are some challenges to breaking KASLR on ARM CPUs. The first challenge is that eviction strategies on ARM CPUs are slow, and the microarchitectural attacks exploiting the cache as a covert channel cannot be implemented on modern ARM CPUs. The second challenge is that non-canonical addresses are stored in the store buffer, although they are invalid. As a result, previous microarchitectural attacks distinguish such addresses as valid kernel addresses erroneously. In this paper, we focus on these challenges to close current gaps in the implementation of recent attacks against modern CPUs. We show how a Translation Look-aside Buffer (TLB) can be used to circumvent the cache memory as a covert channel in order to attack ASLR on both ARM and Intel CPUs. To the best of our knowledge, we are the first to break KASLR on ARM-based Android and iOS mobile devices. Furthermore, our attacks can be performed in JavaScript to break KASLR of the browser without the need for an Evict+Reload operation, which consumes a lot of time. The results of our attacks show that the attacker can distinguish whether or not the virtual address is valid in less than 0.0417 seconds and 0.0488 seconds on Android and iOS mobile devices, respectively.

In the current paper we investigate the possibility of designing secure blind signature scheme based on ElGamal signature equation. We define the generalized construction and analyze its security. We consider two types of schemes with the proposed construction, that cover all existing schemes. For schemes of the first type we provide generic ROS-style attack that violates unforgeability in the parallel setting. For schemes of the second type we prove that they do not provide either blindness, or unforgeability. As the result, we prove that all known ElGamal blind signature schemes are not secure. Moreover, these results show that the existence of secure ElGamal blind signature scheme is potentially possible only for small set of signature equations and requires the non-standard way of generating the first component of the signature.

In the UC framework, a protocol must be subroutine respecting; therefore, shared trusted setup might cause security issues. To address this drawback, Generalized UC (GUC) framework is introduced by Canetti et al. (TCC 2007). In this work, we investigate the impossibility and feasibility of GUC-secure commitments with global random oracles (GRO) as trusted setup. In particular, we show it is impossible to have a 2-round (1 round for the committing phase and 1 round for the opening phase) GUC-secure commitment in the global observable RO model by Canetti et al. (CCS 2014). We then give a new round-optimal GUC-secure commitment that uses only MiniCrypt assumptions (i.e. the existence of one-way functions) in the global observable RO model. In addition, we also examine the complete picture on round complexity of the GUC-secure commitments in various global RO models.