International Association
for Cryptologic Research

We explore a bitwise modification in Ajtai's one-way function. Our main contribution is to define the higher-bit approximate inhomogeneous short integer solution (ISIS) problem and prove its reduction to the ISIS problem. In this new instance, our main idea is to discard low-weighted bits to gain compactness. As an application, we construct a bitwise version of a hash-and-sign signature in the random oracle model whose security relies on the (Ring)-LWE and (Ring)-ISIS assumptions. Our scheme is built from the hash-and-sign digital signature scheme based on the relaxed notion of approximate trapdoors introduced by Chen, Genise and Mukherjee (2019). Their work can be interpreted as a bitwise optimization of the work of Micciancio and Peikert (2012). We extend this idea and apply our technique to the scheme by discarding low-weighted bits in the public key. Our modification brings improvement in the public key size but also in the signature size when used in the right setting. However, constructions based on the higher-bit approximate ISIS save memory space at the expense of loosening security. Parameters must be set in regards with this trade-off.

A threshold public key encryption protocol is a public key system where the private key is distributed among $n$ different servers. It offers high security since no single server is entrusted to perform the decryption in its entirety. It is the core component of many multiparty computation protocols which involves mutually distrusting parties with common goals. It is even more useful when it is homomorphic, which means that public operations on ciphertexts translate to operations on the underlying plaintexts. In particular, Cramer, Damgård and Nielsen at Eurocrypt 2001 provided a new approach to multiparty computation from linearly homomorphic threshold encryption schemes. On the other hand, there has been recent interest in developing multiparty computations modulo $2^k$ for a certain integer $k$, that closely match data manipulated by a CPU. Multiparty computation would therefore benefit from an encryption scheme with such a message space that would support a distributed decryption.

In this work, we provide the first threshold linearly homomorphic encryption whose message space is $\mathbf{Z}/2^k\mathbf{Z}$ for any $k$. It is inspired by Castagnos and Laguillaumie's encryption scheme from RSA 2015, but works with a class group of discriminant whose factorisation is unknown.

Its natural structure à la Elgamal makes it possible to distribute the decryption among servers using linear integer secret sharing, allowing any access structure for the decryption policy. Furthermore its efficiency and its flexibility on the choice of the message space make it a good candidate for applications to multiparty computation.

Security against side-channels and faults is a must for the deployment of embedded cryptography. A wide body of research has investigated solutions to secure implementations against these attacks at different abstraction levels. Yet, to a large extent, current solutions focus on one or the other threat. In this paper, we initiate a mode-level study of cryptographic primitives that can ensure security in a (new and practically-motivated) adversarial model combining leakage and faults. Our goal is to identify constructions that do not require a uniform protections of all their operations against both attack vectors. For this purpose, we first introduce a versatile and intuitive model to capture leakage and faults. We then show that a MAC introduced at Asiacrypt 2021 natively enables a leveled implementation where only its underlying tweakable block cipher must be protected, as long as only its tag verification can be faulted. We finally describe two approaches to amplify security in the case where also the tag generation can be faulted. One is based on iteration and requires the adversary to inject increasingly large faults to succeed. The other is based on randomness and allows provable security against differential faults.

Threshold implementation is a method based on secret sharing to secure cryptographic ciphers (and in particular S-boxes) against differential power analysis. Until now, threshold implementations were only constructed for specific types of functions and some small S-boxes, but no general construction for all S-boxes was ever presented. The lower bound for the number of shares of threshold implementation is $t+1$, where $t$ is the algebraic degree of the S-box. Since the smallest number of shares $t+1$ is not possible for all S-Boxes, as proven by Bilgin et al. in 2015, then there does not exist a universal construction with $t+1$ shares. Hence, if there is a universal construction working for all permutations then it should work with at least $t+2$ shares. In this paper, we present the first optimal universal construction with $t+2$ shares. This construction enables low latency hardware implementations without the need for randomness. In particular, we apply this result to find the first two uniform sharings of the AES S-box. Area and performance figures for hardware implementations are provided.

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.