In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is a branching program where each node is allowed to make 𝔽₂-linear queries, and is read-once in the sense that the queries on each path is linearly independent. As their main result, they constructed an explicit function with average-case complexity 2^{n/3-o(n)} against a slightly restricted model, which they call strongly read-once linear branching programs. The main tool in their lower bound result is a new type of extractor, called directional affine extractors, that they introduced. Our main result is an explicit function with 2^{n-o(n)} average-case complexity against the strongly read-once linear branching program model, which is almost optimal. This result is based on a new connection from this problem to sumset extractors, which is a randomness extractor model introduced by Chattopadhyay and Li (STOC '16) as a generalization of many other well-studied models including two-source extractors, affine extractors and small-space extractors. With this new connection, our lower bound naturally follows from a recent construction of sumset extractors by Chattopadhyay and Liao (STOC '22). In addition, we show that directional affine extractors imply sumset extractors in a restricted setting. We observe that such restricted sumset sources are enough to derive lower bounds, and obtain an arguably more modular proof of the lower bound by Gryaznov, Pudlák and Talebanfard. We also initiate a study of pseudorandomness against linear branching programs. Our main result here is a hitting set generator construction against regular linear branching programs with constant width. We derive this result based on a connection to Kakeya sets over finite fields.

We consider the problem of extracting randomness from sumset sources, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An (n,k,C)-sumset source X is a distribution on {0,1}n of the form X1 + X2 + … + XC, where Xi’s are independent sources on n bits with min-entropy at least k. Prior extractors either required the number of sources C to be a large constant or the min-entropy k to be at least 0.51 n.

We give an explicit construction of an affine extractor (over$\mathbb{F}_{2}$) that works for affine sources on$n$bits with min-entropy$k\geq\log n\cdot(\log\log n)^{1+o(1)}$. This improves prior work of Li (FOCS'16) that requires min-entropy at least$\text{poly} (\log n)$. Our construction is based on the framework of using correlation breakers and resilient functions, a paradigm that was also used by Li. On a high level, the key sources of our improvement are based on the following new ingredients: (i) A new construction of an affine somewhere random extractor, that we use in a crucial step instead of a linear seeded extractor (for which optimal constructions are not known) that was used by Li. (ii) A near optimal construction of a correlation breaker for linearly correlated sources. The construction of our correlation breaker takes inspiration from an exciting line of recent work that constructs two-source extractors for near logarithmic min-entropy.

More and more customers are purchasing digital content through the Internet because it is both popular and convenient. However, there are lots of pirated editions of digital products and they have become more available and easier to obtain. Hence, proving who the legal owner of digital content has become an important issue. In this study, the authors want to preserve customer ownership; they propose an intact arbitration mechanism to solve the fairness transaction between the customer and the shop. The arbiter can make correct judgements without the customer's and the shop's private keys in the arbitration phase. In order to achieve the above objectives, the security of this protocol is based on three cryptographic techniques: the subliminal channel, one-way hash function and RSA cryptosystem. Our scheme not only protects a customer's legal ownership of digital content, but also achieves fair transaction, customer anonymity, owner tracing of E-cash and payment security.