International Association
for Cryptologic Research

Verifiable random functions (VRFs), introduced by Micali, Rabin and Vadhan (FOCS’99), are the public-key equivalent of pseudorandom functions. A public verification key and proofs accompanying the output enable all parties to verify the correctness of the output. However, all known standard model VRFs have a reduction loss that is much worse than what one would expect from known optimal constructions of closely related primitives like unique signatures. We show that:

1. Every security proof for a VRF that relies on a non-interactive assumption has to lose a factor of Q, where Q is the number of adversarial queries. To that end, we extend the meta-reduction technique of Bader et al. (EUROCRYPT’16) to also cover VRFs. 2. This raises the question: Is this bound optimal? We answer this question in the affirmative by presenting the first VRF with a reduction from the non-interactive qDBDHI assumption to the security of VRF that achieves this optimal loss.

We thus paint a complete picture of the achievability of tight verifiable random functions: We show that a security loss of Q is unavoidable and present the first construction that achieves this bound.

The LWE problem with its ring variants is today the most prominent candidate for building efficient public key cryptosystems resistant to quantum computers. NTRU-type cryptosystems use an LWE-type variant with small max-norm secrets, usually with ternary coefficients from the set $\{-1,0,1\}$. The presumably best attack on these schemes is a hybrid attack that combines lattice reduction techniques with Odlyzko's Meet-in-the-Middle approach. Odlyzko's algorithm is a classical combinatorial attack that for key space size ${\cal S}$ runs in time ${\cal S}^{0.5}$. We substantially improve on this Meet-in-the-Middle approach, using the representation technique developed for subset sum algorithms. Asymptotically, our heuristic Meet-in-the-Middle attack runs in time roughly ${\cal S}^{0.25}$, which also beats the ${\cal S}^{\frac 1 3}$ complexity of the best known quantum algorithm.

For the round-3 NIST post-quantum encryptions NTRU-Encrypt and NTRU-Prime we obtain non-asymptotic instantiations of our attack with complexity roughly ${\cal S}^{0.35}$. As opposed to other combinatorial attacks, our attack benefits from larger LWE field sizes $q$, as they are often used in modern lattice-based signatures. For example, for BLISS signatures we obtain non-asymptotic combinatorial attacks in between ${\cal S}^{0.31}$ and ${\cal S}^{0.35}$, for GLP signatures in ${\cal S}^{0.3}$.

Our attacks do not invalidate the security claims of the aforementioned schemes. However, they establish improved combinatorial upper bounds for their security. We leave it is an open question whether our new Meet-in-the-Middle attack in combination with lattice reduction can be used to speed up the hybrid attack.

Keywords: Meet in the Middle, Representation Technique, NTRU/BLISS/GLP

This work introduces a new interactive oracle proof system based on the MPC-in-the-Head paradigm. To improve concrete efficiency and offer flexibility between computation time and communication size, a generic proof construction based on multi-round MPC protocols is proposed, instantiated with a specific protocol and implemented and compared to similar proof systems. Performance gains over previous work derive from a multi-party multiplication check optimized for the multi-round and MPC-in-the-Head settings. Of most interest among implementation optimizations is the use of identical randomness across repeated MPC protocol executions in order to accelerate computation without excessive cost to the soundness error. The new system creates proofs of SHA-256 pre-images of 43KB in 53ms with 16 MPC parties, or 23KB in 188ms for 128 parties. As a signature scheme, the non-interactive variant produces signatures, based on the AES-128 circuit, of 19KB in 4.2ms; this is 35% faster and 33 % larger than the Picnic3 scheme (13kB in 5.3ms for 16 parties) which is based on the 90% smaller LowMC circuit.

Mesh messaging applications allow users in relative proximity to communicate without the Internet. The most viable offering in this space, Bridgefy, has recently seen increased uptake in areas experiencing large-scale protests (Hong Kong, India, Iran, US, Zimbabwe, Belarus), suggesting its use in these protests. It is also being promoted as a communication tool for use in such situations by its developers and others. In this work, we report on a security analysis of Bridgefy. Our results show that Bridgefy, as analysed, permitted its users to be tracked, offered no authenticity, no effective confidentiality protections and lacked resilience against adversarially crafted messages. We verified these vulnerabilities by demonstrating a series of practical attacks on Bridgefy. Thus, if protesters relied on Bridgefy, an adversary could produce social graphs about them, read their messages, impersonate anyone to anyone and shut down the entire network with a single maliciously crafted message.

The introduction of the automatic search boosts the cryptanalysis of symmetric-key primitives to some degree. However, the performance of the automatic search is not always satisfactory for the search of long trails or ciphers with large state sizes. Compared with the extensive attention on the enhancement for the search with the mixed integer linear programming (MILP) method, few works care for the acceleration of the automatic search with the Boolean satisfiability problem (SAT) or satisfiability modulo theories (SMT) method. This paper intends to fill this vacancy. Firstly, with the additional encoding variables of the sequential counter circuit for the original objective function in the standard SAT method, we put forward a new encoding method to convert the Matsui's bounding conditions into Boolean formulas. This approach does not rely on new auxiliary variables and significantly reduces the consumption of clauses for integrating multiple bounding conditions into one SAT problem. Then, we evaluate the accelerating effect of the novel encoding method under different sets of bounding conditions. With the observations and experience in the tests, a strategy on how to create the sets of bounding conditions that probably achieve extraordinary advances is proposed. The new idea is applied to search for optimal differential and linear characteristics for multiple ciphers. For PRESENT, GIFT-64, RECTANGLE, LBlock, TWINE, and some versions in SIMON and SPECK families of block ciphers, we obtain the complete bounds (full rounds) on the number of active S-boxes, the differential probability, as well as the linear bias. The acceleration method is also employed to speed up the search of related-key differential trails for GIFT-64. Based on the newly identified 18-round distinguisher with probability $2^{-58}$, we launch a 26-round key-recovery attack with $2^{60.96}$ chosen plaintexts. To our knowledge, this is the longest attack on GIFT-64. Lastly, we note that the attack result is far from threatening the security of GIFT-64 since the designers recommended users to double the number of rounds under the related-key attack setting.

This paper presents three attack vectors of bit-wise cryptanalysis including rotational, bit-wise differential, and zero-sum distinguishing attacks on the AND-RX permutation Friet-PC, which is implemented in a lightweight authenticated encryption scheme Friet. First, we propose a generic procedure for a rotational attack on AND-RX cipher with round constants. By applying the proposed attack to Friet-PC, we can construct an 8-round rotational distinguisher with a time complexity of 2^{102}. Next, we explore single- and dual-bit differential biases, which are inspired by the existing study on Salsa and ChaCha, and observe the best bit-wise differential bias with 2^{−9.552}. This bias allows us to practically construct a 9-round bit-wise differential distinguisher with a time complexity of 2^{20.044}. Finally, we construct 13-, 15-, 17-, and 30-round zero-sum distinguishers with time complexities of 2^{31}, 2^{63}, 2^{127}, and 2^{383}, respectively. To summarize our study, we apply three attack vectors of bit-wise cryptanalysis to Friet-PC and show their superiority as effective attacks on AND-RX ciphers.

Sharding is an emerging technique to overcome scalability issues on blockchain based public ledgers. Without sharding, every node in the network has to listen to and process all ledger protocol messages. The basic idea of sharding is to parallelize the ledger protocol: the nodes are divided into smaller subsets that each take care of a fraction of the original load by executing lighter instances of the ledger protocol, also called shards. The smaller the shards, the higher the efficiency, as by increasing parallelism there is less overhead in the shard consensus.

In this vein, we propose a novel approach that leverages the sharding safety-liveness dichotomy. We separate the liveness and safety in shard consensus, allowing us to dynamically tune shard parameters to achieve essentially optimal efficiency for the current corruption ratio of the system. We start by sampling a relatively small shard (possibly with a small honesty ratio), and we carefully trade-off safety for liveness in the consensus mechanism to tolerate small honesty without losing safety. However, for a shard to be live, a higher honesty ratio is required in the worst case. To detect liveness failures, we use a so-called control chain that is always live and safe. Shards that are detected to be not live are resampled with increased shard size and liveness tolerance until they are live, ensuring that all shards are always safe and run with optimal efficiency. As a concrete example, considering a population of 10K parties, 30% corruption and 60-bit security, our design permits shards of size 200 parties in contrast to 6K parties in previous designs.

Moreover, in this highly concurrent execution setting, it is paramount to guarantee that both the sharded ledger protocol and its sub protocols (e.g., the shards) are secure under composition. To prove the security of our approach, we present ideal functionalities capturing a sharded ledger as well as ideal functionalities capturing the control chain and individual shard consensus, which needs adjustable liveness. We further formalize our protocols and prove that they securely realize the sharded ledger functionality in the UC framework.

The inherent difficulty of maintaining stateful environments over long periods of time gave rise to the paradigm of serverless computing, where mostly-stateless components are deployed on demand to handle computation tasks, and are teared down once their task is complete. Serverless architecture could offer the added benefit of improved resistance to targeted denial-of-service attacks, by hiding from the attacker the physical machines involved in the protocol until after they complete their work. Realizing such protection, however, requires that the protocol only uses stateless parties, where each party sends only one message and never needs to speaks again. Perhaps the most famous example of this style of protocols is the Nakamoto consensus protocol used in Bitcoin: A peer can win the right to produce the next block by running a local lottery (mining), all while staying covert. Once the right has been won, it is executed by sending a single message. After that, the physical entity never needs to send more messages.

We refer to this as the You-Only-Speak-Once (YOSO) property, and initiate the formal study of it within a new model that we call the YOSO model. Our model is centered around the notion of roles, which are stateless parties that can only send a single message. Crucially, our modelling separates the protocol design, that only uses roles, from the role-assignment mechanism, that assigns roles to actual physical entities. This separation enables studying these two aspects separately, and our YOSO model in this work only deals with the protocol-design aspect.

We describe several techniques for achieving YOSO MPC; both computational and information theoretic. Our protocols are synchronous and provide guaranteed output delivery (which is important for application domains such as blockchains), assuming honest majority of roles in every time step. We describe a practically efficient computationally-secure protocol, as well as a proof-of-concept information theoretically secure protocol.

Abstract

Modern cryptographic algorithms have an enormous key diversity, so if we want to test their strength for all the keys, it will take practically an infinite time. To avoid this, we use the sampling method, in which we examine a much smaller number of keys n and then we make estimation for the total key population N with a predetermined sampling error. For the generation of the n cipher outputs (samples) with the n corresponding keys, the critical questions are how many samples we will test and how large must be the size of each sample. The general rule is that, the sampling error is reduced as we increase the number of the samples. But since the tests must be executed in an acceptable time, we must compromise the above rule with some additional factors, such as the type of the cryptographic cipher, the kind and the size of the plain information and of course the available computer power. In this study we examine the interrelations of all the above factors, and we propose applicable solutions.

Keywords: Cryptography, Data encryption, Communication security, Computer security, Data security, Information security.

Event date: 21 August to 16 August 2021
Submission deadline: 25 April 2021

Event date: 19 July to 20 July 2021

Event date: 4 October to 6 October 2021
Submission deadline: 10 May 2021
Notification: 30 June 2021

The Naval Postgraduate School (NPS) is accepting applications for the position of Assistant or Associate Professor (tenure-track) in the Department of Computer Science. We encourage all qualified candidates to apply and are especially interested in candidates with a background in artificial intelligence, data science, distributed systems, machine learning, or security. We seek to fill the position by June 2021 and will consider applications beginning 30 March 2021. Additional position details can be found at: https://main.hercjobs.org/jobs/14480892

Closing date for applications:

Contact: Geoff Xie, Search Committee Chair

More information: https://main.hercjobs.org/jobs/14480892

Postdoc positions are available in the Cryptology and Data Security research group at the Institute of Computer Science, University of Bern, led by Christian Cachin.

Our research addresses all aspects of security in distributed systems, especially cryptographic protocols, consistency, consensus, and cloud-computing security. We are particularly interested in blockchains, distributed ledger technology, cryptocurrencies, and their security and economics.

Candidates should have a strong background in computer science. They should like conceptual, rigorous thinking for working theoretically, or be interested in building innovative systems for working practically. Demonstrated expertise in cryptography, distributed computing, or blockchain technology is a plus. Applicants should hold a Ph.D., with contributions in the relevant research topics.

Positions are available starting immediately and come with a competitive salary. The selection process runs until suitable candidates have been found. The University of Bern conducts excellent research and lives up its vision that “Knowledge generates value”. The city of Bern lies in the center of Switzerland and offers some of the highest quality of life worldwide.

If you are interested, please apply be sending email with one single PDF file and subject line set to Application for Postdoc addressed directly to Prof. Christian Cachin at crypto (at) inf.unibe.ch.

Closing date for applications:

Contact: For more information, please contact Christian Cachin (https://crypto.unibe.ch/cc/).

More information: https://crypto.unibe.ch/jobs/

The Cybersecurity - Identity Management group at the Hasso-Plattner-Institute (HPI), University of Potsdam is looking for a motivated PhD student or Postdoc in the area of cryptography and privacy.

Your future tasks

• Development and analysis of provably secure cryptographic protocols for real-world problems. Topics of interest include (but are not limited to):
  • Privacy-enhancing technologies
  • Password-based cryptography
  • Foundations and solutions for real-world cryptography
• 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
• Profound knowledge in the areas of cryptography and IT security (for postdoctoral candidates proven in the form of publications in these areas)
• Excellent English language skills

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. Please submit your application documents in a single PDF file via email.

Closing date for applications:

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

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

The APSIA group led by Peter Y.A. Ryan is offering a post-doc position in a research project on future-proofing privacy of secure electronic voting led by Johannes Müller. The position is fully funded for 2 years and may be extended up to 5 years.

Your Role

The candidate will shape research directions and produce results in one or more of the following topics:

• Protocol security
• Post-quantum cryptography
• Information-theoretic security
• Implementation of security protocols

Your Profile

• A PhD degree in Computer Science, Applied Mathematics or a related field
• Competitive research record in (applied) cryptography or protocol security
• Experience with secure e-voting or protocol security proofs is a plus
• Experience with post-quantum cryptography or information-theoretic security is a plus
• Experience with implementation of security protocols is a plus

Please apply online formally through the HR system (see link). Applications by email will not be considered.

Closing date for applications:

Contact: Johannes Müller

More information: https://recruitment.uni.lu/en/details.html?id=QMUFK026203F3VBQB7V7VV4S8&nPostingID=57676&nPostingTargetID=80219&mask=karriereseiten&lg=UK

We are looking for an assistant/associate professor to extend and complement the cryptology research and teaching of the Cyber Security Section at DTU Compute. The position is available from August 1 2021 or according to mutual agreement.

Closing date for applications:

Contact: Professor Lars Ramkilde Knudsen, lrkn@dtu.dk. Please use the above link when applying for the position. Applications sent by email will not be considered.

More information: https://www.dtu.dk/english/about/job-and-career/vacant-positions/job?id=fa3c2175-2322-42c9-b822-167147cf4e70

We introduce the first construction for secure two-party computation of Poisson regression, which enables two parties who hold shares of the input samples to learn only the resulting Poisson model while protecting the privacy of the inputs.

Our construction relies on new protocols for secure fixed-point exponentiation and correlated matrix multiplications. Our secure exponentiation construction avoids expensive bit decomposition and achieves orders of magnitude improvement in both online and offline costs over state of the art works. As a result, the dominant cost for our secure Poisson regression are matrix multiplications with one fixed matrix. We introduce a new technique, called correlated Beaver triples, which enables many such multiplications at the cost of roughly one matrix multiplication. This further brings down the cost of secure Poisson regression.

We implement our constructions and show their extreme efficiency. Our secure exponentiation for 20-bit fractional precision takes less than 0.07ms. One iteration of Poisson regression on a dataset with 10,000 samples with 1000 binary features, requires 16.47s offline time, 23.73s online computation and 7.279MB communication. For several real datasets this translates into training that takes seconds and only a couple of MB communication.

Iterative methods are a standard technique in many areas of scientific computing. The key idea is that a function is applied repeatedly until the resulting sequence converges to the correct answer. When applying such methods in a secure computation methodology (for example using MPC, FHE, or SGX) one either needs to perform enough steps to ensure convergence irrespective of the input data, or one needs to perform a convergence test within the algorithm, and this itself leads to a leakage of data. Using the Banach Fixed Point theorem, and its extensions, we show that this data-leakage can be quantified. We then apply this to a secure (via MPC) implementation of the PageRank methodology. For PageRank we show that allowing this small amount of data-leakage produces a much more efficient secure implementation, and that for many underlying graphs this `leakage' is already known to any attacker.

Bitcoin transfers value on a public ledger of transactions anyone can verify. Coin ownership is defined in terms of public keys. Despite potential use for private transfers, research has shown that users’ activity can often be traced in practice. Businesses have been built on dragnet surveillance of Bitcoin users because of this lack of strong privacy, which harms its fungibility, a basic property of functional money. Although the public nature of this design lacks strong guarantees for privacy, it does not rule it out. A number of methods have been proposed to strengthen privacy. Among these is CoinJoin, an approach based on multiparty transactions that can introduce ambiguity and break common assumptions that underlie heuristics used for deanonymization. Existing implementations of CoinJoin have several limitations which may partly explain the lack of their widespread adoption. This work introduces WabiSabi, a new protocol for centrally coordinated CoinJoin implementations utilizing keyed verification anonymous credentials and homomorphic value commitments. This improves earlier approaches which utilize blind signatures in both privacy and flexibility, enabling novel use cases and reduced overhead.