I/O-Efficient algorithms for topological sort and related problems
Jeremy T. Fineman,
This paper presents I/O-efficient algorithms for topologically sorting a directed acyclic graph and for the more general problem identifying and topologically sorting the strongly connected components of a directed graph G = (V, E). Both algorithms are randomized and have I/O-costs O(sort(E) · poly(log V )), with high probability, where sort(E) = O(E/B logM/B(E/B)) is the I/O cost of sorting an |E|-element array on a machine with sizeB blocks and size-M cache/internal memory. These are the first algorithms for these problems that do not incur at least one I/O per vertex, and as such these are the first I/O-efficient algorithms for sparse graphs. By applying the technique of time-forward processing, these algorithms also imply I/O-efficient algorithms for most problems on directed acyclic graphs, such as shortest paths, as well as the single-source reachability problem on arbitrary directed graphs.
Toward RSA-OAEP without Random Oracles.
Nairen Cao, Adam O'Neill and Mohammad Zaheri
We show new partial and full instantiation results under chosen-ciphertext security for the widely implemented and standardized RSA-OAEP encryption scheme of Bellare and Rogaway (EUROCRYPT 1994) and two variants. Prior work on such instantiations either showed negative results or settled for “passive” security
notions like IND-CPA. More precisely, recall that RSA-OAEP adds redundancy and randomness to a message before composing two rounds of an underlying Feistel transform, whose round functions are modeled as random oracles (ROs), with RSA. Our main results are:
• Either of the two oracles (while still modeling the other as a RO) can be instantiated in RSA-OAEP under IND-CCA2 using mild standard-model assumptions on the round functions and generalizations of algebraic properties of RSA shown by Barthe, Pointcheval, and B´aguelin (CCS 2012). The algebraic properties are only shown to hold at practical parameters for small encryption exponent (e = 3), but we argue they have value for larger e as well.
• Both oracles can be instantiated simultaneously for two variants of RSA-OAEP, called “t-clear” and “sclear” RSA-OAEP. For this we use extractability-style assumptions in the sense of Canetti and Dakdouk(TCC 2010) on the round functions, as well as novel yet plausible “XOR-type” assumptions on RSA. While admittedly strong, such assumptions may nevertheless be necessary at this point to make positive progress.
In particular, our full instantiations evade impossibility results of Shoup (J. Cryptology 2002), Kiltz and Pietrzak (EUROCRYPT 2009), and Bitansky et al. (STOC 2014). Moreover, our results for s-clear RSAOAEP yield the most efficient RSA-based encryption scheme proven IND-CCA2 in the standard model (using bold assumptions on cryptographic hashing) to date.
LRCRYPT: Leakage-Resilient Cryptographic System (Design and Implementation).
Xiaoqi Yu, Nairen Cao, Jun Zhang,
Due to the advancement of side-channel attacks, leakage-resilient cryptography has attracted a lot of attention in recent years. Many fruitful results have been proposed by researchers. Most, if not all, of these results are theoretical in nature. Not much has been done to realize these schemes for practical use. In this work, we design and provide a leakage-resilient cryptographic system LRCRYPT with programming interfaces for users to build leakage-resilient cryptographic applications. LRCRYPT consists of a few fundamental building blocks that perform leakage-resilient public-key encryption, leakage-resilient signature, and leakage-resilient secret-key encryption, which can also be extended to many existing leakage resilience cryptographic primitives. We have conducted both a security analysis and a performance evaluation on LRCRYPT. To our knowledge, LRCRYPT is the first to work in this domain.
Dynamic Proofs of Retrievability with improved worst case overhead.
Xiaoqi Yu, Nairen Cao, Jun Zhang,
Proofs of Retrievability (POR) is a scheme to build a verifiable storage on a remote server that a client can access the data randomly, and periodically execute an efficient Audit protocol to ensure that the data is intact. In dynamic POR, the difficulties are to maintain the latest version of the data while achieving efficient Update and Audit. In this paper, we propose PDPOR that achieves the best worse-case overhead O(logN) for both Write and Audit protocols together with the best worse-case bandwidth. We also prove the security of DPOR using simpler techniques.