Jarek Duda

Jarek Duda

Auto-generated profile, based on publicly available information

Jarek Duda

Jagiellonian University Krakow Poland

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
9 July 2021 in IEEE Transactions on Information Forensics and Security
Verified
Journal Article
Open access
Seyit A. CamtepeSeyit A. Camtepe
Seyit A. Camtepe
JDJarek Duda
Jarek Duda
AMArash Mahboubi
Arash Mahboubi
PMPawel Morawiecki
Pawel Morawiecki
SNSurya Nepal
Surya Nepal
Josef PieprzykJosef Pieprzyk
Josef Pieprzyk
Compression is widely used in Internet applications to save communication time, bandwidth and storage. Recently invented by Jarek Duda asymmetric numeral system (ANS) offers an improved efficiency and a close to optimal compression. The ANS algorithm has been deployed by major IT companies such as Facebook, Google and Apple. Compression by itself does not provide any security (such as confidentiality or authentication of transmitted data). An obvious solution to this problem is an encryption of compressed bitstream. However, it requires two algorithms: one for compression and the other for encryption. In this work, we investigate natural properties of ANS that allow to incorporate authenticated encryption using as little cryptography as possible. We target low-level security communication and storage such as transmission of data from IoT devices/sensors. In particular, we propose three solutions for joint compression and encryption (compcrypt). The solutions offer different tradeoffs between security and efficiency assuming a slight compression deterioration. All of them use a pseudorandom bit generator (PRBG) based on lightweight stream ciphers. The first solution is close to original ANS and applies state jumps controlled by PRBG. The second one employs two copies of ANS, where compression is switched between the copies. The switch is controlled by a PRBG bit. The third compcrypt modifies the encoding function of ANS depending on PRBG bits. Security and efficiency of the proposed compcrypt algorithms are evaluated. The first compcrypt is the most efficient with a slight loss of compression quality. The second one consumes more storage but the loss of compression quality is negligible. The last compcrypt offers the best security but is the least efficient.

17 April 2023 in Entropy
Verified
Journal Article
Open access
PDF file
Josef PieprzykJosef Pieprzyk
Josef Pieprzyk
JDJarek Duda
Jarek Duda
MPMarcin Piotr Pawlowski
Marcin Piotr Pawlowski
Seyit A. CamtepeSeyit A. Camtepe
Seyit A. Camtepe
AMArash Mahboubi
Arash Mahboubi
PMPaweł Morawiecki
Paweł Morawiecki
Source coding has a rich and long history. However, a recent explosion of multimedia Internet applications (such as teleconferencing and video streaming, for instance) renews interest in fast compression that also squeezes out as much redundancy as possible. In 2009 Jarek Duda invented his asymmetric numeral system (ANS). Apart from having a beautiful mathematical structure, it is very efficient and offers compression with a very low coding redundancy. ANS works well for any symbol source statistics, and it has become a preferred compression algorithm in the IT industry. However, designing an ANS instance requires a random selection of its symbol spread function. Consequently, each ANS instance offers compression with a slightly different compression ratio. The paper investigates the compression optimality of ANS. It shows that ANS is optimal for any symbol sources whose probability distribution is described by natural powers of 1/2. We use Markov chains to calculate ANS state probabilities. This allows us to precisely determine the ANS compression rate. We present two algorithms for finding ANS instances with a high compression ratio. The first explores state probability approximations in order to choose ANS instances with better compression ratios. The second algorithm is a probabilistic one. It finds ANS instances whose compression ratios can be made as close to the best ratio as required. This is done at the expense of the number θ of internal random “coin” tosses. The algorithm complexity is O(θL3), where L is the number of ANS states. The complexity can be reduced to O(θLlog2L) if we use a fast matrix inversion. If the algorithm is implemented on a quantum computer, its complexity becomes O(θ(log2L)3).

9 December 2019 in arXiv
Verified
Preprint
Open access
PDF file
JDJarek Duda
Jarek Duda
In stochastic gradient descent, especially for neural network training, there are currently dominating first order methods: not modeling local distance to minimum. This information required for optimal step size is provided by second order methods, however, they have many difficulties, starting with full Hessian having square of dimension number of coefficients. This article proposes a minimal step from successful first order momentum method toward second order: online parabola modelling in just a single direction: normalized $\hat{v}$ from momentum method. It is done by estimating linear trend of gradients $\vec{g}=\nabla F(\vec{\theta})$ in $\hat{v}$ direction: such that $g(\vec{\theta}_\bot+\theta\hat{v})\approx \lambda (\theta -p)$ for $\theta = \vec{\theta}\cdot \hat{v}$, $g= \vec{g}\cdot \hat{v}$, $\vec{\theta}_\bot=\vec{\theta}-\theta\hat{v}$. Using linear regression, $\lambda$, $p$ are MSE estimated by just updating four averages (of $g$, $\theta$, $g\theta$, $\theta^2$) in the considered direction. Exponential moving averages allow here for inexpensive online estimation, weakening contribution of the old gradients. Controlling sign of curvature $\lambda$, we can repel from saddles in contrast to attraction in standard Newton method. In the remaining directions: not considered in second order model, we can simultaneously perform e.g. gradient descent. There is also discussed its learning rate approximation as $\mu=\sigma_\theta / \sigma_g$, allowing e.g. for adaptive SGD - with learning rate separately optimized (2nd order) for each parameter.

21 February 2025 in International Journal of Information Security
Verified
Journal Article
Open access
PDF file
Josef PieprzykJosef Pieprzyk
Josef Pieprzyk
MPMarcin Piotr Pawlowski
Marcin Piotr Pawlowski
PMPaweł Morawiecki
Paweł Morawiecki
AMArash Mahboubi
Arash Mahboubi
JDJarek Duda
Jarek Duda
Seyit A. CamtepeSeyit A. Camtepe
Seyit A. Camtepe
The generation of pseudorandom binary sequences is of great importance in numerous applications, ranging from simulation and gambling to cryptography. Pseudorandom bit generators (PRBGs) can be divided into two categories based on their claimed security. The first category includes PRBGs that are provably secure, such as the Blum–Blum–Shub generator. The security of the second category relies on heuristic arguments. Unfortunately, PRBGs from the first category are inherently inefficient, and some are vulnerable to quantum attacks. In contrast, those in the second category are highly efficient, though their security depends on their resistance to known cryptographic attacks. This work presents a construction of a PRBG based on the asymmetric numeral system (ANS) compression algorithm. We define a family of PRBGs for $$2^R$$ 2 R ANS states and prove that it is indistinguishable from a truly random generator for sufficiently large R. To enhance efficiency, we explore PRBGs with smaller values of $$R = 7, 8, 9$$ R = 7 , 8 , 9 and demonstrate methods for removing local correlations in the output stream. We permute output bits using rotation and Keccak transformations, showing that the permuted bits pass all NIST tests. Our PRBG design is provably secure for large values of R and heuristically secure for smaller values. Additionally, we claim that our PRBG is secure against quantum adversaries.

9 September 2024 in Journal of Information Security and Applications
Verified
Journal Article
Open access
AMArash Mahboubi
Arash Mahboubi
Seyit A. CamtepeSeyit A. Camtepe
Seyit A. Camtepe
KAKeyvan Ansari
Keyvan Ansari
MPMarcin Piotr Pawlowski
Marcin Piotr Pawlowski
PMPaweł Morawiecki
Paweł Morawiecki
JDJarek Duda
Jarek Duda

13 September 2024
Verified
Book Chapter
Closed access
PDF file
AMArash Mahboubi
Arash Mahboubi
Seyit A. CamtepeSeyit A. Camtepe
Seyit A. Camtepe
KAKeyvan Ansari
Keyvan Ansari
MPMarcin Piotr Pawlowski
Marcin Piotr Pawlowski
PMPaweł Morawiecki
Paweł Morawiecki
Josef PieprzykJosef Pieprzyk
Josef Pieprzyk