One Way Function

The one-way function is one of the most fundamental concept in cryptography. It is the basis of the construction of other crypographic algorithms.

Informally, if $f$ is a one-way function, then it’s easy to compute $f(x)$ from $x$, but it’s hard to guess $x$ from $f(x)$.

Formal Definition

The formal definition is that:

\(f:D\to R\) is a one-way function (OWF) if, for any probabilistic polynomial time (PPT) adversary \(A\), and for any \(x\) uniformly randomly sampled from \(D\), the probability that \(f(A(y))=y\) is negligible, where \(y=f(x)\).

The definition can be written in the math language as: For all PPT \(A\), \[Pr[x\xleftarrow{$}D, y=f(x), x’=A(y): f(x’)=f(x)] \le negl(n)\]

The adversary is an algorithm that aims at inverting the one-way function. It can be probabilistic (i.e. not deterministic). But the running time must be bound to polynomial time. We demand the one-way function not to be secure against some adversaries, but all adversaries.

read more

Why Ctrl-1 is Not Working in Terminal

When I configured my Emacs, I found it pretty annoying that many keybindings working in GUI didn’t work in the terminal.

After some googling, I learned that it was caused by how terminals send keys.

Briefly, the terminal treats the following keys as the same (meaning it can’t distinguish which one you actually pressed):

  • <Ctrl-I> is the same as <Tab>;
  • <Ctrl-J> is the same as <Enter>;
  • <Ctrl-M> is also the same as <Enter>;
  • <Ctrl-]> is the same as <Esc> (that’s why <Ctrl-]> also allows you to return to Normal mode in Vim);
  • <Ctrl-?> (aka <Ctrl-Shift-/>) is the same as <Delete>;
  • <Esc> B is the same as <Alt-B> (try it in the shell, they all move the cursor backwards by word).

read more

Understanding JavaScript Promise

We know that in JavaScript we have three ways to write asynchronous programs: the callback style, using promises and async/await.

It takes me a long time to figure out what’s the relationship between them. The truth is kind of surprising: they are much more similar than they look like. I would like to show you how they are related in this post.

Let’s start from the traditional callback style.

In the callback style, an asynchronous function takes an additional argument – the callback. The callback is not invoked until the operation is complete.

The callback is a function, but it’s slightly different from how we normally use functions.

When we call a normal function, we care about what it returns, since we’re going to use that value in the rest of the program.

But as for the callbacks, we never care about their return values. And most of the time we just return immediately after the asynchronous function returns. Here the callback itself represents the rest of the program.

read more

Bash Programming Tutorial

Bash Programming Tutorial

Variables

Define variables

Variables in Bash are defined with a equal sign:

var='the value'

There is no space before and after the equal sign. The reason is simple – Bash cannot distinguish a variable assignment from a program with arguments if there are spaces around the equal sign:

# Does it mean assigning 'nick' to a variable named cat, or
# executing the program /bin/cat with two arguments, namely,
# '=' and 'nick'?
cat = 'nick'

Use a variable

To use a variable, we need to put a dollar sign before the variable:

name=John
echo "Hello, $name"

We can also use braces to surround the variable. It’s equivalent to the form without braces with an exception:

echo "Hello, ${name}"

# Without braces, the variable becomes $namefoo
echo "Hello, ${name}foo"

read more

Multi-file Search and Replace in Vim

Multi-file Search and Replace in Vim

Ferret is a Vim multi-file search plugin. Compared to ack.vim, ferret asynchronously does the search job. It also has several improvements in integrating with quickfix windows, allowing for easier multi-file substitutions.

Installing ferret is easy. In vim-plugged, put the following line in the vimrc file to install it:

Plug 'wincent/ferret'

Ferret uses ripgrep, ag or ack in the background. Make sure you have any of them installed in your system.

Settings

Default ferret mappings are not very easy to remember. Instead, I setup my own key mappings in vimrc, resembling Vim’s own searching commands like * and /:

read more

Don't Overuse hjkl in Vim

Don't Overuse hjkl in Vim

hjkl is a remarkable improvement over arrow keys, since they keep your fingers in the home row. However, overusing them could be another hindrance to an efficient use of Vim, for they only move by a character at a time, whereas Vim provides many efficient motions that allows you to move faster.

Go to a line

If you find yourself pressing jjjj or kkkk all the time, then you probably should check out <line>gg (e.g. go to the 12nd line with 12gg).

<line>G is equivalent to <line>gg, but I find it much easier to press g twice than holding the shift key.

Word-based motions

Instead of holding h or l, you can use w and b; w moves forward to the start of next word, and b moves backward. There is another similar command e that moves forward to end of next word.

If there are too many punctuations in the line under cursor, then you might find w and b a little annoying, since each punctuation is regarded as an individual word (due to the definition that a word is a sequence of alphabetic and digital characters, check out :h iskeyword).

read more

Redux or not: Managing States in Vanilla React

Redux or not: Managing States in Vanilla React

Since the first day we learned React, we have been told not to overuse states in React. We are also encouraged to use stateless functional components over stateful class components.

These suggestions easily lead to an apparent conclusion for beginners that we shouldn’t use states at all, but rather, when we do need them, seek for some independent state management libraries like Redux.

There were several reasons why we hated vanilla states so much:

  1. When the project gets larger, it soon becomes untrackable for the local states scattering in various different components.
  2. State sharing between components can be painful.
  3. Passing a prop from an outer component to a deeply nested component where the prop is used can also be painful; it’s called prop drilling.
  4. The stateful logic is usually mixed together with the UI renderer, making itself hard to test or reuse.
  5. Class components are harder to be optimized than functional components during compilation.

read more

Setup React + MobX + TypeScript

Setup React + MobX + TypeScript

Create a React project

npx create-react-app my-react-mobx-app --use-npm --typescript

It creates a directory named my-react-mobx-app under the current directory, which has the following features pre-configured out of box:

  • Webpack: supports ES6/ES.Next features, CSS/image loaders
  • React: in TypeScript
  • Jest: a unit test framework
  • Eslint: checks bad programmatic habits, but doesn’t enforce any coding style

read more

Querying By Boolean Values in DynamoDB with GSI

Querying By Boolean Values in DynamoDB with GSI

It is a common scenario in DynamoDB that you want to query all the items by a boolean value. e.g. you have a table that stores all the tasks, some running and some completed. And you want to periodically fetch out all the running tasks without scanning the whole table or separating them into two tables.

One way to do it is to use global secondary index. However, indexing in DynamoDB is different from that in a relational database. Just migrating the knowledge of MySQL indexing to DynamoDB might cause some confusions.

read more