International Association
for Cryptologic Research

In this paper, we construct an efficient interactive proof system for the graph 3-coloring problem and shows that it is computationally zero-knowledge against a quantum malicious verifier. Our protocol is inline with the sketch of an efficient protocol by Brassard and Crepéau (FOCS 1986) that later has been elaborated by Kilian (STOC 1992). Their protocol is not post-quantum secure since its soundness property holds based on the intractability of the factoring problem. Putting aside the post-quantum security, we argue that Kilian's interactive protocol for the graph 3-coloring problem does not fulfill the soundness property even in the classical setting.

In this paper, we propose an XOR-homomorphic commitment scheme based on the Learning Parity with Noise (LPN) problem and use it to construct an efficient quantum computationally zero-knowledge interactive proof system for the graph 3-coloring problem.

Integral cryptanalysis is a powerful tool for attacking symmetric primitives, and division property is a state-of-the-art framework for finding integral distinguishers.

This work describes new theoretical and practical insights into traditional bit-based division property. We focus on analyzing and exploiting monotonicity/convexity of division property and its relation to the graph indicator. In particular, our investigation leads to a new compact representation of propagation, which allows CNF/MILP modeling for larger S-Boxes, such as 16-bit Super-Sboxes of lightweight block ciphers or even 32-bit random S-boxes. This solves the challenge posed by Derbez and Fouque (ToSC 2020), who questioned the possibility of SAT/SMT/MILP modeling of 16-bit Super-Sboxes. As a proof-of-concept, we model the Super-Sboxes of the 8-round LED by CNF formulas, which was not feasible by any previous approach.

Our analysis is further supported by an elegant algorithmic framework. We describe simple algorithms for computing division property of a set of $n$-bit vectors in time $O(n2^n)$, reducing such sets to minimal/maximal elements in time $O(n2^n)$, computing division property propagation table of an $n\times m$-bit S-box and its compact representation in time $O((n+m)2^{n+m})$. In addition, we develop an advanced algorithm tailored to "heavy" bijections, allowing to model, for example, a randomly generated 32-bit S-box.

Recently, the application of multi-party secure computing schemes based on homomorphic encryption in the field of machine learning attracts attentions across the research fields. Previous studies have demonstrated that secure protocols adopting packed additive homomorphic encryption (PAHE) schemes based on the ring learning with errors (RLWE) problem exhibit significant practical merits, and are particularly promising in enabling efficient secure inference in machine-learning-as-a-service applications. In this work, we introduce a new technique for performing homomorphic linear transformation (HLT) over PAHE ciphertexts. Using the proposed HLT technique, homomorphic convolutions and inner products can be executed without the use of number theoretic transform and the rotate-and-add algorithms that were proposed in existing works. To maximize the efficiency of the HLT technique, we propose APAS, a hardware-software co-design framework consisting of approximate arithmetic units for the hardware acceleration of HLT. In the experiments, we use actual neural network architectures as benchmarks to show that APAS can improve the computational and communicational efficiency of homomorphic convolution by 8x and 3x, respectively, with an energy reduction of up to 26x as compared to the ASIC implementations of existing methods.

A large number of the symmetric-key mode of operations, such as classical CBC-MAC, have serial structures. While a serial mode gives an implementation advantage in terms of required memory or footprint compared to the parallel counterparts, it wastes the capability of parallel process even when it is available. The problem is becoming more relevant as lightweight cryptography is going to be deployed in the real world. In this article, we propose an alternative implementation strategy for serial MAC modes and serial authenticated encryption (AE) modes that allows 2-block parallel operation for verification/decryption. Our proposal maintains the original functionality and security. It is simple yet novel, and generally applicable to a wide range of existing modes including two NIST recommendations, CMAC and CCM. We demonstrate the effectiveness of our proposal by showing several case studies with software implementations.

Recent Bitcoin attacks [CCS'21, CCS'21, ICDCS'19] commonly exploit the phenomenon of so-called weak block synchronization in Bitcoin. The attacks use two independently-operated Bitcoin monitors — i.e., Bitnodes and a system of customized supernodes — to confirm that block propagation in Bitcoin is surprisingly slow. In particular, Bitnodes constantly reports that around 30% of nodes are 3 blocks (or more) behind the blockchain tip and the supernodes show that on average more than 60% of nodes do not receive the latest block even after waiting for 10 minutes. In this paper, we carefully re-evaluate these controversial claims with our own experiments in the live Bitcoin network and show that block propagation in Bitcoin is, in fact, fast enough (e.g., most peers we monitor receive new blocks in about 4 seconds) for its safety property. We identify several limitations and bugs of the two monitors, which have led to these inaccurate claims about the Bitcoin block synchronization. We finally ask several open-ended questions regarding the technical and ethical issues around monitoring blockchain networks.

We propose the use of Hensel codes (a mathematical tool lifted from the theory of $p$-adic numbers) as an alternative way to construct fully homomorphic encryption (FHE) schemes that rely on the hardness of some instance of the approximate common divisor (AGCD) problem. We provide a self-contained introduction to Hensel codes which covers all the properties of interest for this work. Two constructions are presented: a private-key leveled FHE scheme and a public-key leveled FHE scheme. The public-key scheme is obtained via minor modifications to the private-key scheme in which we explore asymmetric properties of Hensel codes. The efficiency and security (under an AGCD variant) of the public-key scheme are discussed in detail. Our constructions take messages from large specialized subsets of the rational numbers that admit fractional numerical inputs and associated computations for virtually any real-world application. Further, our results can be seen as a natural unification of error-free computation (computation free of rounding errors over rational numbers) and homomorphic encryption. Experimental results indicate the scheme is practical for a large variety of applications.

Existing oblivious storage systems provide strong security by hiding access patterns, but do not scale to sustain high throughput as they rely on a central point of coordination. To overcome this scalability bottleneck, we present Snoopy, an object store that is both oblivious and scalable such that adding more machines increases system throughput. Snoopy contributes techniques tailored to the high-throughput regime to securely distribute and efficiently parallelize every system component without prohibitive coordination costs. These techniques enable Snoopy to scale similarly to a plaintext storage system. Snoopy achieves 13.7x higher throughput than Obladi, a state-of-the-art oblivious storage system. Specifically, Obladi reaches a throughput of 6.7K requests/s for two million 160-byte objects and cannot scale beyond a proxy and server machine. For the same data size, Snoopy uses 18 machines to scale to 92K requests/s with average latency under 500ms.

In 2014, the author conceived of a quantal version of the classical cryptographic Diffie-Hellman key exchange protocol. However, the paper was declined to be published (by a not disclosed journal). No further publication attempts were made by the author. In the time afterwards, the aforementioned idea was conceived by others as well, resulting in a number of publications regarding this topic and even slight improvements. Thereby underlining the significance of the author's original idea, despite of being rejected by peer reviewed journals. The paper at hand therefore serves two purposes: First, it might serve others (especially young researchers) as an example to not feel discouraged by publication refusals, if they truly deem them as important novelties. Second, it provides an easy to understand introduction to grasp the concept of a quantum Diffie-Hellman key exchange. All of the following paragraphs, including the remainder of this abstract, are taken from the original 2014 publication attempt and are unchanged in comparison to the 2014 original:

In this work, a quantal version of the classical cryptographic Diffie-Hellman key exchange protocol is introduced. It is called Quantum Diffie-Hellman key exchange. Unlike for the existing quantum key distribution protocols, actual quantum states, and not their measurement outcomes, are regarded as finally exchanged keys/information. By implementation of that quantal Diffie-Hellman version, both communication parties in the end are in possession of identically prepared, and secret quantum states. Thus the cryptographically important principle of forward secrecy is now available in a quantum physical framework. As a merit of the quantum setting, an improvement of the classical Diffie-Hellman protocol is also achieved, as neither of the two parties exactly know the final, exchanged states.

The discipline of reverse engineering integrated circuits (ICs) is as old as the technology itself. It grew out of the need to analyze competitor’s products and detect possible IP infringements. In recent years, the growing hardware Trojan threat motivated a fresh research interest in the topic. The process of IC reverse engineering comprises two steps: netlist extraction and specification discovery. While the process of netlist extraction is rather well understood and established techniques exist throughout the industry, specification discovery still presents researchers with a plurality of open questions. It therefore remains of particular interest to the scientific community. In this paper, we present a survey of the state of the art in IC reverse engineering while focusing on the specification discovery phase. Furthermore, we list noteworthy existing works on methods and algorithms in the area and discuss open challenges as well as unanswered questions. Therefore, we observe that the state of research on algorithmic methods for specification discovery suffers from the lack of a uniform evaluation approach. We point out the urgent need to develop common research infrastructure, benchmarks, and evaluation metrics.

Over the last decade attacks have repetitively demonstrated that bitstream protection for SRAM-based FPGAs is a persistent problem without a satisfying solution in practice. Hence, real-world hardware designs are prone to intellectual property infringement and malicious manipulation as they are not adequately protected against reverse-engineering.

In this work, we first review state-of-the-art solutions from industry and academia and demonstrate their ineffectiveness with respect to reverse-engineering and design manipulation. We then describe the design and implementation of novel hardware obfuscation primitives based on the intrinsic structure of FPGAs. Based on our primitives, we design and implement LifeLine, a hardware design protection mechanism for FPGAs using hardware/software co-obfuscated cryptography. We show that LifeLine offers effective protection for a real-world adversary model, requires minimal integration effort for hardware designers, and retrofits to already deployed (and so far vulnerable) systems.

In this paper, we perform a comprehensive evaluation on blockchain sharding protocols. We deconstruct the blockchain sharding protocol into four foundational layers with orthogonal functionalities, securing some properties. We evaluate each layer of seven state-of-the-art blockchain sharding protocols, and identify a considerable number of new attacks, questionable design trade-offs and some open challenges. The layered evaluation allows us to unveil security and performance problems arising from a fundamental design choice, namely the coherence of system settings across layers. In particular, most sharded blockchains use different trust and synchrony assumptions across layers, without corresponding architectural guarantees. Unless a hybrid architecture were used, assuming differentiated system settings across layers can introduce subtle but severe failure syndromes or reduce the system’s performance.

We study the effects of the XOR transformation, that is, $f^{\oplus 2}(x_1,x_2):= f(x_1)\oplus f(x_2)$, on one-wayness. More specifically, we present an example showing that if one-way functions exist, there also exists a one-way function $f$ such that $f^{\oplus 2}$ is not even a distributional one-way function, demonstrating that one-wayness may severely deteriorate.

Assume that $X_0,X_1$ (respectively $Y_0,Y_1$) are $d_X$ (respectively $d_Y$) indistinguishable for circuits of a given size. It is well known that the product distributions $X_0Y_0,\,X_1Y_1$ are $d_X+d_Y$ indistinguishable for slightly smaller circuits. However, in probability theory where unbounded adversaries are considered through statistical distance, it is folklore knowledge that in fact $X_0Y_0$ and $X_1Y_1$ are $d_X+d_Y-d_X\cdot d_Y$ indistinguishable, and also that this bound is tight.

We formulate and prove the computational analog of this tight bound. Our proof is entirely different from the proof in the statistical case, which is non-constructive. As a corollary, we show that if $X$ and $Y$ are $d$ indistinguishable, then $k$ independent copies of $X$ and $k$ independent copies of $Y$ are almost $1-(1-d)^k$ indistinguishable for smaller circuits, as against $d\cdot k$ using the looser bound. Our bounds are useful in settings where only weak (i.e. non-negligible) indistinguishability is guaranteed. We demonstrate this in the context of cryptography, showing that our bounds yield simple analysis for amplification of weak oblivious transfer protocols.

Repeated Modular Squaring is a versatile computational operation that has led to practical constructions of timed-cryptographic primitives like time-lock puzzles (TLP) and verifiable delay functions (VDF) that have a fast growing list of applications. While there is a huge interest for timed-cryptographic primitives in the blockchains area, we find two real-world concerns that need immediate attention towards their large-scale practical adoption: Firstly, the requirement to constantly perform computations seems unrealistic for most of the users. Secondly, choosing the parameters for the bound $T$ seems complicated due to the lack of heuristics and experience.

We present Opensquare, a decentralized repeated modular squaring service, that overcomes the above concerns. Opensquare lets clients outsource their repeated modular squaring computation via smart contracts to any computationally powerful servers that offer computational services for rewards in an unlinkable manner. Opensquare naturally gives us publicly computable heuristics about a pre-specified number ($T$) and the corresponding reward amounts of repeated squarings necessary for a time period. Moreover, Opensquare rewards multiple servers for a single request, in a sybil resistant manner to incentivise maximum server participation and is therefore resistant to censorship and single-points-of failures. We give game-theoretic analysis to support the mechanism design of Opensquare: (1) incentivises servers to stay available with their services, (2) minimizes the cost of outsourcing for the client, and (3) ensures the client receives the valid computational result with high probability. To demonstrate practicality, we also implement Opensquare's smart contract in Solidity and report the gas costs for all of its functions. Our results show that the on-chain computational costs for both the clients and the servers are quite low, and therefore feasible for practical deployments and usage.

The chair for Security Engineering at Ruhr University Bochum, Germany, is seeking for PhD students and Post-Docs in the areas of cryptographic hardware/software, side-channel analysis, FPGA security, etc.

For PhD positions, candidates must hold an MSc (or equivalent) in computer engineering, electrical engineering or computer science. The candidates are required to have outstanding grades.

For Post-Doc positions, candidates must hold a PhD in computer engineering, electrical engineering or computer science. Furthermore, they must have a demonstrated record of top-quality research in foundations of cryptographic hardware and embedded systems. This is usually proved by publications in IACR conferences, particularly CHES.

Please send your application per email (as a single PDF) to Amir Moradi (amir.moradi at rub.de). The application should include a full CV, a cover letter motivating you application, a short description of your two best research articles (for Post-Doc positions). Review of applications will begin immediately and will continue until the positions are filled, the starting date is flexible.

Closing date for applications:

Contact: Amir Moradi

More information: https://www.seceng.rub.de/moradi

Timed commitments [Boneh and Naor, CRYPTO 2000] are the timed analogue of standard commitments, where the commitment can be non-interactively opened after a pre-specified amount of time passes. Timed commitments have a large spectrum of applications, such as sealed bid auctions, fair contract signing, fair multi-party computation, and cryptocurrency payments. Unfortunately, all practical constructions rely on a (private-coin) trusted setup and do not scale well with the number of participants. These are two severe limiting factors that have hindered the widespread adoption of this primitive.

In this work, we set out to resolve these two issues and propose an efficient timed commitment scheme that also satisfies the strong notion of CCA-security. Specifically, our scheme has a transparent (i.e. public-coin) one-time setup and the amount of sequential computation is essentially independent of the number of participants. As a key technical ingredient, we propose the first (linearly) homomorphic time-lock puzzle with a transparent setup, from class groups of imaginary quadratic order. To demonstrate the applicability of our scheme, we use it to construct a new distributed randomness generation protocol, where $n$ parties jointly sample a random string. Our protocol is the first to simultaneously achieve (1) high scalability in the number of participants, (2) transparent one-time setup, (3) lightning speed in the optimistic case where all parties are honest, and (4) ensure that the output random string is unpredictable and unbiased, even when the adversary corrupts $n-1$ parties. To substantiate the practicality of our approach, we implemented our protocol and our experimental evaluation shows that it is fast enough to be used in practice. We also evaluated a heuristic version of the protocol that is at least 3 orders of magnitude more efficient both in terms of communication size and computation time. This makes the protocol suitable for supporting hundreds of participants.

Number-theoretic algorithms often need to calculate one or both of two related quantities: modular inversion and Jacobi symbol. These two functions seem unrelated at first glance, but in fact the algorithms for calculating them are closely related: they can both be calculated either by variants of Euclid's GCD algorithm, or when the modulus is prime, by exponentiation. As a result, an implementation of one algorithm can often be adapted to compute the other instead, or they can even be calculated together in a batch.

The Bernstein-Yang right-to-left modular inversion algorithm is notable for taking constant, asymptotically subquadratic time. Right-to-left algorithms are tricky to adapt for the Jacobi symbol, because they do not consider the signs of the values being operated on. But the Jacobi symbol is defined only on positive integers, and the rules for computing it need corrections if negative integers are introduced.

In this short paper, we show how to overcome this difficulty and produce a right-to-left Jacobi symbol algorithm based on Bernstein-Yang.

The goal of the bounded storage model (BSM) is to construct unconditionally secure cryptographic protocols, by only restricting the storage capacity of the adversary, but otherwise giving it unbounded computational power. Here, we consider a streaming variant of the BSM, where honest parties can stream huge amounts of data to each other so as to overwhelm the adversary's storage, even while their own storage capacity is significantly smaller than that of the adversary. Prior works showed several impressive results in this model, including key agreement and oblivious transfer, but only as long as adversary's storage $m = O(n^2)$ is at most quadratically larger than the honest user storage $n$. Moreover, the work of Dziembowski and Maurer (DM) also gave a seemingly matching lower bound, showing that key agreement in the BSM is impossible when $m > n^2$.

In this work, we observe that the DM lower bound only applies to a significantly more restricted version of the BSM, and does not apply to the streaming variant. Surprisingly, we show that it is possible to construct key agreement and oblivious transfer protocols in the streaming BSM, where the adversary's storage can be significantly larger, and even exponential $m = 2^{O(n)}$. The only price of accommodating larger values of $m$ is that the round and communication complexities of our protocols grow accordingly, and we provide lower bounds to show that an increase in rounds and communication is necessary.

As an added benefit of our work, we also show that our oblivious transfer (OT) protocol in the BSM satisfies a simulation-based notion of security. In contrast, even for the restricted case of $m = O(n^2)$, prior solutions only satisfied a weaker indistinguishability based definition. As an application of our OT protocol, we get general multiparty computation (MPC) in the BSM that allows for up to exponentially large gaps between $m$ and $n$, while also achieving simulation-based security.

A randomness encoder is a generalization of encoding schemes with an efficient procedure for encoding \emph{uniformly random strings}. In this paper we continue the study of randomness encoders that additionally have the property of being continuous non-malleable. The beautiful notion of non-malleability for encoding schemes, introduced by Dziembowski, Pietrzak and Wichs (ICS’10), states that tampering with the codeword can either keep the encoded message identical or produce an uncorrelated message. Continuous non-malleability extends the security notion to a setting where the adversary can tamper the codeword polynomially many times and where we assume a self-destruction mechanism in place in case of decoding errors. Our contributions are: (1) two practical constructions of continuous non-malleable randomness encoders in the random oracle model, and (2) a new compiler from continuous non-malleable randomness encoders to continuousnon-malleable codes, and (3) a study of lower bounds for continuous non-malleability in the random oracle model.

Selective opening attacks (SOA) (for public-key encryption, PKE) concern such a multi-user scenario, where an adversary adaptively corrupts some fraction of the users to break into a subset of honestly created ciphertexts, and tries to learn the information on the messages of some unopened (but potentially related) ciphertexts. Until now, the notion of selective opening attacks is only considered in two settings: sender selective opening (SSO), where part of senders are corrupted and messages together with randomness for encryption are revealed; and receiver selective opening (RSO), where part of receivers are corrupted and messages together with secret keys for decryption are revealed.

In this paper, we consider a more natural and general setting for selective opening security. In the setting, the adversary may adaptively corrupt part of senders and receivers \emph{simultaneously}, and get the plaintext messages together with internal randomness for encryption and secret keys for decryption, while it is hoped that messages of uncorrupted parties remain protected. We denote it as Bi-SO security since it is reminiscent of Bi-Deniability for PKE.

We first formalize the requirement of Bi-SO security by the simulation-based (SIM) style, and prove that some practical PKE schemes achieve SIM-Bi-$\text{SO}$-CCA security in the random oracle model. Then, we suggest a weak model of Bi-SO security, denoted as SIM-wBi-$\text{SO}$-CCA security, and argue that it is still meaningful and useful. We propose a generic construction of PKE schemes that achieve SIM-wBi-$\text{SO}$-CCA security in the standard model and instantiate them from various standard assumptions. Our generic construction is built on a newly presented primitive, namely, universal$_{\kappa}$ hash proof system with key equivocability, which may be of independent interest.