International Association
for Cryptologic Research

Decentralized finance based on blockchain has experienced rapid development. To safeguard the privacy of participants, decentralized anonymous payment (DAP) systems such as ZCash and Zether have emerged. These systems employ cryptographic techniques to conceal the trader addresses and payment amounts. However, this anonymity presents challenges in terms of regulation. To address this issue, we propose the Walsh-DAP (WDAP) scheme, an efficient and generic regulation scheme for decentralized anonymous payments that strikes a balance between regulation and privacy preservation. Our scheme introduces two regulation policies: first, users who have exceeded their spending limits within a certain period will be identified during the regulation process; second, the supervisor possesses the capability to trace any anonymous transaction. To implement regulation effectively, we have designed an innovative commitment scheme, Walsh commitment, which leverages the orthogonal properties of Walsh codes to achieve the features of aggregation and extraction. The supervisor in WDAP only needs to deal with the aggregation result of the Walsh commitments instead of the huge amount of raw transactions information, which greatly increases the efficiency. In a DAP system with 256 users, 10 transaction per second and 30 days as a regulation period, we reduced the communication cost for regulation from 14 GB to 94.20 KB, and the computing cost from $\text{1.6}\times \text{10}^{\text{5}}$ s to 2.17 s. Both improvement is of over five orders of magnitude. We formally discussed the security of the whole system, and verified its feasibility and practicability in the ZCash system.

The Hidden Number Problem (HNP) has been extensively used in the side-channel attacks against (EC)DSA and Diffie-Hellman. The lattice approach is a primary method of solving the HNP. In EUROCRYPT 2021, Albrecht and Heninger constructed a new lattice to solve the HNP, which converts the HNP to the SVP. After that, their approach became the state-of-the-art lattice method of solving the HNP. But Albrecht and Heninger's approach has a high failure rate for solving the HNP with one bit of nonce ($1$-bit HNP) because there are enormous vectors related to the modulus $q$ shorter than the target vector in Albrecht and Heninger's Lattice.

To decrease the number of vectors that are shorter than the target vector and avoid the duplicated reduction, we introduce the modulo-$q$ lattice, a residue class ring of the general lattice modulo $q$, where $q$ is the modulus of the HNP. We present a new sieving algorithm to search for the shortest vectors in the modulo-$q$ lattice. Our algorithm uses built-in modulo $q$ arithmetic and many optimization techniques. As a result, we can solve a general 1-bit HNP ($q=2^{120}$) within 5 days and solve a general 1-bit HNP ($q=2^{128}$) within 17 days.

In the dishonest-majority setting, generic secure multiparty computation (MPC) protocols are fundamentally vulnerable to attacks in which malicious participants learn their outputs and then force the protocol to abort before outputs are delivered to the honest participants. In other words, generic MPC protocols typically guarantee security with abort.

This flavor of security permits denial-of-service attacks in many applications, unless the cheating participants who cause aborts are identified. At present, there is a substantial performance gap between the best known protocols that are secure with non-identifiable abort, and the best known protocols that achieve security with identifiable abort (IA). Known constructions with IA rely on generic zero-knowledge proofs, adaptively secure oblivious transfer (OT) protocols, or homomorphic primitives.

We present a novel approach for realizing functionalities with a weak form of input-revealing IA, which is based on delicate and selective revealing of committed input values. We refer to this new approach as vindicating release. When our approach is applied to several well-known protocols---including a variant of PVW OT, Softspoken OT extension, DKLs multiplication, and MASCOT generic MPC---the resulting protocols can be combined to realize any sampling functionality with (standard) IA. Such a realization is statistically secure given a variant of statically-corruptable ideal OT, and it differs minimally in terms of cost, techniques, and analysis from the equivalent realization (using the same well-known protocols, unmodified) that lacks identifiability.

Using our protocol to sample the correlated randomness of the IOZ compiler reduces the compiler's requirements from an adaptively secure OT protocol to a variant of statically-corruptable ideal OT.

MAYO is a topical modification of the established multivariate signature scheme Unbalanced Oil and Vinegar (UOV), with a significantly reduced public key size while maintaining the appealing properties of UOV, like short signatures and fast verification. Therefore, MAYO is considered an attractive candidate in the NIST standardization process for additional post-quantum signatures and an adequate solution for real-world deployment in resource-constrained devices.

This paper presents the first hardware implementation of the signature scheme MAYO. Our implementation can be easily integrated with different FPGA architectures. Additionally, it includes an agile instantiation with respect to the NIST-defined security levels for long-term security and encompasses modules' optimizations such as the vector-matrix multiplication and the Gaussian elimination method employed during the signing process. Our implementation is tested on the Zynq ZedBoard with the Zynq-7020 SoC and its performance is evaluated and compared to its counterpart multivariate scheme UOV.

Masking is a prominent strategy to protect cryptographic implementations against side-channel analysis. Its popularity arises from the exponential security gains that can be achieved for (approximately) quadratic resource utilization. Many variants of the countermeasure tailored for different optimization goals have been proposed over the past decades. The common denominator among all of them is the implicit demand for robust and high entropy randomness. Simply assuming that uniformly distributed random bits are available, without taking the cost of their generation into account, leads to a poor understanding of the efficiency and performance of secure implementations. This is especially relevant in case of hardware masking schemes which are known to consume large amounts of random bits per cycle due to parallelism. Currently, there seems to be no consensus on how to most efficiently derive many pseudo-random bits per clock cycle from an initial seed and with properties suitable for masked hardware implementations. In this work, we evaluate a number of building blocks for this purpose and find that hardware-oriented stream ciphers like Trivium and its reduced-security variant Bivium B outperform all competitors when implemented in an unrolled fashion. Unrolled implementations of these primitives enable the flexible generation of many bits per cycle while maintaining high performance, which is crucial for satisfying the large randomness demands of state-of-the-art masking schemes. According to our analysis, only Linear Feedback Shift Registers (LFSRs), when also unrolled, are capable of producing long non-repetitive sequences of random-looking bits at a high rate per cycle even more efficiently than Trivium and Bivium B. Yet, these instances do not provide black-box security as they generate only linear outputs. We experimentally demonstrate that using multiple output bits from an LFSR in the same masked implementation can violate probing security and even lead to harmful randomness cancellations. Circumventing these problems, and enabling an independent analysis of randomness generation and masking scheme, requires the use of cryptographically stronger primitives like stream ciphers. As a result of our studies, we provide an evidence-based estimate for the cost of securely generating n fresh random bits per cycle. Depending on the desired level of black-box security and operating frequency, this cost can be as low as 20n to 30n ASIC gate equivalents (GE) or 3n to 4n FPGA look-up tables (LUTs), where n is the number of random bits required. Our results demonstrate that the cost per bit is (sometimes significantly) lower than estimated in previous works, incentivizing parallelism whenever exploitable and potentially moving low randomness usage in hardware masking research from a primary to secondary design goal.

It has been an important research topic to design novel symmetric-key primitives for advanced protocols like secure multiparty computation (MPC), fully homomorphic encryption (FHE) and zero-knowledge proof systems (ZK). Many such existing primitives adopt quite different design strategies from conventional block ciphers. One notable feature is that many of these ciphers are defined over a large finite field and the power map is commonly used to construct the nonlinear component due to its strong resistance against the differential and linear cryptanalysis. In this paper, we target the MPC-friendly ciphers AIM and RAIN used for the post-quantum signature schemes AIMer (CCS 2023 and NIST PQC Round 1 Additional Signatures) and Rainer (CCS 2022), respectively. Specifically, we could find equivalent representations of the 2-round RAIN and the full-round AIM respectively, which make them vulnerable to either the polynomial method or the simplified crossbred algorithm or the fast exhaustive search attack. Consequently, we could break 2-round RAIN with the 128/192/256-bit key in only $2^{116}/2^{171}/2^{224}$ bit operations. For the full-round AIM with the 128/192/256-bit key, we could break them in $2^{136.2}/2^{200.7}/2^{265}$ bit operations, which are equivalent to about $2^{115}/2^{178}/2^{241}$ calls of the underlying primitive.

Shamir’s secret sharing scheme is one of the substantial threshold primitives, based on which many security protocols are constructed such as group authentication schemes. Notwithstanding the unconditional security of Shamir's secret sharing scheme, protocols that are designed based on this scheme do not necessarily inherit this property. In this work, we evaluate the security of a lightweight group authentication scheme, introduced for IoT networks in IEEE IoT Journal in 2020, and prove its weakness against the linear subspace attack, which is a recently-proposed cryptanalytical method for secret sharing-based schemes. Then, we propose an efficient and attack-resistant group authentication protocol for IoT networks.

Unbalanced Oil and Vinegar is a multivariate signature scheme that was introduced in 1999. Most multivariate candidates for signature schemes at NIST's PQC standardization process are either based on UOV or closely related to it. The UOV trapdoor is a secret subspace, the "oil subspace". We show how to recover an equivalent secret key from the knowledge of a single vector in the oil subspace in any characteristic. The reconciliation attack was sped-up by adding some bilinear equations in the subsequent computations, and able to conclude after two vectors were found. We show here that these bilinear equations contain enough information to dismiss the quadratic equations and retrieve the secret subspace with linear algebra for practical parametrizations of UOV, in at most 15 seconds for modern instanciations of UOV.

This proves that the security of the UOV scheme lies in the complexity of finding exactly one vector in the oil space. In addition, we deduce a key recovery attack from any forgery attack by applying a corollary of our main result.

We show how to extend this result to schemes related to UOV, such as MAYO and VOX.

A major challenge of any asynchronous MPC protocol is the need to reach agreement on the set of private inputs to be used as input for the MPC functionality. Ben-Or, Canetti and Goldreich [STOC 93] call this problem Agreement on a Core Set (ACS) and solve it by running $n$ parallel instances of asynchronous binary Byzantine agreements. To the best of our knowledge, all results in the perfect and statistical security setting used this same paradigm for solving ACS. This leads to a fundamental barrier of expected $\Omega(\log n)$ rounds for any asynchronous MPC protocol (even for constant depth circuits).

We provide a new solution for Agreement on a Core Set that runs in expected $O(1)$ rounds, is perfectly secure, and resilient to $t<\frac{n}{4}$ corruptions. Our solution is based on a new notion of Asynchronously Validated Asynchronous Byzantine Agreement (AVABA) and new information theoretic analogs to techniques used in the authenticated model. We show a similar result with statistical security for $t<\frac{n}{3}$.

Deploying cryptography on embedded systems requires security against physical attacks. At CHES 2019, M&M was proposed as a combined countermeasure applying masking against SCAs and information-theoretic MAC tags against FAs. In this paper, we show that one of the protected AES implementations in the M&M paper is vulnerable to a zero-value SIFA2-like attack. A practical attack is demonstrated on an ASIC board. We propose two versions of the attack: the first follows the SIFA approach to inject faults in the last round, while the second one is an extension of SIFA and FTA but applied to the first round with chosen plaintext. The two versions work at the byte level, but the latter version considerably improves the efficiency of the attack. Moreover, we show that this zero-value SIFA2 attack is specific to the AES tower-field decomposed S-box design. Hence, such attacks are applicable to any implementation featuring this AES S-box architecture.

Then, we propose a countermeasure that prevents these attacks. We extend M&M with a fine-grained detection-based feature capable of detecting the zero-value glitch attacks. In this effort, we also solve the problem of a combined attack on the ciphertext output check of M&M scheme by using Kronecker's delta function. We deploy the countermeasure on FPGA and verify its security against both fault and side-channel analysis with practical experiments.

Homomorphic encryption (HE) allows computing encrypted data in the ciphertext domain without knowing the encryption key. It is possible, however, to break fully homomorphic encryption (FHE) algorithms by using side channels. This article demonstrates side-channel leakages of the Microsoft SEAL HE library. The proposed attack can steal encryption keys during the key generation phase by abusing the leakage of ternary value assignments that occurs during the number theoretic transform (NTT) algorithm. We propose two attacks, one for -O0 flag non-optimized code implementation which targets addition and subtraction operations, and one for -O3 flag compiler optimization which targets guard and mul root operations. In particular, the attacks can steal the secret key coefficients from a single power/electromagnetic measurement trace of SEAL’s NTT implementation. To achieve high accuracy with a single-trace, we develop novel machine-learning side-channel profilers. On an ARM Cortex-M4F processor, our attacks are able to extract secret key coefficients with an accuracy of 98.3% when compiler optimization is disabled, and 98.6% when compiler optimization is enabled. We finally demonstrate that our attack can evade an application of the random delay insertion defense.

Mimblewimble is a cryptocurrency protocol with good privacy and scalability properties. A trade-off of Mimblewimble is the requirement that transactions are interactive between sender and receiver. TariScript is presented as an extension to Mimblewimble that adds scripting capabilities to the protocol. We describe the theoretical basis for TariScript and present the modifications required to make it secure. The trade-offs and use cases for TariScript are briefly covered.

The random oracle model (ROM), introduced by Bellare and Rogaway (CCS 1993), enables a formal security proof for many (efficient) cryptographic primitives and protocols, and has been quite impactful in practice. However, the security model also relies on some very strong and non-standard assumptions on how an adversary interacts with a cryptographic hash function, which might be unrealistic in a real world setting and thus could lead one to question the validity of the security analysis. For example, the ROM allows adaptively programming the hash function or observing the hash evaluations that an adversary makes.

We introduce a substantially weaker variant of the random oracle model in the post-quantum setting, which we call "non-observable quantum random oracle model" (NO QROM). Our model uses weaker heuristics than the quantum random oracle model by Boneh, Dagdelen, Fischlin, Lehmann, Schaffner, and Zhandry (ASIACRYPT 2011), or the non-observable random oracle model proposed by Ananth and Bhaskar (ProvSec 2013). At the same time, we show that our model is a viable option for establishing the post-quantum security of many cryptographic schemes by proving the security of important primitives such as extractable non-malleable commitments, digital signatures, and chosen-ciphertext secure public-key encryption in the NO QROM.

We present cryptanalysis of the inhomogenous short integer solution (ISIS) problem for anomalously small moduli \(q\) by exploiting the geometry of BKZ reduced bases of $q$-ary lattices.

We apply this cryptanalysis to examples from the literature where taking such small moduli has been suggested. A recent work [Espitau–Tibouchi–Wallet–Yu, CRYPTO 2022] suggests small \(q\) versions of the lattice signature scheme FALCON and its variant MITAKA.

For one small \(q\) parametrisation of FALCON we reduce the estimated security against signature forgery by approximately 26 bits. For one small \(q\) parametrisation of MITAKA we successfully forge a signature in $15$ seconds.

Column Parity Mixers, or CPMs in short, are a particular type of linear maps, used as the mixing layer in permutation-based cryptographic primitives like Keccak-f (SHA3) and Xoodoo. Although being successfully applied, not much is known regarding their algebraic properties. They are limited to invertibility of CCPMs, and that the set of invertible CCPMs forms a group. A possible explanation is due to the complexity of describing CPMs in terms of linear algebra. In this paper, we introduce a new approach to studying CPMs using module theory from commutative algebra. We show that many interesting algebraic properties can be deduced using this approach, and that known results regarding CPMs turn out to be trivial consequences of module theoretic concepts. We also show how this approach can be used to study the linear layer of Xoodoo, and other linear maps with a similar structure which we call DCD-compositions. Using this approach, we prove that every DCD-composition where the underlying vector space with the same dimension as that of Xoodoo has a low order. This provides a solid mathematical explanation for the low order of the linear layer of Xoodoo, which equals 32. We design a DCD-composition using this module theoretic approach, but with a higher order using a different dimension.

Continuous Group-Key Agreement (CGKA) allows a group of users to maintain a shared key. It is the fundamental cryptographic primitive underlying group messaging schemes and related protocols, most notably TreeKEM, the underlying key agreement protocol of the Messaging Layer Security (MLS) protocol, a standard for group messaging by the IETF. CKGA works in an asynchronous setting where parties only occasionally must come online, and their messages are relayed by an untrusted server. The most expensive operation provided by CKGA is that which allows for a user to refresh their key material in order to achieve forward secrecy (old messages are secure when a user is compromised) and post-compromise security (users can heal from compromise). One caveat of early CGKA protocols is that these update operations had to be performed sequentially, with any user wanting to update their key material having had to receive and process all previous updates. Late versions of TreeKEM do allow for concurrent updates at the cost of a communication overhead per update message that is linear in the number of updating parties. This was shown to be indeed necessary when achieving PCS in just two rounds of communication by [Bienstock et al. TCC'20].

The recently proposed protocol CoCoA [Alwen et al. Eurocrypt'22], however, shows that this overhead can be reduced if PCS requirements are relaxed, and only a logarithmic number of rounds is required. The natural question, thus, is whether CoCoA is optimal in this setting.

In this work we answer this question, providing a lower bound on the cost (concretely, the amount of data to be uploaded to the server) for CGKA protocols that heal in an arbitrary $k$ number of rounds, that shows that CoCoA is very close to optimal. Additionally, we extend CoCoA to heal in an arbitrary number of rounds, and propose a modification of it, with a reduced communication cost for certain $k$.

We prove our bound in a combinatorial setting where the state of the protocol progresses in rounds, and the state of the protocol in each round is captured by a set system, each set specifying a set of users who share a secret key. We show this combinatorial model is equivalent to a symbolic model capturing building blocks including PRFs and public-key encryption, related to the one used by Bienstock et al.

Our lower bound is of order $k\cdot n^{1+1/(k-1)}/\log(k)$, where $2\le k\le \log(n)$ is the number of updates per user the protocol requires to heal. This generalizes the $n^2$ bound for $k=2$ from Bienstock et al. This bound almost matches the $k\cdot n^{1+2/(k-1)}$ or $k^2\cdot n^{1+1/(k-1)}$ efficiency we get for the variants of the CoCoA protocol also introduced in this paper.

Order-preserving encryption (OPE) allows efficient comparison operations over encrypted data and thus is popular in encrypted databases. However, most existing OPE schemes are vulnerable to inference attacks as they leak plaintext frequency. To this end, some frequency-hiding order-preserving encryption (FH-OPE) schemes are proposed and claim to prevent the leakage of frequency. FH-OPE schemes are considered an important step towards mitigating inference attacks.

Unfortunately, there are still vulnerabilities in all existing FH-OPE schemes. In this work, we revisit the security of all existing FH-OPE schemes. We are the first to demonstrate that plaintext frequency hidden by them is recoverable. We present three ciphertext-only attacks named frequency-revealing attacks to recover plaintext frequency. We evaluate our attacks in three real-world datasets. They recover over 90% of plaintext frequency hidden by any existing FH-OPE scheme. With frequency revealed, we also show the potentiality to apply inference attacks on existing FH-OPE schemes.

Our findings highlight the limitations of current FH-OPE schemes. Our attacks demonstrate that achieving frequency-hiding requires addressing the leakages of both non-uniform ciphertext distribution and insertion orders of ciphertexts, even though the leakage of insertion orders is always ignored in OPE.

Public randomness is a fundamental component in many cryptographic protocols and distributed systems and often plays a crucial role in ensuring their security, fairness, and transparency properties. Driven by the surge of interest in blockchain and cryptocurrency platforms and the usefulness of such component in those areas, designing secure protocols to generate public randomness in a distributed manner has received considerable attention in recent years. This paper presents a systematization of knowledge on the topic of public randomness with a focus on cryptographic tools providing public verifiability and key themes underlying these systems. We provide concrete insights on how state-of-the-art protocols achieve this task efficiently in an adversarial setting and present various research gaps that may be suitable for future research.

We present TVA, a multi-party computation (MPC) system for secure analytics on secret-shared time series data. TVA achieves strong security guarantees in the semi-honest and malicious settings, and high expressivity by enabling complex analytics on inputs with unordered and irregular timestamps. TVA is the first system to support arbitrary composition of oblivious window operators, keyed aggregations, and multiple filter predicates, while keeping all data attributes private, including record timestamps and user-defined values in query predicates. At the core of the TVA system lie novel protocols for secure window assignment: (i) a tumbling window protocol that groups records into fixed-length time buckets and (ii) two session window protocols that identify periods of activity followed by periods of inactivity. We also contribute a new protocol for secure division with a public divisor, which may be of independent interest. We evaluate TVA on real LAN and WAN environments and show that it can efficiently compute complex window-based analytics on inputs of $2^{22}$ records with modest use of resources. When compared to the state-of-the-art, TVA achieves up to $5.8\times$ lower latency in queries with multiple filters and two orders of magnitude better performance in window aggregation.

We have several open positions for PhD students and Postdocs to join our group at the Hasso-Plattner-Institute (HPI) in the area of cryptography and privacy. The HPI is academically structured as the independent Faculty of Digital Engineering at the University of Potsdam, and unites excellent research and teaching with the advantages of a privately financed institute.

Your tasks

• Development and analysis of provably secure cryptographic protocols for real-world problems. Topics of interest include (but are not limited to):
  • Privacy-preserving protocols
  • Hardware-based cryptography
  • User- and privacy-friendly identity management
  • Foundations for real-world protocols
• Publish and present results at top-tier international conferences
• Participate in teaching activities

Your skills

• Master's degree (or PhD for postdoctoral position) in Computer Science, Mathematics, or a related area by the time of appointment
• Strong algorithmic or mathematical background and good knowledge in the area of cryptography (for postdoctoral candidates proven in the form of publications)
• Fluent in English

We look forward to your application including a CV and motivation letter. Applications for the PhD position should also include a list of attended Master courses and grades, whereas applications for the Postdoc position should include contact information for two references.

Closing date for applications:

Contact: Anja Lehmann; anja.lehmann [at] hpi.de

More information: https://hpi.de/lehmann/home.html