International Association
for Cryptologic Research

Constructing advanced cryptographic primitives such as obfuscation or broadcast encryption from standard hardness assumptions in the post quantum regime is an important area of research, which has met with limited success despite significant effort. It is therefore extremely important to find new, simple to state assumptions in this regime which can be used to fill this gap. An important step was taken recently by Wee (Eurocrypt '22) who identified two new assumptions from lattices, namely evasive ${\sf LWE}$ and tensor ${\sf LWE}$, and used these to construct broadcast encryption and ciphertext policy attribute based encryption for ${\sf P}$ with optimal parameters. Independently, Tsabary formulated a similar assumption and used it to construct witness encryption (Crypto '22). Following Wee's work, Vaikuntanathan, Wee and Wichs independently provided a construction of witness encryption (Asiacrypt '22).

In this work, we advance this line of research by providing the first construction of multi-input attribute based encryption (${\sf MIABE}$) for the function class ${\sf NC_1}$ for any constant arity from evasive ${\sf LWE}$. Our construction can be extended to support the function class ${\sf P}$ by using evasive and a suitable strengthening of tensor ${\sf LWE}$. In more detail, our construction supports $k$ encryptors, for any constant $k$, where each encryptor uses the master secret key ${\sf msk}$ to encode its input $(\mathbf{x}_i, m_i)$, the key generator computes a key ${\sf sk}_f$ for a function $f \in {\sf NC}_1$ and the decryptor can recover $(m_1,\ldots,m_k)$ if and only if $f(\mathbf{x}_1,\ldots,\mathbf{x}_k)=1$. The only known construction for ${\sf MIABE}$ for ${\sf NC}_1$ by Agrawal, Yadav and Yamada (Crypto '22) supports arity $2$ and relies on pairings in the generic group model (or with a non-standard knowledge assumption) in addition to ${\sf LWE}$. Furthermore, it is completely unclear how to go beyond arity $2$ using this approach due to the reliance on pairings.

Using a compiler from Agrawal, Yadav and Yamada (Crypto '22), our ${\sf MIABE}$ can be upgraded to multi-input predicate encryption for the same arity and function class. Thus, we obtain the first constructions for constant-arity predicate and attribute based encryption for a generalized class such as ${\sf NC}_1$ or ${\sf P}$ from simple assumptions that may be conjectured post-quantum secure. Along the way, we show that the tensor ${\sf LWE}$ assumption can be reduced to standard ${\sf LWE}$ in an important special case which was not known before. This adds confidence to the plausibility of the assumption and may be of wider interest.

Quantitative analyses of the costs of cryptographic attack algorithms play a central role in comparing cryptosystems, guiding the search for improved attacks, and deciding which cryptosystems to standardize. Unfortunately, these analyses often turn out to be wrong.

Formally verifying complete proofs of attack performance is a natural response but crashes into an insurmountable structural problem: there are large gaps between the best proven cost among known attack algorithms and the best conjectured cost among known attack algorithms. Ignoring conjectured speedups would be a security disaster.

This paper presents a case study demonstrating the feasibility and value of successfully formalizing what state-of-the-art attack analyses actually do. The input to this formalization is not a proof, and the output is not a formally verified proof; the formalization process nevertheless enforces clear definitions, systematically accounts for all algorithm steps, simplifies review, improves reproducibility, and reduces the risk of error.

Concretely, this paper's CryptAttackTester (CAT) software includes formal specifications of (1) a general-purpose model of computation and cost metric, (2) various attack algorithms, and (3) formulas predicting the cost and success probability of each algorithm. The software includes general-purpose simulators that systematically compare the predictions to the observed attack behavior in the same model. The paper gives various examples of errors in the literature that survived typical informal testing practices and that would have been immediately caught if CAT-enforced links had been in place.

The case study in CAT is information-set decoding (ISD), the top attack strategy against the McEliece cryptosystem. CAT formalizes analyses of many ISD algorithms, covering interactions between (1) high-level search strategies from Prange, Lee–Brickell, Leon, Stern, Dumer, May–Meurer–Thomae, and Becker–Joux–May–Meurer; (2) random walks from Omura, Canteaut–Chabaud, Canteaut–Sendrier, and Bernstein–Lange–Peters; and (3) speedups in core subroutines such as linear algebra and sorting.

Account Abstraction is a powerful feature that will transform today Web3 onboarding UX. This notes describes an EVM (Ethereum Virtual Machine) implementation of the well known secp256r1 curves optimized for the specificities of the EVM environment. Our optimizations rely on EVM dedicated XYZZ elliptic coordinates system, hacked precomputations, and assembly tricks to cut from more than 1M to 200K/62K (with or withoutprecomputations)

In this work, we revisit the severely limited throughput problem of cryptocurrencies and propose a novel rebalancing approach for Payment Channel Networks (PCNs). PCNs are a popular solution for increasing the blockchain throughput, however, their benefit depends on the overall users’ liquidity. Rebalancing mechanisms are the state-of-the-art approach to maintaining high liquidity in PCNs. However, existing opt-in rebalancing mechanisms exclude users that may assist in rebalancing for small service fees, leading to suboptimal solutions and under-utilization of the PCNs’ bounded liquidity.

We introduce the first rebalancing approach for PCNs that includes all users, following an “all for one and one for all” design philosophy that yields optimal throughput. The proposed approach introduces a double-auction rebalancing problem, which we term Musketeer, where users can participate as buyers (paying fees to rebalance) or sellers (charging fees to route transactions). The desired properties tailored to the unique characteristics of PCNs are formally defined, including the novel property of cyclic budget balance that is a stronger variation of strong budget balance. Basic results derived from auction theory, including an impossibility and multiple mechanisms that either achieve all desiderata under a relaxed model or sacrifice one of the properties, are presented. We also propose a novel mechanism that leverages time delays as an additional cost to users. This mechanism is provably truthful, cyclic budget balanced, individually rational, and economic efficient but only with respect to liquidity.

First, the WESP encryption algorithm is defined. Encryptions are created by a system of equations in which the equations are generated using the values of tables that act as the encryption key. Next, it is shown that if the encryption tables are not known, the equations in the system of equations cannot be known, and it is demonstrated that the system of equations cannot be solved if the equations are not known, and thus the encryption cannot be broken in a closed form. Then, we calculate for all symbols used in the algorithm, the minimum amount of trials needed, in order to be able to verity the trials. Since the algorithm is constantly updating key values the verifying becomes impossible if equations are not evaluated in order. The calculation shows that the minimum number of trials required is such that the number of trials, i.e., the time required to break the encryption, increases exponentially as the key size grows. Since there is no upper limit on the key size there is neither any upper limit on the time it requires to break the encryption. It is also shown that the well-known mathematical "P vs NP" problem is solved by the presented proof. Since there is at least one algorithm (WESP) that is NP (verifiable in polynomial time) but not P (solvable in polynomial time), P cannot be the same set as NP.

Since the announcement of the NIST call for a new lightweight cryptographic standard, a lot of schemes have been proposed in response. Xoodyak is one of these schemes and is among the finalists of the NIST competition with a sponge structure very similar to the Keccak hash function – the winner of the SHA3 NIST competition. In this paper with conditional cube attack technique, we fully recover the key of Xoodyak reduced to 6 and 7 rounds with time complexity resp. 2^{42.58} and 2^{76.003} in the nonce-reusing scenario. In our attack setting, we import the cube variables in the absorbing associated data phase, which has higher degree of freedom in comparison to data absorption phase. We use MILP tool for finding enough cube variables to perform the conditional key recovery attack. The 6-round attack is practical and has been implemented. To the best of our knowledge, this is the first proposed attack on 7-round Xoodyak.

FPGAs have been used in the cloud since several years, as accelerators for various workloads such as machine learning, database processes and security tasks. As for other cloud services, a highly desired feature is virtualization in which multiple tenants can share a single FPGA to increase utilization and by that efficiency. By solely using standard FPGA logic in the untrusted tenant, on-chip logic sensors allow remote power analysis side-channel and covert channel attacks on the victim tenant. However, such sensors are implemented by unusual circuit constructions, such as ring oscillators, delay lines, or unusual interconnect configuration, which might be easily detected by bitstream and/or netlist checking. In this paper, we show that such structural checking methods are not universal solutions as the attacks can make use of any normal circuits, which mean they are ``benign-looking'' to any checking method. We indeed demonstrate that -- without any additional and suspicious implementation constraints -- standard circuits intended for legitimate tasks can be misused as a sensor thereby monitoring instantaneous power consumption, and hence conducting key-recovery attacks. This extremely stealthy attack is a threat that can originate from the application layers, i.e. through various high-level synthesis approaches.

Anonymous or attribute-based credential (ABC) systems are a versatile and important cryptographic tool to achieve strong access control guarantees while simultaneously respecting the privacy of individuals. A major problem in the practical adoption of ABCs is their transferability, i.e., such credentials can easily be duplicated, shared or lent. One way to counter this problem is to tie ABCs to biometric features of the credential holder and to require biometric verification on every use. While this is certainly not a viable solution for all ABC use-cases, there are relevant and timely use-cases, such as vaccination credentials as widely deployed during the COVID-19 pandemic. In such settings, ABCs that are tied to biometrics, which we call Biometric-Bound Attribute-Based Credentials (bb-ABC), allow to implement scalable and privacy-friendly systems to control physical access to (critical) infrastructure and facilities.

While there are some previous works on bb-ABC in the literature, the state of affairs is not satisfactory. Firstly, in existing work the problem is treated in a very abstract way when it comes to the actual type of biometrics. Thus, it does not provide concrete solutions which allow for assessing their practicality when deployed in a real-world setting. Secondly, there is no formal model which rigorously captures bb-ABC systems and their security requirements, making it hard to assess their security guarantees. With this work we overcome these limitations and provide a rigorous formalization of bb-ABC systems. Moreover, we introduce two generic constructions which offer different trade-offs between efficiency and trust assumptions, and provide benchmarks from a concrete instantiation of such a system using facial biometrics. The latter represents a contact-less biometric feature that provides acceptable accuracy and seems particularly suitable to the above use-case.

Event date: 15 July to 17 July 2024
Submission deadline: 19 February 2024
Notification: 8 April 2024

Event date: 15 July to 17 July 2024
Submission deadline: 6 November 2023
Notification: 22 January 2024

Event date: 16 December to 20 December 2023
Submission deadline: 20 July 2023
Notification: 15 September 2023

There is a vacancy for up to 3 positions as PhD Research Fellow in Informatics – Cryptology at the Department of Informatics. The positions are for a fixed-term period of 3 years with the possibility of a 4th year with compulsory other work (e.g. teaching duties at the Department). The positions are financed by the University of Bergen.

The successful candidates will be supervised by one of the faculty members at the Selmer center, depending on their interests and the nature of the research project.

Potential work tasks related to some of the topics:

• Statistical and algebraic cryptanalysis of modern block and stream ciphers
• Cryptanalysis of lattice-based postquantum cryptography protocols
• Construction of cryptographically optimal functions and related objects
• Design and analysis of symmetric ciphers, cryptographic hash functions and other related primitives
• Design and analysis of error-correcting codes and code-based cryptographic schemes

Please apply by September 15, 2023 through jobbnorge. Full job description available here: https://www.jobbnorge.no/en/available-jobs/job/246889/phd-research-fellow-in-informatics-cryptology-up-to-3-positions

Closing date for applications:

Contact: Assoc. Prof. Nikolay Kaleyski, Department of Informatics, University of Bergen.

More information: https://www.jobbnorge.no/en/available-jobs/job/246889/phd-research-fellow-in-informatics-cryptology-up-to-3-positions

There is an open call for a Postdoc position in the Cyber Security and Applied Cryptograhy research group at the Institute of Computer Science, University of St.Gallen, led by Prof. Katerina Mitrokotsa.

Our research interests are centered around information security and applied cryptography, with the larger goal of safeguarding communications and providing strong privacy guarantees. We are active in several areas, a subset of which include:

• Verifiable computation
• Secure, private and distributed aggregation
• Secure multi-party computation
• Privacy-preserving biometric authentication
• Anonymous credentials
• Distributed and privacy-preserving authentication

Candidates should have a strong background in applied cryptography and provable security, are able to work independently and also collaborate in a team. Applicants must hold a Ph.D., with contributions in the relevant research topics and have publications in good venues.

The starting date for the position is flexible and come with a very competitive salary. The selection process runs until the suitable candidate has been found. The University of St.Gallen conducts excellent research with international implications. The city of St.Gallen is located one hour from Zurich and offers a high quality of life.

Please apply by 30th June 2023 through the job portal (via link).

Closing date for applications:

Contact: https://jobs.unisg.ch/offene-stellen/postdoc-fellow-in-cryptography-information-security-m-f-d/25ddb9d0-5c47-41ac-8bde-5789dbaca5c4

More information: https://jobs.unisg.ch/offene-stellen/postdoc-fellow-in-cryptography-information-security-m-f-d/25ddb9d0-5c47-41ac-8bde-5789dbaca5c4

We are looking for a bright and motivated PhD student to work in the topics of information security and cryptography.

The student is expected to work on topics that include security and privacy issues in authentication. More precisely, the student will be working on investigating efficient and privacy-preserving authentication that provides: i) provable security guarantees, and ii) rigorous privacy guarantees.

Key Responsibilities:

• Perform exciting and challenging research in the domain of information security and cryptography.
• Support and assist in teaching computer security and cryptography courses.

Profile:

• The PhD student is expected to have a MSc degree or equivalent, and strong background in cryptography, network security and mathematics.
• Experience in one or more domains such as cryptography, design of protocols, secure multi-party computation and differential privacy is beneficial.
• Excellent programming skills.
• Excellent written and verbal communication skills in English

The Chair of Cyber Security, https://cybersecurity.unisg.ch/, led by Prof. Katerina Mitrokotsa, is a part of the Institute of Computer Science (ICS) at the University of St.Gallen. Our research interests are centered around information security and applied cryptography, with the larger goal of safeguarding communications and providing strong privacy guarantees. We are currently active in multiple areas including the design of provably secure cryptographic protocols and cryptographic primitives that can be employed for reliable authentication, outsourcing computations in cloud-assisted settings, network security problems as well as secure and privacy-preserving machine learning. As a doctoral student you will be a part of the Doctoral School of Computer Science (DCS), https://dcs.unisg.ch.

The starting date for the position is flexible and come with a very competitive salary. The selection process runs until the suitable candidate has been found.

Please apply by 30th June 2023 through the job portal (via link).

Closing date for applications:

Contact: https://jobs.unisg.ch/offene-stellen/funded-phd-student-in-applied-cryptography-privacy-preserving-authentication-m-w-d/2e2030aa-7e9a-497f-b4f9-c33c47ba06c7

More information: https://jobs.unisg.ch/offene-stellen/funded-phd-student-in-applied-cryptography-privacy-preserving-authentication-m-w-d/2e2030aa-7e9a-497f-b4f9-c33c47ba06c7

We are calling for a PhD Candidate position (4 years) that wants to obtain a doctoral degree and contribute to ongoing research in cryptography engineering at our crypto-group.

Relevant research problems for this position are in the context of real-world quantum-safe algorithms:

• Creating tools and methods for analysing hardware/software cryptographic implementations, including machine-learning tools.
• Physical side-channel analysis and testing of embedded devices performing cryptographic functions.
• Techniques for realizing cryptographic hardware concerned with physical side-channels.

Responsibilities include:

• Conduct collaborative research within the problem area of real-world cryptography as described above
• Contribute to the cryptography engineering laboratory at the department
• Co-supervise master students relevant to this research activity

Your main supervisor will be Professor Stig Frode Mjølsnes and co-supervisor will be Associate Professor Tjerand Silde at the Department of Information Security and Communication Technology in Trondheim, Norway.

Please see the URL for the complete call text.

Closing date for applications:

Contact: Prof. Stig F. Mjølsnes (sfm@ntnu.no) Closing date: Sept. 15, 2023.

More information: https://www.jobbnorge.no/en/available-jobs/job/246480/phd-candidate-in-cryptography-engineering

Applications are invited from Indian nationals for the position of ‘Project Associate - 1’ in a IBITF-funded research project with the following details:

Title of the project:
HideAndSeek: Searchable Encryption for Financial Databases

Essential qualifications: Bachelor’s degree in Computer Science/Information Technology/Electrical Engineering/Electronics and Communications Engineering from a recognized University or equivalent.

Desirable: Preference will be given to candidates who have qualified GATE or CSIR-UGC NET and have working experience relevant to the project. Candidates with expertise in the following are strongly encouraged to apply:

1) Expertise in Python/C++/Java
2) Expertise in NoSQL and distributed databases such as MongoDB, Cassandra, Riak, etc.
3) Some familiarity with Cryptographic primitives

Closing date for applications:

Contact:
Dr. Dhiman Saha, CSE, IIT Bhilai
Dr. Subhajit Siddhanta, CSE, IIT Bhilai

More information: https://iitbhilai.ac.in/index.php?pid=adv_feb23_01

In recent years there has been much focus on the development of core cryptographic primitives based on lattice assumptions. This has been driven by the NIST call for post-quantum key encapsulation and digital signature specifications. However, there has been much less work on efficient privacy-preserving protocols with post-quantum security.

In this work we present an efficient electronic voting scheme from lattice assumptions, ensuring the long-term security of encrypted ballots and voters' privacy. The scheme relies on the NTRU and RLWE assumptions. We begin by conducting an extensive analysis of the concrete hardness of the NTRU problem. Extending the ternary-NTRU analysis of Ducas and van Woerden (ASIACRYPT 2021), we determine the concrete fatigue point of NTRU to be $q=0.0058\cdot\sigma^2\cdot d^{\: 2.484}$ (above which parameters become overstretched) for modulus $q$, ring dimension $d$, and secrets drawn from a Gaussian of parameter $\sigma$. Moreover, we demonstrate that the nature of this relation enables a more fine-grained choice of secret key sizes, leading to more efficient parameters in practice.

Using the above analysis, our second and main contribution is to significantly improve the efficiency of the state-of-the-art lattice-based voting scheme by Aranha et al. (ACM CCS 2023). Replacing the BGV encryption scheme with NTRU we obtain a factor $\times 5.3$ reduction in ciphertext size and $\times 2.6$ more efficient system overall, making the scheme suitable for use in real-world elections.

As an additional contribution, we analyse the (partially) blind signature scheme by del Pino and Katsumata (CRYPTO 2022). We note that the NTRU security is much lower than claimed and propose new parameters. This results in only a minor efficiency loss, enabled by our NTRU analysis where previous parameter selection techniques would have been much more detrimental.

Time-lock puzzles wrap a solution $\mathrm{s}$ inside a puzzle $\mathrm{P}$ in such a way that ``solving'' $\mathrm{P}$ to find $\mathrm{s}$ requires significantly more time than generating the pair $(\mathrm{s},\mathrm{P})$, even if the adversary has access to parallel computing; hence it can be thought of as sending a message $\mathrm{s}$ to the future. It is known [Mahmoody, Moran, Vadhan, Crypto'11] that when the source of hardness is only a random oracle, then any puzzle generator with $n$ queries can be (efficiently) broken by an adversary in $O(n)$ rounds of queries to the oracle.

In this work, we revisit time-lock puzzles in a quantum world by allowing the parties to use quantum computing and, in particular, access the random oracle in quantum superposition. An interesting setting is when the puzzle generator is efficient and classical, while the solver (who might be an entity developed in the future) is quantum powered and is supposed to need a long sequential time to succeed. We prove that in this setting there is no construction of time-lock puzzles solely from quantum (accessible) random oracles. In particular, for any $n$-query classical puzzle generator, our attack only asks $O(n)$ (also classical) queries to the random oracle, even though it does indeed run in quantum polynomial time if the honest puzzle solver needs quantum computing.

Assuming perfect completeness, we also show how to make the above attack run in exactly $n$ rounds while asking a total of $m\cdot n$ queries where $m$ is the query complexity of the puzzle solver. This is indeed tight in the round complexity, as we also prove that a classical puzzle scheme of Mahmoody et al. is also secure against quantum solvers who ask $n-1$ rounds of queries. In fact, even for the fully classical case, our attack quantitatively improves the total queries of the attack of Mahmoody et al. for the case of perfect completeness from $\Omega(mn \log n)$ to $mn$. Finally, assuming perfect completeness, we present an attack in the ``dual'' setting in which the puzzle generator is quantum while the solver is classical.

We then ask whether one can extend our classical-query attack to the fully quantum setting, in which both the puzzle generator and the solver could be quantum. We show a barrier for proving such results unconditionally. In particular, we show that if the folklore simulation conjecture, first formally stated by Aaronson and Ambainis [arXiv'2009] is false, then there is indeed a time-lock puzzle in the quantum random oracle model that cannot be broken by classical adversaries. This result improves the previous barrier of Austrin et. al [Crypto'22] about key agreements (that can have interactions in both directions) to time-lock puzzles (that only include unidirectional communication).

Practical Identity Based Encryption (IBE) schemes use the costly bilinear pairing computation. Clifford Cock proposed an IBE based on quadratic residuosity in 2001 which does not use bilinear pairing but was not efficient in practice, due to the large ciphertext size. In 2007, Boneh et al. proposed the first space efficient IBE that was also based on quadratic residuosity problem. It was an improvement over Cock's scheme but still the time required for encryption was quartic in the security parameter. In this paper, we propose a compact, space and time efficient identity based encryption scheme without pairing, based on a variant of Paillier Cryptosystem and prove it to be CPA secure. We have also proposed a CCA secure scheme based on the basic IBE scheme using the Fujisaki-Okamoto transformation. We have proved both the schemes in the random oracle model.

Succinct arguments that rely on the Merkle-tree paradigm introduced by Kilian (STOC 92) suffer from larger proof sizes in practice due to the use of generic cryptographic primitives. In contrast, succinct arguments with the smallest proof sizes in practice exploit homomorphic commitments. However these latter are quantum insecure, unlike succinct arguments based on the Merkle-tree paradigm.

A recent line of works seeks to address this limitation, by constructing quantum-safe succinct arguments that exploit lattice-based commitments. The eventual goal is smaller proof sizes than those achieved via the Merkle-tree paradigm. Alas, known constructions lack succinct verification. In this paper, we construct the first interactive argument system for NP with succinct verification that, departing from the Merkle-tree paradigm, exploits the homomorphic properties of lattice-based commitments. For an arithmetic circuit with N gates, our construction achieves verification time polylog(N) based on the hardness of the Ring Short-Integer-Solution (RSIS) problem.

The core technique in our construction is a delegation protocol built from commitment schemes based on leveled bilinear modules, a new notion that we deem of independent interest. We show that leveled bilinear modules can be realized from pre-quantum and from post-quantum cryptographic assumptions.