International Association
for Cryptologic Research

The Department of Computer Science at Durham University is looking for a postdoctoral researcher from 1 Jan 2022 to work on an EPSRC project on topics related to password-hashing algorithms and idealized models of computation for a period of two years. We would be interested in applicants holding (or nearing the completion of) a PhD in Cryptography (or related fields) who have strong interests in the foundational aspects of crypto, proof techniques, and definitional work. Publications at competitive venues and ability to work independently are a plus. Applicants with backgrounds in Algorithms and Complexity are also very welcome to apply.

Durham is one of the top (and oldest) universities in the UK, and the CS department hosts one of the strongest Theory groups in the UK across the ACiD and NESTiD groups. The annual salary for the position is ​​£42,149.

Closing date for applications:

Contact: Pooya Farshim. Please submit a CV containing publications and references.

More information: https://farshim.github.io/

Distributed deep learning frameworks, such as split learning, have recently been proposed to enable a group of participants to collaboratively train a deep neural network without sharing their raw data. Split learning in particular achieves this goal by dividing a neural network between a client and a server so that the client computes the initial set of layers, and the server computes the rest. However, this method introduces a unique attack vector for a malicious server attempting to steal the client's private data: the server can direct the client model towards learning a task of its choice. With a concrete example already proposed, such training-hijacking attacks present a significant risk for the data privacy of split learning clients.

In this paper, we propose SplitGuard, a method by which a split learning client can detect whether it is being targeted by a training-hijacking attack or not. We experimentally evaluate its effectiveness, and discuss in detail various points related to its use. We conclude that SplitGuard can effectively detect training-hijacking attacks while minimizing the amount of information recovered by the adversaries.

How much computational resource do we need for cryptography? This is an important question of both theoretical and practical interests. In this paper, we study the problem on pseudorandom functions (PRFs) in the context of circuit complexity. Perhaps surprisingly, we prove extremely tight upper and lower bounds in various circuit models.

* In general $B_2$ circuits, assuming the existence of PRFs, PRFs can be constructed in $2n + o(n)$ size, simplifying and improving the $O(n)$ bound by Ishai et al. (STOC 2008). We show that such construction is almost optimal by giving an unconditional $2n-O(1)$ lower bound.

* In logarithmic depth circuits, assuming the existence of $NC^1$ PRFs, PRFs can be constructed in $2n + o(n)$ size and $(1+\epsilon) \log n$ depth simultaneously.

* In constant depth linear threshold circuits, assuming the existence of $TC^0$ PRFs, PRFs can be constructed with wire complexity $n^{1+O(1.61^{-d})}$. We also give an $n^{1+\Omega(c^{-d})}$ wire complexity lower bound for some constant $c$.

The upper bounds are proved with generalized Levin's trick and novel constructions of "almost" universal hash functions; the lower bound for general circuits is proved via a tricky but elementary wire-counting argument; and the lower bound for $TC^0$ circuits is proved by extracting a "black-box" property of $TC^0$ circuits from the "white-box" restriction lemma of Chen, Santhanam, and Srinivasan (Theory Comput. 2018). As a byproduct, we prove unconditional tight upper and lower bounds for "almost" universal hashing, which we believe to have independent interests.

Following Natural Proofs by Razborov and Rudich (J. Comput. Syst. Sci. 1997), our results make progress in realizing the difficulty to improve known circuit lower bounds which recently becomes significant due to the discovery of several "bootstrapping results". In $TC^0$, this reveals the limitation of the current restriction-based methods; in particular, it brings new insights in understanding the strange phenomenon of "sharp threshold results" such as the one presented by Chen and Tell (STOC 2019).

In this paper we derive a suit of lemmas which allows users to internally reflect EasyCrypt programs into distributions which correspond to their denotational semantics (probabilistic reflection). Based on this we develop techniques for reasoning about rewinding of adversaries in EasyCrypt. (A widely used technique in cryptology.) We use reflection and rewindability results to prove the security of a coin-toss protocol.

Proof of reserves protocols enable cryptocurrency exchanges to prove solvency, i.e. prove that they have enough reserves to meet their liabilities towards their customers. MProve (EuroS&PW, 2019) was the first proof of reserves protocol for Monero which provided some privacy to the exchanges’ addresses. As the key images and the addresses are inherently linked in the MProve proof, an observer could easily recognize the exchange-owned address when a transaction spending from it appears on the blockchain. This is detrimental for an exchange’s privacy and becomes a natural reason for exchanges to not adopt MProve. To this end, we propose MProve+, a Bulletproofs- based (S&P, 2018) NIZK protocol, which unlinks the key images and the addresses, thus alleviating the drawback of MProve. Furthermore, MProve+ presents a promising alternative to MProve due to an order of magnitude smaller proof sizes along with practical proof generation and verification times.

A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity, ${\rm K}^t$, is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures: * We show, perhaps surprisingly, that the $\rm KT$ complexity is bounded-error average-case hard if and only if there exist one-way functions in *constant parallel time* (i.e., ${\sf NC}^0$). This result crucially relies on the idea of *randomized encodings*. Previously, a seminal work of Applebaum, Ishai, and Kushilevitz (FOCS'04; SICOMP'06) used the same idea to show that ${\sf NC}^0$-computable one-way functions exist if and only if logspace-computable one-way functions exist. * Inspired by the above result, we present randomized average-case reductions among the ${\sf NC}^1$-versions and logspace-versions of ${\rm K}^t$ complexity, and the $\rm KT$ complexity. Our reductions preserve both bounded-error average-case hardness and zero-error average-case hardness. To the best of our knowledge, this is the first reduction between the $\rm KT$ complexity and a variant of ${\rm K}^t$ complexity. * We prove tight connections between the hardness of ${\rm K}^t$ complexity and the hardness of (the hardest) one-way functions. In analogy with the Exponential-Time Hypothesis and its variants, we define and motivate the *Perebor Hypotheses* for complexity measures such as ${\rm K}^t$ and $\rm KT$. We show that a Strong Perebor Hypothesis for ${\rm K}^t$ implies the existence of (weak) one-way functions of near-optimal hardness $2^{n-o(n)}$. To the best of our knowledge, this is the first construction of one-way functions of near-optimal hardness based on a natural complexity assumption about a search problem. * We show that a Weak Perebor Hypothesis for ${\rm MCSP}$ implies the existence of one-way functions, and establish a partial converse. This is the first unconditional construction of one-way functions from the hardness of ${\rm MCSP}$ over a natural distribution. * Finally, we study the average-case hardness of ${\rm MKtP}$. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.

The paper provides a complete description of the digital signature scheme based on the Stern identification protocol. We also present the proof of the existential unforgeability of the scheme under the chosen message attack (EUF-CMA) in the random oracle model (ROM) under assumptions of hardness of syndrome decoding and hash function collision finding problems. Finally, we discuss the choice of the signature parameters and introduce a parameter set providing 80-bit security.

Training deep neural networks requires large scale data, which often forces users to work in a distributed or outsourced setting, accompanied with privacy concerns. Split learning framework aims to address this concern by splitting up the model among the client and the server. The idea is that since the server does not have access to client's part of the model, the scheme supposedly provides privacy. We show that this is not true via two novel attacks. (1) We show that an honest-but-curious split learning server, equipped only with the knowledge of the client neural network architecture, can recover the input samples and also obtain a functionally similar model to the client model, without the client being able to detect the attack. (2) Furthermore, we show that if split learning is used naively to protect the training labels, the honest-but-curious server can infer the labels with perfect accuracy. We test our attacks using three benchmark datasets and investigate various properties of the overall system that affect the attacks' effectiveness. Our results show that plaintext split learning paradigm can pose serious security risks and provide no more than a false sense of security.

Chats have become an essential means of interpersonal interaction. Yet untraceable private communication remains an elusive goal, as most messengers hide content, but not communication patterns. The knowledge of communication patterns can by itself reveal too much, as happened e.g., in the context of the Arab Spring. The subliminal channel in cryptographic systems - as introduced by Simmons in his pioneering works - enables untraceable private communication in plain sight. In this context, blockchains are a natural object for subliminal communication: accessing them is innocuous, as they rely on distributed access for verification and extension. At the same time, blockchain transactions generate hundreds of thousands transactions per day that are individually signed and placed on the blockchain. This significantly increases the availability of publicly accessible cryptographic transactions where subliminal channels can be placed. In this paper we propose a public-key subliminal channel using ECDSA signatures on blockchains and prove that our construction is undetectable in the random oracle model under a common cryptographic assumption. While our approach is applicable to any blockchain platform relying on (variants of) ECDSA signatures, we present a proof of concept of our method for the popular Bitcoin protocol and show the simplicity and practicality of our approach.

We present an implementation of the hash-based post-quantum signature scheme SPHINCS+ that enables heavily memory-restricted devices to sign messages by streaming-out a signature during its computation and to verify messages by streaming-in a signature. We demonstrate our implementation in the context of Trusted Platform Modules (TPMs) by proposing a SPHINCS+ integration and a streaming extension for the TPM specification. We evaluate the overhead of our signature-streaming approach for a stand-alone SPHINCS+ implementation and for its integration in a proof-of-concept TPM with the proposed streaming extension running on an ARM Cortex-M4 platform. Our streaming interface greatly reduces the memory requirements without introducing a significant performance penalty. This is achieved not only by removing the need to store an entire signature but also by reducing the stack requirements of the key generation, sign, and verify operations. Therefore, our streaming interface enables small embedded devices that do not have sufficient memory to store an entire SPHINCS+ signature or that previously were only able to use a parameter set that results in smaller signatures to sign and verify messages using all SPHINCS+ variants. Since the streaming concept aggravates fault attacks on hash-based signature schemes, we briefly discuss countermeasures to attenuate such attacks in a signature-streaming scenario.

The BeleniosVS electronic voting scheme offers an attractive mix of verifiability and privacy properties. Moreover, using the ProVerif protocol-verification tool, BeleniosVS has automatic machine-aided analysis of (end-to-end) verifiability in 96 different threat models with the machine-aided analysis finding proofs in 22 cases and finding attacks in the remaining 74 cases. The high number of threat models covered by ProVerif delivers a much richer security analysis than the norm.

We revisit the BeleniosVS scheme and propose several refinements to the ProVerif security model and scheme which increase the number of threat models in which the scheme has verifiability from 22 to 28. Our new ProVerif security model also implies end-to-end verifiability but the requirements are easier to satisfy. Interestingly, in all six improvements, both the changes to the security model and one or more changes to the scheme are necessary to prove verifiability.

In this paper, we present a new secret trapdoor function for the design of multivariate schemes that we call ``Onyx'', suitable for encryption and signature. It has been inspired by the schemes presented in Ariadne Thread and Pepper: New mul-tivariate cryptographic schemes with public keys in degree 3. . From this idea, we present some efficient encryption and signature multivariate schemes with explicit parameters that resist all known attacks. In particular they resist the two main (and often very powerful) attacks in this area: the Gröbner attacks (to compute a solution of the system derived from the public key) and the MinRank attacks (to recover the secret key). Specific attacks due to the properties of the function and its differential are also addressed in this paper. The ``Onyx'' schemes have public key equations of degree 3. Despite this, the size of the public key may still be reasonable since we can use larger fields and smaller extension degrees. Onyx signatures can be as short as the ``birthday paradox'' allows, i.e. twice the security level, or even shorter thanks to the Feistel-Patarin construction, like many other signatures schemes based on multivariate equations.

This paper describes Djed, an algorithmic stablecoin protocol that behaves like an autonomous bank that buys and sells stablecoins for a price in a range that is pegged to a target price. It is crypto-backed in the sense that the bank keeps a volatile cryptocurrency in its reserve. The reserve is used to buy stablecoins from users that want to sell them. And revenue from sales of stablecoins to users are stored in the reserve. Besides stablecoins, the bank also trades reservecoins in order to capitalize itself and maintain a reserve ratio significantly greater than one. To the best of our knowledge, this is the first stablecoin protocol where stability claims are precisely and mathematically stated and proven. Furthermore, the claims and their proofs are formally verified using two different techniques: bounded model checking, to exhaustively search for counter-examples to the claims; and interactive theorem proving, to build rigorous formal proofs using a proof assistant with automated theorem proving features.

We construct a simple public-coin zero-knowledge proof system solely based on symmetric primitives, from which we can apply the Fiat-Shamir heuristic to make it non-interactive. Our construction can be regarded as a simplified cut-and-choose-based malicious secure twoparty computation for the zero-knowledge functionality. Our protocol is suitable for pedagogical purpose for its simplicity (code is only 728 lines).

Physically Unclonable Functions (PUFs) and True Random Number Generators (TRNGs) are two highly useful hardware primitives to build up the root-of-trust for an embedded device. PUFs are designed to offer repetitive and instance-specific randomness, whereas TRNGs are expected to be invariably random. In this paper, we present a dual-mode PUF-TRNG design that utilises two different hardware-intrinsic properties, i.e. oscillation frequency of the Transition Effect Ring Oscillator (TERO) cell and the propagation delay of a buffer within the cell to serve the purpose of both PUF and TRNG depending on the exact requirement of the application. The PUF design is also proposed to have a built-in resistance to machine learning (ML) and deep learning (DL) attacks, whereas the TRNG exhibits sufficient randomness.

This paper introduces the concept of information with a foreseeable lifespan and explains who to achieve this primitive via a new method for encoding and storing information in DNA-RNA sequences.

The storage process can be divided into three time-frames. Within the first (life), we can easily read out the stored data with high probability. The second time-frame (agony) is a parameter-dependent state of uncertainty; the data is not easily accessible, but still cannot be guaranteed to be inaccessible. During the third (death), the data can with high probability not be recovered without a large computational effort which can be controlled via a security parameter. The quality of such a system, in terms of a foreseeable lifespan, depends on the brevity of the agony time-frame, and we show how to optimise this.

In the present paper, we analyse the use of synthetic DNA and RNA as a storage medium since it is a suitable information carrier and we can manipulate the RNA nucleotide degradation rate to help control the lifespan of the message embedded in the synthesized DNA/RNA molecules. Other media such as Bisphenol A thermal fax paper or unstable nonvolatile memory technologies can be used to implement the same principle but the decay models of each of those phenomena should be re-analysed and the formulae given in this paper adapted correspondingly.

Open vote network is a secure multi-party protocol allowing to compute a sum of integer votes without revealing their values. As such, it has several applications in social choice and financial applications.

An inherent limitation of OV-Net is its lack of robustness against denial-of-service attacks, which occur when at least one of the voters initiates the protocol but (maliciously or accidentally) does not complete it. Unfortunately such a situation is very likely to occur in any real-world implementation of the protocol. This will cost serious time delays from either waiting for the failing parties and perhaps having to perform extra protocol rounds with the remaining participants.

This paper provides a solution to this problem by extending OV-Net with mechanisms tolerating a number of unresponsive participants. The price to pay is a carefully controlled privacy loss, an increase in computation, and a statistical loss in the accuracy.

Two main classes of optical TEMPEST attacks against the confidentiality of information processed/delivered by devices have been demonstrated in the past two decades; the first class includes methods for recovering content from monitors, and the second class includes methods for recovering keystrokes from physical and virtual keyboards. In this paper, we identify a new class of optical TEMPEST attacks: recovering sound by analyzing optical emanations from a device’s power indicator LED. We analyze the response of the power indicator LED of various devices to sound and show that there is an optical correlation between the sound that is played by connected speakers and the intensity of their power indicator LED due to the facts that: (1) the power indicator LED of various devices is connected directly to the power line, (2) the intensity of a device’s power indicator LED is correlative to the power consumption, and (3) many devices lack a dedicated means of countering this phenomenon. Based on our findings, we present the Glowworm attack, an optical TEMPEST attack that can be used by eavesdroppers to recover sound by analyzing optical measurements obtained via an electro-optical sensor directed at the power indicator LED of various devices (e.g., speakers, USB hub splitters, and microcontrollers). We propose an optical-audio transformation (OAT) to recover sound in which we isolate the speech from optical measurements obtained by directing an electro-optical sensor at a device’s power indicator LED Finally, we test the performance of the Glowworm attack in various experimental setups and show that an eavesdropper can apply the attack to recover speech from speakers’ power LED indicator with good intelligibility from a distance of 15 meters and with fair intelligibility from 35 meters.

The Institute of Information Security and the Perceptual User Interfaces Group at University of Stuttgart, Germany invite applications for a PhD position on "Privacy-Preserving Attentive User Interfaces" at the intersection of Security/Privacy/Cryptography, Machine Learning, and Human-Computer Interaction.

Apply if you belong to the top 5% of students in your peer group, are highly motivated and capable of addressing and solving scientifically challenging problems, and if you are interested in doing research in an internationally oriented, interdisciplinary, and highly successful team. We value strong analytical skills. Knowledge of cryptography, in particular, privacy enhancing technologies such as Multi Party Computation and Differential Privacy, is an asset. Knowledge of German is not required.

The University of Stuttgart is an equal opportunity employer. Applications from women are strongly encouraged. Severely challenged persons will be given preference in the case of equal qualifications.

To apply, please send email with subject "PhD position: Privacy-Preserving Attentive User Interfaces" and a single PDF file containing the following documents to ralf.kuesters@sec.uni-stuttgart.de:

• Cover letter (explaining your scientific background and your motivation to apply)
• Curriculum Vitae
• List of publications (if any)
• Copies of transcripts and certificates (Bachelor and Master)
• Names and contact addresses of at least two references

The deadline for applications is

September 12th, 2021.

Late applications will be considered until the position is filled.

See https://sec.uni-stuttgart.de/ for more information about the Institute of Information Security (Prof. Küsters) and http://www.perceptualui.org/ for the Perceptual User Interfaces Group (Prof. Bulling).

Closing date for applications:

Contact: Prof. Dr. Ralf Küsters

ralf.kuesters@sec.uni-stuttgart.de

More information: https://sec.uni-stuttgart.de/

Join https://ist.ac.at/en/research/kokoris-group/ and work on decentralized systems. This position is in support of the Marie Skłodowska-Curie fellowship and is intended to support candidates in order to either strengthen their academic profile or pivot their career towards entrepreneurship or social impact. More info at https://ist.ac.at/en/education/postdocs/ist-bridge/ Deadlines: 05/11/21 – 05/05/22 – 05/11/22 – 05/05/23 – 05/11/23 Competitive salary and full social coverage.

Closing date for applications:

Contact: Lefteris Kokoris-Kogias

More information: https://twitter.com/LefKok/status/1427299702530363405