International Association
for Cryptologic Research

We present a rate-$1$ construction of a publicly verifiable non-interactive argument system for batch-$\mathsf{NP}$ (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of $k$ NP statements each with an $m$-bit witness, has size $m + \mathsf{poly}(\lambda,\log k)$.

In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size $m \cdot \mathsf{poly}(\lambda,\log k)$ (Choudhuri, Jain, and Jin, STOC 2021, following Kalai, Paneth, and Yang 2019). We show how to use our rate-$1$ BARG scheme to obtain the following results, all under the LWE assumption: - A multi-hop BARG scheme for $\mathsf{NP}$. - A multi-hop aggregate signature scheme (in the standard model). - An incrementally verifiable computation (IVC) scheme for arbitrary $T$-time deterministic computations with proof size $\mathsf{poly}(\lambda,\log T)$. Prior to this work, multi-hop BARGs were only known under non-standard knowledge assumptions or in the random oracle model; aggregate signatures were only known under indistinguishability obfuscation (and RSA) or in the random oracle model; IVC schemes with proofs of size $\mathsf{poly}(\lambda,T^{\epsilon})$ were known under a bilinear map assumption, and with proofs of size $\mathsf{poly}(\lambda,\log T)$ under non-standard knowledge assumptions or in the random oracle model.

The post-quantum security of cryptographic systems assumes that the quantum adversary only receives the classical result of computations with the secret key. Furthermore, if the adversary is able to obtain a superposition state of the result, it is unknown whether the post-quantum secure schemes still remain secure.

In this paper, we formalize one class of public-key encryption schemes, named oracle-masked schemes, relative to random oracles. For each oracle-masked scheme, we design a preimage extraction procedure and prove that it simulates the quantum decryption oracle with a certain loss. We also observe that the implementation of the preimage extraction procedure for some oracle-masked schemes does not need to take the secret key as input. This contributes to the IND-qCCA security proof of these schemes in the quantum random oracle model (QROM). As an application, we prove the IND-qCCA security of schemes obtained by the Fujisaki-Okamoto (FO) transformation and REACT transformation in the QROM, respectively.

Notably, our security reduction for FO transformation is tighter than the reduction given by Zhandry (Crypto 2019).

OMAC --- a single-keyed variant of CBC-MAC by Iwata and Kurosawa --- is a widely used and standardized (NIST FIPS 800-38B, ISO/IEC 29167-10:2017) message authentication code (MAC) algorithm. The best security bound for OMAC is due to Nandi who proved that OMAC's pseudorandom function (PRF) advantage is upper bounded by $ O(q^2\ell/2^n) $, where $ n $, $ q $, and $ \ell $, denote the block size of the underlying block cipher, the number of queries, and the maximum permissible query length (in terms of $ n $-bit blocks), respectively. In contrast, there is no attack with matching lower bound. Indeed, the best known attack on OMAC is the folklore birthday attack achieving a lower bound of $ \Omega(q^2/2^n) $. In this work, we close this gap for a large range of message lengths. Specifically, we show that OMAC's PRF security is upper bounded by $ O(q^2/2^n + q\ell^2/2^n)$. In practical terms, this means that for a $ 128 $-bit block cipher, and message lengths up to $ 64 $ Gigabyte, OMAC can process up to $ 2^{64} $ messages before rekeying (same as the birthday bound). In comparison, the previous bound only allows $ 2^{48} $ messages. As a side-effect of our proof technique, we also derive similar tight security bounds for XCBC (by Black and Rogaway) and TMAC (by Kurosawa and Iwata). As a direct consequence of this work, we have established tight security bounds (in a wide range of $\ell$) for all the CBC-MAC variants, except for the original CBC-MAC.

Forward-secure encryption (FSE) allows communicating parties to refresh their keys across epochs, in a way that compromising the current secret key leaves all prior encrypted communication secure. We investigate a novel dimension in the design of FSE schemes: fast-forwarding (FF). This refers to the ability of a stale communication party, that is "stuck" in an old epoch, to efficiently "catch up" to the newest state, and frequently arises in practice. While this dimension was not explicitly considered in prior work, we observe that one can augment prior FSEs -- both in symmetric- and public-key settings -- to support fast-forwarding which is sublinear in the number of epochs. However, the resulting schemes have disadvantages: the symmetric-key scheme is a security parameter slower than any conventional stream cipher, while the public-key scheme inherits the inefficiencies of the HIBE-based forward-secure PKE.

To address these inefficiencies, we look at the common real-life situation which we call the bulletin board model, where communicating parties rely on some infrastructure -- such as an application provider -- to help them store and deliver ciphertexts to each other. We then define and construct FF-FSE in the bulletin board model, which addresses the above-mentioned disadvantages. In particular,

* Our FF-stream-cipher in the bulletin-board model has: (a) constant state size; (b) constant normal (no fast-forward) operation; and (c) logarithmic fast-forward property. This essentially matches the efficiency of non-fast-forwardable stream ciphers, at the cost of constant communication complexity with the bulletin board per update.

* Our public-key FF-FSE avoids HIBE-based techniques by instead using so-called updatable public-key encryption (UPKE), introduced in several recent works (and more efficient than public-key FSEs). Our UPKE-based scheme uses a novel type of "update graph" that we construct in this work. Our graph has constant in-degree, logarithmic diameter, and logarithmic "cut property" which is essential for the efficiency of our schemes. Combined with recent UPKE schemes, we get two FF-FSEs in the bulletin board model, under the DDH and the LWE assumptions.

Partially blind signatures, an extension of ordinary blind signatures, are a primitive with wide applications in e-cash and electronic voting. One of the most efficient schemes to date is the one by Abe and Okamoto (CRYPTO 2000), whose underlying idea - the OR-proof technique - has served as the basis for several works.

We point out several subtle flaws in the original proof of security, and provide a new detailed and rigorous proof, achieving similar bounds as the original work. We believe our insights on the proof strategy will find useful in the security analyses of other OR-proof-based schemes.

Non-malleable codes (Dziembowski, Pietrzak and Wichs, ICS 2010 & JACM 2018) allow protecting arbitrary cryptographic primitives against related-key attacks (RKAs). Even when using codes that are guaranteed to be non-malleable against a single tampering attempt, one obtains RKA security against poly-many tampering attacks at the price of assuming perfect memory erasures. In contrast, continuously non-malleable codes (Faust, Mukherjee, Nielsen and Venturi, TCC 2014) do not suffer from this limitation, as the non-malleability guarantee holds against poly-many tampering attempts. Unfortunately, there are only a handful of constructions of continuously non-malleable codes, while standard non-malleable codes are known for a large variety of tampering families including, e.g., NC0 and decision-tree tampering, AC0, and recently even bounded polynomial-depth tampering. We change this state of affairs by providing the first constructions of continuously non-malleable codes in the following natural settings: - Against decision-tree tampering, where, in each tampering attempt, every bit of the tampered codeword can be set arbitrarily after adaptively reading up to $d$ locations within the input codeword. Our scheme is in the plain model, can be instantiated assuming the existence of one-way functions, and tolerates tampering by decision trees of depth $d = O(n^{1/8})$, where $n$ is the length of the codeword. Notably, this class includes NC0. - Against bounded polynomial-depth tampering, where in each tampering attempt the adversary can select any tampering function that can be computed by a circuit of bounded polynomial depth (and unbounded polynomial size). Our scheme is in the common reference string model, and can be instantiated assuming the existence of time-lock puzzles and simulation-extractable (succinct) non-interactive zero-knowledge proofs.

In the context of quantum-resistant cryptography, cryptographic group actions offer an abstraction of isogeny-based cryptography in the Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) setting. In this work, we revisit the security of two previously proposed natural protocols: the Group Action Hashed ElGamal key encapsulation mechanism (GA-HEG KEM) and the Group Action Hashed Diffie-Hellman non-interactive key-exchange (GA-HDH NIKE) protocol. The latter protocol has already been considered to be used in practical protocols such as Post-Quantum WireGuard (S&P '21) and OPTLS (CCS '20).

We prove that active security of the two protocols in the Quantum Random Oracle Model (QROM) inherently relies on very strong variants of the Group Action Strong CDH problem, where the adversary is given arbitrary quantum access to a DDH oracle. That is, quantum accessible Strong CDH assumptions are not only sufficient but also necessary to prove active security of the GA-HEG KEM and the GA-HDH NIKE protocols.

Furthermore, we propose variants of the protocols with QROM security from the classical Strong CDH assumption, i.e., CDH with classical access to the DDH oracle. Our first variant uses key confirmation and can therefore only be applied in the KEM setting. Our second but considerably less efficient variant is based on the twinning technique by Cash et al. (EUROCRYPT '08) and in particular yields the first actively secure isogeny-based NIKE with QROM security from the standard CDH assumption.

Event date: 1 May to 5 May 2023
Submission deadline: 19 October 2022
Notification: 19 January 2023

iTrust is a Cyber Security Research Center in SUTD and a National Satellite of Excellence in Singapore for securing critical infrastructure. iTrust hosts the world-class cyber-physical system (CPS) testbeds for water treatment (SWaT), water distribution (WADI) and power grid (EPIC). iTrust will build a new maritime testbed of shipboard OT systems (MariOT) for cybersecurity research, education, training, live-fire exercise, and technology validation.

We are looking for postdocs / research fellows with expertise on cybersecurity in general and CPS security, applied cryptography, or applied ML in particular. The candidates should have track record of strong R&D capability, with publications at leading security conferences (http://jianying.space/conference-ranking.html).

We are also looking for research assistants / software engineers with strong programming skills and good knowledge of cybersecurity, computer networks and applied ML.

Only **short-listed** candidates will be contacted for interview. Successful candidates will be offered internationally competitive remuneration.

Interested candidates please send your CV to Prof. Jianying Zhou.

Closing date for applications:

Contact: Prof. Jianying Zhou (Email: jianying_zhou@sutd.edu.sg)

More information: http://jianying.space/

Description

IO Global is searching for a Cryptographic Engineer to join their Core Technology team. As Cryptographic Engineer you will have the exciting challenge of working on cutting-edge research and technology focusing on the market’s needs. You will be working with the Cardano-related projects, such as Cardano Core Cryptographic Primitives, Hydra, Mithril or Sidechains.

The Cryptography Engineering team is growing with the goal of bringing recent academic papers into production. In this team, you will work closely with researchers and engineers, being the bridge between both teams. As Cryptography Engineer you are responsible for writing high-quality code. To support you, our products have software architects, product managers, project managers, formal methods specialists, and QA test engineers, with whom you must communicate professionally, effectively, and efficiently.

Your mission

Working with teams across time zones

• Working independently on software development tasks
• Being proactive and requiring minimal supervision or mentoring to complete tasks
• Reviewing specifications produced by architects and formal methods specialists
• Contributing to the design of algorithms
• Troubleshooting, debugging, and upgrading software
• Writing documentation for the code
• Writing technical user manuals
• Understanding complex cryptographic concepts from academic papers
• Bridging ideas from academic papers to production ready systems.

Requirements

Your expertise

• Degree in computer science or mathematics is desirable, but not essential.
• Experience with systems programming (C/C++/Rust)
• Skilled in software development methods such as agile programming and test-driven development
• Experience in developing cryptography protocols would be a bonus, as would blockchain experience.

Location

IOG is a fully distributed organization and therefore this is a remote position. Due to team distribution we are ideally searching for someone in an European timezone.

Closing date for applications:

Contact: marios.nicolaides@iohk.io

More information: https://apply.workable.com/io-global/j/1B3EF63104/

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

Cryptography Research Center

In our connected digital world, secure and reliable cryptography is the foundation of digital information security and data integrity. We address the world’s most pressing cryptographic questions. Our work covers post-quantum cryptography, lightweight cryptography, cloud encryption schemes, secure protocols, quantum cryptographic technologies and cryptanalysis.

Position: Cryptography Hardware Engineer

Designing, implementing and verifying/validating cryptographic hardware cores for FPGAs and/or ASICs

Designing, implementing and verifying/validating cryptographic hardware cores for FPGAs and/or ASICs

Participating in cutting edge research projects

Skills required for the job

Experience with architecture and design of hardware cryptographic accelerators

Strong knowledge of RTL coding, logic design principles along with timing and power implications

Good understanding of a wide range of (synchronous/asynchronous) digital and/or analog circuit design techniques

Hands-on experience with state-of-the-art CAD tools (for FPGAs and/or ASICs)

Experience with advanced CMOS designs - (nice to have)

Knowledge of Verification techniques like Tcl scripts, makefile testing, Cosimulation (UVM flow good to have) - (nice to have)

Understanding of implementation attacks (e.g., side-channel analysis and/or fault injection) and the corresponding countermeasures - (nice to have)

Proven experience (i.e., papers and/or patents) doing academic and/or industrial research

Qualifications

PhD degree in hardware/cryptography engineering (preferred) or BS/MS degree in electrical/electronic/computer engineering or 5+ years of relevant experience in the industry

Closing date for applications:

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

Chakraborty, Prabhakaran, and Wichs (PKC'20) recently introduced a new tag-based variant of lossy trapdoor functions, termed cumulatively all-lossy-but-one trapdoor functions (CALBO-TDFs). Informally, CALBO-TDFs allow defining a public tag-based function with a (computationally hidden) special tag, such that the function is lossy for all tags except when the special secret tag is used. In the latter case, the function becomes injective and efficiently invertible using a secret trapdoor. This notion has been used to obtain advanced constructions of signatures with strong guarantees against leakage and tampering, and also by Dodis, Vaikunthanathan, and Wichs (EUROCRYPT'20) to obtain constructions of randomness extractors with extractor-dependent sources. While these applications are motivated by practical considerations, the only known instantiation of CALBO-TDFs so far relies on the existence of indistinguishability obfuscation.

In this paper, we propose the first two instantiations of CALBO-TDFs based on standard assumptions. Our constructions are based on the LWE assumption with a sub-exponential approximation factor and on the DCR assumption, respectively, and circumvent the use of indistinguishability obfuscation by relying on lossy modes and trapdoor mechanisms enabled by these assumptions.

Randomized cache architectures have proven to significantly increase the complexity of contention-based cache side channel attacks and therefore pre\-sent an important building block for side channel secure microarchitectures. By randomizing the address-to-cache-index mapping, attackers can no longer trivially construct minimal eviction sets which are fundamental for contention-based cache attacks. At the same time, randomized caches maintain the flexibility of traditional caches, making them broadly applicable across various CPU-types. This is a major advantage over cache partitioning approaches.

A large variety of randomized cache architectures has been proposed. However, the actual randomization function received little attention and is often neglected in these proposals. Since the randomization operates directly on the critical path of the cache lookup, the function needs to have extremely low latency. At the same time, attackers must not be able to bypass the randomization which would nullify the security benefit of the randomized mapping. In this paper we propose \cipher (\underline{S}ecure \underline{CA}che \underline{R}andomization \underline{F}unction), the first dedicated cache randomization cipher which achieves low latency and is cryptographically secure in the cache attacker model. The design methodology for this dedicated cache cipher enters new territory in the field of block ciphers with a small 10-bit block length and heavy key-dependency in few rounds.

The random oracle methodology is central to the design of many practical cryptosystems. A common challenge faced in several systems is the need to have a random oracle that outputs from a structured distribution $\mathcal{D}$, even though most heuristic implementations such as SHA-3 are best suited for outputting bitstrings.

Our work explores the problem of sampling from discrete Gaussian (and related) distributions in a manner that they can be programmed into random oracles. We make the following contributions:

-We provide a definitional framework for our results. We say that a sampling algorithm $\mathsf{Sample}$ for a distribution is explainable if there exists an algorithm $\mathsf{Explain}$ where, for a $x$ in the domain, we have that $\mathsf{Explain}(x) \rightarrow r \in \{0,1\}^n$ such that $\mathsf{Sample}(r)=x$. Moreover, if $x$ is sampled from $\mathcal{D}$ the explained distribution is statistically close to choosing $r$ uniformly at random. We consider a variant of this definition that allows the statistical closeness to be a "precision parameter'' given to the $\mathsf{Explain}$ algorithm. We show that sampling algorithms which satisfy our `explainability' property can be programmed as a random oracle.

-We provide a simple algorithm for explaining \emph{any} sampling algorithm that works over distributions with polynomial sized ranges. This includes discrete Gaussians with small standard deviations.

-We show how to transform a (not necessarily explainable) sampling algorithm $\mathsf{Sample}$ for a distribution into a new $\mathsf{Sample}'$ that is explainable. The requirements for doing this is that (1) the probability density function is efficiently computable (2) it is possible to efficiently uniformly sample from all elements that have a probability density above a given threshold $p$, showing the equivalence of random oracles to these distributions and random oracles to uniform bitstrings. This includes a large class of distributions, including all discrete Gaussians.

-A potential drawback of the previous approach is that the transformation requires an additional computation of the density function. We provide a more customized approach that shows the Miccancio-Walter discrete Gaussian sampler is explainable as is. This suggests that other discrete Gaussian samplers in a similar vein might also be explainable as is.

We give algebraic relations among equations of three algebraic modelings for MinRank problem: support minors modeling, Kipnis–Shamir modeling and minors modeling.

Lurk is an in-development, Turing-complete programming language for recursive zk-SNARKs. It is a statically scoped dialect of Lisp, implemented in Rust to support evaluation, proving, and verification in zero-knowledge. Since Lurk is Turing-complete, it can be used (within resource limits) to make and prove arbitrary computational claims without the constraints of traditional fixed-circuit SNARKs. A Rust Cryptography Engineer for Lurk will help drive the development of the Lurk programming language. The ideal candidate for this job will have deep knowledge of zero-knowledge cryptography and experience writing zk-proofs or zk-proof adjacent software in Rust. You can learn more about Lurk at https://github.com/lurk-lang and the Rust implementation at https://github.com/lurk-lang/lurk-rs.

Closing date for applications:

Contact: Luke Sandquist

More information: https://boards.greenhouse.io/protocollabs/jobs/4616824004

We have two PhD positions in Post Quantum Cryptography at UNSW, Sydney funded by the Sydney Quantum Academy (SQA).

1. Post Quantum Cryptography for Blockchains
2. Towards a Quantum-Safe Internet

The scholarships are for a maximum period of 4 years.

Prospective students are expected to have strong mathematical inclination and strong background in data structures, discrete mathematics and algorithms. Candidates with knowledge of cryptography (such as completion of undergraduate/graduate course or research project) will be preferred.

Open to students who have completed a bachelor’s degree or a master’s degree in Computer Science, Mathematics or a related discipline. Candidates in their final year of study are welcome to apply.

SQA Deadline: September 26, 2022.
UNSW Deadline: September 30, 2022.

Closing date for applications:

Contact: Please contact Dr. Sushmita Ruj (Email: Sushmita.ruj@unsw.edu.au) with your CV and transcripts if you are interested.

More information: https://www.sydneyquantum.org/program/sqa-phd-scholarships/

Topic: Remote attack on a quantum key distribution system. Modern-era cryptography is threatened by recent developments in quantum computing. One way of mitigating this threat is quantum cryptography, or more specifically quantum key distribution (QKD) protocol. A QKD system consists in hardware to create and transport quantum states, as well as software to interface quantum hardware with classical communication infrastructure. Literature on attacks is still limited in this field. Examples are Makarov et al., Nature Photon. 2010 and Alléaume et al., Phys. Rev. A 2016. These works mainly concern physical vulnerabilities on the hardware hence they require to gain physical access to the network in order to perform the attack. In an objective of certification and standardisation of future QKD systems, the whole spectrum of vulnerabilities must be studied, including remote attacks. The subject of this post-doc offer aims at finding attacks on a QKD system without physical access to the hardware, as well as suggesting countermeasures. In the target attack scenario, the attacker has no physical access to hardware, but he can leave a third-party software on one of the machines of the QKD system. How the attacker gains access to the machine to drop the software file is out of scope. The objective of this work is to make the third-party software modify the behaviour of physical systems in order to cause a leak of sensitive information or a denial of service. Fully software oriented attacks, such as memory scrapping or random generation weakening, are thus excluded from this work. An example of acceptable attack would be a modification of the clock by the third-party, see Jouguet et al., Phys. Rev. A 2020 (the difference being that clock modification is caused by software instead of hardware). Another possibility would be to change the physical parameters of the QKD system, e.g. by using the API of the pilot component of the system. the post-doc will focus on a specific operational QKD system. Ideal profile: PhD in quantum physics with interest for computer security or the opposite. Useful skills: cryptography; reverse engineering; software development.

Closing date for applications:

Contact: Eleni Diamanti, Laboratoire d’Informatique de Sorbonne Université (LIP6)

Private and Secure Computation on Personal Data The recruited postdoctoral researcher is expected to work on the design of a distributed data vault that can (i) store personal data while keeping it safe from third parties, (ii) support computation on encrypted or otherwise protected personal data to obtain aggregate statistics while respecting the privacy of the individual data items, (iii) provide means to remunerate users that enable computation on their personal data. In particular, we aim to address this challenge by relying on a byzantine-fault tolerant [1,2] decentralized storage platform that can store data reliably in encrypted form. We plan to combine techniques like multiparty computation [3] and homomorphic encryption [4] with technologies like trusted execution environments [5] to enable computation on such encrypted data. This will allow us to address a variety of use cases, such as decentralized [6] and federated machine learning algorithms [7]. The system should also keep track of the usage of personal data to support remuneration schemes. To this end, we plan to leverage our recent theoretical work on lightweight distributed ledgers [8, 9]. The postdoctoral researcher will contribute by performing original research on these topics, and will also participate in the supervision of Masters and PhD students. In doing so, he or she will collaborate with Davide Frey and other members of the WIDE team, as well as with international partners within the SOTERIA project and other related projects. Although teaching is not a requirement, the candidate can also choose to teach relevant courses at the University of Rennes 1 and affiliated institutions.

Closing date for applications:

Contact: Davide Frey

More information: https://recrutement.inria.fr/public/classic/fr/offres/2022-05366

The Theory of Computer Science (TCS) group at the Informatics Institute (IvI) of the University of Amsterdam (UvA) is looking for an excellent candidate for a fully funded PhD position as part of QSI (Quantum-Safe Internet), a Marie Curie Innovative Training Network (MSCA-ITN). The QSI network involves top-ranking partner universities from France, Italy, Germany, the Netherlands, Denmark, Spain, the UK, and Switzerland, as well as industrial partners.

You will conduct research at the intersection of quantum and post-quantum cryptography and publish/ present the results at top venues for research in crypto/ IT Security. You will be supervised by Prof. Christian Schaffner and Dr. Florian Speelman.

We are looking for a candidate with:

• a MSc in computer science, mathematics, or a related field;
• strong academic performance in university-level courses related to cryptography, IT security, theoretical CS, or mathematics;
• professional command of English and good presentation skills;
• compliance with the MSCA-ITN mobility rule: you must not have resided or carried out your main activity (work, studies, etc.) in the Netherlands for more than 12 months in the 36 months immediately before your recruitment date.

Familiarity with provable security and/ or a strong mathematical background are a plus.

We offer:

• Full-time employment for the duration of the PhD
• A well-rounded training offered by the QSI network, covering a range of topics related to secure communications in the quantum era, as well as complementary training intended to enhance your personal development.
• Generous travel budget that allows for, e.g., exposure to different sectors via planned placements and attendance to summer schools.

Closing date for applications:

Contact: Prof. Christian Schaffner

More information: https://vacatures.uva.nl/UvA/job/PhD-Quantum-Cryptography/754463502/