International Association
for Cryptologic Research

Komargodski et.al. introduced {\em Evolving Secret Sharing} which allows an imaprtial participant, called \emph{dealer}, to share a secret among unbounded number of participants over any given access structure. In their construction for evolving secret sharing over general access structure, the size of share of the $i^{th}$ participant happens to be exponential $(\mathcal{O}(2^{i-1}))$. They also provided constructions for $(k,\infty)$ threshold secret sharing. We consider the problem of evolving secret sharing with $t$ essential participants, namely, over $t$-$(k,\infty)$ access structure, a generalization of $(k,\infty)$ secret sharing $(t=0)$. We further generalize this access structure to a possible case of unbounded number of essential participants and provide a construction for secret sharing on it. Both the constructions are information theoretically secure and reduce the share size of the construction due to Komargodski et.al. over general access structure, exponentially. Moreover, the essential participants receive ideal (and hence, optimal) shares in the first construction.

In this paper, we revisit the difference enumeration techniques for LowMC and develop new algebraic techniques to achieve efficient key-recovery attacks with negligible memory complexity. \mbox{Benefiting} from our technique to reduce the memory complexity, we could significantly improve the attacks on LowMC when the block size is much larger than the key size and even break LowMC with such a kind of parameter. On the other hand, with our new key-recovery technique, we could significantly improve the time to retrieve the full key if given only a single pair of input and output messages together with the difference trail that they take, which was stated as an interesting question by Rechberger et al. in ToSC 2018. Combining both the techniques, with only 2 chosen plaintexts, we could break 4 rounds of LowMC adopting a full S-Box layer with block size of 129, 192 and 255 bits, respectively, which are the 3 recommended parameters for Picnic3, an alternative \mbox{third-round} candidate in NIST's Post-Quantum Cryptography competition. We have to emphasize that our attacks do not indicate that Picnic3 is broken as the Picnic use-case is very different and an attacker cannot even freely choose 2 plaintexts to encrypt for a LowMC instantiation. However, such parameters are deemed as secure in the latest LowMC. Moreover, much more rounds of seven instances of the backdoor ciphers \mbox{LowMC-M} as proposed by Peyrin and Wang in CRYPTO 2020 can be broken without finding the backdoor by making full use of the allowed $2^{64}$ data. The above mentioned attacks are all achieved with negligible memory.

The Services and Cybersecurity (SCS) group at the University of Twente invites applications for a 4-year PhD position in evidence-based security response.

We are looking for candidates with a solid background in network and system security.

More information and the link to apply:
https://www.utwente.nl/en/organization/careers/!/1097214/full-time-phd-position-in-evidence-based-security-response

Deadline for applications: 30 September 2020, 23:59 CET

Closing date for applications:

Contact: Dr. Andreas Peter (a.peter@utwente.nl)

More information: https://www.utwente.nl/en/organization/careers/!/1097214/full-time-phd-position-in-evidence-based-security-response

Decentralised Randomness Beacon (DRB) is a service that periodically generates publicly verifiable randomness, which plays critical roles in various cryptographic protocols. However, constructing DRB protocols is challenging. Existing DRB protocols suffer from either strong network synchrony assumptions, high communication complexity or attacks. In this paper, we propose RandChain, a new family of permissioned DRB protocols. RandChain is constructed from Sequential Proof-of-Work (SeqPoW) – a Proof-of-Work (PoW) variant that is sequential, i.e., non-parallelisable – and Nakamoto consensus. In RandChain, nodes jointly maintain a blockchain, and each block attaches a random output. Given the last block, each node deterministically derives a SeqPoW puzzle, and keeps solving SeqPoW (aka. mining) until finding a valid solution, of which the value is unpredictable. The first node solving SeqPoW includes a block to the blockchain. The SeqPoW solution’s hash is the random output in this block. RandChain applies Nakamoto consensus so that nodes agree on a unique blockchain. We formalise SeqPoW, propose two constructions, prove their security and evaluate their performance. Our results show that SeqPoW is practical. We then formalise DRBs and analyse RandChain's security. Our analysis shows that RandChain implements a DRB protocol and can produce strongly unpredictable and unbiasible randomness. While as simple and scalable as PoW-based consensus, RandChain achieves better energy efficiency and decentralisation than PoW-based consensus, thanks to the non-parallelisable mining. We also discuss considerations of deploying RandChain in practice, including adding finality, mining non-outsourceability, and difficulty adjustment to RandChain.

This note describes several attacks on the MALICIOUS framework for creating backdoored tweakable block ciphers. It is shown that, although the embedded malicious tweak pair itself is hard to recover, it is feasible to find additional weak tweak pairs that can be used to mount key-recovery attacks. Full-round attacks on most instances of LowMC-M are given. Our attacks are far from optimized and significant future improvements are to be expected.

We focus on low-data attacks, since these are the most relevant for typical use-cases of LowMC. In addition, this implies that our attacks can not be prevented by limiting the amount of data that can be encrypted using the weak tweak pair.

Despite our findings, we believe that the MALICIOUS framework can be used to create backdoored variants of LowMC provided that the parameters are modified.

In this paper we show that deep learning can be used to identify the shape of power traces corresponding to the responses of a protected arbiter PUF implemented in FPGAs. To achieve that, we combine power analysis with bitstream modification. We train a CNN classifier on two 28nm XC7 FPGAs implementing 128-stage arbiter PUFs and then classify the responses of PUFs from two other FPGAs. We demonstrate that it is possible to reduce the number of traces required for a successful attack to a single trace by modifying the bitstream to replicate PUF responses.

At EUROCRYPT 2020, Hosoyamada and Sasaki proposed the first dedicated quantum attack on hash functions --- a quantum version of the rebound attack exploiting differentials whose probabilities are too low to be useful in the classical setting. This work opens up a new perspective toward the security of hash functions against quantum attacks. In particular, it tells us that the search for differentials should not stop at the classical birthday bound. Despite these interesting and promising implications, the concrete attacks described by Hosoyamada and Sasaki make use of large quantum random access memories (qRAMs), a resource whose availability in the foreseeable future is controversial even in the quantum computation community. Without large qRAMs, these attacks incur significant increases in time complexities. In this work, we reduce or even avoid the use of qRAMs by performing a quantum rebound attack based on differentials with non-full-active super S-boxes. Along the way, an MILP-based method is proposed to systematically explore the search space of useful truncated differentials with respect to rebound attacks. As a result, we obtain improved attacks on \aes-\texttt{MMO}, \aes-\texttt{MP}, and the first classical collision attacks on 4- and 5-round \grostl-\texttt{512}. Interestingly, the use of non-full-active super S-box differentials in the analysis of \aes-\texttt{MMO} gives rise to new difficulties in collecting enough starting points. To overcome this issue, we consider attacks involving two message blocks to gain more degrees of freedom, and we successfully compress the qRAM demand of the collision attacks on \texttt{AES}-\texttt{MMO} and \texttt{AES}-\texttt{MP} (EUROCRYPT 2020) from $2^{48}$ to a range from $2^{16}$ to $0$, while still maintaining a comparable time complexity. To the best of our knowledge, these are the first dedicated quantum attacks on hash functions that slightly outperform Chailloux, Naya-Plasencia, and Schrottenloher's generic quantum collision attack (ASIACRYPT 2017) in a model where large qRAMs are not available. This work demonstrates again how a clever combination of classical cryptanalytic technique and quantum computation leads to improved attacks, and shows that the direction pointed out by Hosoyamada and Sasaki deserves further investigation.

We give new proofs that justify the SIGMA and TLS 1.3 key exchange protocols not just in principle, but in practice. By this we mean that, for standardized elliptic curve group sizes, the overall protocol actually achieves the intended security level.

Prior work gave reductions of both protocols' security to the underlying building blocks that were loose (in the number of users and/or sessions), so loose that they gave no guarantees for practical parameters. Adapting techniques by Cohn-Gordon et al. (Crypto 2019), we give reductions for SIGMA and TLS 1.3 to the strong Diffie-Hellman problem which are tight, and prove that this problem is as hard as solving discrete logarithms in the generic group model. Leveraging our tighter and fully-quantitative bounds, we meet the protocols' targeted security levels when instantiated with standardized curves and improve over prior bounds by up to over 80 bits of security across a range of real-world parameters.

Contact tracing is an effective tool in controlling the spread of infectious diseases such as COVID-19. It involves digital monitoring and recording of physical proximity between people over time with a central and trusted authority, so that when one user reports infection, it is possible to identify all other users who have been in close proximity to that person during a relevant time period in the past and alert them. One way to achieve this involves recording on the server the locations, e.g. by reading and reporting the GPS coordinates of a smartphone, of all users over time. Despite its simplicity, privacy concerns have prevented widespread adoption of this method. Technology that would enable the "hiding" of data could go a long way towards alleviating privacy concerns and enable contact tracing at a very large scale. In this article we describe a general method to hide data. By hiding, we mean that instead of disclosing a data value x, we would disclose an "encoded" version of x, namely E(x), where E(x) is easy to compute but very difficult, from a computational point of view, to invert. We propose a general construction of such a function E and show that it guarantees perfect recall, namely, all individuals who have potentially been exposed to infection are alerted, at the price of an infinitesimal number of false alarms, namely, only a negligible number of individuals who have not actually been exposed will be wrongly informed that they have.

With the emergence of the Industrial Internet of Things (IIoT), numerous operations based on smart devices contribute to producing convenience and comfortable applications for individuals and organizations. Considering the untrusted feature of the communication channels in IIoT, it is essential to ensure the authentication and incontestableness of the messages transmitted in the IIoT. In this paper, we firstly proposed a certificate-based parallel key-insulated aggregate signature (CB-PKIAS), which can resist the fully chosen-key attacks. Concretely, the adversary who can obtain the private keys of all signers in the system is able to forge a valid aggregate signature by using the invalid single signature. Furthermore, our scheme inherits the merits of certificate-based and key-insulated to avoid the certificate management problem, key escrow problems as well as the key exposures simultaneously. In addition, the rigorous analysis and the concrete simulation experiment demonstrated that our proposed scheme is secure under the random oracle and more suitable for the IIoT environment.

This paper presents the first functional encryption schemes for quadratic functions (or degree-2 polynomials) achieving simulation-based security in the semi-adaptive model with constant-size secret key. The unique prior construction with the same security guarantee by Gay [PKC 20] has secret keys of size linear in the message size. They also enjoy shorter ciphertexts:

- our first scheme is based on bilateral DLIN (decisional linear) assumption as Gay's scheme and the ciphertext is 15% shorter;

- our second scheme based on SXDH assumption and bilateral DLIN assumption is more efficient; it has 67% shorter ciphertext than previous SXDH-based scheme with selective indistinguishability security by Baltico et al. [CRYPTO 17]; the efficiency is comparable to their second scheme in the generic group model.

Technically, we roughly combine Wee's ``secret-key-to-public-key'' compiler [TCC 17] with Gay's paradigm [PKC 20]. We avoid (partial) function-hiding inner-product functional encryption used in Gay's work and make our schemes conceptually simpler.

ARX algorithms are a class of symmetric-key algorithms constructed by Addition, Rotation, and XOR, which achieve the best software performances in low-end microcontrollers. To evaluate the resistance of an ARX cipher against differential cryptanalysis and its variants, the recent automated methods employ constraint satisfaction solvers, such as SMT solvers, to search for optimal characteristics. The main difficulty to formulate this search as a constraint satisfaction problem is obtaining the differential models of the non-linear operations, that is, the constraints describing the differential probability of each non-linear operation of the cipher. While an efficient bit-vector differential model was obtained for the modular addition with two variable inputs, no differential model for the modular addition by a constant has been proposed so far, preventing ARX ciphers including this operation from being evaluated with automated methods.

In this paper, we present the first bit-vector differential model for the n-bit modular addition by a constant input. Our model contains O(log_2(n)) basic bit-vector constraints and describes the binary logarithm of the differential probability. We also represent an SMT-based automated method to look for differential characteristics of ARX, including constant additions, and we provide an open-source tool ArxPy to find ARX differential characteristics in a fully automated way. To provide some examples, we have searched for related-key differential characteristics of TEA, XTEA, HIGHT, and LEA, obtaining better results than previous works. Our differential model and our automated tool allow cipher designers to select the best constant inputs for modular additions and cryptanalysts to evaluate the resistance of ARX ciphers against differential attacks.

We construct indistinguishability obfuscation (iO) solely under circular-security properties of encryption schemes based on the Learning with Errors (LWE) problem, i.e. the same kind of assumption as are currently known to imply (unlevelled) fully-homomorphic encryption (FHE). As an added bonus, this assumption can be conjectured to be post-quantum secure; yielding the first provably secure iO construction that is post-quantum secure.

Brakerski, Doettling, Garg, and Malavolta [EUROCRYPT 2020] showed a construction of iO obtained by combining certain natural \emph{homomorphic} encryption schemes. However, their construction was heuristic in the sense that security argument could only be presented in the random oracle model. In a beautiful recent work, Gay and Pass [ePrint 2020] showed a way to remove the heuristic step. They obtain a construction proved secure under circular security of natural homomorphic encryption schemes --- specifically, they use homomorphic encryption schemes based on LWE and DCR, respectively. In this work, we remove the need for DCR-based encryption and obtain a result solely from the circular security of LWE-based encryption schemes.

Anonymous veto networks (AV-nets), originally proposed by Hao and Zielinski (2006), are particularly lightweight protocols for evaluating a veto function in a peer-to-peer network such that anonymity of all protocol participants is preserved. Prior to this work, anonymity in all AV-nets from the literature relied on the decisional Diffie-Hellman (DDH) assumption and can thus be broken by (scalable) quantum computers. In order to defend against this threat, we propose two practical and completely lattice-based AV-nets. The first one is secure against passive and the second one is secure against active adversaries. We prove that anonymity of our AV-nets reduces to the ring learning with errors (RLWE) assumption. As such, our AV-nets are the first ones with post-quantum anonymity. We also provide performance benchmarks to demonstrate their practicality.

This paper proposes new Polynomial IOPs for arithmetic circuits. They rely on the monomial coefficient basis to representation the matrices and vectors arising from the arithmetic constraint satisfaction system, and build on new protocols for establishing the correct computation of linear algebra relations such as matrix-vector products and Hadamard products. Our protocols give rise to concrete proof systems with succinct verification when compiled down with a cryptographic compiler whose role is abstracted away in this paper. Depending only on the compiler, the resulting SNARKs are either transparent or rely on a trusted setup.

Distributed ledgers, such as those arising from blockchain protocols, have been touted as the centerpiece of an upcoming security-critical information technology infrastructure. Their basic properties---consistency and liveness---can be guaranteed under specific constraints about the resources of an adversary relative to the resources of the nodes that follow the protocol. Given the intended long-livedness of these protocols, perhaps the most fundamental open security question currently is their behavior and potential resilience to temporary spikes in adversarial resources.

In this work we give the first thorough treatment of self-healing properties of distributed ledgers covering both proof-of-work (PoW) and proof-of-stake (PoS) protocols. Our results quantify the vulnerability period that corresponds to an adversarial spike and classify three types of currently deployed protocols with respect to their self-healing ability: PoW-based blockchains, PoS-based blockchains, and iterated Byzantine Fault Tolerant (iBFT) protocols.

We prove that the module learning with errors (M-LWE) problem with arbitrary polynomial-sized modulus p is classically at least as hard as standard worst-case lattice problems, as long as the module rank d is not smaller than the number field degree n. Previous publications only showed the hardness under quantum reductions. We achieve this result in an analogous manner as in the case of the learning with errors (LWE) problem. First, we show the classical hardness of M-LWE with an exponential-sized modulus. In a second step, we prove the hardness of M-LWE using a binary secret. And finally, we provide a modulus reduction technique. The complete result applies to the class of power-of-two cyclotomic fields. However, several tools hold for more general classes of number fields and may be of independent interest.

We analyze the multi-user security of the streaming encryption in Google's Tink library via an extended version of the framework of nonce-based online authenticated encryption of Hoang et al. (CRYPTO'15) to support random-access decryption. We show that Tink's design choice of using random nonces and a nonce-based key-derivation function indeed improves the concrete security bound. We then give two better alternatives that are more robust against randomness failure. In addition, we show how to efficiently instantiate the key-derivation function via AES, instead of relying on HMAC-SHA256 like the current design in Tink. To accomplish this we give a multi-user analysis of the XOR-of-permutation construction of Bellare, Krovetz, and Rogaway (EUROCRYPT'98).

Event date: 1 March to 5 March 2021
Submission deadline: 17 September 2020
Notification: 3 December 2020

The Institute of Science and Technology Austria invites applications for several open positions in all areas of computer science including cryptography, systems security and privacy.

IST Austria offers:

• A highly international and interdisciplinary research environment with English as working language on campus
• State-of the art facilities and scientific support services (www.ist.ac.at/scientific-service-units/)
• Competitive start-up package and salary
• Guaranteed annual base funding including funding for PhD students and postdocs
• Wide portfolio of career support
• Child-care facilities and support on campus

IST Austria is an international institute dedicated to basic research and graduate education in the natural, mathematical, and computational sciences. The Institute fosters an interactive, collegial, and supportive atmosphere, sharing space and resources between research groups whenever possible, and facilitating cross-disciplinary collaborations. Our PhD program involves a multi-disciplinary course schedule and rotations in research groups and hire scholars from diverse international backgrounds. The campus of IST Austria is located close to Vienna, one of the most livable cities in the world.

Assistant professors receive independent group leader positions with an initial contract of six years, at the end of which they are reviewed by international peers. If the evaluation is positive, an assistant professor is promoted to a tenured professor.
Candidates for tenured positions are distinguished scientists in their respective research fields and have at least six years of experience in leading a research group.

Please apply online at: www.ist.ac.at/jobs/faculty

The closing date for applications is October 30, 2020.

IST Austria values diversity and is committed to equal opportunity. We strive for increasing the number of women, particularly in fields where they are underrepresented, and therefore we strongly encourage female researchers to apply.

Closing date for applications:

Contact: krzysztof.pietrzak@ist.ac.at

More information: https://ist.ac.at/en/jobs/faculty/