Last Week's ePrint Updates
Distributed Shuffling in Adversarial Environments
Kasper Green Larsen, Maciej Obremski, Mark Simkin
We formalize and study the problem of distributed shuffling in adversarial environments. In this setting, there are $m$ shufflers that have access to a public bulletin board that stores a vector $(c_1, \dots, c_n)$ of rerandomizable commitments. The shufflers repeatedly read $k$ of the $n$ commitments, with $k$ potentially much smaller than $n$, and shuffle them. An adversary has the ability to initially corrupt and then track some of the commitments throughout the shuffles and can adaptively corrupt a bounded number of shufflers in every single round. The goal of the distributed shuffling protocol is to hide the output locations of commitments that are not corrupted by the adversary. We present and analyze a protocol that solves this problem with essentially optimal shuffling complexity. As an exemplary data point, our protocol can shuffle a list of length $n$ with shuffles of size $k$, where $k \in \Omega(\lg^2 n)$, in the presence of an adversary that can corrupt $4n/5$ many shufflers in each round and can corrupt $4n/5$ commitments in the input vector. Our $m$party shuffling protocol with $m \in \Omega(n/k)$ terminates in $\mathcal{O}(\lg n)$ rounds. We provide numerical benchmarks that validate our theoretically proven guarantees and in fact show that the number of rounds is not just theoretically, but also concretely small. Our shuffling protocol can either improve efficiency or lead to more secure solutions in multiple research domains, such as the design of mixnets, single secret leader election protocols, and electronic voting.
2022/560Survey on the Effectiveness of DAPARelated Attacks against Shift Register Based AEAD Schemes
Shivam Bhasin, Dirmanto Jap, Wei Cheng Ng, Siang Meng Sim

2022/561Orientations and cycles in supersingular isogeny graphs
Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, Katherine E. Stange, Ha T. N. Tran
The paper concerns several theoretical aspects of oriented supersingular lisogeny volcanoes and their relationship to closed walks in the supersingular lisogeny graph. Our main result is a bijection between the rims of the union of all oriented supersingular lisogeny volcanoes over $\overline{\mathbb{F}}_p$ (up to conjugation of the orientations), and isogeny cycles (nonbacktracking closed walks which are not powers of smaller walks) of the supersingular lisogeny graph modulo p. The exact proof and statement of this bijection are made more intricate by special behaviours arising from extra automorphisms and the ramification of p in certain quadratic orders. We use the bijection to count isogeny cycles of given length in the supersingular lisogeny graph exactly as a sum of class numbers, and also give an explicit upper bound by estimating the class numbers.
2022/562Find the Bad Apples: An efficient method for perfect key recovery under imperfect SCA oracles – A case study of Kyber
Muyan Shen, Chi Cheng, Xiaohan Zhang, Qian Guo, Tao Jiang
Sidechannel resilience is a crucial feature when assessing whether a postquantum cryptographic proposal is sufficiently mature to be deployed. In this paper, we propose a generic and efficient adaptive approach to improve the sample complexity (i.e., the required number of traces) of plaintextchecking (PC) oraclebased sidechannel attacks (SCAs), a major class of key recovery chosenciphertext SCAs on latticebased key encapsulation mechanisms. This new approach is preferable when the constructed PC oracle is imperfect, which is common in practice, and its basic idea is to design new detection codes that can determine erroneous positions in the initially recovered secret key. These secret entries are further corrected with a small number of additional traces. This work benefits from the generality of PC oracle and thus is applicable to various schemes and implementations. We instantiated the proposed generic attack framework on Kyber512 and fully implemented this attack instance. Through extensive computer simulations and also a realworld experiment with electromagnetic (EM) leakages from an ARMCortextM4 platform, we demonstrated that the newly proposed attack could greatly improve the stateoftheart in terms of the required number of traces. For instance, the new attack requires only 41% of the EM traces needed in a majorityvoting attack in our experiments, where the raw oracle accuracy is fixed.
2022/563FAPRIL: Towards Faster PrivacyPreserving FingerprintBased Localization
Christopher van der Beets, Raine Nieminen, Thomas Schneider
Fingerprinting is a commonly used technique to provide accurate localization for indoor areas, where global navigation satellite systems, such as GPS and Galileo, cannot function or are not precise enough. Although fingerprintbased indoor localization has gained wide popularity, existing solutions that preserve privacy either rely on noncolluding servers or have high communication which hinder deployment. In this work we present FAPRIL, a privacypreserving indoor localization scheme, which takes advantage of the latest secure twoparty computation protocol improvements. We can split our scheme into two parts: an input independent setup phase and an online phase. We concentrate on optimizing the online phase for mobile clients who run on a mobile data plan and observe that recurring operands allow to optimize the total communication overhead even further. Our observation can be generalized, e.g., to improve multiplication of Arithmetic secret shared matrices. We implement FAPRIL on mobile devices and our benchmarks over a simulated LTE network show that the online phase of a private localization takes under 0.15 seconds with less than 0.20 megabytes of communication even for large buildings. The setup phase, which can be precomputed, depends heavily on the setting but stays in the range 0.28  4.14 seconds and 0.69  16.00 megabytes per localization query. The round complexity of FAPRIL is constant for both phases.
2022/564Power Contracts: Provably Complete Power Leakage Models for Processors
Roderick Bloem, Barbara Gigerl, Marc Gourjon, Vedad Hadžić, Stefan Mangard, Robert Primas
The protection of cryptographic software implementations against poweranalysis attacks is critical for applications in embedded systems. A commonly used algorithmic countermeasure against these attacks is masking, a secretsharing scheme that splits a sensitive computation into computation on multiple random shares. In practice, the security of masking schemes relies on several assumptions that are often violated by microarchitectural sideeffects of CPUs. Many past works address this problem by studying these leakage effects and building corresponding leakage models that can then be integrated into a software verification workflow. However, these models have only been derived empirically, putting the otherwise rigorous security statements made with verification in question. We solve this problem in two steps. First, we introduce a contract layer between the (CPU) hardware and the software that allows the specification of microarchitectural sideeffects on masked software in an intuitive language. Second, we present a method for proving the correspondence between contracts and CPU netlists to ensure the completeness of the specified leakage models. Then, any further security proofs only need to happen between software and contract, which brings benefits such as reduced verification runtime, improved user experience, and the possibility of working with vendorsupplied contracts of CPUs whose design is not available on netlistlevel due to IP restrictions. We apply our approach to the popular RISCV IBEX core, provide a corresponding formally verified contract, and describe how this contract could be used to verify masked software implementations.
2022/565AntMan: Interactive ZeroKnowledge Proofs with Sublinear Communication
Chenkai Weng, Kang Yang, Zhaomin Yang, Xiang Xie, Xiao Wang
Recent works on interactive zeroknowledge (ZK) protocols provide a new paradigm with high efficiency and scalability. However, these protocols suffer from high communication overhead, often linear to the circuit size. In this paper, we proposed two new ZK protocols with communication sublinear to the circuit size, while maintaining a similar level of computational efficiency.  We designed a ZK protocol that can prove $B$ executions of any circuit $C$ in communication $O(B + C)$ field elements (with free addition gates), while the best prior work requires a communication of $O(BC)$ field elements. Our protocol is enabled by a new tool called as informationtheoretic polynomial authentication code, which may be of independent interest.  We developed an optimized implementation of this protocol which shows high practicality. For example, with $B=2048$, $C=2^{20}$, and under 50 Mbps bandwidth and 16 threads, QuickSilver, a stateoftheart ZK protocol based on vector oblivious linear evaluation (VOLE), can only prove $0.78$ million MULT gates per second (mgps) and send one field element per gate; our protocol can prove $14$ mgps ($18\times$ improvement) and send $0.0064$ field elements per gate ($156\times$ improvement) under the same hardware configuration.  Extending the above idea, we constructed a ZK protocol that can prove a single execution of any circuit $C$ in communication $O(C^{3/4})$. This is the first ZK protocol with sublinear communication for an arbitrary circuit in the VOLEbased ZK family.
2022/566Improved MITM Cryptanalysis on Streebog
Jialiang Hua, Xiaoyang Dong, Siwei Sun, Zhiyu Zhang, Lei Hu, Xiaoyun Wang
At ASIACRYPT 2012, Sasaki et al. introduced the guessanddetermine approach to extend the meetinthemiddle (MITM) preimage attack. At CRYPTO 2021, Dong et al. proposed a technique to derive the solution spaces of nonlinear constrained neutral words in the MITM preimage attack. In this paper, we try to combine these two techniques to further improve the MITM preimage attacks. Based on the previous MILPbased automatic tools for MITM attacks, we introduce new constraints due to the combination of guessanddetermine and nonlinearly constrained neutral words to build a new automatic model. As a proof of work, we apply it to the Russian national standard hash function Streebog, which is also an ISO standard. We find the first 8.5round preimage attack on Streebog512 compression function and the first 7.5round preimage attack on Streebog256 compression function. In addition, we give the 8.5round preimage attack on Streebog512 hash function. Our attacks extend the best previous attacks by one round. We also improve the time complexity of the 7.5round preimage attack on Streebog512 hash function and 6.5round preimage attack on Streebog256 hash function.
2022/568On Seedless PRNGs and Premature Next
Sandro Coretti, Yevgeniy Dodis, Harish Karthikeyan, Noah StephensDavidowitz, Stefano Tessaro
Pseudorandom number generators with input (PRNGs) are cryptographic algorithms that generate pseudorandom bits from accumulated entropic inputs (e.g., keystrokes, interrupt timings, etc.). This paper studies in particular PRNGs that are secure against premature next attacks (Kelsey et al., FSE '98), a class of attacks leveraging the fact that a PRNG may produce an output (which could be seen by an adversary!) before enough entropy has been accumulated. Practical designs adopt either unsound entropyestimation methods to prevent such attacks (as in Linux's /dev/random) or sophisticated poolbased approaches as in Yarrow (MacOS/FreeBSD) and Fortuna (Windows). The only prior theoretical study of premature next attacks (Dodis et al., Algorithmica '17) considers either a seeded setting or assumes a constant entropy rate, and thus falls short of providing and validating practical designs. Assuming the availability of random seed is particularly problematic, first because this requires us to somehow generate a random seed without using our PRNG, but also because we must ensure that the entropy inputs to the PRNG remain independent of the seed. Indeed, all practical designs are seedless. However, prior works on seedless PRNGs (Coretti et al., CRYPTO '19; Dodis et al., ITC '21, CRYPTO'21) do not consider premature next attacks. The main goal of this paper is to investigate the feasibility of theoretically sound seedless PRNGs that are secure against premature next attacks. To this end, we make the following contributions:  We prove that it is impossible to achieve seedless PRNGs that are secure against prematurenext attacks, even in a rather weak model. Namely, the impossibility holds even when the entropic inputs to the PRNG are independent. In particular, our impossibility result holds in settings where seedless PRNGs are otherwise possible.  Given the above impossibility result, we investigate whether existing seedless poolbased approaches meant to overcome premature next attacks in practical designs provide meaningful guarantees in certain settings. Specifically, we show the following. * We introduce a natural condition on the entropic input and prove that it implies security of the roundrobin entropy accumulation PRNG used by Windows 10, called Fortuna. Intuitively, our condition requires the input entropy ``not to vary too wildly'' within a given roundrobin round. * We prove that the ``root pool'' approach (also used in Windows 10) is secure for general entropy inputs, provided that the system's state is not compromised after system startup.
2022/558FC1: A Powerful, NonDeterministic, Symmetric Key Cipher
Michele Fabbrini
In this paper we describe a symmetric key algorithm that offers an unprecedented grade of confidentiality. Based on the uniqueness of the modular multiplicative inverse of a positive integer a modulo n and on its computability in a polynomial time, this nondeterministic cipher can easily and quickly handle keys of millions or billions of bits that an attacker does not even know the length of. The algorithm’s primary key is the modulo, while the ciphertext is given by the concatenation of the modular inverse of blocks of plaintext whose length is randomly chosen within a predetermined range. In addition to the full specification, we present a working implementation of it in Julia Programming Language, accompanied by real examples of encryption and decryption.
2022/567DeCAF: Decentralizable Continuous Group Key Agreement with Fast Healing
Joël Alwen, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo PascualPerez, Krzysztof Pietrzak
Continuous group key agreement (CGKA) allows a group of users to maintain a continuously updated shared key in an asynchronous setting where parties only come online sporadically and their messages are relayed by an untrusted server. CGKA captures the basic primitive underlying group messaging schemes. Current solutions including TreeKEM (``Message Layer Security'' (MLS) IETF draft) cannot handle concurrent requests while retaining low communication complexity. The exception being CoCoA, which is concurrent while having extremely low communication complexity (in groups of size $n$ and for $m$ concurrent updates the communication per user is $\log(n)$, i.e., independent of $m$). The main downside of CoCoA is that in groups of size $n$, users might have to do up to $\log(n)$ update requests to the server to ensure their (potentially corrupted) key material has been refreshed. We present a new ``fast healing'' concurrent CGKA protocol, named DeCAF, where users will heal after at most $\log(t)$ requests, with $t$ being the number of corrupted users. Our new protocol is particularly interesting to realize decentralized group messaging, where protocol messages (add/remove/update) are being posted on a blockchain rather than sent to a server. In this setting, concurrency is crucial once requests are more frequent than blocks. Our new protocol significantly outperforms (the only alternative with sublinear communication and PCS) CoCoA in this setting: it heals much faster ($\log(t)$ vs. $\log(n)$ rounds). The communication per round and user is $m\cdot\log(n)$, but in this setting  where there is no server who can craft specific messages to users depending on their position in the tree  CoCoA requires the same communication.
2022/559