oh-my-zsh[1] does that for me. It's a pretty great function.
To use it, I use:
bindkey "^[[A" history-beginning-search-backwardEdit: Seems ctrl-up and ctrl-down does the trick.
It emulates the Fish behavior (which is just awesome). I'm not sure if it requires oh-my-zsh, but I think it doesn't.