International Association
for Cryptologic Research

Cryptocurrencies have become tremendously popular since the creation of Bitcoin. However, its central Proof-of-Work consensus mechanism is very power hungry. As an alternative, Proof-of-Space (PoS) was introduced that uses storage instead of computations to create a consensus. However, current PoS implementations are complex and sensitive to the Nothing-at-Stake problem, and use mitigations that affect their permissionless and decentralised nature.

We introduce Proof-of-Space Search (PoSS) which embraces Hellman's time-memory trade-off to create a much simpler algorithm that avoids the Nothing-at-Stake problem. Additionally, we greatly stabilise block-times using a novel dynamic Logarithmic Embargo (LE) rule. Combined, we show that PoSSLE is a simple and stable alternative to PoW with many of its properties, while being an estimated 10 times more energy efficient and sustaining consistent block times.

The Non-Interactive Anonymous Router (NIAR) model was introduced by Shi and Wu [SW21] as an alternative to conventional solutions to the anonymous routing problem, in which a set of senders wish to send messages to a set of receivers. In contrast to most known approaches to support anonymous routing (e.g. mix-nets, DC-nets, etc.) which rely on a network of routers communicating with users via interactive protocols, the NIAR model assumes a $single$ router and is inherently $non$-$interactive$ (after an initial setup phase). In addition to being non-interactive, the NIAR model is compelling due to the security it provides: instead of relying on the honesty of some subset of the routers, the NIAR model requires anonymity even if the router (as well as an arbitrary subset of senders/receivers) is corrupted.

In this paper, we present a protocol for the NIAR model that improves upon the results from [SW21] in two ways:

- Improved computational efficiency (quadratic to near linear): Our protocol matches the communication complexity of [SW21] for each sender/receiver, while reducing the computational overhead for the router to polylog overhead instead of linear overhead.

- Relaxation of assumptions: Security of the protocol in [SW21] relies on the Decisional Linear assumption in bilinear groups; while security for our protocol follows from the existence of any rate-1 oblivious transfer (OT) protocol (instantiations of this primitive are known to exist under DDH, QR and LWE [DGI19,GHO20]).

PlonK is a prominent universal and updatable zk-SNARK for general circuit satisfiability. We present aPlonK, a variant of PlonK that reduces the proof size and verification time when multiple statements are proven in a batch. Both the aggregated proof size and the verification complexity of aPlonK are logarithmic in the number of aggregated statements. Our main building block, inspired by the techniques developed in SnarkPack (Gailly, Maller, Nitulescu, FC 2022), is a multi-polynomial commitment scheme, a new primitive that generalizes polynomial commitment schemes. Our techniques also include a mechanism for involving committed data into PlonK statements very efficiently, which can be of independent interest. We also implement an open-source industrial-grade library for zero-knowledge PlonK proofs with support for aPlonK. Our experimental results show that our techniques are suitable for real-world applications (such as blockchain rollups), achieving significant performance improvements in proof size and verification time.

Differential attacks are among the most important families of cryptanalysis against symmetric primitives. Since their introduction in 1990, several improvements to the basic technique as well as many dedicated attacks against symmetric primitives have been proposed. Most of the proposed improvements concern the key-recovery part. However, when designing a new primitive, the security analysis regarding differential attacks is often limited to finding the best trails over a limited number of rounds with branch and bound techniques, and a poor heuristic is then applied to deduce the total number of rounds a differential attack could reach. In this work we analyze the security of the SPEEDY family of block ciphers against differential cryptanalysis and show how to optimize many of the steps of the key-recovery procedure for this type of attacks. For this, we implemented a search for finding optimal trails for this cipher and their associated multiple probabilities under some constraints and applied non-trivial techniques to obtain optimal data and key-sieving. This permitted us to fully break SPEEDY-7-192, the 7-round variant of SPEEDY supposed to provide 192-bit security. Our work demonstrates among others the need to better understand the subtleties of differential cryptanalysis in order to get meaningful estimates on the security offered by a cipher against these attacks.

Blind signatures are a fundamental tool for privacy-preserving applications. Known constructions of concurrently secure blind signature schemes either are prohibitively inefficient or rely on non-standard assumptions, even in the random oracle model. A recent line of work (ASIACRYPT `21, CRYPTO `22) initiated the study of concretely efficient schemes based on well-understood assumptions in the random oracle model. However, these schemes still have several major drawbacks: 1) The signer is required to keep state; 2) The computation grows linearly with the number of signing interactions, making the schemes impractical; 3) The schemes require at least five moves of interaction.

In this paper, we introduce a blind signature scheme that eliminates all of the above drawbacks at the same time. Namely, we show a round-optimal, concretely efficient, concurrently secure, and stateless blind signature scheme in which communication and computation are independent of the number of signing interactions. Our construction also naturally generalizes to the partially blind signature setting.

Our scheme is based on the CDH assumption in the asymmetric pairing setting and can be instantiated using a standard BLS curve. We obtain signature and communication sizes of 9KB and 36KB, respectively. To further improve the efficiency of our scheme, we show how to obtain a scheme with better amortized communication efficiency. Our approach batches the issuing of signatures for multiple messages.

The invertibility of a random function (IRF, in short) is an important problem and has wide applications in cryptography. For ex- ample, searching a preimage of Hash functions, recovering a key of block ciphers under the known-plaintext-attack model, solving discrete loga- rithms over a prime field with large prime, and so on, can be viewed as its instances. In this work we describe the invertibility of multiple random functions (IMRF, in short), which is a generalization of the IRF. In order to solve the IMRF, we generalize the birthday theorem. Based on the generalized birthday theorem and time-memory tradeoff (TMTO, in short) method, we present an efficient TMTO method of solving an IMRF, which can be viewed as a generalization of three main TMTO attacks, that is, Hellman’s attack, Biryukov and Shamir’s attack with BSW sampling, and Biryukov, Mukhopadhyay and Sarkar’s time- memory-key tradeoff attack. Our method is highly parallel and suitable for distributed computing environments. As a generalization of Hellman’s attack, our method overcomes its shortcoming of using only one pair of known plaintext and ciphertext and first admits more than one datum in a TMTO on block ciphers at the single key scenario. As a generaliza- tion of Biryukov and Shamir’s attack with BSW sampling, our method overcomes its shortcoming of using only a few data with specific prefix in stream ciphers and can utilize all data without any waste. As appli- cations, we get two new tradeoff curves: N2 = TM2D3, N = PD and D=τforblockciphers,andN2 =τ3TM2D2,N=τPDandD≥τ for stream ciphers, where τ is the number of random functions, that is, the number of independent computing units available to an attacker, N is the size of key space (for block ciphers) or state (for stream ci- phers) space, D the number of data captured by the attacker, and T, M, P the time/memory/precomputation cost consumed at each computing unit respectively. As examples, assume that 4096 computing units can be available for the attacker. Denote by 5-tuple (τ, T, M, D, P ) the costof our method. Then the cost of breaking DES, AES-128 and A5/1 is (212, 225.3, 225.3, 212, 244), (212, 273.3, 273.3, 212, 2116) and (212, 222.7, 217.3,217.3, 234.7) respectively

We present a new public-key ABE for DFA based on the LWE assumption, achieving security against collusions of a-priori bounded size. Our scheme achieves ciphertext size $\tilde{O}(\ell + B)$ for attributes of length $\ell$ and collusion size $B$. Prior LWE-based schemes has either larger ciphertext size $\tilde{O}(\ell \cdot B)$, or are limited to the secret-key setting. Along the way, we introduce a new technique for lattice trapdoor sampling, which we believe would be of independent interest. Finally, we present a simple candidate public-key ABE for DFA for the unbounded collusion setting.

A trace and revoke ($\sf{TR}$) scheme is an $N$ user traitor tracing scheme which additionally enables the encryptor to specify a list $L \subseteq$ of revoked users so that these users can no longer decrypt ciphertexts. The ``holy grail'' of this line of work is a construction which resists unbounded collusions, achieves ciphertext, public and secret key sizes independent (ignoring logarithmic dependencies) of $|L|$ and $|N|$, and is based on polynomial hardness assumptions. In this work we make the following contributions:

1. Public Trace Setting: We provide a construction which (i) achieves optimal parameters, (ii) supports embedding identities (from an exponential space) in user secret keys, (iii) relies on polynomial hardness assumptions, namely compact functional encryption (${\sf FE}$) and a key-policy attribute based encryption (${\sf ABE}$) with special efficiency properties constructed by Boneh et al. (Eurocrypt 2014) from Learning With Errors (${\sf LWE}$), and (iv) enjoys adaptive security with respect to the revocation list. The previous best known construction by Nishimaki, Wichs and Zhandry (Eurocrypt 2016) which achieved optimal parameters and embedded identities, relied on indistinguishability obfuscation, which is considered an inherently subexponential assumption and achieved only selective security with respect to the revocation list. 2. Secret Trace Setting: We provide the first construction with optimal ciphertext, public and secret key sizes and embedded identities from any assumption outside Obfustopia. In detail, our construction relies on Lockable Obfuscation which can be constructed using ${\sf LWE}$ (Goyal, Koppula, Waters and Wichs, Zirdelis, Focs 2017) and two ${\sf ABE}$ schemes: (i) the key-policy scheme with special efficiency properties by Boneh et al. (Eurocrypt 2014) and (ii) a ciphertext-policy ${\sf ABE}$ for ${\sf P}$ which was recently constructed by Wee (Eurocrypt 2022) using a new assumption called evasive and tensor ${\sf LWE}$. This assumption, introduced to build an ${\sf ABE}$, is believed to be much weaker than lattice based assumptions underlying ${\sf FE}$ or ${\sf iO}$ -- in particular it is required even for lattice based broadcast, without trace.

Moreover, by relying on subexponential security of ${\sf LWE}$, both our constructions can also support a super-polynomial sized revocation list, so long as it allows efficient representation and membership testing. Ours is the first work to achieve this, to the best of our knowledge.

This paper provides a cryptographic application to our previous paper [Li22h], where we considered noisy systems of discrete exponential equations over a land, which is a monoid without the requirement of associativity. In this paper we give a general methodology for signature scheme construction from noisy systems.

The Distorted Bounded Distance Decoding Problem (DBDD) was introduced by Dachman-Soled et al. [Crypto ’20] as an intermediate problem between LWE and unique-SVP (uSVP). They presented an approach that reduces an LWE instance to a DBDD instance, integrates side information (or “hints”) into the DBDD instance, and finally reduces it to a uSVP instance, which can be solved via lattice reduction. They showed that this principled approach can lead to algorithms that perform better than ad-hoc algorithms that do not rely on lattice reduction. The current work focuses on new methods for integrating hints into a DBDD instance. We introduce a variant of DBDD which we coin Ellipsoidal Bounded Distance Decoding (EBDD), and view an EBDD instance as providing the promise that the correct solution is the unique lattice point contained in an ellipsoid. We then view “hints” as geometric operations on the EBDD ellipsoid. Our approach allows us to introduce two new types of hints: (1) Inequality hints, corresponding to the region of intersection of an ellipsoid and a halfspace; (2) Combined hints, corresponding to the region of intersection of two ellipsoids. Since the regions in (1) and (2) are not necessarily ellipsoids, we replace them with approximations. We also consider compatibility of our approach with “perfect,” “approximate,” “modular,” and “short vector” hints from the prior work. We apply our techniques to the decryption failure and side-channel attack settings. We show that “inequality hints” can be used to model decryption failures, and that our new approach yields a geometric analogue of the “failure boosting” technique of D’anvers et al. [ePrint, ’18]. We also show that “combined hints” can be used to fuse information from a decryption failure and a side-channel attack, resulting in reduced hardness of the resulting uSVP instance, compared to a naive combination of the information. We provide experimental data for both applications. The code that we have developed to implement the integration of hints and hardness estimates extends the Toolkit from prior work and has been released publicly.

The history of equations dates back to thousands of years ago, though the equals sign "=" was only invented in 1557. We formalize the processes of "decomposition" and "restoration" in mathematics and physics by defining "discrete exponential equations" and "noisy equation systems" over an abstract structure called a "land", which is more general than fields, rings, groups, and monoids. Our abstract equations and systems provide general languages for many famous computational problems such as integer factorization, ideal factorization, isogeny factorization, learning parity with noise, learning with errors, learning with rounding, etc. From the abstract equations and systems we deduce a list of new decomposition problems and noisy learning problems. We also give algorithms for discrete exponential equations and systems over algebraic integers. Our motivations are to develop a theory of decomposition and restoration; to unify the scattered studies of decomposition problems and noisy learning problems; and to further permeate the ideas of decomposition and restoration into all possible branches of mathematics. A direct application is a methodology for finding new hardness assumptions for cryptography.

SPyCoDe (Semantic and Cryptographic Foundations of Security and Privacy by Compositional Design) is a special research program funded by FWF.

We offer 14 interdisciplinary and interconnected research projects at the intersection of Cryptography, System Security, and Formal Methods. The projects are listed below, each is led by a PI in collaboration with at least another member of the SPyCoDe faculty

1. Cross-Layer Security for Blockchain Consensus (Pietrzak, ISTA)
2. Cross-Layer Side-Channel Security (Gruss, TU Graz)
3. Cryptographic Techniques for Blockchain Security (Andreeva, TU Vienna)
4. Cryptographic Techniques for System Security (Eichlseder, TU Graz)
5. Enforcement of Security and Privacy Policies across Multi-Party Code (Lindorfer, TU Vienna)
6. Formal Verification of Side Channel Properties (Bloem, TU Graz)
7. Game-Theoretic Models for Blockchain Applications (Fuchsbauer, TU Vienna)
8. Interface Theory for Security and Privacy Employer (Henzinger, ISTA)
9. Logic-based Reasoning for Hyperproperties (Kovács, TU Vienna)
10. Quantitative and Probabilistic Security Analysis (Oswald, U Klagenfurt)
11. Secure Blockchains in Network Transition Periods (Ullrich, U Vienna)
12. Secure Network and Hardware for Efficient Blockchains (ISTA, Kokoris-Kogias)
13. Security and Privacy by Design for Smart Contracts (Maffei, TU Vienna)
14. Side-Channel Resistant System Design (Mangard, Graz)

Closing date for applications:

Contact: Olha Denisova recruiting-questions@spycode.at for questions about the application. Any of the affiliated faculty (https://spycode.at/people/) with questions about their projects.

More information: https://spycode.at/apply/

The Laboratory for Computation Security at EPFL, led by Prof. Alessandro Chiesa, is hiring a Cryptography Engineer.

You will join the lab as a full-time developer, and collaborate with other researchers (graduate students and postdoctoral scholars) to create high-quality open-source software that realizes complex cryptographic protocols.

The group's research include, but is not limited to, computational complexity, zero-knowledge proofs, succint non-interactive arguments (SNARGs) and privacy-enhancing technologies (such as peer-to-peer private payment systems and smart contracts).

Responsabilities:

• Realizing secure and efficient implementations of new cryptographic protocols
• Developing and contributing to open-source libraries for cryptographic proofs
• Helping prepare pedagogical material (software projects for courses)

Your Profile:

• Master's degree in Computer Science (or equivalent engineering experience)
• Experience in software development with Rust and C++
• Knowledge of basic algebra (groups, finite fields, ...) and basic cryptography (hash functions, encryption, ...)

For the full job posting, please refer to: https://recruiting.epfl.ch/Vacancies/2318/Description/2

Closing date for applications:

Contact: Alessandro Chiesa

More information: https://recruiting.epfl.ch/Vacancies/2318/Description/2

The department of Mathematics & Statistics of the University of South Florida Invites applications for a full-time tenure-track faculty position in mathematics at the Assistant Professor level. We are particularly interested in applications from candidates in Applied Analysis or Applied Algebra. The latter includes Cryptography and Coding Theory. The search committee will start to review the completed applications on November 15th, 2022 and will continue until the position is filled. The Mathematics & Statistics department is home of a cryptographic research center (usf-crypto.org), and offers multiple courses in cryptography and coding theory.

Closing date for applications:

Contact: Jean-François Biasse

More information: https://www.mathjobs.org/jobs/list/20917

The Institute of Logic and Computation, research unit Security and Privacy, at TU Wien offers a position as a university assistant (post-doc) limited to 6 years for 40 hours/week.
Your profile:

• Completion of an appropriate doctorate and in-depth knowledge of the subject area
• An outstanding publication record in top security and privacy conferences
• Research background in one of the following topics: formal methods for security and privacy, blockchain technologies, intersection between machine learning and security or privacy, or web security
• Experience in teaching and publication activities as well as interest and pleasure in research and working with students
• Organisational and analytical skills as well as a structured way of working
• Excellent skills in English communication and writing, knowledge of German (level B2) or willingness to learn it in the first year.

We offer an excellent research environment and a very competitive salary (B1 scale, 56.861,70 EUR per year before tax).

We look forward to receiving your application until 10.11.2022. Applications are only processed online: https://jobs.tuwien.ac.at/Job/194015

Closing date for applications:

Contact: Univ.-Prof. Dr. Matteo Maffei

More information: https://jobs.tuwien.ac.at/Job/194015

We are seeking internship candidate for our hardware penetration testing lab in Cork, Ireland. The Cork site is home to a range of digital IP teams working on cutting edge IP for the latest Snapdragon chip sets. The security lab team is working with the latest tools and techniques to perform hardware penetration testing. Successful candidates will be joining a vibrant hardware security lab team, with a strong collaboration with several Qualcomm security labs around the global.

The internship program will skill up the candidate in developing side-channel analysis attacks in the context of post-quantum cryptography, including (but not limited to): literature exploration of most relevant algorithms, open problems, and industry vs. academy gaps; high-performance implementation of state-of-the-art attacks and addition feature to in-house tools.

Minimum qualifications

• Towards the end of M.Sc. or Ph.D. academic degree in Computer Engineering and/or Electrical (or physics) Engineering, or related field
• 6 months is the minimum period for internship program
• Basic knowledge in linear and abstract algebra
• Good knowledge in system-level programming languages (e.g., C, C++, Rust)
• Good communication skills, curiosity and enthusiasm, ability to work independently and willingness to learn

Preferred qualifications

• Knowledge in cryptography and security-related topics (e.g., key management and authentication)
• Good understanding of SoC architecture, ASIC design, and/or hardware security
• Hands-on experience with: VHDL/Verilog, FPGA prototyping, lab equipment

Education requirements
Intern/co-op placement as part of Master/PhD program.

Closing date for applications:

Contact: Santos Merino del Pozo (sdelpozo@qti.qualcomm.com)

The ANR Project CIAO is looking for a one year postdoc on isogeny based cryptography. The researcher will be working on any area related to this topic: security, implementations, hash functions, key exchange, signature, VDF, higher dimensional isogenies...

The location will be at the Bordeaux Mathematical institute, in France.
https://www.math.u-bordeaux.fr/imb/spip.php?lang=fr
https://www.inria.fr/fr/centre-inria-universite-bordeaux

The application is open and should ideally be filled before April 2023, although an extension should be possible.

The postdoctoral researcher will be part of the LFANT team
https://lfant.math.u-bordeaux.fr/
who develops the Pari/GP software
https://pari.math.u-bordeaux.fr/

If you are interested, please send an email including your CV and a list of publications.

Closing date for applications:

Contact: Damien Robert
http://www.normalesup.org/~robert/pro/infos.html

As part of its strategic development, the Department of Informatics is seeking applications from candidates for the position of Lecturer in Computer Science (Cryptography), starting in September 2023, or as soon as possible thereafter. The successful applicant for this post will undertake research and teaching in an area of Cryptography and more broadly Cybersecurity. They will be assigned to teach on the Department’s MSc in Cybersecurity (face to face and/or online), or other postgraduate or undergraduate degree programmes offered by the Department of Informatics, and will be expected to supervise both undergraduate and postgraduate projects. While we cannot guarantee teaching in cryptography, we hope to expand our cryptography teaching portfolio in the near future. Accordingly, the successful applicant will need knowledge and awareness of current research and practical challenges in Cryptography. All areas of cryptography are of interest to the Department, including but not limited to theory (TCC), applied (RWC), public-key (PKC), symmetric-key (FSE) and embedded systems and hardware (CHES). Outstanding candidates engaged in research and teaching which complements that of the existing members of the Department will be considered favourably. The successful candidate will be appointed to the Cybersecurity (CYS) group and will have the opportunity to contribute to the Security Hub and to the King’s EPSRC-NCSC Academic Centre of Excellence in Cybersecurity Research (ACE-CSR) - https://www.kcl.ac.uk/cybersecurity-centre. The successful candidate will have the opportunity to collaborate with colleagues in the new cryptography lab launching in January 2023 and other labs in the CYS group. Research collaboration across research groups, with departmental hubs and with other Departments in the Faculty and across the College is strongly encouraged. …

Closing date for applications:

Contact: Martin Albrecht

More information: https://martinralbrecht.wordpress.com/2022/10/09/lecturer-%e2%89%85-assistant-professor-juniorprofessor-maitre-de-conferences-in-cryptography-at-kings-college-london/

Event date: 15 February to 17 February 2023

Event date: 29 May to 31 May 2023
Submission deadline: 31 December 2022
Notification: 20 February 2023