International Association
for Cryptologic Research

Anonymous identity-based identification scheme in the ad-hoc group is a multi-party cryptographic primitive that allows participants to form an ad-hoc group and prove membership anonymously in such a group. In this paper, we cryptanalyze an ad-hoc anonymous identity-based identification scheme proposed by Barapatre and Rangan and show that the scheme is not secure against key-only universal impersonation attack. We note that anyone can impersonate as a valid group member to convince the honest verifier successfully, even without knowing the group secret key. Moreover, we proposed a fix on the scheme and provide a security proof for our fixed scheme. The fixed scheme we proposed fulfills the security requirements of an ad-hoc anonymous identity-based identification scheme that are correctness, soundness, and anonymity.

Data trading is an emerging business, in which data sellers provide buyers with, for example, their private datasets and get paid from buyers. In many scenarios, sellers prefer to sell pieces of data, such as statistical results derived from the dataset, rather than the entire dataset. Meanwhile, buyers wish to hide the results they retrieve. Since it is not preferable to rely on a trusted third party (TTP), we are wondering, in the absence of TTP, whether there exists a \emph{practical} mechanism satisfying the following requirements: the seller Sarah receives the payment if and only if she \emph{obliviously} returns the buyer Bob the \emph{correct} evaluation result of a function delegated by Bob on her dataset, and Bob can only derive the result for which he pays. Despite a lot of attention data trading has received, a \emph{desirable} mechanism for this scenario is still missing. This is due to the fact that general solutions are inefficient when the size of datasets is considerable or the evaluated function is complicated, and that existing efficient cryptographic techniques cannot fully capture the features of our scenario or can only address very limited computing tasks.

In this paper, we propose the \emph{first desirable} mechanism that is practical and supports a wide variety of computing tasks --- evaluation of arbitrary functions that can be represented as polynomials. We introduce a new cryptographic notion called \emph{blind polynomial evaluation} and instantiate it with an explicit protocol. We further combine this notion with the blockchain paradigm to provide a \emph{practical} framework that can satisfy the requirements mentioned above.

Uncloneable encryption, introduced by Broadbent and Lord (TQC'20), is an encryption scheme with the following attractive feature: an adversary cannot create multiple ciphertexts which encrypt to the same message as the original ciphertext. The constructions proposed by Broadbent and Lord have the disadvantage that they only guarantee one-time security; that is, the encryption key can only be used once to encrypt the message.

In this work, we study uncloneable encryption schemes, where the encryption key can be re-used to encrypt multiple messages. We present two constructions from minimal cryptographic assumptions: (i) a private-key uncloneable encryption scheme assuming post-quantum one-way functions and, (ii) a public-key uncloneable encryption scheme assuming a post-quantum public-key encryption scheme.

We consider a set of security and privacy problems under reliability and storage constraints that can be tackled by using codes and particularly focus on the secret-key agreement problem. Polar subcodes (PSCs) are polar codes (PCs) with dynamically-frozen symbols and have a larger code minimum distance than PCs with only statically-frozen symbols. A randomized nested PSC construction, where the low-rate code is a PSC and the high-rate code is a PC, is proposed for successive cancellation list (SCL) and sequential decoders. This code construction aims to perform lossy compression with side information, i.e., Wyner-Ziv (WZ) coding. Nested PSCs are used in the key agreement problem with physical identifiers and two terminals since WZ-coding constructions significantly improve on Slepian-Wolf coding constructions such as fuzzy extractors. Significant gains in terms of the secret-key vs. storage rate ratio as compared to nested PCs with the same list sizes are illustrated to show that nested PSCs significantly improve on all existing code constructions. The performance of the nested PSCs is shown to improve with larger list sizes, unlike the nested PCs considered. A design procedure to efficiently construct nested PSCs and possible improvements to the nested PSC designs are also provided.

Do you want beneficial technologies being shaped by your ideas? Whether in the areas of mobility solutions, consumer goods, industrial technology or energy and building technology – with us, you will have the chance to improve quality of life all across the globe. Welcome to Bosch.

The Robert Bosch GmbH is looking forward to your application!

Job Description

• As a PhD in our research group you are contributing to research and development projects in an open source context.
• This includes understanding, evaluating and applying Privacy-Preserving Computing Technologies (PPCTs) including Computing On Encrypted Data techniques, Trusted Execution Environments, and methods for Statistical Disclosure Control.
• Embedded into a team of security and cloud technology experts, you apply your knowledge on PPCTs to design, implement and evaluate PPCT-based solutions in the context of the Franco-German BMBF/MESRI-funded CRYPTECS research project.
• Thanks to your insights, you help combine PPCTs and Cloud Native technologies to make PPCTs ready for use in an industrial context.
• Your responsibility includes the design, development and prototypical implementation of PPCT solutions. You push the state of the art in the field of PPCTs and publish your results together with renowned researchers from the international CRYPTECS consortium.

Qualifications

• Education: Very good master’s degree in computer science or related discipline, ideally combined with initial experience in the area of Cloud Native technologies
• Personality: Positive team player, who is highly motivated, has an innovative mindset, is eager to learn new things, and is passionate about applied research
• Working Practice: Initial hands-on experience with software development, ideally in an open source context
• Experience and Knowledge: Knowledge in the area of cryptography, ideally experience in PPCTs and modern Cloud Native technologies
• Languages: Fluent in English (written and spoken)
<

Closing date for applications:

Contact:
Need support during your application?
Kevin Heiner (Human Resources), Phone: +49 711 811 12223
Need further information about the job?
Dr. Sven Trieflinger (Functional Department), Phone: +49 711 811 24801

More information: https://smrtr.io/5fm_3

A Statistical Information Theoretic Secure (SITS) system utilizing the Chinese Remainder Theorem (CRT), coupled with Fully Homomorphic Encryption (FHE) for Distributed Communication-less Secure Multiparty Computation (DCLSMPC) of any Distributed Unknown Finite State Machine (DUFSM) is presented. Namely, secret shares of the input(s) and output(s) are passed to/from the computing parties, while there is no communication between them throughout the computation. We propose a novel approach of transition table representation and polynomial representation for arithmetic circuits evaluation, joined with a CRT secret sharing scheme and FHE to achieve SITS communication-less within computational secure execution of DUFSM. We address the severe limitation of FHE implementation over a single server to cope with a malicious or Byzantine server. We use several distributed memory-efficient solutions that are significantly better than the majority vote in replicated state machines, where each participant maintains an FHE replica. A Distributed Unknown Finite State Machine (DUFSM) is achieved when the transition table is secret shared or when the (possible zero value) coefficients of the polynomial are secret shared, implying communication-less SMPC of an unknown finite state machine.

In proof-of-stake (PoS) blockchains, stakeholders that extend the chain are selected according to the amount of stake they own. In S\&P 2019 the ``Ouroboros Crypsinous'' system of Kerber et al.\ (and concurrently Ganesh et al.\ in EUROCRYPT 2019) presented a mechanism that hides the identity of the stakeholder when adding blocks, hence preserving anonymity of stakeholders both during payment and mining in the Ouroboros blockchain. They focus on anonymizing the messages of the blockchain protocol, but suggest that potential identity leaks from the network-layer can be removed as well by employing anonymous broadcast channels.

In this work we show that this intuition is flawed. Even ideal anonymous broadcast channels do not suffice to protect the identity of the stakeholder who proposes a block.

We make the following contributions. First, we show a formal network-attack against Ouroboros Crypsinous, where the adversary can leverage network delays to distinguish who is the stakeholder that added a block on the blockchain. Second, we abstract the above attack and show that whenever the adversary has control over the network delay -- within the synchrony bound -- loss of anonymity is inherent for any protocol that provides liveness guarantees. We do so, by first proving that it is impossible to devise a (deterministic) state-machine replication protocol that achieves basic liveness guarantees and better than $(1-2\f)$ anonymity at the same time (where $\f$ is the fraction of corrupted parties). We then connect this result to the PoS setting by presenting the tagging and reverse tagging attack that allows an adversary, across several executions of the PoS protocol, to learn the stake of a target node, by simply delaying messages for the target. We demonstrate that our assumption on the delaying power of the adversary is realistic by describing how our attack could be mounted over the Zcash blockchain network (even when Tor is used). We conclude by suggesting approaches that can mitigate such attacks.

We study uncloneable quantum encryption schemes for classical messages as recently proposed by Broadbent and Lord. We focus on the information-theoretic setting and give several limitations on the structure and security of these schemes: Concretely, 1) We give an explicit cloning-indistinguishable attack that succeeds with probability $\frac12 + \mu/16$ where $\mu$ is related to the largest eigenvalue of the resulting quantum ciphertexts. 2) For a uniform message distribution, we partially characterize the scheme with the minimal success probability for cloning attacks. 3) Under natural symmetry conditions, we prove that the rank of the ciphertext density operators has to grow at least logarithmically in the number of messages to ensure uncloneable security. 4) The \emph{simultaneous} one-way-to-hiding (O2H) lemma is an important technique in recent works on uncloneable encryption and quantum copy protection. We give an explicit example which shatters the hope of reducing the multiplicative "security loss" constant in this lemma to below 9/8.

The k-XOR problem can be generically formulated as the following: given many n-bit strings generated uniformly at random, find k distinct of them which XOR to zero. This generalizes collision search (two equal elements) to a k-tuple of inputs.

This problem has become ubiquitous in cryptanalytic algorithms. Applications include variants in which the XOR operation is replaced by a modular addition (k-SUM) or other non-commutative operations (e.g., the composition of permutations). The case where a single solution exists on average is of special importance.

The generic study of quantum algorithms k-XOR (and variants) was started by Grassi et al. (ASIACRYPT 2018), in the case where many solutions exist. At EUROCRYPT 2020, Naya-Plasencia and Schrottenloher defined a class of "quantum merging algorithms" obtained by combining quantum search. They represented these algorithms by a set of "merging trees" and obtained the best ones through linear optimization of their parameters.

In this paper, we give a new, simplified representation of merging trees that makes their analysis easier. As a consequence, we improve the quantum time complexity of the Single-solution k-XOR problem by relaxing one of the previous constraints, and making use of quantum walks. Our algorithms subsume or improve over all previous quantum generic algorithms for Single-solution k-XOR. For example, we give an algorithm for 4-XOR (or 4-SUM) in quantum time $\widetilde{\mathcal{O}}(2^{7n/24})$.

In this work, we study disappearing cryptography in the bounded storage model. Here, a component of the transmission, say a ciphertext, a digital signature, or even a program, is streamed bit by bit. The stream is so large for anyone to store in its entirety, meaning the transmission effectively disappears once the stream stops.

We first propose the notion of online obfuscation, capturing the goal of disappearing programs in the bounded storage model. We give a negative result for VBB security in this model, but propose candidate constructions for a weaker security goal, namely VGB security. We then demonstrate the utility of VGB online obfuscation, showing that it can be used to generate disappearing ciphertexts and signatures. All of our applications are NOT possible in the standard model of cryptography, regardless of computational assumptions used.

We push a little further the study of two characterizations of almost perfect nonlinear (APN) functions introduced in our recent monograph. We state open problems about them, and we revisit in their perspective a well-known result from Dobbertin on APN exponents. This leads us to new results about APN power functions and more general APN polynomials with coefficients in a subfield F_{2^k} , which ease the research of such functions and of differentially uniform functions, and simplifies the related proofs by avoiding tedious calculations. In a second part, we give slightly simpler proofs than in the same monograph, of two known results on Boolean functions, one of which deserves to be better known but needed clarification, and the other needed correction.

Current proofs of current multi-signature schemes yield bounds on adversary advantage that are loose, failing to match the indications of cryptanalysis, and failing to justify security of implementations of the schemes in the 256-bit groups that are the choice of practioners. We bridge this gap via proofs in the Algebraic Group Model (AGM). For classical 3-round schemes we give AGM proofs with tight bounds. We then give a new 2-round multi-signature scheme, as efficient as prior ones, for which we prove a tight AGM bound. These results are obtained via a framework in which a reduction is broken into a chain of sub-reductions involving intermediate problems. By giving as many as possible of the sub-reductions tightly in the standard model, we minimize use of the AGM, and also hedge the AGM proofs with standard-model ones from different starting points.

It has been common knowledge that for a stream cipher to be secure against generic TMD tradeoff attacks, the size of its internal state in bits needs to be at least twice the size of the length of its secret key. In FSE 2015, Armknecht and Mikhalev however proposed the stream cipher Sprout with a Grain-like architecture, whose internal state was equal in size with its secret key and yet resistant against TMD attacks. Although Sprout had other weaknesses, it germinated a sequence of stream cipher designs like Lizard and Plantlet with short internal states. Both these designs have had cryptanalytic results reported against them. In this paper, we propose the stream cipher Atom that has an internal state of 159 bits and offers a security of 128 bits. Atom uses two key filters simultaneously to thwart certain cryptanalytic attacks that have been recently reported against keystream generators. In addition, we found that our design is one of the smallest stream ciphers that offers this security level, and we prove in this paper that Atom resists all the attacks that have been proposed against stream ciphers so far in literature. On the face of it, Atom also builds on the basic structure of the Grain family of stream ciphers. However, we try to prove that by including the additional key filter in the architecture of Atom we can make it immune to all cryptanalytic advances proposed against stream ciphers in recent cryptographic literature.

Side-channel attacks are a threat to secrets stored on a device, especially if an adversary has physical access to the device. As an effect of this, countermeasures against such attacks for cryptographic algorithms are a well-researched topic. In this work, we deviate from the study of cryptographic algorithms and instead focus on the side-channel protection of a much more basic operation, the comparison of a known attacker-controlled value with a secret one. Comparisons sensitive to side-channel leakage occur in tag comparisons during the verification of message authentication codes (MACs) or authenticated encryption, but are typically omitted in security analyses. Besides, also comparisons performed as part of fault countermeasures might be sensitive to side-channel attacks. In this work, we present a formal analysis on comparing values in a leakage resilient manner by utilizing cryptographic building blocks that are typically part of an implementation anyway. Our results indicate that there is no need to invest additional resources into implementing a protected comparison operation itself if a sufficiently protected implementation of a public cryptographic permutation, or a (tweakable) block cipher, is already available. We complement our contribution by applying our findings to the SuKS message authentication code used by lightweight authenticated encryption scheme ISAP, and to the classical Hash-then-PRF construction.

Cryptanalysis of symmetric-key ciphers, e.g., linear/differential cryptanalysis, requires an adversary to know the internal structures of the targeted ciphers. On the other hand, deep learning-based cryptanalysis has attracted significant attention because the adversary is not assumed to have knowledge of the targeted ciphers except the interfaces of algorithms. Such a blackbox attack is extremely strong; thus we must design symmetric-key ciphers that are secure against deep learning-based cryptanalysis. However, previous attacks do not clarify what features or internal structures affect success probabilities; therefore it is difficult to employ the results of such attacks to design deep learning-resistant symmetric-key ciphers. In this paper, we focus on toy SPN block ciphers (small PRESENT and small AES) and propose deep learning-based output prediction attacks. Due to its small internal structures, we can build learning models by employing the maximum number of plaintext/ciphertext pairs, and we can precisely calculate the rounds in which full diffusion occurs. We demonstrate the following: (1) our attacks work against a similar number of rounds attacked by linear/differential cryptanalysis, (2) our attacks realize output predictions (precisely plaintext recovery and ciphertext prediction) that are much stronger than distinguishing attacks, and (3) swapping the order of components or replacement components affects the success probabilities of the attacks. It is particularly worth noting that swapping/replacement does not affect the success probabilities of linear/differential cryptanalysis. We expect that our results will be an important stepping stone in the design of deep learning-resistant symmetric key ciphers.

Branching program is an important component of indistinguishability obfuscation (IO) schemes, its size greatly influences the efficiencies of corresponding IO schemes. There are two major candidates of branching programs, Bar86 branching program and IK00 branching program. Bar86 branching program was shown to efficiently recognize NC$^1$ circuits. In specific, a Boolean circuit of depth $d$ can be recognized by a Bar86 branching program of length not larger than $4^d$ (Therefore of size not larger than $5^2 \times 4^d$). In this short paper we present similar result about IK00 branching program. We show that IK00 branching program efficiently recognizes NC$^1$ circuits, that is, a Boolean circuit of depth $d$ can be recognized by an IK00 branching program of size not larger than $(n+1) \times 4^d$, where $n$ is input length. Our result may be a negative evidence for IK00 branching program to efficiently recognize polynomial-time computable functions.

In our previous paper we introduced a novel SNARK-based construction, called Zendoo, that allows Bitcoin-like blockchains to create and communicate with sidechains of different types without knowing their internal structure. We also introduced a specific construction, called Latus, allowing creation of fully verifiable sidechains. But in there we omitted a detailed description of an incentive scheme for Latus that is an essential element of a real decentralized system. This paper fills the gap by introducing details of the incentive scheme for the Latus sidechain. Represented ideas can also be adopted by other SNARK-based blockchains to incentivize decentralized proofs creation.

In 1989, Shamir presented an efficient identification scheme (IDS) based on the permuted kernel problem (PKP). After 21 years, PKP was generalized by Lampe and Patarin, who were able to build an IDS similar to Shamir's one, but using the binary field. This binary variant presented some interesting advantages over Shamir's original IDS, such as reduced number of operations and inherently resistance against side-channel attacks. In the security analysis, considering the best attacks against the original PKP, the authors concluded that none of these existing attacks appeared to have a significant advantage when attacking the binary variant. In this paper, we propose the first attack that targets the binary PKP. The attack is analyzed in detail, and its practical performance is compared with our theoretical models. For the proposed parameters originally targeting 79 and 98 bits of security, our attack can recover about 100% of all keys using less than $2^{63}$ and $2^{77}$ operations, respectively.

State-separating proofs (SSP) is a recent methodology for structuring game-based cryptographic proofs in a modular way. While very promising, this methodology was previously not fully formalized and came with little tool support. We address this by introducing SSProve, the first general verification framework for machine-checked state-separating proofs. SSProve combines high-level modular proofs about composed protocols, as proposed in SSP, with a probabilistic relational program logic for formalizing the lower-level details, which together enable constructing fully machine-checked crypto proofs in the Coq proof assistant. Moreover, SSProve is itself formalized in Coq, including the algebraic laws of SSP, the soundness of the program logic, and the connection between these two verification styles.

Code-based cryptographic schemes are highly regarded among the quantum-safe alternatives to current standards. Yet, designing code-based signatures using traditional methods has always been a challenging task, and current proposals are still far from the target set by other post-quantum primitives (e.g. lattice-based). In this paper, we revisit a recent work using an innovative approach for signing, based on the hardness of the code equivalence problem. We introduce some optimizations and provide a security analysis for all variants considered. We then show that the new parameters produce instances of practical interest.